Mean-Field Sampling for Cooperative Multi-Agent Reinforcement Learning
Authors: Emile Timothy Anand
Ishani Karmarkar
Guannan Qu
Venue: NeurIPS 2025 spotlight ()
Keywords: multi-agent reinforcement learning
mean-field RL
online decision making
sampling theory
large-scale systems
Primary area: theory
TL;DR: We develop and analyze a scalable algorithm for multi-agent RL by sampling from the mean-field distribution of the agents to overcome the curse of dimensionality.

Abstract: Designing efficient algorithms for multi-agent reinforcement learning (MARL) is fundamentally challenging because the size of the joint state and action spaces grows exponentially in the number of agents. These difficulties are exacerbated when balancing sequential global decision-making with local agent interactions. In this work, we propose a new algorithm $\texttt{SUBSAMPLE-MFQ}$ ($\textbf{Subsample}$-$\textbf{M}$ean-$\textbf{F}$ield-$\textbf{Q}$-learning) and a decentralized randomized policy for a system with $n$ agents. For any $k\leq n$, our algorithm learns a policy for the system in time polynomial in $k$. We prove that this learned policy converges to the optimal policy on the order of $\tilde{O}(1/\sqrt{k})$ as the number of subsampled agents $k$ increases. In particular, this bound is independent of the number of agents $n$.

Mean-Field Sampling for Cooperative Multi-Agent Reinforcement Learning
Emile Anand"
Ishani Karmarkar Stanford University Palo Alto, CA, 94305 Schanik@stane edu
Georgia Institute of Technology Atlanta, GA 30308
emile@gatech.ers edu
Guannan Qu
Carnegie Mellon University Pittsburgh, PA 94035 gqu@andrew cmu. cmu.edu
Abstract
Designing efficient algorithms for multi-agent reinforcement learning (MARI.) is fundamentally challenging because the size of the joint state and action spaces grows exponentially in the number of agents. These difficulties are exacerbated when balancing sequential global decision- makinn with local agent interactions. In this work, we propose a new algorithm SUBSAMPLE-ME (Subsample-Menn) Field- Q- D-laariigg) and decentralized randomized policy for system with agents. For any I n, our algorithm learns a policy for the system in time polynomial k. We prove that this learned policy converges the optimal policy the order of Ó /Vk) the number of subsampled agents increases. In particular, this bound is independent of the number of agents n.
Introduction
Reinforcement Learning (RL) has become a popular framework to solve sequential decision making problems in unknown environments and has achieved tremendous success wide array of domains such as playing the game of Go (Silver et al. 2016). robotic control [Kober et al. 2013 and autonomous driving [Kiran et al. 2022 Lin et al. 2023a]. key feature of most real-worn -wolld systems is their uncertain nature, and thus, RL has emerged as powerful tool for learning optimal policies for multi-agent systems to operate unknown environments [Kim and Giannakis 2017 Zhang et al.. 2021 Lin et al. 2024| Anand and Qu 2024]. While early RL works focused on the single-agent setting, multi-agent RL (MARL) has recently achieved impressive success in many applications, such as coordinating robotic swarms [Priiss et al., 2017 DeWeese and Qu 2024). real-time bidding [Jin cct al. 2018), ride-sharing [Li et al. 2019]. and stochastic games [Jin et al. 2020).
Despite growing interest in MARL, extending RL to multi-agent settings poses significant compu- tational challenges due the curse of dimensionality. MARL fundamentally difficult as agents in the real-world not only interact with the environment but also with each other (Shapley) 1953] :
each of the n agents has state space S and action space A, the global state-action space has size (|S||A])" which is exponential in n. Thus, many RL algorithms (such as temporal difference learning and tabular Q-learning) require computing and storing an ||S||| " Q-table [Sutton)
et al. 1999 Bertsekas and Titsikliss, 1996). This scalability issue has been observed in variety of
MARL. settings [Blondel and Tsitsikli 2000) Papadimitriou and Tsitsiklis 1999 Littman 1994].
'Wor partially done while visiting student Camegie Mellon University and intern Cognition AI.
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

An exciting line of work that addresses this intractability is mean-field MARL (aasry and Lions 2007
Yang et al. 2018 Gu et al. 202T 2022 Hu et al. 2023]. The mean-field approach assumes agents are homogeneous in their state-action spaces, enabling their interactions to be approximated by two-agent setting: here, each agent interacts with a representative "mean agent" which evolves as the empirical distribution of states of all other agents. With these assumptions, mean-field MARL learns an optimal policy with sample complexity O(n (S] ||||)|||S|]] [S||A)) which is polynomial in the number of agents. However, if n is large, this remains prohibitive even for moderate values of |S] and |A].
Motivated by this problem, in this paper we study the cooperative setting-where agents work collaboratively to maximize structured global seward-and ask: Can we design scalable MARI, algorithm for learning an approximately optimal policy in a cooperative multi-agent system?
Contributions. We answer this question affirmatively. Our key contributions are outlined below.
Subsampling algorithm. We model the problem as Markov Decision Process (MDP) with a global agent and n local agents. We propose SUBSAMPLE- MFQ to address the challenge of MARL with large number of local agents. SUBSAMPLE-MFQ selects S n local agents to learn a deterministic policy # by applying mean-field value iteration on the k-local-agent subsystem to learn Que which can be viewed as a smaller Q function. SUBSAMPLE-M, then deploys stochastic policy T where the global agent samples i local agents uniformly at each step and uses # to determine its action, while each local agent samples k- 1 other local agents and uses aeet to determine its action.
Sample complexity and theoretical guarantee. As the number of local agents increases, the size of QK scales polynomially with k, rather than polynomially with as in mean-field MARL. Analogously, when the size of the local agent's state space grows, the size of Q₁ scales exponentially with k, rather than exponentially with as in traditional Q-learning. The key analytic technique underlying our results is novel MDP sampling result. This result shows that the performance gap between =h= and the optimal policy x" is at most D(1/VR) with high probability. The choice of k reveals a fundamental trade-off' between the size of the Q-table and the optimality of mTg For example, if k is set to (logn), SUBSAMPLE- MFQ is the first centralized MARL algorithm to achieve polylogarithmic run-time in n, representing an exponential speedup over the previously best-known polytime mean-field MARL methods, while maintaining a decaying optimality gap as n gets large,
While our results are theoretical in nature, we hope SUBSAMPLE-WE will further exploration of sampling in Markov games, and potentially inspire new practical multi agett- algorithms.
Related work. MARL has a rich history, starting with early works on Markov games [Littman 1994 Sutton et al. 1999]. which are multi-agent extension of MDPs. MARL has since been actively studied /hhan et al. 202T] in a broad range of settings. MARL is most similar to the category of "succinetly described" MDPs [Blondel and Tsitsiklis 2000), where the state/action space is a product space formed by the individual state/action spaces of multiple agents, and where the agents interact to maximize an objective. A recent line of research constrains the problem to sparse networked instances to enforce local interactions between agents [Qu et al. 2020a Lin et al., 2020, Mondal al. 2022]. In this formulation, the agents correspond to vertices on a graph who only interact with nearby agents. By exploiting Gamarnik's 's correlation decay property from combinatorial optimization [Gamarnik et al., 2009), they overcome the curse of dimensionality by simplifying the problem to only search over the policy space derived from the truncated graph to learn approximately optimal solutions. However, as the underlying network structure becomes dense with many local interactions, the neighborhood of each agent gets large, and these algorithms become intractable.
Mean-Field RL. Under assumptions of homogeneity in the state/action spaces of the agents, the problem of densely networked multi-agent RL was studied by Yang et al. (2018), 8), Gu et al. [202T), who approximated the solution in polynomial time with mean-field approach where the approximation error scales in ((1/vn)) In contrast, our work achieves subpolynomial runtimes by directly sampling from this meen-field distribution. Cui and Koeppl [2022] introduce heterogeneity to mean-field MARL by modeling non-uniform interactions through graphons; however, these methods crucially assume the existence of graphon sequences that converge in cut-norm to the finite graph. In the cooperative setting, [Subramanian et al. (2022). Cui et al. 2023) studies a meen-field setting with g types of homogeneous agents; however, their learned policy does not provably converge to the optimum.
Other related works. Our work is related to factored MDPs, where there is a global action affecting
every agent; however, in our case, each agent has its own action [Min et al. 2023 Lauer and

---

Riedmiller 2000 Jin et al. [2020) reduces the dependence of the product action space to an additive dependence with V-learning. Our work further reduces the complexity of the joint state space. which has not been previously accomplished. We add to the growing literature on the Centralized Training with Decentralized Execution regime [Zhou et al. [023], as our algorithm learns a provably approximately optimal policy using centralized information, but makes decisions using only local information during execution. Finally, one can efficiently approximate the Q-table through function approximation (Jin al. 2021]. However, achieving theoretical bounds on the performance loss due to function approximation is intractable without strong assumptions such as linear Bellman completeness low Bellman- -luderr dimension [Golowich and Moitra 2024 While work primarily studies the finite tabular setting, we extend it to non-tabular linear MDPs in Appendix
Preliminaries
Notation. For k, IN where & S n, let (()) denote the set of k-sized subsets of [n] fl....................... n). For any vector E Rd, let ||æ||2 and ||=||oo denote the standard & and foo norms of = respectively, Let || denote the matrix 4--ormm of A E R=xm. Given variables $1,.... 8n. S2 == (s: : A for A C [n]. We use (-) to suppress polylogarithmic factors in all problem parameters except n. For a discrete measurable space F), the total variation distance between probability measures pl: P2 nex Ip1 (z)) p2(x)), Next,
D(-) denotes that æ is random element sampled from a distribution D, and we denote that is a random sample from the uniform distribution over finite set Ω by (S2). We include detailed notation table in Table !
is given by TV(p1: P2) 2 Enex
2.1 Problem formulation
We consider a system of n + agents, where agent 9 is a "global decision making agent" and the remaining n agents, denoted by [n]. are "local agents." At time t, the agents are in state s(t) = (sg (4), 81 (t), (()) E S == Sy x S where (t) E Sg denotes the global agent's state, and for each i E [m]. (t) E Sy denotes the state of the i'th local agent. The agents cooperatively select actions (t) (t)
ag (t)) E == A,xA", where ag E Ag denotes the global agent's 's action and (t) At denotes the i'th local agent's ' action. At time t + 1, the next state for all the agents is independently generated by stochastic transition kernels Pa S x Sg x An + (S,))
and P1 S S S x A + (Si)) as follows:
(1) The system then collects structured stage reward a(s()),a(t)) where the reward S A TR. depends on st)) and a(t) through Equation ( and where ry and r is typically application specific.
(t+ ~ (t)) at()), s,(t 1) ~ s (t)), Vi Vi E [n].
r(s,a) a)
(g(5g:0g) (gg)
Σ (E(M)
(r( Sg: az)
7
global component
local component
A policy т : S + P(A) maps from states to distributions of actions such that a T(-ss). Given 7 E (0, 1), we seek to learn policy ı that maximizes the (r-diicountedd) value for each 8 E S:
va (*)(s) = (s)==Bco)stt Ea(o~=(1e) r'r(s(t), = =8]
The cardinality of the search space simplex for the optimal policy is ||,","""" which exponential in the number of agents, underscoring the need for efficient approximation algorithms.
To efficiently learn policies that maximize the objective, we make the following standard assumptions:
Assumption 2.1 (Finite state/action spaces). We assume that the state and action spaces of all the agents in the MARL game are finite: |S]] [S, [Agl. |A| < co. Appendix of the supplementary material relaxes this assumption to the ton-tabular setting with infinite continuous sets.
Assumption 2.2 (Bounded rewards). The components of the reward function are bounded. Specifi- cally, [|rg( lloo S ig. and |m((-:)))ll & Ft. This implies []r((,)))oo S Fg + ñ ==
Definition 2.3 (e-optimal policy). Given policy simplex II, II is c-optimal policy if (s) 2 su V*" (s)
3

---

Motivating examples. Below we give examples of two cooperative MARL settings which are naturally modeled by our setting. Our experiments Appendix B reveal monotonic improvement in the learned policies as k while providing a substantial speedup over mean-field Q-learning"
relos000 Ry core
relesses di cara
relezzocs Su care
Controller
Controller
Controller
Globol agent
agones are
SUNITOO
Total traffic: - Masy
Agents collectively
optimize congeation 60X - e Se-aa"
Figure I: Bounded exploration in warehouse accidents, and traffic congestions with Gaussian squeeze.
In this task, n homogeneous agents determine individual actions o, to jointly maximize the objective r(z) xe =x=x===)) / where = > i=1 ag and and are the pre- defined mean and variance the system. In scenarios of traffic congestion, each agent i [m] is a controller trying to send vehicles into the main road, where controllers coordinate with each other to avoid congestion, hence avoiding either over-use or under-use, thereby contributing to the entire system. This GS problem is previously studied in Yang et al. [2018). and serves as ablation study on the impact of subsampling for MARL.
Gaussian squeeze:
Consider an M x M grid. Each agent's state is a coordinate in [M] x [M]. The state represents the center of a d x d box where the global agent constrains the local agents' movements. Initially, all agents are in the same location. At each time-step, the local agents take actions (t) E R (e.g., up, down, left, right) to transition between states and collect rewards. The transition kernel ensures that local agents remain within the d x d box dictated by the global agent, using knowledge of at(t), Sg (t), and s; (t). In warehouse settings where shelves have collapsed, creating hazardous or inaccessible areas, we want agents to clean these areas. However, exploration in these regions may be challenging due to physical constraints or safety concerns, causing exploration in these regions be disincentivized from the local agents' perspectives. Through appropriate design of the reward and transition functions, the global agent could guide the local agents to focus on specific d x grids, allowing efficient cleanup while minimizing risk.
Constrained exploration:
Capturing heterogeneity. FollowinggMondal et al. 2022 Xu and Klabjan 2023], our model can capture heterogeneity in the local agents by modeling agent types as part of the state: to do this, assign a type & E E to each local agent by letting S E x S/, where is set that enumerates possible types that treated any local agent. The transition and reward functions can vary depending on the agent's 's type. The global agent can provide unique signals to local agents of each type by letting 8y Sg and og Ag denote state/action vector where each element corresponds to a type.
fixed part of the agent's 's state, and S/ is the latent state space of
3 Algorithmic Approach: Subsampled Value Iteration
Q-learning. Our starting point is the classic Q-learning framework (Wtkkins and Dayan 1992 for offline-RL, which seeks to learn the Q-function Q S x A + R. For any policy n, ("(s a) =
E" D> D (*)(s(t), (()) s, a(0) =a]. Initially, (" 0. for all (s, a) A. Then, for all LE [T]. it is updated as Q (s, a) T-TQ'ss, (s, a), where the Bellman operator T is
(s, rs,,a)
max a'EA
('
(4)
It is well known that T is yccontractive, ensuring that the above updates converge unique Q" such that TQ" = Q" The optimal policy x S + A can then be computed greedily as
We provide supporting code for the algorithm and experiments in httph::://// //ge:t///ttttt htttp::://gghuuu...oommmmmeeeees Mean- Field--ass Suiidd-Subammpeee. Saapppeee---Laalll Learning

---

(((s) = arg maX.EA (s. a). However, the update complexity for the Q-function is O([S][A] = O |S|| || ") which exponential in the number of local agents increases.
Mean-field transformation. To address this, mean-field MARL Yang et al. 2018 (under homo-
geneity assumptions) studies the empirical distribution function F=(m)" 2 R, for 21 == St x Ar:
1 Σ
F Fanm (2) =
1ss 20, = V/ == (Zer E Z1
S A
(5)
n be the space of Zzl-sized vectors (or |St x | -sized tables), where each entry is in {0, 1/n, ..,, 1}. Intuitively, un (Zi) is a discrete distribution over (Si, Ai) where each probability assigned is a multiple of 1/n. Then, FIIm E (2) indicates the proportion of agents in each mate-action pair.
Let un (2)
= 1 {O.....
................................ ....,,n]]]
As in Q-learning, in mean-field Q-learning initially (9 81, ag. 01 F = 0. At each time t [T], we update Q as Q++1 TQQ', where T is the Bellman operator in distribution space:
T (sg: 81, ag. 01, Famay) r(s, a) yIP d.~
(' g 81 ogg dj Felass)
max ((1 (d..a) ViE[n]
EA,
Since the Q-function is permutation-invariant in the homogeneous local agents, one sees that for eacht 2 0, (' si]. ag (mn)) = Q'(xg. $1, ag. 01, Fz In other words, mean-field Q-learning implements the same updates as standard Q-learning. However, the update complexity of Q is only O |gg 2 11),, which scales polynomially in but exponentially in [Z(]-
Remark 3.1. Existing methods use sample complexity ((min[|SyllAAg]
1S, | +))::
one uses Q-leanning if 1-1 < n 2 and mean-field value iteration otherwise. In each regime, as n scales, the update complexity becomes computationally infeasible.
To further reduce the update complexity, we propose SUBSAMPLE-MPY to overcome the polynomial (in n) sample complexity of mean-field Q-learning and the exponential (in n) sample complexity of traditional Q-learning. We begin by motivating the intuition behind our algorithms.
3.1 Overview of approach.
Offline Planning: Algorithm 1 First, the global agent randomly samples a subset of local agents S [n] such that ( k. for S n. then ignores all other local agents [n] \ A, and performs value iteration (using samples to update the Q-function in each iterate) to approximately learn the Q-function Quet. and policy *gst for this surrogate subsystem of l local agents. We denote the surrogate reward gained by this subsystem at each time step by TA S x A - R, where
r a) r (g(8)
1
Σ TEA
84, 81,
(6)
A
In Theorem F.3 we show that [| k.m 10 o0 is Lipschitz continuous with respect to the TV-distance between the state/action pairs of the subsampled agents and the full set agents. Equipped with this approximation guarantee, we show how to construct approximately optimal policy on the full system on n agents. In general, converting this policy on & local agents to a policy on the full n-agent system without sacrificing on centralized -rriiinnniiiingngggn decentrralized-exectttie (CTDE) [Xu and Klabjan 2023 Zhou et al. 2023 which shows that designing performant decentralized policies can be highly non-trivial.
guarantees be intractable, and there is line on works
Online Execution: Algorithm 2] In order to circumvent this obstacle and convert the optimality of each agent's action in the i local-agent subsystem to approximate optimality guarantee on the full
cst n-agent system, we propose a randomized policy Tkmm where the global agent samples A E (In)) at gest each sime derive an action ag < k.m S2), and where each local agent samples other local agents A, to derive an action f- akm (Sg. S;. S..). Finally, Theorem 4.4 shows that
the policy π km
est converges to the optimal policy π²" as k + n with rate Õ Vk
5

---

3.2 Algorithm description.
We now formally describe the algorithms. Before describing Algorithm I (SUBSAMPLE- MFQQ Learn- ing) and Algorithm 2 (SUUSAMPLE-MTTT Execution) in detail, it will be helpful to first define the empirical distribution function:
Definition 3.2 (Empirical Distribution Function). For any population (21..... 2n) E 2j', where Z S x Ar, define the empirical distribution function F=A 2 + R, for all 2 (2 2n) E S x Ar and for all A E ((r) by Fza (1)) = Eies { = 2,,0; = )
Let (4x = b (o......... k}} 211 be the space of | /sized vectors (or |Si] x |Ail-sizes tables) where each entry is in 10,1/k, 2/k, 1). Intuitively, μu (2)) is a discrete distribution over (St, Ar) where each probability assigned is multiple of 1/k. Here, Fsa. (xx indicates the proportion of agents (in the k-local-agen subsystem) at each statc/action pair.
Algorithm I (Offline learning). Let E N denote the sample size for the learning algorithm with sampling parameter k I n. As in Remark 3.1 when 2 < | 211, the algorithm uses traditional value-iteration, and when |2 |2, k uses mean-field value iteration. We formally describe the procedure for each regime below:
Regime with Large State/Action Space: When |Z| k < | we iteratively learn the optimal Q-function for subsystem with k-local agents denoted by Qk.m S x St Ag AB R, which is initialized to O. At time f, we update
kmm (Sg. Sa, Sg. u2) = T Q SA, Og. aa),
where Tk.m is the empirically adapted Bellman operator in Equation ( Since the system is unknown, Ta.m cannot directly perform the Bellman update, so it instead uses m random samples si Po((1sg: ag) and sf Pr( 5g. a;) for each j [m], i E A to approximate the system:
Tk.m Vm (8g, SA, ag as) TA (s, Y
Σ max Dh.m S' og d's).
JE(m) of
a' Ext
Since Tr.m is --cottractive, Algorithm applies value iteration with T until Qu.m converges to fixed point satisfying Te.m k.m Q k.m yielding a deterministic policy *k,m (8 82) where
T (sg: 82)= = arg max Qua (sgs Sa. ag. as).
(8)
agE ayEAn
Regime with Large Number of Agents: When 12, > 12 we learn the optimal mean-field
Q-function for a k local agent system, denoted by Qk.m S x S x ( x Ag x A: + R, which is initialized to O. At time t, we update
Quti (8g, 81, Fiz:01, ag)
(8 81; Fig. 01 (1,ag):
where Fr.m the empirically udapted mean-field Bellman operator Equation 10p. Similarly, as the system is unknown, Fk.m cannot directly perform the Bellman update and instead uses m random samples s/2 ~ Po(:119300 (g) and of Pi(-181.8gg a.), Vj E [m], i E A to approximate the system:
Tr. Q (sg. $1. F=g. an, ag) ar) -2 Σ max
Qh 84 aaazz aj dny)
m
je[m] o' esEd,,afEd, Edd Fag ((i))
(10)
Since @i.m. depends on SA and as through FrA Te.m is also 7-contractive. So, Algorithm
I applies
value iteration with 7 until Qu.m converges to a fixed point satisfying Te.m Quet = Quet yielding a deterministic policy *est (8g. 81, Fsz):
k.mm (5g 81, Fog)
arg max
Qest (Sgs 81, Fag. an, (g)
e, E.E as F. EMe-1 (Ai)
For k.m ($g. S1, = ai a, a'yc0 let [agee (syy sa sa)دe = o and ( (sg, 81. s

---

Algorithm SUB-SAMPLE-MFQ: Learning
Require: A multi-agent system as in Section
number of iterations T,, sampling parameters [m].
m E N, and discount factor y E (0.1).
1: Let A = (1....,A k). Á = f2. ................................ ,.), and (x) [ x-- b 10, k- 1}}1 x Ail
2: if | S |2, then
3: // /Sub-sampled version of standard Q-learning
4: Initialize 2% (8g. SA, Og. a2) 0, v(8g. SA, (g. as).
5: for = to do
6: for (sy. SD.0s, ag) E E x St x Ag x A do
7:
Qh (8g. SA, Og. a=)== - Te, Qk (Ag. $2. Ogy UA)
8: Let the greedy policy be ńt est k,m (8g. 82) = arg max ay EAA (8 Sa, Ogs as).
9:
else
10:
// /Sub-sampled version mean-field Q-learning
11: Initialize Q2 (5g. $1, Fz a1 ag) 0, v(sg. $2,
12:
for = 1 to T do
13:
for (sg. 81, Fag a1, ag) E Sg x uk 1 x Ai x Ag do
2ith (5g, $1, Fss. 01, ag) ) Fa.m 21 (5 $1 Fsg3 a1 ag) gost
14:
15: Let the greedy policy be
kkm ($g. S/. Fs = arg max on egg EAi, EAi, Fug EKK 1(A1)
OT kim (8g, 81, Fss a1, ag) ag).
Remark 3.3. Since mean-field Q-learning maintains the same updates as standard Q-learning (from (.1 follows by noting that the Q-function is permutation-invaaiiat in the homogeneous local agents), the deterministic policies gest
"k,m (8gs 8A) and gest (5gs $1, F'ag) are equivalent.
Algorithm 2 (Online implementation). In Algorithm (SUBSAMPLE-MM) MFQ: Execution) the global agent samples local agents (t) ~ (()) at each step to derive action (t) = [ $2 (t)))
and each local agent samples other local agents (t) ~ u ((nl)) to derive action at
[#ggt (5g, 8;, &A (1))], The system then incurs a reward r(s, a). This procedure of first sampling
agents and then applying #gg., is denoted by stochastic policy "k.m (als), where neet (ag) 8) is the
global agent's action distribution and Tk (az(s) is the local agent's action distribution:
mm (ag (s)
1
k.m (sg: 82) = a)
(11)
AE
est J.m (ails)
(TTka (s 8i, Foz) Fez)=aa)
(12)
(E(())))
The agents then transition to their next states.
4 Theoretical Guarantees and Analysis Approach
We now show the value of the expected discounted cumulative reward produced by akmm is approxi- mately optimal, where the optimality gap decays as k + n and m grows.
Bellman noise. We introduce the notion of Bellman noise, which is used in the main theorem. Note that Tk.m is an unbiased estimator of the adapted Bellman operator Te.
Qu Ss. as) as)==)=aaa (r)
max (. of A,AA
(13)
Let @8(8g 84, ag 02) = 0. For <> 0, let Q1+1 = Q/. where Th is defined for S n in Equa-
tion 13 Then, To is also a 7-cottraction with fixed-point Qi- By the law of large numbers, lim Jkm Ts and [| Q - as + co. For finite cx.m 1g2sst - Q blo
7

---

Algorithm 2 SUBSAMPLE-MFG Execution
Require: Parameter 7" for the number of iterations for the decision-making sequence. Sampling parameter & E [ml, m E N. Discount factor Policy T (sg: Fsa)).
1: Learn f.g. from Algorithm
2: Sample (0), [1n] (0)) So. where sy is distribution the initial global state (5g. 8(n))
3: Initialize the total reward Rg =
4: Policy "k.m (s) is defined as follows:
0 to T" do 5: for 0
6: Choose A uniformly at random from (()) and let a,(() = [ (s, (t), (
7: for = 1 to n do
8:
Choose A; uniformly at random from (k-1) and let a1) = [ (s)( (; 84. (1))
9:
Let sy + 1) Po (o (t), (t),aa(t))) (t))).
10: Let st + 1) ~ (t())s(t),, sg (t), (t)),, eie [n].
R4+1 R4 + + r(),
the well-studied Bellman noise. To compare the performance between x= and x we define the value function of policy Definition 4.1. For a given policy म, the value function V S R for == Sg x ST is given by:
Σ 2r'rs((), ((1)) E0)
oc
(*(s)=
E
(14)
a(t))at-ls(()
Intuitively, (s) is the expected discounted cumulative reward when starting from state s and applying actions from the policy π across an infinite horizon.
With the above preparations, we are primed present our main result: a high-probability bound the optimality gap for our learned policy ky that decays with rate ((1/V)..
Theorem 4.2. Let kk.m denote the learned policy deployed SUBSAMPLE-MFO, Execution. Then, for all so S = Sg ST we have
n k +1
40 4 [b
1
V* (5o) Vm (so) - (1 7
In
+ +2k.
2nk
(1 7)
10
We prove Theorem 4.4 in Appendix G and provide proof sketch in Appendix D We also generalize the result to stochastic rewards in Appendix H
To control the Bellman noise ck.m, we show that for sufficiently many samples m Ckmm also decays
on the order of ((L/Vk) with high probability. For this, we introduce Lemma 4.3 Lemma 4.3 (Controlling the Bellman Noise.). For h: E [nl], let
m 2255 log( Bess(SSSlA,, [-Al| log
1
(1-7)5
(1 7)
be the number of samples in Equation [0).. If the number of iterations T satisfies T 2 2 log Pyk then with probability at least 100 the Bellman error satisfies cg,m S 00
I-7
Vk
We defer the proof of Lemma 4.3 to Appendix G.1 To simplify notation, let T
n est k.m Then, by
combining Lemma and Theorem 4.2) we obtain our main result in Theorem
Theorem 4.4. Let Ti denote the learned policy from SUBSAMPLE-MEQ Execution where the
number of samples m is determined in Lemma 4.3 Suppose T
2 log PVK 1-7 1-y. Then, Vso E S =
Sn x SP, with probability at least 1/100e* we have
l + In
40F |A | IALII
4
V (so)
V 1 (so)
11 - 2
2nk
(1 11
Vi
'hh 1/ * term can be replaced any arbitrary > 0 the of attaching logarithmic dependencies of 7 on the 4/Vl term in the error bound.
8

---

Remark 4.5, One could also derive an alternate bound that retains the T factor via a 7 dependence in the final bound (which shows an exponentially decaying error with the time horizon T). Moreover, in Lemma G.10 we show that the query complexity is on the order of O(m7|S |S | Ag Arl*), and we bound T and set poly(1/(1 - -))) to attain the 1/V rate.
Remark 4.6. Additionally, our poly(1/(1-3)
-dependence may be loose since we do not use more complicated variance reduction techniques as in Sidford et al. [201 8a b). Wainwright [2019] Jin et al. [024] to optimize the number of samples m which is used to bound the Bellman error ck.m- Moreover, incorporating variance reduction would significantly complicate the algorithm and intuition.
Our analysis hinges two non-trivial technical steps. Firstly, for an intermediary step in Theorem E.3 we establish that TV distance, rather than the stronger KL-divergence, is the correct metric to use (as the KL-divergence between FSA and F= decays too slowly as k n, we show in Lemma (. This requires exploiting a recent extension of the DKW inequality to sampling without replacement [Anand and Qu 2024), J, and showing that the transition dynamies we study saturates the data- processing inequality for TV-distance. Secondly, we adapt the celebrated performance-differem lemma (Kakade and Langford [002) to our multi-agent setting, which entails principled analysis and careful probabilistic argument (to which we refer the reader to Appendix
Remark 4.7. We also extend the formulation of SUBSAMPLE-MFQ to off-policy Q-learning Chen ct al. 2021b). Chen and Maguluri [2022a], which replaces the generative oracle assumption with a stochastic approximation scheme that learns approximately optimal policy using historical data. Appendix @ provides theoretical guarantees with a similar decaying optimality gap as in Theorem 4.4
Remark 4.8. The asymptotic sample complexity of Algorithm| | for learning #gat for fixed ls is min [S 11,1,,,,,, [). ((1l |Z]|s, AA, }}, which is at least polynomially faster the standard Q-learning or mield value iteration as discussed in Remark 3.1 By Theorem (44 as k + n, the optimality gap decays, revealing a fundamental trade-off in the choice of k: increasing & im- proves the performance of the policy, but increases the size of the Q-function. We explore this trade-off further in our experiments. If we set k Ollog n)), this leads to sample complexity of min (O(n |2 |S, Ag), Ó(log n.) 2 [|,,g This is an exponential speedup on the com- plexity from mean-field value iteration (from (oly(n) to poly(log n)). as well as over traditional value-iteration (from exp(n) to poly(n)). where the optimality gap decays to 0 with rate O m
Remark 4.9. If k = O(log n), SUBSAMPLE-MPY handles |8| S O(log n/ log log n) types of local agents, since the run-time of the learning algorithm becomes (n)y This surpasses the previous heterogencity capacity from Mondal et al. (022).. which only handles constant |g] < O(1). In- creasing the agent heterogeneity using this type formulation does make the algorithm somewhat more expensive since it factors into the query complexity via the state space of the local agents; however, since the optimality gap of the learned policy is on the order of ((1V/k) (modulo very small Vlog |S ||| factors), increasing the amount of agent heterogeneity does not degrade the quality of the learned policy as the theoretical bound does not get worse. Moreover, recent methods from the graphon mean-field MARL community might be able to enable stronger heterogeneity in the system [Cui and Koeppl 2022
Anand and Liaw 2025
Hu et al. 2023
In the non nan-tabular setting with infinite state/action spaces, one could replace the Q-learning algorithm with any arbitrary value-based RL method that learns Qx with function approximation [Sutton et al. 1999] such as deep Q-networks [Silver et al. 2016). Doing so raises an additional error that factors into Theorem 4.4 We formalize this below.
Assumption 4.10 (Linear MDP with infinite state spaces). Suppose S, and S are infinite compact sets. Furthermore, suppose there exists a feature map Φ : S x A - Rdd and d unknown (signed) measures μ (n²) ........" ((t)) over S and a vector 0 E Rd such that for any (s, a) S A, we have ((.(s,a) = (Ø(s, (()),)),(()) and r(s, a) = (ø(s, a),0). 0).
The existence of Φ: S A Rd implies one can estimate the fufuccioon of any policy linear function. This assumption is commonly used in policy iteration algorithms Lattimore et al. (2020).
Wang et al. 2023). J. and allows one to obtain sample complexity bounds that are independent of [S]
and [ Finally. as is standard in RI., we assume bounded feature-norms [Taahuu et al. 2023 :
Assumption 4.11 (Bounded features). We assume that (|o(s, a) I 1 for all (s. S A.
9

---

Then, through reduction from Zhang et al. [2024]. Ren et al. (2024) that uses function approximation to learn the spectral features Φu: for Qt. we derive performance guarantee for the learned policy estt where the optimality gap decays with
Theorem 4.12. When The is derived from the spectral features on learned in Qi, and M is the number of samples used in the function approximation. then
| S log 2k
+ 24 |1
)]
200
201
Pr xx (8) v" (8) S
2 1
Vi
VM
(1 7)vkk)
k 200
We defer the proof of Theorem 4.12 to Appendix U
Conclusion and Future Works
This work develops subsampling for mean field MARL in a cooperative system with global decision- making agent and n homogeneous local agents. We propose SUBSAMPLE-MFQ which learns each agent's best response the mean effect from sample of its neighbors, allowing exponential reduction on the sample complexity of approximating solution to the MDP. We provide theoretical analysis on the optimality gap of the learned policy, showing that (with high probability) the learned policy converges the optimal policy with the number of agents k sampled the rate ((IVV)). and validate our theoretical results through numerical experiments. We show that the decay rate is maintained, on expectation, when the reward functions are stochastic and when agents learn from single trajectory on historical data through off- off-policy Q-learning. Finally, we extend this result to the non-tabular setting with infinite state and action spaces under assumptions of a linear MDP model.
Limitations and future work. Our current work assumes that the global and local agents cooperate to optimize a structured reward under a specific dynamic model. While this model more general than the federated learning setting, one direction would be to extend our algorithms and analysis to weaker network assumptions. We believe our framework, which can handle dense subgraphs, as well as expander-graph decompositions (Reingold 2008 Anand and Umans| 2023 Anand 2025) may be amenable for this. Secondly, our current work incorporates mild heterogeneity among agents and assumes they cooperative; thus, another avenue would be to consider settings with competitive agents or more complex agent heterogeneity. Finally, would be exciting to generalize this work to the online no-regret setting.
Societal Impacts. This work is theoretical and foundational nature. As such, while it enables more scalable multi-agent algorithms, it is not tied to any specific applications or deployments.
This work was supported by NSF Grants 2154171, CAREER Award 23391 12, CMU CyLab Seed Funding, and CCF 2338816. We gratefully acknowledge insightful discussions with Siva Theja Maguluri, Yiheng Lin, Jan van den Brand, Adam Wierman, Yunbum Kook, Yi Wu, Sarah Liaw, and Rishi Veerapaneni. Finally, thank the anonymous NeurIPS reviewers for their helpful feedback.
Acknowledgements.
10

---

References
Emile Anand. Towards the pseudorandommess of expander random walks for read-once acco circuits,
2025. htttpe://arxav.orr//bb/////
Emile Anand and Sarah Liaw. Feel-good thompson sampling for contextual bandits: markov chain monte carlo showdown, 2025.
15290
Emile Anand and Guannan Qu. Efficient reinforcement learning for global decision making in the presence of local agents at scale. arXiV, 2024. URL
Emile Anand and Chris Umans. Pseudorandommess of the Sticky Random Walk. Caltech Undergruda- ate Thesis, 2023, URL https://ttssssis htt.tteesssssss...r.reeeeeaaaaee caltech. Seeel_Theiis_Sbbaiie
pdf
Emile Anand, Jan van den Brand, Mehrdad Ghadiri, and Daniel J. Zhang. The Bit Complex- ity of Dynamic Algebraic Formulas and Their Determinants. In Karl Bringmann, Martin Grohe, Gabriele Puppis, and Ola Svensson, editors, 5 International Colloquium on Automata, Languages, and Programmiing (ICALP 2024), volume 297 of Leibniz International Proceed- ings in Informatics (LIPIcs), pages 10:1-10:20, Dagstuhl, Germany, 2024, Schloss Dagstuhl- Leibniz-Zentrum für Informatik. ISBN 978-3-95977-3322-5. doi: 10.42330LIIIIc311AAPP.00000 10. WRL.https://rrer otgp:///.a.a....../oo/o/oo/o//// LIPIcs. ICALP 2024.02242 10/LIPIcs ICALP 2024. 10.24.0..p. pdf.
de/
Emile Anand, Jan van den Brand, and Rose McCarty. The structural complexity of matrix-vector multiplication. arXiv preprint arXiv: 2025. httph:tt/: /ttppaww..oooooooooooo 2502. 21240
Stefan Banach. Sur les opérations dans les ensembles abstraits leur application aux équations intégrales. Fundamenta Mathematicae, 3(1):133-181 1922. URL http:://uun: org /oc/ 213289
Dimitri P. Bertsekas and John N. Tsitsiklis. Newro-Dynamic Programmingg Athena Scientific, 1st edi- tion, 1996. ISBN 108.
pdf
Vincent D. Blondel and John N. Tsitsiklis. A Survey of Computational Complexity Results in Systems and Control. Automatica, 36(9): 2000. ISSN 0005- doi: https://doi.org/10.1011 (09000000000000000000000 URL https:://///w/ wew.wwwdeeeincdrret...ccm http:///c/occeeeeee///t/////////
p:1/$0005108800005000
Shreyas Chaudhari, Srinivasa Pranav, Emile Anand, and José M. F. Moura. Peer-to-peer learning dynamics of wide neural networks. IEEE International Conference on Acoustics, Speech, and Signal Processing 2025, 2024. URL http::ss///aiii..rr////////////t 2200g/9..s/249.... 15267
Zaiwei Chen and Siva Theja Maguluri. Sample complexity of posicy-based methods under off- off-policy sampling and linear function approximation. International Conference on Artificial Intelligence and Statistics, pages 11195-1133 11214. PMLR, 2022a. URI. htttps::/ppoceeddaiiie mlr. prress/
wwwehhiinneeeeeeeee .dff
Zaiwei Chen and Siva Theja Maguluri. Sample complexity of pasicy-based methods under off- policy sampling and linear function approximation. In Gustau Camps-Vall Francisco J. R. Ruiz, and Isabel Valera, editors, Proceedings of The 25th International Conference Artificial Intelligence and Statistics, volume 151 of Proceedings of Machine Learning Research, pages 11195-11214. PMLR, 28-30 Mar 2022b. URL httpa://proceedingss mlr press/v161/ chen22i/chen221 pdf
Zaiwei Chen, Siva Theja Maguluri, Sanjay Shakkottai, and Karthikeyan Shanmugam. Finite-sample analysis of off-policy td-learning via generalized bellman operators. Advances in Neural Informa- tion Processing Systems, 34:21440 2021a, URL :ttpttpp://prooeedingg./. nwwrinuuu.... ec/ Paper, pdf

---

Zaiwei Chen, Siva Theja Maguluri, Sanjay Shakkottai, and Karthikeyan Shanmugam. A lyapunov theory for finite-sample guarantees of asynchronous q-learning and td-learning variants. arXiv preprint a 102.0/567, 2021b. URI. htt.htt:///ppsonnllll. informs wwwforrssor//ooo..... httg//ii/11.11//0 12887 opre.20222 0249
Zaiwei Chen, Siva Theja Maguluri, and Martin Zubeldia. Concentration of contractive stochastic approximation: Additive and multiplicative noise. The Annals of Applied Probability, 35(2): 1298-1352, 2025.
Kai Cui and Heinz Koeppl. Learning Graphon Mean Field Games and Approximate Nash Equilibria. In International Conference on Learning Representations, 2022. URL /tpps://eeeee net pett/forummiddOsgntlppptee
Kai Cui, Christian Fabian, and Heinz Koeppl. Multi-Agent Reinforcement Learning via Mean
Field Control: Common Noise, Major Agents and Approximation Properties, 2023. URL https
// //arxiv. org/ 2303/ 10665
Alex DeWeese and Guannan Qu. Locally interdependent multi-agent MDP: Theoretical framework for decentralized agents with dynamic dependencies. In Forty-first International Conference on Machine Learning, 2024. URL lnttps://axiv wttp:df.orrp/f/f///// http:/fff2400.6. 0/////2266068888
Thomas G. Dietterich, George Trimponias, and Zhitang Chen. Discovering and removing exogenous state variables and rewards for reinforcement learning, 2018. htttps://arxxi.orrttt
1806.01584
A. Dvoretzky, J. Kiefer, and J. Wolfowitz. Asymptotic Minimax Character of the Sample Distribution Function and of the Classical Multinomial Estimator. The Annals of Mathematical Statisties, 27 (3):642 - 1956. doi: 10. / CRLh:tts:://at or.//o.................. 1177728174
10. 1214/ 11114/amm//
Dylan Foster, Alexander Rakhlin, Ayush Sekhari, and Karthik Sridharan. On the Complex- ity of Adversarial Decision Making. In Alice H. Oh, Alekh Agarwal, Danielle Belgrave, and Kyunghyun Cho, editors, Advances in Neural Information Processing Systems, 2022. URL https://openreviiee http://wwww..eeeorrormmmmcssppps
Scott Fujimoto, David Meger, and Doina Precup. Off-policy deep reinforcement learning without
exploration. In International conference on machine learning, pages 2052-2062. PMLR, 2019.
JRL|https: /httts:///aattiieee wwwpxiivvorgggpeoee wttp:///////.....///// 02900
David Gamarnik, David Goldberg, and Theophane Weber. Correlation Decay in Random Decision Networks, 2009, URL httpp::/www..ww... jstor arg/staable/25440886
Subhashis Ghosal and Aad van der Vaart. Fundamentals of Nonparametric Bayesian Inference: Space of Probability Densities, page 516-527. Cambridge Series in Statistical and Probabilis- tic Mathematics. Cambridge University Press, 2017. URL
cambri
Noah Golowich and Ankur Moitra. The role of inherent bellman error in oflline reinforceen learning with linear function approximation, 2024.
11686
Haotian Gu, Xin Guo, Xiaoli Wei, and Renyuan Xu. Mean-Field Controls with Q-Learning for Cooperative MARL: Convergence and Complexity Analysis. SIAM Journal on Mathematics of Data Science, 164):166-111999 116, 2021. doi: 10. 10.1137720M13367000 httphtt/:///at org/10
1137/20M136077
Haotian Gu, Xin Guo, Xiaoli Wei, and Renyuan Xu. Mean-Field Multi-Agent Reinforcement Learning: A Decentralized Network Approach, 2022. URL htLL:tttp://rrrxv.or////tt 02731 pdf
Yuanquan Hu, Xiaoli Wei, Junji Yan, and Hengxi Zhang. Graphon Mean-Field Control for Coopera- tive Multi-Agent Reinforcement Learning. Journal of the Franklin Institute, (6)(11):147833 2023. ISSN 0016-0032. URL htt/https: //ooi. org/ 1016/j jfranklin. 2023. 09. 002
12

---

Chi Jin. Zhuoran Yang, Zhaoran Wang, and Michael I Jordan. Provably efficient reinforce- ment learning with linear function approximation. In Jacob Abernethy and Shivani Agarwal, editors, Proceedings of Thirty Third Conference on Learning Theory, volume 125 of Pro- ceedings of Machine Learning Research, pages 2137-2143. PMIR, 09-12 Jul 2020. URL mlr. htttps:/pprccedding wwtp:/sr...prr.sreeeeeeeeeeeeeee prress/v15// jin/0a..n..... html
Chi Jin, Qinghua Liu, and Sobhan Miryoosefi. Bellman eluder dimension: New rich classes of rl problems, and sample-efficient algorithms, 2021. URL http:///aaxiii.ooraaa///////////
Junqi Jin, Chengru Song. Han Li, Kun Gai, Jun Wang. and Weinan Zhang. Real-time bidding with multi-agent reinforcement learning in display advertising. Proceedings of the 27th ACM Inter- national Conference Information and Knowledge Management, CIKM 18, page 2193-2201, New York, NY, USA, 2018. Association for Computing Machinery. ISBN 978 450360142. doi: (tttttt/:///l) acm. awt. httg//oi/100// 10000.1140 1145/3269206 32726999262222222111
10.1 (0.114453226220637222111
Yujia Jin, Ishani Karmarkar, Aaron Sidford, and Jiayi Wang. Truncated variance re- duced value iteration. In Advances in Neural Information Processing Systems. 2024. 4550044aafaaaa773f88444444666662 ooppreeeeeeoe-aape---ooooeeeeeee Conference, pdf preprint arXiv:2405.1225..
URL httpps:/ -ew.eeedddiinnnnenneeeeeee neurips cc/ cc/paper.ppp fi www.eespppereeeeeeeeeeaa 202/////224/f1lle Also available as arXiv
Sham Kakade and John Langford. Approximately Optimal Approximate Reinforcement Learning. In Claude Sammut and Achim Hoffman, editors, Proceedings of the Nineteenth International Conference on Machine Learning (ICMI. 2002), pages 267-274, San Francisco, CA, USA, 2002. Morgan Kauffman. ISBN 1-55860-873-7. URL http:t:://tii...cc...caaa hatpa/go..dddddsapapaappaaepee
r1/ //aarrl.ppff
Seung-Jun Kim and Geogios Giannakis. An Online Convex Optimization Approach Real- time Energy Pricing for Demand Response. IEEE Transuctions Smarl Grid, 86)):2844-2793, URL URL. http::://eeeeeeeporreee ieee documettt
2017. doi: 10.1109/TSG.2216.25599999 7438918
B Ravi Kiran, Ibrahim Sobh, Victor Talpaert, Patrick Mannion, Ahmad A. Al Sallab, Senthil Yogamani, and Patrick Pérez. Deep Reinforcement Learning for Autonomous Driving: A Survey, IEEE Transactions on Intelligent Transportation Systems, 23(6):4999-4926, 2022. doi: 10.1109/ NTTS.2021.3054655. URL httpttts///eeeeepllrrre ieee. org//dcuument/8351813
Robert Kleinberg. A multiple-choice secretary algorithm with applications to online auctions. In Proceedings of the Sixteenth Annual A Symposium on Discrete Algorithms, SODA '05 page 630-631, USA. 2005. Society for Industrial and Applied Mathematics. ISBN 0898715857. URL sattps://di acm. org/ 10. 5555/1070433 1070519
Jens Kober, J. Andrew Bagnell, and Jan Peters. Reinforcement Learning in Roboties: A Survey. The International Journal of Robotics Research, 1231111123-1224, 2013. doi: 10.1177702733444114455222 URL WBLLLttppp///ooo.r///000111111 wttp/110.1177/227736491333933331
Kasper Green Larsen, Omar Montasser, and Nikita Zhivotovskiy. Derandomizing multi coalii-distrbbttonn learning. In The Thirty-eighti Annual Conference on Neural Information Processing Systems, 2024.
Jean-Michel Lasry and Louire-Louis Lions. Mean Field Games, Japanese Journal of Mathematics, 2(1):229 2600 March 2007. ISSN 1861-3624. doi: 10. 10.11077/111337-00701
URL httpss
Delinkssrinng http::e....aaatiiiaaaeaeee /ttp:////...../////.....///////.
1007
Tor Lattimore, Csaba Szepesvari, and Gellert Weisz. Learning with good feature representations in bandits and in RL with a generative model. In Hal Daumé III and Aarti Singh, editors, Proceedings of the 37th International Conference on Machine Learning, volume 119 of Proceedings of Machine Learning Research, pages 5662-5670. PMLR, 13-18 Jul 2020. TRR.https://proceddnng mlr. wttppp//eee/eaattiieeeoao
html
Martin Lauer and Martin A. Riedmiller. An algorithm for distributed reinforcement learning cooper- ative multi-agent systems. In Proceedings of the Seventeenth International Conference on Machine Learning, ICML. '00, page 535-542, San Francisco, CA, USA, 2000. Morgan Kaufmann Publishers Inc. ISBN 1558607072. URL pestps://dl acm, org/ doi 10. 5555/ 645529.. 658113
13

---

Gen Li, Yuting Wei, Yuejie Chi, Yuantao Gu, and Yuxin Chen. Sample Complexity of Asynchronous Q-Learning: Sharper Analysis and Variance Reduction. IEEE Transactions on Information Theory. 2022. doi: 10. 10.1109/TT1220213312200 URL wtt.httss///axii..oott org http:////aaxii..oora////00/6/
03041
Minne Li, Zhiwei Qin, Yan Jiao, Yaodong Yang. Jun Wang, Chenxi Wang, Guobin Wu, and Jieping Ye. Efficient ridesharing order dispatching with mean field multi-agent reinforcement learning. In The World Wide Web Conference, WWW '19, page 983-994, New York, NY, USA, 2019. Association for Computing Machinery. ISBN 9781450366748. doi: 10.1145/3305558 0111885588833333333 URL https://doi. orrooo///// 10. 338558888888888888888
Yiheng Lin, Guannan Qu, Longbo Huang, and Adam Wierman. Distributed Reinforcement Learning in Multi-Agent Networked Systems. CoRR, 2ass22066.06555, 2020. URL https://arxiv org/
abs/ abs/2006. 06555
Yiheng Lin, James Preiss, Emile Timothy Anand, Yingying Li. Yisong Yue, and Adam Wierman. Online Adaptive Policy Selection in Time- Varying Systems: No-Regret via Contractive Pertur- bations. Thirty-seventh Conference on Neural Information Processing Systems, 2023a. URL
Yiheng Lin, James A Preiss, Emile Timothy Anand, Yingying Li, Yisong Yue, and Adam Wierman. Leamning-uugmeetted Control via Online Adaptive Policy Selection: No Regret via contractive Perturbations. In ACM SIGMETRICS, Workshop Leareing-augmented Algorithms: Theory and Applications 2023, 2023b. URL httpst::::.. / http://araninnaaganteeeee----aaa algor whrostttths..mmm thms .aatssggitt.bb..... io/ posters
papers//iggmerrics233---33 papp pdf
Yiheng Lin, James Preiss, Fengze Xie, Emile Anand, Soon-Jo Chung, Yisong Yue, and Adam Wierman. Online policy optimization in unknown nonlinear systems. In Shipra Agrawal and Aaron Roth, editors, Proceedings of Thirty Seventh Conference on Learning Theory, volume 247 of Proceedings of Machine Learning Research, pages 3475-3522, PMLR, 30 Jun-03 Jul 2024.
URL
mlr press/pessseo watssss/227//in2224 html
Michael L. Littman. Markov Games as Framework for Multi-Agent Reinforcement Learning, In Ma- chine learning proceedings, Elsevier, page 157-163, 1994. URL https:tt:: http://wwww.cenccceeee...../
Com
Massart. The Tight Constant in the Dvoretzky-Kieferr Silefer-Wolfoitz Inequality.
The An-
nals of Probability, 18(3):1269 1283, 1990. doi: 10.1214/ap//1176999744 URL
https: cttps://proojccteucl1/
ottp://oo....ooooooooooaaaaaaaaa 10. 10.121//ao//1189077...
Yifei Min, Jiafan He, Tianhao Wang, and Quanquan Gu. Cooperative Multi-Agent Reinforcement Learning: Asynchronous Communication and Linear Function Approximation. In Andreas Krause, Emma Brunskill, Kyunghyun Cho, Barbara Engelhardt, Sivan Sabato, and Jonathan Scarlett, editors, Proceedings of the 40th International Conference Machine Learning, volume 202 of Proceedings of Machine Learning Research, pages 24785-2481 PMLR, 23-29 Jul 2023. URL https://prooeeedings mlr arress/v022/mineg htmml
Washim Uddin Mondal, Mridul Agarwal. Vaneet Aggarwal, and Satish V. Ukkusuri. On the Approxi- mation of Cooperative Heterogeneous Multi-Agen Reinforcement Learning (MARL) Using Mean Field Control (MFC). Journal of Machine Learning Research, 23(1), jan 2022. ISSN 1532-4435.
URL https: jmmmr.mm....... org/ papers/ vol. ///////11111221111 pdf.
Michael Naaman. On the Tight Constant in the Multivariate Dvoretzky-Kiefer Wolfoowiz Inequality. Statistics & Probability Letters, 173: 2021. ISSN 0167-7152. doi: https://doi.or//10
1016/j.spl.20211 202.1.0000.2210.0008 5016771522100050X
Christos H. Papadimitriou and John N. Tsitsiklis. The Complexity of Optimal Queuing Network
Control. Mathematics of Operations Research, 24(2):993-055, 1999. ISSN 0364765X, 15265471.
URL https: attpp:///wyy ://www, jjstor org/ stt//////l333
14

---

James A. Preiss, Wolfgang Honig. Gaurav S. Sukhatme, and Nora Ayanian. Crazyswarm: A large nano-quadcopter swarm. In 2017 IEEE International Conference on Robotics and Automation (ICRA), pages 3299 3304, 2017. doi: (0.1199/CRAA2211.7999999 fsee.org/documen//7993333
htttt::///eeeepppoorr
Guannan Qu, Yiheng Lin, Adam Wierman, and Na Li. Scalable Multi-Agent Reinforcement Learning for Networked Systems with Average Reward. In Proceedings of the 34th International Conference on Neural Information Processing Systems, NIPS' 20, Red Hook, NY. USA. 2020a. Curran Asso- ciates Inc. ISBN 9781713829546. URL / neurgp....iip... cttppppp.ccpappp/22//2
pdf
Guannan Qu, Adam Wierman, and Na Li. Scalable Reinforcement Learning of Localized Policies for Multi-Agent Networked Systems. In Alexandre M. Bayen, Ali Jadbabaie, George Pappas, Pablo A. Parrilo, Benjamin Recht, Claire Tomlin, and Melanie Zeilinger, editors, Proceedings of the 2nd Conference on Learning for Dynamics and Control, volume 120 of Proceedings of Machine Learning Research, pages 256-266. PMLR, 10-11 Jun 2020b. URL https::/pproceddigg
mlr. ppwpss/v20//uu00e html
Omer Reingold. Undirected Connectivity in Log-Space. J. ACM, 55(4), sep 2008, ISSN 0004-5411. 1144/119111188 1391291
doi: 19114///139129.1999999 URL httptttt/////.orrrrrr
Zhaolin Ren, Runyu, Zhang, Bo Dai, and Na Li. Scalable spectral representations for network
multiagent control, 2024. URL httpp////aaxxi.o//aaa/////////// 17221
Ross D. Shachter. Bayes-ball: The rational pastime (for determining irrelevance and requisite information in belief networks and influence diagrams), 2013.
Lloyd S. Shapley. A value for n-person games. In Contributions to the Theory of Games, 1953. URL pdf
https://www hwwd///wwwwwwdd.....mm..//./....
Aaron Sidford, Mengdi Wang. Xian Wu, Lin F. Yang. and Yinyu Ye. Near-optimal time and sample complexities for solving discounted markov decision process with a generative model. In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Desa-Bianchi, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 31, pages 7739-7750, 2018a.
Aaron Sidford, Mengdi Wang, Xian Wu, and Yinyu Ye. Variance reduced value iteration and faster algorithms for solving markov decision processes. In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), New Orleans, LA, USA, 2018b. Society for Industrial and Applied Mathematics. doi:
David Silver, Aja Huang, Chris J. Maddison, Arthur Guez, Laurent Sifre, George van den Driessche, Julian Schrittieeser, Ioannis Antonoglou, Veda Panneershelvam, Mare Lanetot, Sander Dieleman, Dominik Grewe, John Nham, Nal Kalchbrenner, Ilya Sutskever, Timothy Lillicrap, Madeleine Leach, Koray Kavukcuoglu, Thore Graepel, and Demis Hassabis. Mastering the Game of Go with Deep Neural Networks and Tree Search. Nature, 529(7587):484 January 2016. ISSN 1476- 4687. doi: 10. 1038////ne weauureee666. 16961. URL https::/p:: / /ww. nature. com cctm///rt.ccle//ature.......
Sriram Ganapathi Subramanian, Matthew E. Taylor, Mark Crowley, and Pascal Poupart. Decentralized mean field games, 2022. URL httt:t/////:rttt
httggaab/2211.0000 09099
Richard S Sutton, David McAllester, Satinder Singh, and Yishay Mansour. Policy gradient methods for reinforcement learning with function approximation. In S. Solla, T. Leen, and K. Müller, editors, Advances in Newral Information Processing Systems, volume 12. MIT Press, 1999. URL http::////////ceddiiing 3G66225500aeeeeeaaaaaaaa3300----
pdf
Volodymyr Tkachuk, Seyed Alireza Bakhtiari, Johannes Kirschner, Matej Jusup, Ilija Bogunovic. and Csaba Szepesvári. Efficient planning in combinatorial action spaces with applications to cooperative multi reinforcement learning. arXiv, 2023. URI.httts::/pprceddiia mlr
Alexandre B. Tsybakov. Introduction to Nonparametric Estimation. Springer Publishing Company, Incorporated, 1st edition, 2008 ISBN 0387790519. URL htt.::tttt://iiit http///iiiiiniiinnnerreeee 10. 1007//1373
springer. com boo/book//
15

---

Martin J Wainwright. Variance-reduced q-learning is minimax optimal. arXiv:1906.04663 2019.
arXiv preprint
Jiangxing Wang. Deheng Ye, and Zongqing Lu. More centralized training, still decentralized
execution: Multi-agent conditional policy factorization, 2023. htRp::ttp:///araa org/ /bs/
2209. 12681
Christopher C. H. Watkins and Peter Dayan. Q-learning. Machine Learning, 8(3):299-292. May 1992. ISSN 1573-0565. doi: 10.1007/BF000992698. URL https://link http:/iiik..siinggg... springer com/ article/10. 1007 1007//00000010///0099922666
Mengfan Xu and Diego Klabjan. Decentralized randomly distributed multi-agent multi-armed bandit with heterogeneous rewards. In Thirty-seventh Conference Neural Information Processing Systems, 2023. URL wRthtttss///////..tt. wtt.pparwo..o...tt.fooourodddddd
Yaodong Yang, Rui Luo, Minne Li, Ming Zhou, Weinan Zhang, and Jun Wang. Mean Field Multi- Agent Reinforcement Learning. In Jennifer Dy and Andreas Krause, editors, Proceedings of the 35th International Conference Machine Learning, volume 80 of Proceedings of Machine Learning Research, pages 5571-5580. PMLR, 10-15 Jul 2018. URL httphtss///proceedding
mlr wwwpppesssss//seeee yan0:/yyng888 html
Hongming Zhang, Tongzheng Ren, Chenjun Xiao, Dale Schuurmans, and Bo Dai. Provable repre- sentation with efficient planning for partially observable reinforcement learning. In Proceedings of the 4/st International Conference Machine Learning, ICML'24. JMLR.org, 2024. URL
https://dl. acm. org/ wwt//oi/goiiooooooooooooooo 5555/3692070.
Kaiqing Zhang, Zhuoran Yang, and Tamer Başar. Multi-Agent Reinforrment Learning: A Selective Overview Theories and Algorithms, 2021. URL htt_//ccpe///rri..o/////////1111
Yihe Zhou, Shunyu Liu, Yunpeng Qing, Kaixuan Chen, Tongya Zheng, Yanhao Huang, Jie Song, and Mingli Song. Is centralized training with decentralized execution framework centralized enough for marl?, 2023. URR.https://aax. http://axwvvvrgaabsrs/a/aaa www.absg.///eeooo.oe....oeaaeeee ort./baa///....1.555.
16

---

A Mathematical Background and Additional Remarks
Outline of the Appendices.
Appendix B presents numerical simulations on the performance of SUBSAMPLE-MFQ on the Gaussian squeeze and constrained exploration tasks.
Appendix presents notation and basic lemmas involving the learned Q Qu-function, as well
stable and practical implementation of Algorithm]] !
Appendix presents proof sketch of our main result in Theorem 4.4
Appendix presents the proof of the Lipschitz continuity between Qx and Q"
Appendix presents our bound on the TV-distance in Theorem D.2
Appendix proves the bound on the optimality gap between the learned policy #p and the optimal policy π².
Appendix presents extension of the result stochastic rewards.
Appendix presents extension of the result to off-policy learning that follows by using historical data.
Appendix presents an extension of the result continuous statc/action spaces under linear MDP assumption.
Appendix presents some practical derandomized variants with randomness sharing..
Table Important notations in this paper.
Notation
Meaning
& (Manhattan) norm;
foo norm;
E
The set of strictly positive integers;
The set of d-dimensional reals;
The set {1,...,1) m), where E Z
The of k-sized subsets of {1...., m]]: ag E A,, is the action of the global agent:
0g
8g E S, is the state of the global agent:
01
On
01. ......:00 an AP
the actions of the local agents 1, ,,...
$1
$1 $1....,5p Sp E ST are the states of the local agents 1....,
(ag. (dg:a1... ai........ an) Ag x AA is the tuple of actions of all agents;
s
(sgi $1,...,8n E Sy x SS"' is the tuple of states of all agents;
2; (st, a,) E 21, for i [ni]:
Mg (x())
N4 (x(2)) (0, 1/k, 2/k, 2/., 1] 1)
1 (t)
n(2)) = pm, (0, 2/tp..//....... 1)
SA
For A (m). and collection of variables {s1:..., 8n }, 82 = t8 14:iE4
af <
Product sigma-algebra generated by sequences =œ and 2/33
x² is the optimal deterministic policy function such that = T (s): #t is the optimal deterministic policy function a constrained system of
m
A = local agents;
Rest is the stochastic policy map learned with parameter such that (s);
Po ag)
Po (-1sg (g) is the stochastic transition kernel for the state of the global agent;
Pt Si, 8i,8g) is the stochastic transition kernel for the state of local agent i [m]: og is the global agent's component of the reward:
ag)
Sg.
ri is the component of the reward for local agent E [n]:
a(
r(s, a) (5 ag) + Eiemn) Ti(Si, Sg. ai) is the reward of the system;
())
( a) rg (Sg. ag) + A Eiea ri(st, 8g. a;) is the constrained system's reward
with A local agents; T is the centralized Bellman operator;
T Tr
Tg is the Bellman operator constrained system of A k local agents;
(1)
&, projection of onto set O
17

---

Definition A.1 (Lipschitz continuity). Given metric spaces (X' dx) and (). dy) and a constant L map f X + -'r L-Lipschitz continuous if for all x, y E X, dy (f(),, f(y) S L. dx(x.y).
Theorem A.2 Canach-Caccioppoli fixed point theorem [Banach] 1922]) Consider the metric space (X, dx), and T X' + X such that T is a L-Lipschitz continuous mapping for y E (0, Then, by the Banach-Cacccioe fixed-point theorem, there exists a unique fixed point x² X for which T(x")= =x= Additionally, x² = lim T (zo) for any Do E N.
B Numerical Experiments
This section provides numerical simulations for the examples outlined in Section All experiments were run on 2-core CPU server with 12GB RAM. We chose parameter complexity for each simulation that was sufficient to emphasize characteristics of the theory, such as the complexity improvement and the decaying optimality gap
Figure 2: a) Reward optimality gap (log scale) with eest running 300 iterations. b) Computation time (in minutes) against sampling parameter k; for S n 8, to learn policy n eett cumulative rewards for l I n 50.
"hm c) Discounted
B.1 Constrained Exploration
(i) denotes the projection of 8, onto its Let Sy St [6]2 where for 8a E Si), se
i'th coordinate. Further, let At = Ag {"up". "down", "right", "left") given formally by (()) (7)), (2), (L)) Let lp(x) denote the projjecttoon of onto set D. Then, let (s'.
Us,, (s + aa (g).s5 (s/ sf at) = (s + |s| - sgg + af). We let the global agent's reward be
(3, a,) = 2 E la, = (2), <1)+2> 1aa = (T),, 5g
(1) > i}. and the local agent's
rewards be (s.. Sy. a4) 1{a 00 6 1(s
( ||s s1111-
Intuitively, the reward function is designed to force the global agent to oscillate vertically in the grid, while forcing the local agents oscillate horizontally around the global agent, thereby simulating constrained exploration. This model has been studied previously in [in et al. (023b)]
For this task, we ran simulation with n 8 agents, with 20 samples in the empirically adapted Bellman operator. provide simulation results in Figure 2p. observe monotonic improvements in the cumulative discounted rewards as k - Since k recovers value-iteration and mean-field MARL algorithms, the reward at & = n is the bascline we compare our algorithm to. When k < n, observe that the reward accrued by SUBSAMPLE-MA is only marginally less than the reward gained by value-iteration.
B.2 Gaussian Squeeze (GS)
In this task, n homogeneous agents determine their individual action to jointly maximize the objective r(z) zee (x=w(=) /o" where Σn a, 0; (0..... 9}, and j and the pre-
defined mean and variance of the system. We consider a homogeneous system devoid of global
WW provide supporting code for the algorithm and experiments in https::ss.. :/tp:th///ttttt/////g http:///hhhub..coooommmettnoo/// Mean- Field--a-e wiwiddd-uusaaplee- -aaplel------ininn
18

---

agent to match the mean-field setting in Yang et al. (2018). where the richness of our model setting can still express GS. We use the global agent to model the state of the system, given by the number of vehicles in each controller's lane.
We set S [4). A (0...... .),, and S, Si such that 5g - and Ag {0). The transition functions given by st(t + 1) s;(t) 1. (fs,(t) sy(t)) + Ber(p) and sy(++1) Σi= st(t + 1)], where Ber(p) is Bernuulli random variable with parameter >> 0. Finally, the global agent's reward function is given by rg (5 (g) Sg and the local agent's reward function is given by (1 Sg. a,) - (=--,))*
max 6/ az).
For this task, we ran scall-scale simulation with n = 8 agents, and a large-scale simulation with 50 agents, and used m 20 samples in the empirical Bellman operator. We provide simulation results in Figure 2 and Figure where Figure 2 demonstrates the exponential improvement in computational complexity of SUBSAMPLE-MPQ, and Figure demonstrates monotonic improvement in the cumulative rewards, consistent with Theorem Here, both metrics outperform the mean-field value iteration benchmark.
C Notation and Basic Lemmas
For convenience, we restate below the various Bellman operators under consideration. Definition C.1 (Bellman Operator T).
TQ'(s.a) := r(s,,)) + +E
o (olaaa)) Pi( aileg.as)
max Q' a')
(15)
a'EAA
Definition C.2 (Adapted Bellman Operator Tx). The adapted Bellman operator updates a smaller Q function (which we denote by Qu), for a surrogate system with the global agent and E [ri] local agents denoted by A, using mean-field value iteration and E A such that:
t ( 85 Frayy aj ag) == ra a) + 7E
a'EA Qi('' 8f Feay d'y
max
(16)
Definition C.3 (Empirical Adapted Bellman Operator 7. The empirical adapted Bellman operator Tk.m empirically estimates the adapted Bellman operator update using mean-field value iteration by drawing m random samples of 8g P-(-| ag) and 8; ~ Pi( (1, 8g. as) for i E A, where for l E [m], the f'th random sample is given by sy and s and E A:
t (h 8j, FRAN, aj ag) == ra a) + 7
Σ m tE(m]
max Q (5g sg, Po Pegny of (17) a'EA
Lemma C.4. For any A C [n]] such that | k. suppose 0 S rrass a) S. Then, for all / N.
Q S 1-
Proof. The proof follows by induction on l. The base case follows from Q% : 0. For the induction, note that by the triangle inequality 11 1loo ||rallo + 71 1illo 7
Remark C.5. By the law of large numbers, limm Ttm =Te, where the error decays in O(1 D(1/vm) by the Chernoff bound. Also, T, = T. Further, Lemma C.4 is independent of the choice of k. Therefore, for k = n,, this implies an identical bound on Q'. An identical argument implies the same bound on Q
T satisfies a 7-contractive property under the infinity norm Watkins and Dayan 1992 show that Th and Tk.m satisfy cycottrace property under infinity norm in Lemmas C.6 and C.7
We similarly
Lemma C.6. T. satisfies the "-contractivv property under infinity norm:
l - 2x S ~ 2x
(18)
19

---

Proof. Suppose we apply Ta to Qx(sg. Fsx: ag) and Q2(sg, FeA ag) for |A| = k. Then:
[ - 1x
E Pa max (%(y/= dz) - E (p max Qx(%), Pg)) (t d'Ed
=Y
max onESg. agEAg Fog (2)
d'EA
(( ViEA,
ViEA
max $ FF, (2),,''
V268g Fog, dgy) - Q F2j dgz) = =>11 - Qull
The equality cancels common LA (s, a) terms in each operator. The second line uses Jensen's inequality, maximizes over actions, and bounds expected values with the maximizers of the random variables.
Lemma C.7. Tr.m satisfies the "y-ontraactive property under infinity norm.
Proof. Similarly Lemma
C.6
suppose
we
apply Trmm
Q ag)
and
kk (sg ag). Then:
lTTe.m 2k- - - Villo
7 m
Σ RE(m
Fzg.o) max F:. dgg) a'EA
max
a'EA
S r
max
12 F2,, d') Q'lls ,s2s:'9))
of e , E2)
= x11 - 12
The first inequality uses the triangle inequality and the general property max f(a) maxseA f(b)] I max.e (f(a)) f(b)]. The last line recovers the definition of infinity norm.
Remark C.8. The 7-contractivity of Th and Te.m attracts the trajectory between two Qx and Qu.m functions on the same state-action tuple by y at each step. Repeatedly applying the Bellman operators produces a unique fixed-point from the Banach fixed-point theorem which introduce in Definitions C.9 and C.10
Definition C.9 (Q -fuucciio, Suppose Q == O and let 1 Fsg, ag) = ( Fea, ag) for E N. Denote the fixed-point of Tg by Q% such that TrQ (8, (8g, Fza, (gg Qi F=A, ag).
Definition C.10 (Quttffnnttoon) Let @2,... == 0 and @ (s,, Fes, ag) = Fr. Vimml (5g Fes ag) for E N. Then, the Banach-Cacciopoli fixed-point of the adapted Bellman operator Tk.m is Qest such that Tk. Qest (Sg: ag) Quet (sg. Fea ag). Corollary C.11. Observe that by recursively using the c-ootracctvve property for T time steps:
li: Q am -x - @4
(19)
|1 - QT ol. ST 11 @o
(20)
Further, noting that Q% Qh. 0, 11 S I-y
i and @eapen lloo S 1 from Lemma C.4
11 - QT 1100 5 1 I-7'
(21)
11
@T. 1l.o
577 1-
(22)
Remark C.12. Corollary C.1 characterizes the error decay between Q and Q and shows that it decays exponentially in the number of Bellman iterations by a T multiplicative factor.
Furthermore, characterize the maximal policies greedy policies obtained from Q" Qú. and Qret
20

---

Definition C.13 (Optimal policy x²), The greedy policy derived from Q" is
(s)
arg max Q* (x,a). aEA
(23)
Definition C.14 (Optimal subsampled policy ai). The greedy policy from Q
arg max (gg Si, Fsay.)= (ag.R.. J AA
2% 8i, Praye ai ag).
(24)
Definition C.15 (Optimal empirically subsampled policy (km)). The greedy policy from Quet is given by Rkm (Sgr Fea):= == (ag (ag.a..Fosyy X
Quet (sg Sir Feare Oi ag).
arg max
(25)
Tigure@detail details the analytic flow on how we use the empirical adapted Bellman operator to perform value iteration on Qu.m to get Quet which approximates Q*.
Algorithm 3 gives stable implementation of Algorithm I with learning rates (m her Algorithm
(m-
provably numerical stable under fixed-point arithmetic (Anand al. 2024 2025 Q in
Algorithm 3 is 7-contractive as in Lemma C.6 given appropriteety conditioned sequence of learning rates 1):
Algorithm 3 Stable (Practical) Implementation of Algorithm !
SUBSAMPLE-QQ Learning
Require: A multi-agent system described in Section Parameter T for the number of iterations
in the initial value iteration step. Hyperparameter E [n]. Discount parameter y E (0, 1). Oracle
O to sample s' P, (-18g; (g) and 8; Pi(-(si, as) for all i [n]] Learning rate sequence
(n)))(T)) where 7/2 (0,1)
1: Let A = [k]]
2: for (1g FZA2)) E Sy x S X Pk- (2,) do
3: for (ag. 01) E Ag x Ar do
4: Set Qh 10.m ($g: $1 F Fai1 01, 0g) = =0
5: fort= d' do
6: for (sg. $1, F FESN)) E Sg St Pk- px-1(Zt) do
7:
for (ag. 01)
Ag A do
8:
Q (8g. 81, FZAr ag. 01) =
1. (8g, 81, ag. 01)
+ T 1
(8g. 81, FsA.1 ag. (1)
9: Let the approximate policy be
4T 81, FsS..)=
arg max
( 81, Feayi ag.
( (axmm)
Theorem C.16. As + co, iT = and Et= dh < co, then Q-learning converges to the optimal Q function asymptotically with probability 1.
Furthermore, finite-time guarantees with the learning rate and sample complexity have been shown in Chen and Maguluri (2022b), which when adapted our Qk.m. framework in Algorithm yields:
Theorem C.17 (Cen and Maguluri [2022b]). For all {1,..., T} and for any 0, if the learning rate sequence n satisfies tie 2 and T |S:]|Ai Al |S,1A,,,, 2 then
(1-y)5
10 km
Qeat || <
Definition C.18 (Star Graph Sz). For n N, the star graph S,, is the complete bipartite graph Kin--
21

---

Sn captures the graph density notion by saturating the set of neighbors of the central node, Such settings find applications beyond RL as well [Chaudhari et al., 2024 Anand and Qu 2024 Li et al.) 2019]. The cardinality of the search space simplex for the optimal policy is exponential in n, so cannot be naively modeled by an MDP: we need exploit the symmetry of the local agents. This intuition allows our subsampling algorithm to run in polylogarithiic time (in n). Some works leverage an exponential decaying property that truncates the search space for policies over immediate neighborhoods of agents; however, this still relies on the assumption that the graph neighborhood for the agent is sparse [Qu et al., 2020a/b) b]; however, Sn is not locally sparse; hence, previous methods do not apply this problem instance.
1
2
3
Figure 3: Star graph S,,
Finally, we argue why mean- mean-field value iteration faithfully performs the same update as value iteration. Lemma C.19 (Equivalence of Mean Mean-Field Value Iteration and Value Iteration). Since the local agents 1....,7 n. are homogeneous their state/action spaces, the Qu-function only depends on them through their empirical distribution F=A. proving the lemma. Therefore, for the remainder of the paper, will use @5 F ag) (5g St, F FzAye Gg. a,) (x $ ag aΔ) interchangeably, unless making remark about the computational complexity learning each function.
D
Proof Sketch
This section details an outline for the proof of Theorem 4.4 as well as some key ideas. At a high level, our SUBSAMPLE-MFQ framework recovers exact mean-field Q learning and traditional value iteration when = n and as m + co. Further, as k k-+, Q; should intuitively get closer to Q' from which the optimal policy is derived. Thus, the proof is divided into three major steps: firstly, we prove Lipschitz continuity bound between Q3 and Q; in terms of the total variation (TV) distance between Fza and F= Next, we bound the TV distance between F.a and F=j.j: Finally, we bound the value differences between T est and n² by bounding Q" n =(((s)))))))))){))))) Q" mft (s)) and then using the performance difference lemma from Kakade and Langford 2002).
Step 1: Lipschitz Continuity Bound. To compare Q7 FAx (g) with Q" (s,s, ay), prove Lipschitz continuity bound between Q7 F=A: (g) and Q% (8g. Fag) with respect to the TV
distance measure between SA E (*I=i) and s.y E (f(e)):
Theorem D.1 (Lipschitz continuity in Qi). For all (s, EESSAAAEE (m]] and N E ((*).
2
(*g Fra.ag) ag) (sg, Pagi ag)l S 1
||( )1x TV (Fza: Fay.)
We defer the proof of Theorem D.I to Appendix See Figure for a comparison between the Q learning and estimation process, and the exact Q-learning framework.
Step 2: Bounding Total Variation (TV) Distance. We bound the TV distance hetween Fra and Fs.. where A (I1)) This task is equivalent to bounding the discrepancy between the empirical distribution and the distribution of the underlying finite population. When each é A is uniformly sampled without replacement, we Lemma F3 from Anand and Qu (2024) which generalizes the Dvoretzky- Kieferr Wolfowitz (DKW) concentration inequality for empirical distribution functions.
Using this, we show:
22

---

@h Cl ag))
(7 8/a]> dgr (mi)
col
(
Quen kmm (8gg F 0g)
(2) Qi(8g, F=a, ag)
2% (8g. Faiu 0g)
Figure 4: Flow of the algorithm and relevant analyses in learning Q". Here, (1) follows by performing Algorithm (SUBSAMPLE-MM) the Lipschitz continuity and total variation distance bounds in Theorems D.1 and D.2 Finally, (4)
Learning) on Q (2) follows from Lemma 4.3 (3) follows from
follows from noting that 2% = ='.
Theorem D.2. Given a finite population 2 (21,..., ; for 2 E 21, let C [n] be a uniformly random sample from Z of size k chosen without replacement. Fix > 0. Then, for all E Z
Pr
sup 2E
Σ iEA
1 = r}
Σ 1f2 =) s 2 2/2//e 2knc?
A
=E/m]
Then, by Theorem D.2 and the definition of total variation distance from Section ō E (0, with probability at least - 8,
we have that for
n1 k
2
(F
(26)
8nkk
We then apply this result to our MARI setting by studying the rate of decay of the objective function between the learned policy =f and the optimal policy x² (Theorem 4.4
Step 3: Performance Difference Lemma to Complete the Proof. As consequence of the prior two
steps and Lemma 4.3 Q' (s, a') and ( F2):4)) become similar as k + n. We further prove that the value generated by the policies x² and Tk est must also be very close (where the residue shrinks as k + n). We then use the well-known performance difference lemma [Kkkade and Langford [002] which we restate in Appendix G.I A crucial theorem needed to use the performance difference lemma is bound on (s's π (s')) Q* A (s'g )).)).
Therefore, we formulate and prove Theorem D.3 which yields probabilistic bound on this difference, where the randomness is over the choice of A E (()):
Theorem D.3. For a fixed s' E S = Sg x S and for E (0, 1]. with probability at least
1 - Ag Ail::
21) 1 1-?
In k +1
In (2|
Q'(s', - (5', RRmm ( F)
V
+
26
2nk
8
We defer the proof of Theorem D.3 and finding optimal value of 5 Lemma G.8 the Appendix. Using Theorem D.3 and the performance difference lemma leads to Theorem 4.4
E Proof of Lipschitz-continuity Bound
This section proves a Lipschitz-continnity bound between Q7 and Q" and includes a framework to compare (2) E [(e((.)) (s. and (s, ) in Lemma E.12
Let 2 = (s,, a:) E Z = St x Ar and د사 = {4 : i A} Zf. For 2, = (s,, a.), let 2((s) = 8,.
and 2,(a) = With abuse of notation, note that (s Qg. $A, as) is equal to QT (sg. ag. ZA).
The following definitions will be relevant to the proof of Theorem E3
Definition E.1 (Empirical Distribution Function). For all z and (s', a') S₁ x A,, where
A C [n).
1
(s',5')
Σ
- d'}
A
23

---

Definition E.2 (Total Variation Distance). Let P and Q be discrete probability distribution over some domain Q2. Then,
1 TV(P,Q) = - - ECO Pr(EE P)(EE)
sup
Theorem E.3 O is 2 || )l -lpsschttt continuous with respect to FEA in total variation
distance). Suppose A, A C [n] such that |
k and | W. Then:
27 2t
(T ag. Fea) (s ag. Fea / S
E
Σ 1=0
11m(,.:>))0 TV (Fsa: Fsa))
Proof. We prove this inductively. First, note that Q ( from the initialization
step, which proves the lemma for T = O, since TV(;)) 2 0. At 1:
(8g ag. PzA) Q (6g) ag. F F2a))1
Q ag: FAA) Tx (sg: Ugg F
Qhls'g Fa's dg) r(sg: 0g) + tnEus,o's afEd,
max
- -r(8g; Fear 0g) - -Be
max (s Fe For
a E,,
|r(sg; ag. 12aa) - -r(gg: Ogg Feai)l
Σ (( 21)
r((g: 2i) W
Σ
k IEA
EEA
BeI ri(g)1 u) E (1 2))
In the first and second equalities, we use the time evolution property of Q and Q by applying the adapted Bellman operators To and Te. to Q% and Q%. respectively, and expanding. In the third and fourth equalities, we note that (?((...)) = (..s) = O, and subtract the common 'global component' of the reward function.
Then, noting the general property that for any function f X - y for | < oo we can write f(x) = Evex f(y) (y- = = we have:
(0) og. FEa)=
Qb (Sgr ag. Fzw))l
Σ
(r($g12){{21 =2} EejnF 2/
Σ
(r((gs 2)112/= 2}
LEEZ
LEEZ
Σ ((((g)2) 2) (EzinEFa 1f21 = 2} - BeqwBs o'
1 = 27}
zEZ
Σ re(sg) 2) (Fza(z) - (2) (Far))))) ZEZ
maxri(8g; 2)1 Σ (1 F (2)
max ze2
sE2
< 21]rr(ss
The second equality follows from the linearity of expectations, and the third equality follows by noting that for any random variable X ~ X. Ex1[X = x| Pr[X = z). The first inequality follows from an application of the triangle inequality and the Cauchy-Schiee Schwarz inequality, and the second inequality uses the definition of TV distance. Thus, at T 1, Q is (2]lrz(ss -Illoo continuous in TV distance, proving the base case.
24

---

Assume that for T S E N:
@ (50 ag Fea) - Qh (3g) agi Fesr)) 1
Σ 27
l1r((s))loo . TV (Fesi Fes
Then, inductively:
12 (8g: ag. P=a) + Og: P=aa)]
(5g:
(8gg 21)
A
A
iEA
+
Bag Eagin's max (s'g d' F'is)
Bagii'' e,e d'
max
Ve dg. P:g.))
o EAg,
d' E'A
s <2111((. 11,00 (Vs, Fsy))
B Po max O% (s)g o/p Fda)) -
V d'g Faia))
+
+
max oyEAg, d'
af EyE EAE
<2|17(+-)11<> (V Pase) + Σ 23 ||r((:-))lxx (TV(Fza Fzg.)
2n |m(()))bbo (V(F ).A.)
In the first inequality, we rewrite the expectations over the states as the expectation over the joint transition probabilities. The second inequality then follows from Lemma E.14 To apply to Lemma E.14 we conflate the joint expectation over (sg. $auar) and reduce it back to the original form of expectation. Finally, the third inequality follows from Lemma E.5
By the inductive hypothesis, the claim proven.
Definition E.4. [Joint Stochastic Kernels] The joint stochastic kernel on (sy. SA) for A C [n] where
| k is defined as Js S. Sk x Sg Ag S x A$ + [0, 1], where
Jk(s'g s/2| ag SA. as) = Pr[[s g. s/2 /5)s ag ss
(27)
Lemma E.5. For all T E N. for any Og Ag. $y Sg SA E St as E At,a's At, and for all joint stochastic kernels Jk as defined Definition E.4
Be ( Ia 8y 8g. sa,0) max QT (5 dg. F.)))
- -Eig, Ee, (e
( dyg Peg.)) aga
max
S Σ 27
[Im(s Mlooo)) (Fza Pay.)
Proof. We prove this inductively. T the statement is true since (-(())))) (G.)) and TV(..)) O.
At 1
E (ogg (orn
max Q g. ag s's. a's)
max Qh a's s'r obiogy
E ( ) Jer (x (::1g)
r ( ( og)) + Eiea (is/,,af, s0))
max ay max d'yd's
&
(r (15),. dg)) + Eieairi d',
-Eeei P )
25

---

Eies ri(5),, a/ 8g)
=
B (sg (1110))
max daa
b
Eiesr re(s), sqg)
(og 2 (1
max "s2'
ki
- F((5 - Buggenggneaatibbaeeeeee. h
Σ F((5g180))
iEA
NEA
In the last equality, note that max
Σ ri o/) = Σ da
max maxxi(k), d(.
Σ max (1,
Σ
IEA
iEA
where (z) max (1(s/, s/y
Then, have:
Bie (eg.ssg)n20trrrbooeeeesss Σ :((((18))) -Ess A aa
1
Σ
SEA
IEA
- k
f( Fo (x)
rESt
Eisyy Lssy.'' (.
E Fi( (x)
BegNE, "uu /oua /a suar)
Σ sESt
ft, N "
- Feg (r)]
< || Esg cs/Dua)) Jaauall o
Yus (oo "aua??
Σ
E
Aua 10, Fa (x)
1o (x)
< [m((s:))0o EsgrE Suar colare Jaaaall Aua lgg auair "auurr"aus"" auus
Σ
E lo Fos (x) E. E. og Fd (x)
#ES,
s <2|1r((.)))les
E " "uus / en//waea Jlavallon
TV A Feg. Esy lua Feig))
< 22(1rr(- TV F2g))
The first equality follows from noting that f(x) [[==)=>xxx((x)11 inequality which allows us swap the order of summations as the summand is finite. The second equality uses the law of total expectation. The first inequality uses Jensen's 's inequality and the triangle inequality. The second inequality uses |] < Ill which holds as ||rz]l>o is the infinite-norm of the local reward functions and is therefore atleast as large any other element in the image of ri. The third inequality follows from the definition of total variation distance, and the final inequality follows from Lemma E.7 This proves the base case.
f(x) 2'} and from Pubini-Tonellis
Then, assume that for T S t' N, for all joint stochastic kernels Th and Jv. and for all d' Ag. a's E Ar:
Eeg J~J (a
max QT ($ dg. s'A)
(eg ( Mo wtl. max QT (5/g dg. s'av, a'a.) 2
Σ
n"
[Io Fag)
1=0
26

---

For the remainder of the proof, we adopt the shorthand B to denote ((ag) (a))) and Egy Nr to denote miaaate Then, inductively, we have:
max 1%+ (s). aaia's
max OF
(5) o gr dy )s = (1) (1)()))
where
(I)
r gr a' d's max "/
re
max (F s' a') agaaz
and
(II)
max d'
rar(d s'))
+ yB (22
max agaa".
(5% " dg a'x))
Let
āg. ās
ra r a'g s's,d's + (x2 (0
max Q s aa.aaaa") ag
arg max "'EAg:d's EAt
and
ág. 0.s"
max ".E.A, EAR
ravil'g o' s''r,
E (oy I Jel
max
(T S dg d'x.)
Then, define TAVد E Alauall by
ais i A,
ā. ais if E A
Similarly, define âsus E AlAuall by
Jii
i A'
dii i
A
Suppose (I) 2 (II). Then,
E (x
max dg. 5's aa
( (
max 2 (s 9.
a' 8 s/s, a'y))))
a a' A
27

---

B Sass Ok 1x+ (s'g s's. 02)
" ag. aم))
(as. 17+ ( ag. s's. 02)
D 2F (s' ag.
ra ( s'' "g. AA)
max Qh (s" any s d') ag.az
- (o rarls'g S' ag. aدy)
max QF (gg ag. s",, sa"))) sa")) ag.0
E Pa S'. و2)
E
s'a ag. إددة
max Qf a' a') oy o
+ ?
max Q dy s' d36.) ag.a
Σ (
K
E 1-
Σ Siis
EEAr
+ > B Beg
Q (S og o3)))
max
E Bo (rlep
max
Q ay s' d'x.)
d'.''s
< 22(1r(()))1l TV(FA,, FEy +7
E29²) In(.-)Ilo.TV(C (V(F2s,FF 1=0
T+1 Σ 22d [m)))))b TV(FFA.
The first equality rewrites the equations with their respective maximizing actions. The first inequality upper-bounds this difference by allowing all terms to share the common action à. Using the Bellman equation, the second equality expands Q and QT+,. The see- ond inequality follows from the triangle inequality. The third equality follows by subtract- ing the common r rg(5" (gg) terms from the reward and noting that the two expectation terms E,gio's Tk( Og. SA, as) Eeg www.ererrrlleadaa.e..o.
can be combined into single expecta-
tion E. 2 (aa))
In the special case where As = شA we derive closed form expression for Js in Lemma E. To justify the third inequality, the second term follows from the induction hypothesis and the first term
28

---

follows from the following derivation:
EiE A r((8) 8 āi)
"aog EiEs' ri(8/s g5.)))))aa)))) a.)
( (:: Eies ()) (1
Eies: 19 s62)
k
|1 E B "uua (Aua Jaauar( www. TV sually Fea: By auall Fowi)
(arr(s))laa TV( F
The above derivation follows from the same argument as in the base case where rf (6), 8g) ri(s,, y âs) for any E A U A. Similarly, if (I) (II,, an analogous argument that replaces م with 0s yields the same result.
Therefore, by the induction hypothesis, the claim is proven.
Remark E.6. Given a joint transition probability function JACAy as defined in Definition E.4 we can recover the transition function for single agent E A A' given by Ji using the law of total probability and the conditional independence between s; and Sg $[n]yi in Equation (28). This characterization is crucial Lemma and Lemma F.5
Ti (-1ss Sy. ag. 8t, a.)
JAUAS (s'uAAy 8/15'g 8y, ag. SAUD SAuA,,suAA) (28)
Here, we use a conditional independence property proven in Lemma E.10
Lemma E.7. The TV-distance between the next-step expected empirical distribution functions is bounded by the TV-distance between the existing empirical distribution functions.
TV Ey B
Falg E. 15 (1
S TVV(F=a; )
Proof. From the definition of total variation distance, we have:
TV Eg Ex suai 106 |To (e Fag Ey' Eas 1t, wwwaa Firs)
Σ Eg Egg 1s, ( (1, Fag (x)
zES,
Ey
(z)
Σ
Σ
( Sy, ag,
81 oz)
Σ
ag. 0z)
k
ZES;
ieA
iEA'
Σ
k Σ Σ
TE 8y ag. 8s, 0z) 1 {8,=8))
ZES
drEAA
iEA
3E
Σ E Σ
Ia Sg, Sy a:) (2:)))
AEEA S:ES iEA
aalss 8n agi's I
2
ZES,
arE.A; S,ES; TEA
3
Jr (als'' 89r ags's
a.Ed SES.
29

---

The second equality uses Lemma E.9, The third equality uses the property that each local agent can only have one state/action pair, and the fourth equality vectorizes the indicator variables. Then,
TV
E (Bsscarlee le (euaaa 5o agg a Aaus Pola Besuar (e
Falss
< 2
Σ
Σ
T1 sg. agr
(8:=0)
Σ
(zllog
8g. Ugz (9
#ESi d.EAA sEE
iEA
NEA
1
Σ
Σ
[1(11s/ 8g. ag. )
1
Σ
J1 8g. ag:
2
k
W
(1:=8))
ArEAi $IES
SEA
iEA
1
ΣΣ
E
Σ
(::=01)
1
Σ
[0:=6r]
|+ Sy. ag:' )112
2
K/
a:EA: 8IES,
JEA
iEA
1
Σ
E
1 L8:=81
2
k: IEA
18:88
k
a.E.A SiES
EEA
1
Σ
(1:=0))
((:=00)
2
k
Vv
(snar)ESixA) XAI
IEA
EEN
Σ
FEa (2) -
2
= FF./
The first inequality uses the triangle inequality. The second inequality and fifth equality follow from Hölder's inequality and the sum of the probabilities from the stochastic transition function J1 being equal to 1. The sixth equality uses Monell'Tonelli's theorem which applies as the total variation distance measure is bounded from above by 1. The final equality recovers the total variation distance for the variable
(s, a) E S x At across agents A and A', which proves the claim.
Next, recall the data processing incquality.
Lemma F.8 (Data Processing Inequality.). Let A and B be random variables over some domain S. Let f be some function (not necessarily deterministically) mapping from S to any codomain T. Then, every f f-divergence x satisfies
X(((A)I((B)) ( x
Remark: We show an analog of the data processing inequality. Under this lens, Lemma E.7 the data-processing relation for the TV distance in our multi-agent setting.
Saturates
Lemma E.9.
1 Σ k
E Asa 18,, (
Fig (z)
Ji ag. st, a.)
iEA
Proof. By expanding on the definition of the empirical distribution function Feg [ Eies 1(8: x),, we have:
Eg EsSus/ ~J
Fag (x)
E
1ss = x}
4 EEA
E (eauarllj-- 166 x}
T: iEA
Σ
Jz Sg. Og. Si, a:)
1: EEA
30

---

The second equality follows from the conditional independence of s from sauar from Lemma E.10 and the final equality uses the fact that the expectation of an indicator random variable is the probability distribution function of the random variable.
Lemma E.10. The distribution s' s'sunral g6 8g. dgs SAUA,, asuA is conditionally independent to the distribution s/ls'g: Sg. ag 84, as for any i AUA.
Proof. We direct the interested reader to the Bayes- Bales-Balllae theorem in Shachter 2013 for proving conditional independence. For ease of exposition, we restate the two rules in Shachter [2013] that introduce the notion of d- d-separations which implies conditional independence. Suppose have causal graph G = (V, F.) where the vertex set [p) for E a set of variables and the edge set E _ 2 denotes dependence through connectivity. Then, the two rules that establish d-separations are as follows:
1. For V, we say that z, y are d-connected if there exists path (x.....))) that can be traced without traversing pair arrows that point at the same vertex.
2. We say that æ, path (x.....y) y) that does not contain an event Z that can be traced without traversing pair of arrows that point at the same vertex.
are d-connected, conditioned on set of variables S V. if there is
x, y E V is not d-connected through any such path, then 2; y is d-separated, which implies conditional independence.
Let 7 { 8y: Og: 8t, ai) be the set of variables we condition on. Then, the below figure demon- strates the causal graph for the events of interest.
Gg
8 AAUA
g
GAAAAA
d
d'uuanp
a/
Figure 5: Causal graph to demonstrate the dependencies between variables.
1. Observe that all paths (through undirected edges) stemming from S' sAJA + SAUANA pass through 8; Z which is blocked.
2. All other paths from s Auuar to & pass through 8g U s'g E 2.
Therefore, Su and of are d-separated by Z. Hence, by Shachter 2013 8 Auu'' and s are conditionally independent.
Lemma E.11. For any joint transition probability function Ts on Sy Sy. St as E A
where A k, given by Js Sy x S.A S x Ag
x S. x A |l + [0, 1), we have:
B (a Ma
max a ofEA
C a'))
-e ( max Q6 2 a.
ege,
31

---

Proof. By expanding the expectations:
B daa
max oEA s. a'))
Σ
Σ
ag, ", ",
8' d'))
max o'
- Σ
Rbly. gr 5'2 89. ag. 80, max " "EAAy""
Q' R. d'2)
(EE,, x
=
max o E
In the second equality, the right-stochasticcty of Ts implies the right-stochasticity of J..
Further, observe that Juls'g A'4, 8g: ag. SA, [s]] s",, s'g, ags s'a as) denotes the probability of the transitions (8g: sa) (5' 5 (5", *K) with actions ag. as at each step, where the joint state evolution is governed by Jn- Thus,
Σ
Juls' s'A. ag. SA as Juls" s s'g. ag. s'y asl = Th
is" gg s'S Sg ag. 82 as!
since Ege,'' Jes, x Jels': g: S Sy. ag SA. aalJa s s'y, Og. S aal is the stochastic proba- bility function corresponding to the two-step evolution of the joint states from (sy. $1) to (s") s under actions ag. a4- This can be thought of as an analogously to the fact that a on the (i,j) 'th entry the square of 0/1 adjacency matrix of graph represents the fact that there is path of distance between vertices i and j.
Finally, the third equality recovers the definition of the expectation, with respect to the joint probability function Je.
We next show limt E (
(s Sa. og. as) (()) Qi(sg sa. ag. as) Q"
O7 (sg.
Lemma E.12. The Q function is the average value of each of the (2) sub-sampled Qi-functions.
(s)
1
Σ
QI S2 ag as) S2
1-7
AE(
Proof. We bound the differences between Q at each Bellman iteration of our approximation to Q"
Note that:
(*
(T SA, Gg. as)
DE
-s,
(sg
12
AE(T.)
+T S/o], ag)
7EE
of ("(5',a') s(=Pi(leaaa,s)))vel))
max of
ra ra Ss 02) + +7B
d)mPo((199.gg)) max { af EAR
Qi (s
(s) s's d' o'a)
AE(
Next, observe that r(ra) (8g, 5/m], ag am))
E T1, Us).
(2)
32

---

To prove this, we write:
Σ
(Tg(80) ag)
1 +
Σ
Ti ais (g)))
k
AE(2))
AE(
iEA
(R-1)
[sg ag) +
ri(s 8g)
l:(?))
n2
sE(ml
rrg Ag) n
ri(si, 0z (5) == 7/m] (1 8(v)- ag. A(n)
(E(m)
In the second equality, we reparameterized the sum to count the number of times each ( 8y) was
added for each E A. To do this, count the number of (k- - 1) other agents that could form k-tuple with agent i, and there are (n 1)) candidates from which we chooses the (A: 1) agents. In the last equality, we expanded and simplified the binomial coefficients.
So, we have that:
(s)
1
Σ
27 (sg Og. (w) aa)
sup (s,a)E8xA
S(m]
16
kk
sup (s.a)ExxA
as)
(8 S2, as) -
=7 sup (a.0)E8xA
E
max (5',aaa) a'EA
E d.Pg(bea d/
max of (s'g 2 dog a'هه eEA EAEA
QT
(E(
=Y sup E
max (ss' a'EA
(ax)
0% - s'a o'g d'2)
max
)E(2)) of o
S9 sup E & (, (sa)ESXA ((i
Q-(s'aa))=
T s's d'y d'a)
max of Ag EAp
AE(
(r(66,a))
Q 26 d's) AE(12)
SY sup (x)
We justify the first inequality by noting the general property that for positive vectors v, v' for which e 2= of which follows from the triangle inequality:
2 |10/
U
AE (m))
=
-1101loo -
AE (lw))
2 ||lloc
||01|
(E((
33

---

Thus, applying this bound recursively, we get:
(8)
AE (1))
(ss''a
sup (s' a')SSAX
AE(
=
Q'(s',d')
sup (s' (')SS
1
The first inequality follows from the y-cottacctoon property of the update procedure, and the ensuing equality follows from our bound on the maximum possible value of from Lemma Cn4 noting that Qh == O. Therefore, as T - 00,
1
(s))
(sg. + 0,
12
AE
which proves the lemma.
Corollary E.13. Since
1 Es)( O7 (sg. sA. (2)
ss. ag. as) = E A 0% (sg. Sg. as). we there-
fore get:
s lim T 8
Qs(
lim E Q Sg.
T-000
T 7
1-7
Consequently,
(= { (s.. 8s. 0
Further, we have that
()) B Q7 as)) 0,
since (7 SA, ag. as) & (s.a).
Lemma E.14. The absolute difference between the expected maximums between Qs and Qu is atmost the maximum of the absolute difference between Qs and Qv, where the expectations are taken over any joint distributions of states J. and the maximums are taken over the actions.
B J-J (tt.a//aa
max L AEEEA,
O7 s's d'a)
(E' s'A og d'ar)
max of d'E
<
max of EA الa'l
E
QT (6 8 d's d'a)
Proof. Denote:
ay 0'. arg max of EAp. (s'g F d's)
a'a EAt
( Fr dg.
9x 02 arg max
C.g..
E.A!
34

---

We extend d to Lg by letting a be the corresponding A \ A variables from "y in A 1AA For the remainder of this proof, we adopt the shorthand E, Egg Auay refer to Eigg Aua Jaaaaaraaaaaa ( "aua)" Then, if E B max EAn Eaf (5 Fzg. ag))
Begi Auua max of EAA (s,, Fely. a/) > O, we have:
max Beg Beg of ",EA
0% dg)) Egga max oGEAR""
O Q (5'g Fz.,
Befidaus o (5 8 og a3) - BB,, (o &as
(2) (2))
I Beg ( S'' og aa)) B (T' S'sr og az))
E Began Suar of (5'g s'' dg: d's) Eagin' Ch (6 (6gs s'r d's))
max of E.g. "AuArEA|AUA) (Aud")
We observe that if the opposite inequality holds (i.e., Bagi max e' EAt Q (6 s'' aly, d's
B max,, E. EAp Q (s/g s'x., dg- a'x.) 0), analogous argument by replacing ag with ag and a' with á yields an identical bound.
Lemma E.15. Suppose z, 2 1. Consider functions! 1' θ1 x O₂ x... .....x O2 x O + R and I" 0 x 02 x... Oz 0 IR, where II...., O2 and 0 "..... Gzz are finite sets. Consider probability distribution function μ.e for i [z] and lée, for E [=]]. Then:
E8, ~ max 6-
0,,0" - E 01 Orm
max #' Ee.
I 0*)
8
0 o
< max E
Eg, Eeinue, [(0.....,0,... 0- E Ormple 0y, 8
0
Proof. Let 0" = arg ca T(0),...,0,,5 and 0- = ga (0,,,...0,,,,)))
Eo Eo, .. max
0r) E., mwee mm da max [' ,,,, 0*)
0, then:
Eg 1 6-E6"
- E e empple --
max
10(1 07)
0 Bamiitaa
Es, -ue, 8
1 ((, - Bimmles @
I'(0)...,004.. 02,
S Eoroue
00,,...,0,,6"" E gimple
0g 0gnjusx
0, o
< max 8" E
Eor~ee r(0 0,, 0²) 0 o
T'(0,....,0,,00 02)
0g 0
Here, we replace each 4* with the maximizers of their corresponding terms, and upper bound them by the maximizer of the larger term. Next, we replace 6 in both expressions with the maximizer choice 6* from O", and further bound the expression by its absolute value.
Ee 8. upe ce 1'O1..... 0z 0*) -EE, -w'eg (ume maxg co- I' 0000,,,,,,,,000 0*)
negative, then an analogous argument that replaces 0r with 0 yields the same result.
35

---

F Bounding Total Variation Distance
As A n,, we prove that the total variation (TV) distance between the empirical distribution of Za and 2[n] goes 0. Here, recall that 2, E St Ar. and 2n {2; E }} for A E ((n) Before bounding the total variation distance between F=A. and F we first introduce Lemma C.5 of Anand and Qu (024) which can be viewed as a generalization of the Dvoretzky-Kiete Kiefer-Wolfowite concentration inequality, for sampling without replacement. We first make important remark.
Remark F.1. First, observe that if A is an independent random variable uniformly supported on (2)), then 8Λ and da are also independent random variables uniformly supported on the global state (*I=l) and the global action (* To see this, let 1/1 : [m]] + Si where 4/1 (1) = 8; and &1 [m] - Ai where (i) a, This naturally extends to 4/a [m]* + St. where vhy (f....... ic) = (Si,...... St.) and & [n]]* + Af, where Ex (ii........ (4. = (ai...... a,,) for all l [n]. Then, the independence of A implies the independence of the generated r-algebra. Further, 4/s and & (which are Lebesgue measurable function of o-algebra) are sub-algebras, implying that 8 and must also be independent random variables.
For reference, we present the multidimenssioal Dvoretzky-Kiefer Wweffrr-Wlffoiiz (DKW) inequality
(Dvoretzky et al. [956], Massart [990]] Naaman [021]) which bounds the difference between an empirical distribution function for a set BA and Bin) when each element of A for | = is sampled
uniformly at random from [n]] with replacement.
Theorem F2 dimeni-di Dvoretzky-Kieffe Wolffoitt (DFW) inequality (Dvoretzky et al.
1956. Naaman 2021)). Suppose B C Bdd and > O. If S [n] sampled uniformly with replacement, then
Pr
sup #EB
Σ
1[B,=x]] -
Σ 1=1
1(B: = x}
<< 2 1 11-((n + 1)e -1
Lemma C.5 of Anand and Qu
2024
generalizes the DKW inequality for sampling without replace-
ment:
Lemma F.3 (Sampling without replacement analogue of the DKW inequality, Lemma C.5 in Anand
and Qu 2024)). Consider a finite population X (x1,..., ..,) E BY where By is a finite set. Let
A
n be random sample of size k chosen uniformly and without replacement. Then, for all
x
E
B₁
Pr
sup .EB
1
Σ 1[
= x)
1 71
Σ
x}
2 1 2
A
iE(m]
3kno? KTI,
Lemma F4, With probability atleast 1 - 2|
(F's FaSH)) S
Proof.
Recall that = (81, E S A₁. From Lemma
substituting B, 2q yields:
Skar2 2 - 2/2//e
Pr
sup 2
(2)( Fi (2)) 2c
R
Kkp22 11 - 2|Si||Atle
which yields the proof.
We now present an alternate bound for the total variation distance, where the distance actually goes to 0 as | + n. For this, we use the fact that the total variation distance between two product distributions is subadditive.
Lemma F.5 (Lemma 1.8.1 of Ghosal and van der Vaart 2017]. Subadditivity of TV distance for Product Distributions). Let P and Q be product distributions over some domain S. Let ai,... Odd be the marginal distributions of P and Bı,..., Bog be the marginal distributions of Q. Then,
d
|P-QI S
||as Bill
36

---

Lemma F.6 (KL-divergence decays too slowly).
Y
Proof. By the symmetry of the total variation distance metric, we have that
(F F=a) = (V= Fajm))-
From the Bretagnolle- incquality Tsybakov 2008 we have that
TV(f.9) V1 Pxu(f)l9),
Here, DKL. (gllg) is the Kullback-Leible (KL) divergence metric between probability distributions f and g over the sample space, which we denote by X' and is given by
f(x)
DkL(fll)) = Σ f(z)
(29)
g(z)
ZEN
Thus, from Equation
29
12 Eies 1/2 =
(F (ma
Σ
1 = 2}
In
A
A Eie(m] 1(z) =
iEA
Σ #E21
Σ
((==2)
In A
A
VEA
Eies 1(z = =}
+
Σ 1 1/2s 2}
In
Ejenn 1(z =}
ZEZ
iEA
n
1
Σ
Σ
1f24 = =2) )
ΣiEs 1 2)
A
A
Eie(n) 1iz = }}
ZEZ
AiEA
< n2
In
In the third line, we note that Σ3EZ, EiEs 1 =] = = must have some state/action pair contained in 2, In the last line, we note that ΣiEA 1(2; = 2} S 1 (2; = =}. For all = E 2,, and thus the summation of logarithmic terms in the third line is negative.
since each local agent contained in A
Eiejol
Finally, using this bound in the Tretagnolle-Hubee inequality yields the lemma.
Corollary F.7. From Lemma F.6 setting A [ni] also recovers TV(Fza: FF(,)) =
Theorem F8, With probability atleast 1 - for E 1)2
In 2|S Ail
+1
Qi(5gs agg ag: Pas) - (8gr Pen.y agg F Fams)
||r(( -loo
1 7
8kn
Proof. From combining the total variation distance bound in Lemma F.4 and the Lipschitz continuity
bound in Theorem E.3 with Ein < 1- for E (0, 1), we have:
26
Pr (sg. FSA Og, Fas) - (8g Fap.) ag. Fagm)) )1 y- -Ime(s)))le 2 21-2|S|||A|(
KTT
Then, reparameterizing 1 -|
Sknr? -+I into - 5 to get
n-k+1 In (2)St(IAA) 8km
gives
that with probability at least 1 - 8,
In ||
k (rr((s))laa
Qi(s Feg ag. Fas) Qn F Farmy 0g Fam)) proving the claim.
5
8km
37

---

G Using the Performance Difference Lemma
In general, convergence analysis requires the guarantee that a stationary optimal policy exists. Fortunately, when working with the empirical distribution function, the existence of a stationary optimal policy is guaranteed when the state/action spaces are finite or countably infinite. However, lifting the knowledge of states onto the continuous empirical distribution function space. and designing a policy on the lifted space still analytically challenging. To cireumvent this, Gu et al. [202]] creates lifted e-nets and does kernel regression to obtain convergence guarantees. Moreover, our result has a similar flavor to MDPs with dynamic exogenous inputs from learning theory, (Dietterich) et al., 2018 Foster et al. 2022 Anand and Qu 2024], wherein our subsampling algorithm treats each sampled state as an endogenous state.
Here, our analytic approach bears a stark difference, wherein we analyze the sampled structure of the mean-field empirical distribution function, rather than studying the structure of the lifted space. For this, we leverage the classical Performance Difference Lemma, which we restate below for completeness.
Lemma G.1 (Performance Difference Lemma, Kakade and Langford 2002 Given policies TT, n2. with corresponding value functions V VT2:
(*) - (s) (s) 1-7
E d' d'mm(((1s")
Here, AT (s', a') VT (s') and d (s') (1 En hh 7 [s'ss] where Pr. ss) is the probability of m reaching state s' at time step starting from state s.
We denote our learned policy Tk.m where:
Re TR.m (8g: ((m)) (TT2,s ($g. 8m]); 1.mma((pp 8(n))s -. T.m (5g ((m)) E P(Ag) x P(Ar)"
where Tkmm (8o, ((m]) = # #2 ($g, Su: FeA..) is the global agent's action and Tk.m f.est (1g,))n) ==
kim (Sgs Sy: Fos,) is the action of the i'th local agent. Here, A is random variable supported on (ill)) is random variable uniformly distributed on [m],, and A is random variable uniformly distributed on [n]] \ u. Then, denote the optimal policy π²" given by
T" (s) = (#) Mp)), कं (sg: Sla)...., (*g, ((m)) E P(Ag) P(Ai)",
where (sg. (mn) the global agent's action, and n. (8,, 8(n)) == (' 81; Fox,) is the action of the i'th local agent. Next, in order to compare the difference in the performance of (s) and Tk.m (sy. siw)), we define the value function of policy rewards, (denoted by V*) as follows:
be the
dddicouuteed
Definition G.2. The value function V S + R of given policy म, for S = S, x ST is:
Dc
(*((s = (a(t)=
Σ
(30)
Theorem G.3. For the optimal policy n" and the learned policy est Thr for any state 50 E S, we have:
y" (s0) - VaE (5o) 5 (1 72
k
2|
+ 2 + (1 71 / Aglk
2r
2nk
8
Proof. Applying the performance difference lemma to the policies gives us:
vx (so) aa (so)
E
eat
Bawree k.m (-1a) (-1a) (s) (s,a))
gruda
E mpst
(1y (s,a') - Ennape (4s Q (s.
1
E
Q (s, - Eartge (1,) (ssaa
goude
gost
k.m
38

---

Next, by the law of total expectation,
B Bawxet kim
(s)
(-1a)
E Σ
(s,
eest RRmm (8gs Poalor #2at (8gg 81, Pa b....>.... .. kk (8gr 8n, Psam))
AE( A A"
A'E(E-1) k-1)
Therefore,
(8, - Bownet (s),
Σ Σ
" (*s(s
(k) (k-1)"
A ArE (1uly) (
(
((
(s, nest (sg: Fea))r
) Thim ($gs 81, F. (=2)).....
, (Sgs Sny Fe
gost
Therefore, by grouping the equations above, we have:
V" (8o) - V (sp)
1 E yoot B Banaes (11)
Σ
Σ EE|D
Q" (ss
onddo
k.m
AE (
('E(lll)) ViE(n]
((())
k-11
Just (8g: 8i, Fages n (8)g: (TT(s)
1
gest Seet ($gr St, Fagt
*km (8g. Fos Paa)g { (8g. ()
K-
sE|n]
(8, # ( (8g, ( (8g. 85, Faa })smm)))
Lemma G.4shows
shows a uniform bound on
gost (. $1 Feg. Fegi)..... gest (sg. 8ns Fsga )) Q" TT" (+1s)) - Q" (s, # (sg. Fea)g,
(independent of A Vi [m)), allowing the sums and the counts in the denominator will cancel out. Observe that kmmm S A and π²" S + A are deterministic functions. Therefore, denote n² (s). Then, from Lemma G.6
E 1 anddan
Eawaee me (:10)
Σ
Σ
Σ
Σ (x(
n (F-1)) (TE(WN)
(E( (lE((ol))
(E(n)
Q (Sgs S4, Feger xt (5)gs {a (T)
Σ
Σ
(igg + (8 Fe )ns # (8g. F Faj )mn)
and
AE((
A' A.;
XE (m)
A ('E((
kum (Sgr Sis F Foges (5)gs (ar (T)(())
F
+
A|
(1 71- 73 Ag 1k1
F
5
In
+ ck.m +
(1 7
8nk
8
39

---

Similarly, from Corollary G.7
we have that
E
Σ
Σ
Q (8g. 86, Fegi
7
soidao
AE ALE (()))
(c-1)
n
est
(8g: s))g: kmmm (8y: 8y: Fs Pags )){(()))))))))) (8, gest "kmm
(8g) #2)g: (Tkim (5g:
(8g: 8y, Foas )
n le
+
2|5 Arl
Agg Agl1
In
ck.m (I (1-
7)
Snkk
Hence, combining the above inequalities, we get:
V" (so) - VT (so) - (1 7)
27
k
In
||
+ 2cR,m +
(1 (1- |Ag AggktAdl
2r
8nk
8
which yields the claim. We defer parameter optimization Lemma G.8
Lemma G.4 (Uniform Bound on Q" with different actions). For all 8 E E, (1x) and A E
(nlv) for E [n], we have:
(s, (-1s)) - (s, Tk.m (Sg, Fg (.kmmsg. 8,, Fo Die(ml)
Q x (s)) Quet (8 Sis F
T" (5) f (s)s
72
iE(m]
Quenn (8g, St, Fagir K.mm (8g Fes )s ( ($ ممددة )
+
Q" agen (8 32)a ( (8 8j. Fa s sE(n
Proof.
Observe that
(* - (s, gest (s Faa )g faget ( (8g. 8i, Fege Pie(m)
<
Qoet (Sgr Sú, Pager # (8gr Foalor mpom (8,, 8i, Foge ); & (9g. 85, Pays )ess)
kE(m)
Qest (Sg. Sis Fage #k.m (9g. Faa) )g geat (sg 81 Fsge); fa (8g. 8j, Fssi }BEB))
Qeet (sy, Sis F. Fog. xt (s) (s)e, (m) (s),
(E(m)
Quet (3 Sis Poses xt (5)g, x (s) {-r (s)))ea))
vE[n]
(8, (s))
Σ
Qest (809 8t, Fager x (5) (8) (a (s)(b)
sE(m]
1
Qust (S9, Sis Fs #pm (89r Fsa)or ) g (sg: 83, Fas ) )ESH))))
+
n2
AE [m]
Q² (s, gest Thim(s (sy, Fea ) { (n 8J, Faas Bsee
(s, xt" (s))
Qret Quet (8gs Sis Feaer xt" (5)gs (x (s)1bSE((
17
40

---

1
@ (8g, 8is F Foal9r {# (s $3 (g,a)) (EE(()))))
"k.
72
<E(N]
(s, Ahe k (8g; 82)g: R (8g. 8J F (aa,))) )Em
which proves the claim.
Lemma G.5. s Sg x Sp For each j E [n], suppose we are given T-length sequences of random variables {Ai..... jell distributed uniformly the support (Iil)). Further, suppose we are given fixed sequence 81,..., ÖT, where each 8, (0, for E [T]. Let
k In 2|Si||Ai1
Tk.t 1-
8kn
Then, for each action a (Ag. a(n)) = T² (s), for t E [T] and j E [m], define deviation events
B. 2 such that:
0g.0 ,.0 11=0000000 (89)88) Fanny aj ag) Qret (8gs 8jz P= aj ay) 2x,t |1r(( + 6k.m
B.
(31)
For i E (T), we define bad-events B, (which is union over each deviation event):
B B-UU U U
B. e
jE(n] EA, ".AAEEA
Next, denote = U B, Then, the probability that no bad event By occurs is:
T
Pr B = Pr[ 2 1 |A, 1A
8
Proof.
(8 8j. Famiis ag. aa ag)
Quat (8g. 85: F= Ag. az)l
Q 8y, : a,) (8 85, Fa Paxg:00:
ag. ag)
+ Qi(3n 8j, Fe ag ag a,) Quet 83, Fesq ag ai)
(5g 83 ag a,) (% 8j. Feag ag. ag ag)
Q2( Fz Faz ag. aj) Quet (8g, 8j, Fasq agp ai)
(sg. Sy F v a,) Q% Sy, Fsag" ag. ag) ck.m
The first inequality above follows from the triangle inequality, and the second inequality
Q% Sj. Fz, F= ag. a,)
Quet ($g. Sz: Fz, xxa ag. ag.ay)
Q 83, 24 ag az)
Qust kym (Sy, 88, F= ags aj)
S kkm
where the eamm follows from Lemma 4.3 From Theorem F.8 we have that with probability at least 1 dc,
(5(g 8j, F Famas ag. 0,) - Q2(5 $j, Fs ag. oz)
S &
|| In
n nn
( loo
6,
8kn
41

---

So, event B, ;.4! occurs with probability atmost 8,.
Here, observe that if we union bound across all the events parameterized by the empirical distributions of ug. 3 Ag x A given by f this also forms a covering of the choice of variables Fs ot by
agents j E [m], and therefore across all choices of A....., AF (subject to the permutation invariance of local agents) for fixed t.
Thus, from the union bound, we get:
Pr[B.] S Σ Σ
Pr[B,
S Ay Pr[B, 1
4, G,EA, Fea, (Ma(AA)
Applying the union bound again proves the lemma:
T
T
Pr[ 2 1 Σ
21
8z
which proves the claim.
Lemma G.6. For any arbitrary distribution 'D of states S Sg x for any A E (k-1) for
i [n]] and for å (0, 1] we have:
E
Σ
Σ
Σ
1
Σ (s
(6)
(m-1)n
AE((T) (1E(
A (mll))
iE[n]
Qeat
k.m (899 8i, Fe Feser x (8) la (o)sbseta))))
n
2|S ||A ||A|
p 6k,m + I- 14 Agglk-d118
5
In
1
8nk
5
Proof. By the linearity of expectations, observe that:
EgnD
Σ
Σ
Σ
n (x, (s))
AE(( (M!))
(
Qust
Qh (8gs Si,
(s) ( (s)g: (T)
Σ
Σ
Σ
ENN (*((s
(
Ae((")) A ('E((!l))
("E(T!N))
(k-
iE(n]
jest (3gr Sis Fsgi, x'' (3)g ( (5), (3))
Let
1
In ||
8nk
8
Then, define the indicator function I [m] X S I(i, s. k)
(0, 1] - (0, 1y:
(0((, - Quen ($g. si, F. x'' (s)g. f (s)) ||(((s)) .)le
1-7 Dx.5 + eam }
The expected difference between (5 n (s')) and Q Qu St, Festr x ()) ( (T) is bounded as follows:
EAND (''s', T (s')) - Qust ($g, Si, Fages xT" (s)g: { (s)
[(i, s, k. 6) Q' T' (s')) Qeat ($g. St, F Fager x' (s) f (s), (s) = -EWD
(1 (1- [1-I(ii,a) 8i, 8)) Q (s', n (s')) - Quet (8g: 8i, 7) ( (s), (s)))
+ F EAND
42

---

Here, we have used the general property for a random variable X and constant that E[X] B|x1[X v c}] + [[ 1 - x]) Then,
ENDD ( -t (s')) - 2k (sg) S1,4 ot (s)g: (s)),a))
k+1
||
In
Ck.m
1- ENWDDI(S', k,))))
8nk
n
K +
||
Ag Agl
In
ckem +
8nk
1-
1
n k
||
In
ckkm +
1-7 Ag Agl
8nk
For the first term the first inequality, we use s c. For the second term, we trivially bound Q" (s', "is',T" (s')) - Q%(5g &t,",, x (s)g. x (s) by the maximum value Q" can take, which is I-y by Lemma C.4 In the second inequality, we use the fact that the expectation of an indicator function is the conditional probability of the underlying event. The second inequality follows from Lemma G.S
S
Since this is uniform bound that is independent of A for j E [m]] and i E [m]] we have:
1/n
Σ
E
(s)) Q (sg 8t, Fe Feger TT (8) for (5))baa)))
AE((.)
(E
A (lel))))))
k +
||
F | Agglk
Ek,m
8rck:
1 1-7
This proves the claim.
Corollary G.7. Changing the notation of the policy Tk in the proofs of Lemmas G.5 and G.6 gest
such that a ~ R.m then yields that:
E
Σ
Σ
(s,
Qb (S:: 8i, Pa Og. an.
(E!! A
A". Peeeeeeeea
(e
n- (2)
(--1)
iE|ml
n
n
k
+
In
Atl |
2|S
+ ckmm + 1- (Agl LAl18
Snk
8
Lemma G.8 (Optimizing Parameters). With probability at least 100
v (50) V (60) S Ô
VK
Proof. Setting 8 = (1-7)²
in the bound for the optimality gap in Theorem G.3 gives:
2PelAA, 1kl
(=((3)) - v (so)
5
F
71
In
||
+ 2 +
2r
(1 7)2
2nk
8
7)2
F
k + 1
1
+ 2
(1 7)2
2nk
- (1
Setting = = 10 for any c > 0 recovers a decaying optimality gap of the order
F
k:
| |
1
V (8o) / (80) 5
In
+ 2
(1 11-99 7)2
2nk
(1 72
10
43

---

Finally, using the probabilistic bound of ck.m S <0 {+)) from Lemma G. G.10 yields that with probability at least 1
vk
100
V" (s0) - Văr.m (50) 5
vk 8
which proves the claim.
G.1 Bounding the Bellman Error
This section is devoted to the proof of Lemma 4.3
Theorem G.9 (Theorem of of et al. (2022) ) Ifm is the number of samples the Bellman
update, there exists universal constant 0 < co < 2 and a Bellman noise 0 < ck.m 1-7 such that
Th Quan + = 1| Qu S Ek.m
where Ck.m satisfies
F. Leoner log²
|S|[A]
log ( (1-2)2
(32)
(1 2 k.m
with probability at least for any E 1). Here, Leover stands for the cover time, which is the time taken for the trajectory to visit all state state-action pairs at least once. Formally,
min {
teover
min (BU.
PB 0o) 25
(33)
where B, denotes the event that all (s, a) E S A have been visited least once between time 0 and time I, and P(B,, so, ao) denotes the probability of B, conditioned on the initial state (So, Go).
Lemma G.10. If T O(T)S, (
2 log i T (i))))
SUB-SAMPLE-MFQ: Learning runs in time
while accruing a Bellman noise Ckm S Õ(1/VK)
with probability at least 1.
Proof. We first prove that 1T² @i1lx -
vk'
For this, it suffices to show 7" f
I- < 1
7" PuF
Then, - (1->) -1->)
again suffices to show e (1 -1- <
1-1
Taking logarithms, we have
FVR
exp(-T(1 - -7) 1-7
ivT 1-7
-T(1 7) < log
ivk
iV
2 1
log
1-7
Since T =
2
log
iv log
the condition holds and -/ - Qi S
1 Then,
1-
1-7
1-7'
Vi'
rearranging Equation
322 and incorporating the convergence error of the Q funfciiio one has that
with probability at least
P.
+ (1 7)2 log S |
k 2r
CR.m
log (I (1-
(34)
V
Then, using the naive bound foover (since we doing offline learning), we have
foover - || (
Substituting this in Equation 34 yields that with probability 1 P.
kv
27 S A,
|
S (Sgl|Ag11Ail1s log (1 -
6k,m <
+
log
(35)
VT
2255 m
44

---

Therefore, letting
100 setting
m 2 (Ag || | ||Ail
1
log L1000ss||AAgl|A/1 log (1 7)3
(36)
(1 - 7)
attains a Bellman error of cn.m of our learning algorithm is
I O(L/Vk) with probability at least
Finally, the runtime
100
O =
[A:))).
which is still polynomial in proving the claim.
H Generalization to Stochastic Rewards
Suppose
we are
given two families distributions, (9 Je,.a,
and
( XA Let R(s, a) denote stochastic reward of the form
R(s,a) (g)
ri(s oz): iE(m)
Σ
(37)
where the rewards of the global agent emerge from a distribution rg(5gg (g) ~ gs,.a,, and the rewards of the local agents ry emerge from a distribution ri(si, 8gs as) basisgar For A C [n]. let RA (s, a) be defined as:
Ra(s,a) = (g($9; + Σ ri(s Sgs as)
(38)
iEA
make some standard assumptions boundedness on Gayia and Eassaaa Assumption H.1. Define
g U
supp (gsp.a))
(s (n),, XA,
C =
U
supp (Cessga))
(E (SSS,
where for any distribution D, supp(D) is the support (set of all random variables D that can be sam- pled with probability strictly larger than of D. Then, let & sup (9) sup (Z) ق inf (9). and Č inf (C). We assume that & co, C < 00, -c, C -oo, and that g, L, E are all known in advance.
Definition H.2. Let the randomized empirical adapted Bellman operator be Frandom such that:
k.m.
Q km (8g. 81, FEA ag. 01) RR(s + ? Σ
max a'EA
(6 s/. F.y Payy, of (39)
éE(m
SUBSAMPLE-MFO/ Learning with Stochastic Rewards. The proposed algorithm averages = samples of the adapted randomized empirical adapted Bellman operator, Trandom and updates the Qu. function using with the average. One can show that Frandum is contraction operator with Temm
module 7. By Banach's 's fixed point theorem, T.aanom admits a unique fixed point Qrandom
45

---

Algorithm 4 SUBSAMPLE-MFQ: Learning with Stochastic Rewards
Require: A multi-agent system described in Section 2 Parameter T for the number of iterations in the initial value iteration step. Sampling parameters E [n] and m E N. Discount parameter
y (0, 1). Oracle O to sample o ~ Pg (g(:)s: ag) and s; Pi Sg. 0,) for all i [n].
1: Set Á = (2......ii ....
2: Set pk-1 = {0, k- k-1 1|
1 2
3: Set m (sg. F=g ag. 01) 0, for (sg. $1, F (1, ag) E S x M Ag x A..
4:
fort T do
5:
for (sg. F ag. a1) E Sy x S x pk- 1k-1 (2)) x Ag x A do
6:
p=
7:
for & ( do
8:
p= p+ Tranlom Q1 km (gg. 81, F2g agg a1)
9:
( 81, F'xx ag. a1) =p/=
10:
For all (8g, 81, P. PRar.) Sg x St x pk- 1 let
Aest kk (sg. 81. FRSU))
QK (8g. S1, Fzass Og. az).
arg max (Ag: JEA, XAI 1(2))
Theorem H.3 (Hoeffding's Theorem [Tybakov 2008 ) Let XI... ..... X, be independent random
variables such that S X; S b, almost surely. Then, lel Sn Xi + + Xn. Then, for all > 0,
26
PlSS, - E[S,] e] 2exp
(40)
Σ (b: a:)²
Lemma H.4. When kmm. is derived from the randomized empirical value iteration operation and applying our online subsampling execution in Algorithm
2
we gel
Pr V= (8o) - Rr.. (80) 5
2
(41)
100
Proof.
Pr - - [s
2 E
2c
< 2 exp
Σ i= 9 C 7 - Σ12
2²
2exp
E L - 9 212
Rearranging this, we get:
2
9 E 9 Z
Pr E - E[Ra a)l 5 5 Im
2 218
(42)
252
Then, setting 8 and setting = 10 + --5 I122/1 |n(2000/) gives:
100VE.
Pr E| (s, a)l 5
200k
100V
Then, applying the triangle inequality to ck.m allows to derive a probabilistic bound on the optimality gap between Qest. and Q", where the gap is increased by - and where the randomness
over the stochasticity of the rewards. Then, the optimality gap between V** and V for when the policy gest is learned using Algorithm 4 in the presence of stochastic rewards obeying Assumption H.T follows
Pr V= (so) - Fra. (8n) I
1 V
21
(43)
100
which proves the lemma.
46

---

Remark H.5. First, note that that through the naive averaging argument, the optimality gap above still decays to 0 with probability decaying 1, as k increases.
Remark H.6. This method of analysis could be strengthened by obtaining estimates of & C, G, and using methods from order statistics to bound the errors of the estimates and use the deviations between estimates to determine optimal online stopping time [Kleinberg] 2005 as is done in the online secretary problem. This, more sophisticated, argument would become an essential step in converting this to truly online learning. with stochastic approximation scheme. Furthermore, one could incorpraate srriance-basede analysis in the algorithm, where we use information derived from higher-order moments do weighted update of the Bellman update [Jin al. 2024], thereby taking advantage of the skewedness of the distribution, and allowing us the freedom to assign an getimism/pessimiise score to our estimate of the reward.
I Partially Relaxing the Offline Learning assumption: Off-Policy Learning
A limitation of the planning Algorithm is that it learns Q in offline manner by assuming generative oracle access to the transition functions Pg, Pr, and reward function r(..). ). In certain realistic RL applications, such generative oracle might not exist, and it is more desirable to perform off-policy learning where the agent continues to learn in an offline manner but from historical data Fujimoto et al. [2019]. In this setting, the agents learn the target policy #t using data generated by different behavior policy (the strategy it uses to explore the environment). There is a significant body of work on the theoretical guarantees in off- offlpo learning Chen et al. 2001bb. Chen and Maguluri 2022b). Chen et al. 2021a 2025
In fact, these previous results are amenable to transforming guarantees about offline Q-learning to off-policy Q-learning, at the cost of log Js, |S 6 |A factors the runtime. Therefore, this section is devoted to showing that our previous result satisfy the assumptions of transforming offline Q-learning to off- off-policy Q-learning for the subsampled QA Qu-function, and we further show that, in expectation, can maintain the decaying optimality gap of ((1/VR) of the learned policy Ta, where the randomness is over the heuristic exploration policy Tb.
The off-policy -eelennngng algorithm is an iterative algorithm to estimate the optimal Q funceion as follows: first, a sample trajectory {(5g. $a, 2g aa)} }} is collected using a suitable behavior policy Tk.b- For simplicity of notation, let S (sg: 8T) and A (ag: a사). Then, initialize Q% [8,1|///1
and let > 0 be determined later. For each 0 and state-action pair (Sa, AA) that updated to S/A the iterate (S, As) is updated by
( Aa) = - @S Aa) - at As) +7 max
Q (1(55.11)) (44) A.AAAAA
Note that the update in Equation 44 does not include expectation and can be computed in single trajectory via historical data. We make the following ergodicity assumption:
Assumption I.1.
The behavior policy nu satisfies To (AAA|SA) > 0 for all (S3.AA) E S, x St x
Ag x AA and the Markov chain Msa = (5(²) J120 induced by n, is irreducible and aperiodic with stationary distribution y and mixing time La (a() = min (t 2 0 max max55es, S.ES, x || (SA.))
(r)ll < 0). There are many heuristics of such behavior policies (Fujimoto al. 2019
Theorem L.2. Let Te be the policy learned through off policy Qu-learning, Then, under Assump-
tion I.1 we have that that with probability at least 100
F
k +
40F S/|| 1
E (so) V** (s0)) -
In
22p.m
(1- 7)2
2nk
7)
10VK
O(1/V/)..
where the randomness in the expectation is over the stochasticity of the exploration policy nt-
47

---

Proposition I.3. Recall that the the following are mree
[Qu(Fss FAA) - (F P
-| -saa for Joraayyyaay...a.aa..aa.. Sa, S
Sg Af and As Ag Af by Theorem E.3
2. 12 $ 1-y by Lemma C.4
3. (S,, As) (S Ab)I s - ( by Lemma C.6
4. The Markov chain Mg enjoys rapid mixing property from Assumption I.I.
Then, by treating the single trajectory update the Qx-function noisy addition to the expected update from the ideal Bellman operator, [Cen et al. [202bb] uses Markovian stochastic approximation to bound O
@x
We restate their result:
b02 adapted to our setting). Suppose = for all Theorem 1.4 (Theorem 3.1 in Chen et al.
t 2 O, where chosen such that ala (Msa) I cQ.0 log |s,
(1-6,)²
Ag1A51' where cq.0 is a numerical
constant. Then, under Proposition I.3 for all t La (MMs)) we have
ElI @illoll S CQ.1 (1- (1 (1-7)) 7)xx
(Maa(Maa)
log
cQQ2
ala (Msa);
(1-7)² 7)2
where CQ.1 -Q.1=34 3( 1)2, CQ2 = 912e( I-y 1)2, and where the randomness in the expectation
over the randomness of the stochasticity of the behaviorlexploration policy Th.
Corollary L,5 (Corollary 3.2 in Chenet 2021b adapted to our setting). To make Blll -iill=0 S
100 for
need
10000k log (100
S [ A, Ail log SS, S
t Ō
(1 7
With this sample complexity, by the triangle inequality we also recover an expected-value analog of Theorem F8 Corollary I.6. For 5 E (0, with probability at least 1 - 5, we have
In 2|5.||AA1
|
n 1n-k
(sQ2 aeg:ay: Fas) - Qn(yy: Fong )
||
1-7
8kn
where the randomness in the expectation is over the stochasticity of the exploration policy Th.
In turn, following the argument in the proof of Theorem G it is straightforward to verify that this leads to a result on the expected performance difference using off-policy learning: Corollary 1.7. With probability at least 100c
EIV" (8o) (so)) S
n
+ 1
In
40F A////|||i||A RIA++
+ 2
(1 7)2 = -(1/Vk)
2nk
(1 7)2
10
where the randomness in the expectation is over the stochasticity of the exploration policy ni.
J Extension to Continuous State/Action Spaces
Multi-agent settings where each agent handles a continuous state and action space find many applica- tions in optimization, control, and synchronization.
Example J.1 (Quadcopter Swarm Drone [Preiss et al., 2017 Consider a system of drones with global controller, where each drone has to chase the controller, and the controller is designed to follow a bounded trajectory. Here, the state of each local agent E [n] is its position and velocity in the bounded region, and the state of the global agent g is signal on its position and direction. The action of each local agent is a velocity vector at E Ai C TR3 which a bounded subset RR3, and the action of the global agent is vector ag Ay 122 which is bounded subset of R??
48

---

Hence, this section is devoted to extending our algorithm and theoretical results to the case where the state and action spaces can be continuous (and therefore have infinite cardinality).
For a measurable space (S, 13), where B a o-algebra on S, let R denote the set of all real-valued B-measurable functions S. Let (X, d) be metrie space, where X is set and d a metric on X. set S S X is dense X if every element of X is either in S or a limit point of S. A set is nowhere dense in X if the interior of its closure in X is empty. A set S C X is of Baire first category if S is a union of countably many nowhere dense sets. A set S C X is of Baire second category if X 5 is of first category.
Preliminaries.
Theorem J.2 (Baire Category Theorem (Jin et al., 2020 ). Let (X, d) be a complete metric space. Then any countable intersection of dense open subsets of X is dense.
Definition J.3 (Linear MDP), MSP(S, A, IP, r) is linear MDP with feature map á @ S:Sx x A -+ R there exist d unknown (signed) measures μ (1²) ,...,,"") over S and vector E Rd such that for any (s, a) E S x A, we have
P(||s, a) (0(s, a), (()));
r(s,a) (Ø(s, a). 0)
Assumption J.4 (Bounded features). Without loss of generality, we assume boundedness of the features: [| a)ll S 1, for ().a) E S x and max (I)( [|01] Vd.
We motivate our analysis by reviewing representation learning in RL via spectral decompositions. For instance, if P(s'ls s/|s, a) admits linear decomposition in terms of some spectral features 6(s, a) and (ss'), then the Q(s, a)- ff-function can be linearly represented in terms of the spectral features 6(s, a).
Then, through a reduction from Ren et al. (2024) that uses function approximation to learn the spectral features on for Qs, we derive a performance guarantee for the learned policy Th where the optimality gap decays with
Theorem J.5. When oh is derived from the spectral features Φx learned in Qu, and M is the mumber of samples used in the function approximation, then
| log 2k
2yr
201
Pr
(8) - "h (6) S 5
(1- l(
VI
VM
50%
100V
We assume the system is linear MDP, where S, and S are infinite compact sets. By reduction from Ren et al. (2024) and using function approximation to learn the spectral features Φb for QR. we derive a performance guarantee for the learned policy gे where the optimality gap decays with k. Assumption J.6. Suppose Sy C RR*,, S C RR", Ag C A C IR are bounded compact sets. From the Baire category theorem, the underlying field IR can be replaced to any set of Baire first category, which satisfies the property that there exists a dense open subset. In particular, replace Assumption 2.I with a boundedness assumption.
Multi-agent settings where each agent handles continuous state/action space find many applications in optimization, control, and synchronization.
Lemma J.7 (Proposition 2.3 in Jin al.
[2020). ). For any linear MDP, for any policy æ, there exist weights ( (w") such that for any (8, a) E x A, we have Q" (s, a) = (ø(s, a). w*)
Lemma J.8 (Proposition A. in Jin et al. (2020). ). For any linear MDP, for any (s, a) E S A. and for any measurable subset B C S, we have that
(s, USS) =
((s,u) T (((B > O.
Property J.9. Suppose that there exist spectral representation (g(5)) E Rd and no((() E Rdd such that the probability transitions (5( (sg, ag) and Pi(s) 8g, a;) can be linearly decomposed by (0,Slsg.00 ag) 0g(Sg. ag) (g
Pg Pg(5,
P((s Sy, a.) = di(s, Sy. a.) (n(ss)
for some features (y((gg (g) E d and (1 8g, ) E Rd. Then, the dynamics are amenable to the following spectral factorization, as in Ren et al. (2024).
49

---

Lemma J.10. Qx admits a linear representation.
Proof. Given the factorization of the dynamics of the multi-agent system, we have:
((s'(s,a) = Ps(s'glg.ag) ag))
II
P((s 8g. az)
2=1
= (dg ag): Mg (5())
II (o) Sg. a...
= 0y ag): Mo (5
Sy. a.), (
= (s, ((
Similarly, for any A S [n]] where /A k; the subsystem consisting of k local agents A has subsystem dynamics given by
P(s'A 8n S Sgs ag as) = (0,( S4, ag. a2), (sn())))
Therefore, Qs admits the linear representation:
2ht (sg, F2a:99) = rg(8sg ag) +
Σ
ri(si, 8g. ai) + +B max Q (5'g Fr'a ay
iEA
= [ ag) + Σ
3p + (PVVM(ss Fes ag))
iea
rs(s,a)
= (8 S2, ag. a2)
7 TSa na (*( (s/)dda))
proving the claim.
Therefore, 6 serves as a good representation for the Qu-function making the problem amenable to the classic linear functional approximation algorithms, consisting of feature generation and policy gradients.
In feature generation [Ren et al. 2024 we generate the appropriate features o, comprising of the local reward functions and the spectral features coming from the factorization of the dynamics. In applying the policy gradient, we perform gradient step to update the local policy weights 0; and update the new policy.
For this, we update the weight w via the TD(0) target remi-gradien method (with step size a)), to get
W 1 w. a(ra a²) + 1T w. 5x(s5a) w.)
(45)
Definition J.11. Let the complete feature map be denoted by : S x d - IR and let the subsampled feature map be denoted by de Sg x Sk x d E R, where we let
(1) (2)
E
(46)
(1,, x (
Here, the system's stage rewards are given by
[r(1) r(S)] R
and
Fk = r (1S, x | e RlSix 1(5))
where d is a www-dimensional embedding we wish to learn.
50

---

Agnostically, the goal is to approximate the value function through the approximation
& (1)
V ~ &&
w E span +b))
(1 x (
This manner of updating the weights can considered via the projected Bellman equation 6.w T ( w) where II = arg min zcδ, || oll Notably, the fixed point of the the projected Bellman equation satisfies
w = (6) 0. - 1 Dr(r + y w)
where D is a diagonal matrix comprising of u's. other words, D2 diag(ei..... Mn). Then,
( (b) ) = 6% Du 7 (p
In turn, this implies
1 - 4. Dar.
Therefore, the problem is amenable to Algorithm in Ren et al. linear function approximation to learn Qk, we use result from
2024 To bound the error of using
Ren et al. 2024
Lemma J.12 (Policy Evaluation Error, Theorem 6 of Ren et al.
(024)). ). Suppose the sample size
M 2 log (4m where is the number of agents and ō E (0,1) an error parameter. Then, with
probability at least 1 - 25, the ground truth Q7 a) function and the approximated Qx-function Q (s, a) satisfies, for any (8,a) E ASXAA
E [[0 QIFA (s, (s,
2h 8
1
7
00
log
+
2ep?
VM
1-7
statistical
approximation error
where ep is the error in approximating the spectral features Øg. di.
Corollary J.13. Therefore, when Tk,m is derived from the spectral features learned in Q1 applying the triangle inequality on the Bellman noise and setting = Ep = vk yields 5
Pr yx (5o) - (5o) S (11 Vi + log (262)
1R 1
7/ 1 |
]
201
21+
VM
VTa
7
50k
100
Using || < 1 and simplitying gives
Pr F= (so) - V.a. (so) s ( log (2k²)
2 -1))
2-F Vk(1 v
201
+
V
VM
100
Remark J.14. Hence, the continuous state/action space setting, as + n and M + oc. a (sp) + a (so) = V* (so). Intuitively, as k + n, the optimality gap diminishes following the arguments in Corollary G.7 As M co, the number of samples obtained allows for more effective learning of the spectral features.
K Towards Deterministic Algorithms: Sharing Randomness
In large distributed systems, the random sampling in our communication network may be a bottleneck for "decentralized execution". In light of this, we have provided practical derandomized heuristic where the agents can share some randomness by only sampling within pre-defined fixed blocks of size.
Following Ren et al. 2024). the result easily generalizes to any positive-definit transition Kernll noise (e.g. Laplacian, Cauchy, Matémn etc.
51

---

Algorithm 5 SUB-SAMPLE-MFA, Execution with weakly shared randomness
Require: A multi-agent system described in Section 2 A distribution so the initial global state $0 = ($g. (n)) Parameter T for the number of iterations for the decision- sequence. Hyperparameter E [n]. Discount parameter ?.. Policy #k (8 SA).
1: Sample (s, (0), spm] (p)))))))))))))))))))11 (0)) 50-
2: Define groups h1..... has of agents where == [ and |h11 = |/2a 1 1| k and mod k.
3: for 0 to T" do
4: for i E [z] do
5: Let A, be uniform sample of (xrl)))) and let ag. (t)
{= (t)
Let ( (1) = majority (1 (s,((), 8., (1)1la (
6:
7:
Let sy + 1)
(t))s,()),,g(t)
8:
Let st +)) PI(-s(0)
9:
(t)), for all [n].
Get reward r(s,a) (g 0g) +/2 Eiena ri 8g)
Algorithm SUB-SSAPPE--T MFQ: Execution with strongly shared randomness
Require: A multi multi-agent agent system as described Section A distribution so on the initial global state
$g (sg. (m)) Parameter T" for the number of iterations for the decision decision-making sequence. [n]. Discount parameter y.. Policy #k,m (8y: S2).
Hyperparameter
1: Sample (0), Sps] (0)) 8g-
2: Define groups ....... , h of agents where x == [2 and [h1| = 1/2 mod k.
1 1 = k and
!hg
3: for t = to T do
4: for E 1] do
5:
Let az, (t) = h (sy (t), sh, (t))]
6: Let af, (t) k..m (sg (t), Sh, (t))lg-
7:
Let Arsidual = (x-(n-In/Aa) (n/ATR))
[n]
8:
Let an_ (t) = [ (s, Urraidnn (t)) (s) Ta/k]]
9:
Let d, (l) = [ (1) 8h, Werddual (4)]l
10:
Let ag (t) majority (fag, (t) :1 [x]))-
Let (1 1) Py (1)o,) (1), ag (1), si(l + 1) P1(-1s((), ((),)))))))))))))))))))))))))),) for all i E [n].
12:
Get reward r(s, a) (g ag) Eie(m ri (8s, ai 8g)
In this section, we propose algorithms SANDON-SUB-SAMPLE-- MFQ and SAA-SSSU-SSMMM-MMMAS-- which shares randomness between agents through various careful groupings and using shared ran- domness within each groups. By implementing these algorithms, we derive simulation results, and establish progress towards derandomizing inherently stochastic approximately-oppie
policies.
Algorithm 5 (Execution with weakly shared randomness). into arbitrary groups of size k. For each group h,, the k local agents sampled the same each iteration. The glohal agent's action is then the majority global agent action determined by each group of local agents. At each round, this requires O( n² /k: (n k)) random numbers.
The local agents are heuristically divided
Algorithm (Execution with strongly shared randomness). The local agents are randomly divided in to groups of size k. For each group, each agent uses the other agents in the group as the & - 1 other sampled states. Similarly, the global agent's 's action then the majority global agent action determined by each group of local agents. Here, at each round, this requires O( [n2 random numbers.
The probability of a bad event (the policy causing the Q-function to exceed the Lipschitz bound) scales with the O(r²)) independent random variables, which is polynomially large. Agnostically, some randomness is always needed to avoid periodic dynamics that may occur when the underlying
52

---

Markov chain is not irreducible. In this case, an adversarial reward function could be designed such that the system does not minimize the optimality gap, thereby penalizing excessive determinism.
This ties into an open problem of interest, which has been recently explored [aarsnn et al. 2024). What is the minimum amount of randomness required for SUBSAMPLE-MPQ (or general mean-field or multi-agent RL algorithms) to perform well? Can we derive theoretical result that demonstrates and balances the tradeoff between the amount of random bits and the performance of the subsampled policy when using the greedy action from the k-agent subsystem derived from Q7 We leave this problem as an exciting direction for future research.
53

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer:
[Yes]
Justification:
We provide clear and formal mathematical proofs support each claim.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize other settings.
is fine to include aspirational goals as motivation as long is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification: We explicitly discuss the limitations of results in the paper: the lack of matching lower bounds to verify if the scaling with the number of sampled agents k: is optimal in the final bound on the optimality gap of Ó(1/Vk), and that we do not provide any online regret bounds.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification. asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on a few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low images taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
54

---

3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer:
[Yes]
Justification:
We provide clear and formal mathematical proofs to support each claim.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification:
We provide a full description of the algorithms and experimental setup.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, other means that appropriate to the research performed.
also be provided via detailed
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how to reproduce that algorithm. (b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (c.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (c.g., to registered users), but it should be possible for other researchers to have some path to reproducing verifying the results.
55

---

5. Open access to data and code
Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Question:
Answer: [Yes]
Justification: Our simulations are all synthetic datasets, but the code we provide in pettps:/ggihhue com/ emiletimothy/Mean our algorithm design, sufficient to faithfully reproduce our experimental results.
Baateee---Lerraa Q-Laarning and
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.ca cc/
for more details.
While we encourage the release of code and data, we understand that this might be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https
/ lisias.ccc/ubbic/guiieeee http:/ggiieee//oeeeee
www.sibmmsssoooooooo ssioncllicy for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible supplemental material (appended the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification:
We an explicit sweep of the parameter k.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core the paper to a level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer:
[Yes]
Justification:
We provide error bars that report over the min-tma values.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by emoo bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
56

---

The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative error rates).
If error bars reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: We provide sufficient information the compute resources in Appendix B all our experiments were run on 2-code CPU server with 12GB RAM.
Guidelines:
The answer NA means that the paper does include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental rums as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't fidn't make it into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics Stttss///heurrp...ccpppb/////// ies
Answer: [Yes]
Justification: The research conducted in this work conforms, in every respect, with the NeurlPS code of ethics.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make to preserve anonymity (e.g., if there is special consid- eration due to laws or regulations their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification: This work is theoretical and foundational nature. As such, it is not tied toa ny specific applications deployments.
Guidelines:
57

---

The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g.. gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
The paper poses no such risks.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [NA]
Justification:
The paper does not use any existing assets.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset used and, possible, include a URL
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
58

---

If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com/dataseta
latasets.paperssit
has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
this information is not available online, the authors are encouraged to reach out to the asset's s creators.
13. New assets
Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Question:
Answer: [NA]
Justification: The paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/cooeemmodll as part their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL or include an anonymized zip file.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: This paper does not involve any crowd-sourcing nor any research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (TRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/teview based the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: This paper does not involve any crowd-sourcing nor any research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
59

---

Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if' applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Does the paper describe the usage of LLMs if is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, or formatting purposes and does not impact the core methodology, scientific rigorousness, originality of the research, declaration is not required.
Question:
Answer: [NA]
Justification: The core method development in this research does not involve LLMS as any important, original, non-standard components.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, non-standard components.
Please refer to our LLM policy hatt::///earrrppccc//ooeeeeeeee/ //t/////ooeeeeeccc////////..1 for what should or should not be described.
60


Reviews:
[{"review_id": "wWxLyIlYj8", "reviewer": "Reviewer_APLY", "summary": "The paper introduces SUBSAMPLE-MFQ, a novel algorithm designed for cooperative Multi-Agent Reinforcement Learning (MARL). By subsampling $k \\leq n$ agents and applying mean-field Q-learning to this reduced subset, the method achieves significant computational savings. The algorithm retains theoretical guarantees, showing that the learned policy converges to the optimal one with an optimality gap of $\\tilde{O}(1/\\sqrt{k})$, independent of the total number of agents $n$. When $k = O(\\log n)$, SUBSAMPLE-MFQ offers exponential improvements over previous methods.", "questions": "* I wonder the feasibility of design a small experiment to validate the conclusion in this paper?", "limitations": "The authors mentioned the work's limitation in the paper.", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strength:\n1. The paper provided rigorous theoretical proof for the algorithm\n2. The paper showed the given algorithm in clear details.\n\nWeakness:\n* Although this paper focuses more on the theory side, no experiments was given.", "was_revised": false, "final_justification": "", "rebuttal": "We thank reviewer APLY for their feedback on our work. \n\nWe did provide two experiments in Appendix B (page 16) corresponding to the motivating examples (Gaussian squeeze and constrained exploration) in Lines 126-145, to numerically validate the theoretical advantages of our SUBSAMPLE-MFQ algorithm. Across these experiments, we also provided figures that plot the log reward optimality gap as a function of $k$, the time taken for SUBSAMPLE-MFQ to compute its learned policy for varying $k$, and the cumulative discounted reward seen by the algorithm for different $k$. \n\nWe could plan to use the extra page in the camera-ready version to move some of the experiments to the main body. We hope this eases any concerns about the experimental validity of the algorithm, and we would be happy to answer any further questions.\n\nThank you,\n\nAuthors"}, {"review_id": "Ctn2apvrHE", "reviewer": "Reviewer_GLs2", "summary": "This paper addresses the fundamental challenge of scalability in cooperative multi-agent reinforcement learning (MARL), where the joint state-action space grows exponentially with the number of agents, n. The authors propose a novel algorithm, SUBSAMPLE-MFQ, that tackles this curse of dimensionality by leveraging mean-field theory and subsampling. The main contribution of the paper is a rigorous theoretical proof showing that the performance gap between the learned policy and the globally optimal policy decays at a rate of O(1/ square root of k). This error bound is independent of the total number of agents n, establishing a clear trade-off between computational complexity and sub-optimality.", "questions": "-  The theoretical results are very impressive. To better contextualize their impact, could you discuss how you expect SUBSAMPLE-MFQ to perform on standard, complex MARL benchmarks like the StarCraft Multi-Agent Challenge (SMAC)? How does the structural assumption of your model (a global agent and non-interacting local agents) map to such environments, and what challenges would arise in applying your method there?\n\n- The paper proves an optimality gap of  O~(1/ square root of k). In the limitations, you correctly note the absence of a matching lower bound. Do you have any intuition on whether this rate is tight for this problem? Or could a different sampling or estimation strategy potentially achieve a faster rate, such as O(1/k)?", "limitations": "yes", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 4, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths\n- This paper presents a significant and original theoretical breakthrough for scalable MARL. The idea of combining mean-field approximation with agent subsampling to achieve complexity that is independent of the total number of agents n is a powerful and novel concept. This directly tackles the most critical bottleneck in MARL—the curse of dimensionality—and provides a new and viable path toward creating provably good algorithms for systems with massive numbers of agents.\n\n-The main theoretical result (Theorem 4.4) is very strong. Proving an optimality gap that does not depend on n is a powerful guarantee. The proof appears rigorous and leverages a non-trivial combination of techniques, including a novel MDP sampling result based on an extension of the DKW inequality and a careful adaptation of the performance difference lemma to the multi-agent sampling context. The analysis is extensive, with the appendices covering extensions to stochastic rewards, off-policy learning, and even continuous spaces, demonstrating the robustness of the framework.\n\n- For a deeply theoretical paper, the presentation is exceptionally clear. The authors do an excellent job of motivating the problem, providing high-level intuition for their approach, and then systematically building up the formalisms. \n\n- The result establishes a fundamental trade-off between computation (polynomial in k) and optimality. By setting k=O(\\log n), the paper demonstrates an exponential speedup over prior mean-field methods while maintaining a provably small, decaying optimality gap. This could inspire a new class of practical, scalable MARL algorithms.\n\nWeaknesses\n-The primary weakness of the paper is its experiments. The simulations are run on two relatively simple, synthetic environments (\"Gaussian squeeze\" and \"constrained exploration\") designed to illustrate the theory. The paper lacks evaluation on any standard, complex MARL benchmarks (e.g., StarCraft, Multi-Agent MuJoCo, etc.). While the results effectively demonstrate the claimed trade-off, they do not show how SUBSAMPLE-MFQ compares to or performs against established, practical MARL algorithms in more realistic settings.\n\n-The theoretical results are derived for a specific cooperative MARL setting with homogeneous local agents and a structured reward and transition dynamic (agents do not directly interact with each other, only through the global state). While the authors mention that heterogeneity can be modeled by including a \"type\" in the state space, this may not be sufficient for all real-world scenarios. The restriction to purely cooperative tasks also limits the immediate applicability to competitive or mixed-motive games.\n\n-The proposed online execution policy (Algorithm 2) requires each of the n agents to sample and observe the states of k-1 other agents at every timestep. While this is tractable from a computational perspective, it assumes a communication or observation network that can support this random sampling at scale. In a massively distributed system, this requirement could itself become a communication bottleneck, which complicates the \"decentralized execution\" claim.", "was_revised": false, "final_justification": "", "rebuttal": "We thank reviewer GLs2 for their feedback on our work. \n\n>While this is tractable from a computational perspective, the decentralized execution assumes a communication or observation network that can support this random sampling at scale. In a massively distributed system, this requirement could itself become a communication bottleneck, which complicates the \"decentralized execution\" claim.\n\nThanks for pointing this out. We can add some discussion on heuristics that derandomize the decentralized execution method, which may be more conductive for practical settings. Specifically, one practical implementation of the algorithm involves allowing the agents to share some randomness by only sampling within pre-defined fixed blocks of size $k$. We can add more detail on this and add this as a new section in the appendix.\n\n\n>To better contextualize their impact, could you discuss how you expect SUBSAMPLE-MFQ to perform on standard, complex MARL benchmarks like the StarCraft Multi-Agent Challenge (SMAC)?  How does the structural assumption of your model (a global agent and non-interacting local agents) map to such environments, and what challenges would arise in applying your method there?\n\nAs the reviewer points out, the primary contributions of our work are theoretical, and we only provided simulations sufficient to numerically validate the theoretical result. For instance, the “Gaussian squeeze” experiment is similar to one conducted in the foundational mean-field MARL paper [1] which we ablate against.  An even more thorough empirical study of cooperative multi-agent RL algorithms would be an interesting avenue for future research for empirical research, however, this is outside of the scope of our current work which focuses on some theoretical bottlenecks of MARL. At the present, some structural assumptions which resist applications of our methods in some standard MARL benchmarks involve the fact that our method only incorporates weak heterogeneity, as well as the fact that it is designed for cooperative multi-agent learning rather than more competitive/game environments.\n\n>Regarding the optimality gap, do we have any intuition on whether this rate is tight for this problem? Or could a different sampling or estimation strategy potentially achieve a faster rate, such as O(1/k)?\n\nThe algorithmic bottleneck in achieving a faster rate than $O(1/\\sqrt{k})$ is actually from learning the $\\hat{Q}_k$ function, rather than the online execution strategy; however, when $k = n$, our algorithm reduces to mean-field learning which has a rate of $O(1/\\sqrt{n})$ (and is known to be tight in light of [1]). Thus, at least when $k =n$, our $O(1/\\sqrt{k})$ rate is tight. This illustrates a natural obstacle against uniformly improving our $O(1/\\sqrt{k})$ rate and perhaps suggests intuition for why our result might be tight. \n\nWe would be happy to answer any further questions.\n\nThank you,\n\nAuthors\n\n========================\n\nReferences:\n\n[1] Mean Field Multi-Agent Reinforcement Learning, Yang et. al. (ICML 2018)"}, {"review_id": "FZdnxfuHeD", "reviewer": "Reviewer_1oj9", "summary": "This paper addresses a challenging and important problem in cooperative multi-agent reinforcement learning (MARL) by proposing a Subsample-Mean-Field Q-learning algorithm that decouples the global dependence among agents through random subsampling. The paper establishes a performance gap of $O(1/\\sqrt{k})$, where $k$ is the number of sampled agents with improved sample complexity. This is a strong and meaningful result in cooperative MARL under the homogeneous agent setting.", "questions": "1) The algorithm's sample complexity appears to be less relevant to the time horizon $T$, which is unusual in RL theory literature. If I understand correctly, it may be due to the large number of samples used in the Bellman updates. It would be beneficial to provide a detailed discussion on this topic.  \n\n2) In the learning period, the algorithm still seems to require a centralized way to do value iteration and (greedy) policy improvement; it would be better to explain how it can be implemented in a practical setting.  \n\n3) While the proposed method is designed for homogeneous agents, it would be valuable for the paper to discuss how the approach might be extended to heterogeneous settings, especially when the agent types are numerous or drawn from a continuous space. Even a discussion of potential challenges or directions would strengthen the broader applicability of the work.", "limitations": "No", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 3, "significance": 4, "originality": 3, "strengths_and_weaknesses": "Strengths \n* The paper tackles an important and challenging problem in cooperative MARL. The proposed algorithm is intuitive, and the performance guarantee of $O(1/\\sqrt{k})$ with improved sample complexity is a great theoretical contribution to cooperative MARL, which might be leveraged to understand more complex settings. \n\nWeaknesses\n* The paper may require a simulator to generate samples, and the number of samples per iteration ($m$) could be very large, scaling exponentially with the size of the local state and action spaces. The method might be limited to the homogeneous setting.", "was_revised": true, "final_justification": "I think it is a nice theory paper in MARL, and I am very positive about it.", "rebuttal": "We thank reviewer 1oj9 for their feedback. Please find our response below:\n\n>The paper may require a simulator to generate samples, and the number of samples per iteration could be very large, scaling exponentially with the size of the local state and action spaces. The method might be limited to the homogeneous setting.\n\nOur algorithm assumes the existence of a simulator to generate samples. As the reviewer points out, this adds an $O(1)$ cost per iteration, resulting in a large query complexity. However, this query complexity was previously exponential in the number of local agents and in the state/action spaces, whereas our work reduces this to a polynomial dependence with the number of local agents and a sub-exponential dependence on the state/action spaces. Moreover, Remark 4.5 and Appendix I details a version of the algorithm that relaxes the assumption of having a generative oracle by only utilizing historical data (by reducing to off-policy $Q$-learning).\n\n>The algorithm's sample complexity appears to be less relevant to the time horizon , which is unusual in RL theory literature. If I understand correctly, it may be due to the large number of samples used in the Bellman updates. It would be beneficial to provide a detailed discussion on this topic.\n\nIn Appendix G.1, we show that a necessary condition of $T>\\frac{2}{1-\\gamma} \\log \\frac{\\tilde{r}\\sqrt{k}}{1-\\gamma}$ is sufficient to allow the Bellman error to be on the order of $\\tilde{O}(1/\\sqrt{k})$. This enables Lemma 4.3 in the main body which allows us to abstract away the dependence on the time-horizon. We can add a parallel derivation that retains the $T$ factor via a $\\gamma^T$ dependence in the final bound (which shows an exponentially decaying error with the time horizon $T$). Moreover, in Lemma G.10, we show that the query complexity is on the order of $O(mT|S_g||S_l|^k|A_g||A_l|^k)$, and we bound $T$ and set $m={\\text{poly}}(1/(1-\\gamma))$ to attain the $1/\\sqrt{k}$ rate. We can make these dependencies more explicit in Theorem 4.2 in the final version of this paper. \n\nAdditionally, we can explain that our polynomial dependence on $\\frac{1}{1-\\gamma}$ may be loose since we do not use more complicated variance reduction techniques as in [1, 2, 3, 4] to optimize the number of samples $m$ which is used, in turn, to bound the Bellman error $\\epsilon_{k,m}$. This was primarily because our goal was to analyze the necessary number of sampled agents as well as to keep complex algorithms as simple as possible (and incorporating variance reduction would significantly complicate the algorithm and intuition). \n\n>In the learning period, the algorithm still seems to require a centralized way to do value iteration and (greedy) policy improvement; it would be better to explain how it can be implemented in a practical setting.\n\nCentralized learning is the only provable way for a multi-agent system to learn the true optimum policy in the full-information setting, as the optimum policy $\\pi^*$ lives in a set whose cardinality depends on the joint state/action space. To clarify, there exists decentralized-training MARL algorithms with provable convergence guarantees to some equilibrium policy; however, these algorithms generally do not converge to the optimum policy. Since our algorithm only requires centralized training on $k\\leq n$ agents, it is more scalable than previous optimum-searching policies. One practical suggestion that exploits the homogeneity of the local agents is to allow each local agent to compute the joint $Q$-function instead of having a controller share the learned policy with all the agents: this leads to a natural trade-off between the communication complexity and the sample complexity of the algorithm which can be optimized for in various practical settings, and we can add this as a discussion in Remark 4.8 in the main body.\n\n>While the proposed method is designed for homogeneous agents, it would be valuable for the paper to discuss how the approach might be extended to heterogeneous settings, especially when the agent types are numerous or drawn from a continuous space. Even a discussion of potential challenges or directions would strengthen the broader applicability of the work.\n\nIndeed, while the current algorithm can only work for the homogeneous setting, we add two caveats:\n1) As the reviewer points out, we mention an extension to a partially heterogeneous-agent setting by modeling types as a part of the state/action spaces of the local agents, in the “capturing heterogeneity” paragraph in page 4 and Remark 4.7. \n2) There has been a line of recent work on extending mean-field MARL using a graphon-based framework that supports a continuum of distinct transition probabilities (which is also a form of heterogeneity). It may be possible to extend our subsampling framework to graphon mean-field MARL. Adapting this to our sampling framework may be highly non-trivial, and we leave this as an open problem for future works. Nonetheless, we can add a detailed discussion on this as part of Remark 4.7.\n\nWe hope this answers your questions, and look forward to further discussions.\n\nThank you,\n\n\nAuthors\n\n====================\n\nReferences:\n\n[1] Variance Reduced Value Iteration and Faster Algorithms for Solving Markov Decision Processes (Sidford et. al., SODA 2018) \n\n[2] Near-Optimal Time and Sample Complexities for Solving Discounted Markov Decision Process with a Generative Model  (Sidford et. al., NeurIPS 2018)\n\n[3] Truncated Variance Reduced Value Iteration (Jin et. al., NeurIPS 2024)\n\n[4] Variance-reduced Q-learning is minimax optimal (Mainwright, arXiV 2019)"}, {"review_id": "mYjEAOGvae", "reviewer": "Reviewer_PDRU", "summary": "This paper proposes a novel algorithm, \\textbf{SUBSAMPLE-MFQ (Subsample-Mean-Field Q-learning)}, to address the scalability challenges in cooperative multi-agent reinforcement learning (MARL). Traditional MARL suffers from exponential complexity in the number of agents, and although mean-field MARL reduces this to polynomial complexity, it remains computationally prohibitive for large-scale systems. \n\nThe authors introduce a sampling-based approximation strategy: by selecting a small number $k \\leq n$ of local agents and applying value iteration on this reduced system, they learn a policy that can be extended stochastically to the full agent population. The key theoretical contribution is showing that the performance gap between the learned policy and the global optimum decays at a rate of $\\widetilde{O}(1/\\sqrt{k})$, independent of the total number of agents $n$. Thus, by choosing $k = O(\\log n)$, the algorithm achieves a \\textit{polylogarithmic runtime} in $n$, representing an exponential speedup over previous approaches. The paper also extends this framework to off-policy learning and non-tabular settings.", "questions": "1. Can the authors provide more comprehensive experiments on common MARL benchmarks (e.g., MAgent, PettingZoo, SMAC) to evaluate practical performance?\n\n2. How does the method scale or degrade with increasing agent heterogeneity? Can you support this with empirical results?\n\n3. Could the authors discuss how the learned policies can be implemented with function approximators like neural networks in practical settings?\n\n4. Is there any guidance on how to select $k$ in real-world tasks to balance performance and computational efficiency?\nHow does SUBSAMPLE-MFQ compare empirically to recent centralized training and decentralized execution (CTDE) methods?", "limitations": "Yes.", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 4, "significance": 4, "originality": 3, "strengths_and_weaknesses": "Strengths\n\n1. Theoretical contributions are strong and rigorous. The authors provide a provable convergence rate, detailed complexity bounds, and analysis for both tabular and non-tabular settings.\n\n2. The approach is sound and novel, building a strong bridge between mean-field theory and sampling-based approximation in MARL.\n\n3. The paper includes clear algorithmic details, including formal descriptions (Algorithm 1 & 2), and supportive mathematical analysis.\n\nWeaknesses\n\n1. The experimental section is minimal and primarily relegated to the appendix. There is no strong empirical validation of the claimed exponential speedup or policy performance on standard benchmarks.\n\n2. While the paper discusses extension to heterogeneity, the current algorithm assumes mostly homogeneous agent types.\n\n3. Real-world deployment constraints (e.g., communication or decentralized execution under limited observability) are not empirically studied.", "was_revised": true, "final_justification": "The authors response the questions clearly, and it is a good thoery work in RL.", "rebuttal": "We thank reviewer PDRU for their feedback. Please find our response below:\n\n>While the paper discusses extension to heterogeneity, the algorithm assumes mostly homogeneous agent types.\n\nIndeed, while the current algorithm can only work for the homogeneous setting, we add two caveats:\n1) As the reviewer points out, we mention an extension to a partially heterogeneous-agent setting by modeling types as a part of the state/action spaces of the local agents, in the “capturing heterogeneity” paragraph in page 4 and Remark 4.7. \n2) There has been a line of recent work on extending mean-field MARL using a graphon-based framework that supports a continuum of distinct transition probabilities (which is also a form of heterogeneity). It may be possible to extend our subsampling framework to graphon mean-field MARL. Adapting this to our sampling framework may be highly non-trivial, and we leave this as an open problem for future works. Nonetheless, we can add a detailed discussion on this as part of Remark 4.7.\n\n>Can the authors provide more comprehensive experiments on common MARL benchmarks (e.g., MAgent, PettingZoo, SMAC) to evaluate practical performance?\n\nAs our work is a theoretical framework to the NeurIPS theory track submission, we only provided sufficient experiments to numerically validate the theory. That being said, an even more thorough empirical study of cooperative multi-agent RL algorithms is an interesting avenue for future research for empirical research, however, this is outside of the scope of our current work. Moreover, the above benchmarks (MAgent, PettingZoo, SMAC) do not fit our MARL setting (for instance, SMAC requires heterogeneous agents, MAgent requires competitive agents, and PettingZoo does not support our global-agent/local-agent setup). \n\n>How does the method scale/degrade with increasing agent heterogeneity? Can you support this with empirical results?\n\nIncreasing the agent heterogeneity using our “type-formulation” makes the algorithm somewhat more expensive since it factors into the query complexity via the state space of the local agents. **However**, since the optimality gap of the learned policy is on the order of $\\tilde{O}(1/\\sqrt{k})$ (modulo very small $\\sqrt{\\log(|\\mathcal{S}_l| |\\mathcal{A}_l|)}$ factors), **increasing the amount of agent heterogeneity does not degrade the quality of the learned policy as the theoretical bound does not get worse.**\n\n>Could the authors discuss how the learned policies can be implemented with function approximators like neural networks in practical settings?\n\nLearning the policy and sharing it to all the agents is the computational bottleneck in practical settings. After this, it is efficient to implement the learned policies since the empirical distribution only takes $O(k)$ time to compute, and this dependency is tight. In Appendix J, we extended our algorithm to continuous spaces. In this set-up, the learned policy could be  implemented with neural operators and other function approximators to parameterize and evaluate the policy.\n\n>Is there any guidance on how to select k in real-world tasks to balance performance and computational efficiency? How does SUBSAMPLE-MFQ compare empirically to recent centralized training and decentralized execution (CTDE) methods?\n\nTheoretically, $k = O(\\log n)$ suffices to have a decaying error rate with best efficiency, as we mention in Remark 4.6, and as is validated by our experiments. To the best of our knowledge, there is no previous CTDE method that utilized a similar parameterized (with respect to $k$) method for learning a MARL policy in the full-observation setting.\n\nWe hope this answers your questions, and look forward to further discussions.\n\nThank you,\n\nAuthors"}]

Author rebuttal:

Meta-review: The paper “develop[s] and analyze[s] a scalable algorithm for multi-agent RL by sampling the mean-field distribution of the agents to overcome the curse of dimensionality.”  All reviewers rated the paper highly, universally stating that it is a good theory paper that delivers on its claims.  Some concerns were expressed about the limited experimental results.
Decision: Accept (spotlight)