Mean-Field Sampling for Cooperative Multi-Agent Reinforcement Learning

🕒 Published (v1): 2025-01-01 · Source: NeurIPS · Venue: NeurIPS 2025 · link

Ask a follow-up

Open an assistant pre-loaded with this paper's context.

💬 Ask ChatGPT✦ Ask Claude

TL;DR

SUBSAMPLE-MFQ is a cooperative MARL algorithm that learns a near-optimal joint policy by running mean-field Q-learning on a randomly subsampled subset of k ≤ n local agents rather than all n. The learned policy's optimality gap is provably Õ(1/√k), independent of n, enabling polylogarithmic runtime in n when k = O(log n)—an exponential speedup over prior mean-field methods.

Problem

Standard Q-learning for n-agent MARL requires a Q-table of size exponential in n. Mean-field MARL reduces this to polynomial in n but remains prohibitive at scale. No prior centralized MARL algorithm achieves subpolynomial (in n) runtime while maintaining a provably decaying optimality gap.

Method

The paper models the system as a global agent plus n homogeneous local agents. SUBSAMPLE-MFQ has two phases:

Offline learning (Algorithm 1): Sample a random subset ∆ of k local agents; run mean-field value iteration (or tabular Q-learning, whichever is cheaper) on this k-agent surrogate MDP to learn Q̂ᵉˢᵗ_k and deterministic policy π̂ᵉˢᵗ_k. The surrogate reward averages only over the k subsampled agents.

Online execution (Algorithm 2): At each timestep, the global agent draws a fresh uniform random subset of k agents from [n] and applies π̂ᵉˢᵗ_k; each local agent i draws k−1 peers uniformly at random and applies the same policy. This randomized policy π^est_k induces a stochastic marginal distribution over actions.

The key analytic tools are: (1) extending the DKW inequality to sampling without replacement to bound TV distance between the subsampled empirical distribution and the full distribution; (2) adapting the performance-difference lemma to the multi-agent setting.

Key Contributions

• SUBSAMPLE-MFQ algorithm with formal correctness and sample-complexity guarantees for cooperative MARL.
• Main theorem: optimality gap V^π*(s₀) − V^π^est_k(s₀) ≤ Õ(1/√k) with probability ≥ 1 − 1/(100eᵏ), independent of n.
• First centralized MARL algorithm with polylogarithmic runtime in n (k = O(log n) yields sample complexity min{Õ(n^(log|Z_l|)|S_g||A_g|), Õ((log n)^|Z_l||Z_l||S_g||A_g|)}).
• Extension to off-policy Q-learning (historical data) with the same Õ(1/√k) gap.
• Extension to non-tabular linear MDPs with function approximation (Theorem 4.12).
• Handles O(log n / log log n) agent types (vs. O(1) in prior work) under k = O(log n).

Results

All results are theoretical; empirical experiments are in appendices.

• Optimality gap: Õ(1/√k) with high probability (1 − 1/100eᵏ) for all initial states (Theorem 4.4).
• Sample complexity at k = O(log n): exponential speedup over standard Q-learning (exp(n) → poly(n)) and over mean-field value iteration (poly(n) → poly(log n)).
• Baseline comparison: Mean-field Q-learning [Yang et al. 2018, Gu et al. 2021] has complexity O(n|S||A|^(|S||A|)), which is polynomial in n but exponential in |Z_l|; SUBSAMPLE-MFQ reduces both axes simultaneously.
• Experiments (Appendix B): Monotonic improvement in policy quality as k → n on Gaussian squeeze and constrained exploration tasks, with substantial runtime speedup over mean-field Q-learning.

Limitations

• Assumes a cooperative setting with a structured, separable reward; does not handle competitive or mixed-motive agents.
• Requires homogeneous local agents (same state/action space); heterogeneity is supported only through a type-embedding trick, limited to O(log n / log log n) types under k = O(log n).
• Global-agent/local-agent structure is more restrictive than arbitrary network topologies; extension to sparse or arbitrary graphs is left as future work.
• Poly(1/(1−γ)) dependence in sample bounds is likely loose; variance reduction techniques are not incorporated.
• Tabular setting dominates; function approximation extension (Appendix J) inherits additional approximation error.
• Online no-regret formulation is not addressed.

Relevance to Agentic AI / LLM Agents

This paper directly addresses scalable decision-making in multi-agent systems—a foundational problem for deploying large fleets of LLM agents that must cooperate toward a shared goal. The global-agent + n local-agents model is a natural abstraction for orchestrator–worker agent architectures, where a central LLM coordinates many specialized subagents. The subsampling insight (each agent needs only a small random peer sample to act near-optimally) has practical implications for reducing communication overhead and inference cost in multi-agent LLM pipelines. The CTDE (Centralized Training, Decentralized Execution) framing aligns directly with how multi-agent LLM systems are trained and deployed.