mlsanityData to 14 Oct 2026

Mean-Field Sampling for Cooperative Multi-Agent Reinforcement Learning

arXiv 2412.00661 ↗First posted 1 Dec 2024cs.LG cs.AI cs.MAcited by 9

Not on the map. Why?

Abstract (arXiv)

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 textttSUBSAMPLE-MFQ (Subsample-Mean-Field-Q-learning) and a decentralized randomized policy for a system with n agents. For any k≤ 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 tildeO(1/√k) as the number of subsampled agents k increases. In particular, this bound is independent of the number of agents n.

Key facts. Cited by 9 papers in the map (data through 14 Oct 2026). Builds on 40 of its 73 references that are in the map. First posted on arXiv 1 Dec 2024.

Builds on

40 of 73 references.

References · 40

  1. 2018Off-Policy Deep Reinforcement Learning without Explorationcited by 1,241
  2. 2020Deep Reinforcement Learning for Autonomous Driving: A Surveycited by 721
  3. 2019Multi-Agent Reinforcement Learning: A Selective Overview of Theories and Algorithmscited by 567
  4. 2019Provably Efficient Reinforcement Learning with Linear Function Approximationcited by 520
  5. 2021Bellman Eluder Dimension: New Rich Classes of RL Problems, and Sample-Efficient Algorithmscited by 223
  6. 2018Mean Field Multi-Agent Reinforcement Learningcited by 207
  7. 2019Learning with Good Feature Representations in Bandits and in RL with a Generative Modelcited by 127
  8. 2021V-Learning -- A Simple, Efficient, Decentralized Algorithm for Multiagent RLcited by 114
  9. 2020Sample Complexity of Asynchronous Q-Learning: Sharper Analysis and Variance Reductioncited by 95
  10. 2019Probabilistic Recursive Reasoning for Multi-Agent Reinforcement Learningcited by 68
  11. 2018Real-Time Bidding with Multi-Agent Reinforcement Learning in Display Advertisingcited by 65
  12. 2021Decentralized Q-Learning in Zero-sum Markov Gamescited by 58
28 more
  1. 2019Efficient Ridesharing Order Dispatching with Mean Field Multi-Agent Reinforcement Learningcited by 57
  2. 2021A Lyapunov Theory for Finite-Sample Guarantees of Asynchronous Q-Learning and TD-Learning Variantscited by 57
  3. 2020Scalable Multi-Agent Reinforcement Learning for Networked Systems with Average Rewardcited by 50
  4. 2020Mean-Field Controls with Q-learning for Cooperative MARL: Convergence and Complexity Analysiscited by 49
  5. 2022On the Complexity of Adversarial Decision Makingcited by 33
  6. 2021On the Approximation of Cooperative Heterogeneous Multi-Agent Reinforcement Learning (MARL) using Mean Field Control (MFC)cited by 32
  7. 2021Mean-Field Multi-Agent Reinforcement Learning: A Decentralized Network Approachcited by 28
  8. 2021Learning Graphon Mean Field Games and Approximate Nash Equilibriacited by 28
  9. 2023Concentration of Contractive Stochastic Approximation: Additive and Multiplicative Noisecited by 26
  10. 2018Discovering and Removing Exogenous State Variables and Rewards for Reinforcement Learningcited by 24
  11. 2019Dynamic Programming Principles for Mean-Field Controls with Learningcited by 23
  12. 2022More Centralized Training, Still Decentralized Execution: Multi-Agent Conditional Policy Factorizationcited by 19
  13. 2013Bayes-Ball: The Rational Pastime (for Determining Irrelevance and Requisite Information in Belief Networks and Influence Diagrams)cited by 18
  14. 2023Is Centralized Training with Decentralized Execution Framework Centralized Enough for MARL?cited by 18
  15. 2021Finite-Sample Analysis of Off-Policy TD-Learning via Generalized Bellman Operatorscited by 17
  16. 2022Online Adaptive Policy Selection in Time-Varying Systems: No-Regret via Contractive Perturbationscited by 14
  17. 2022Graphon Mean-Field Control for Cooperative Multi-Agent Reinforcement Learningcited by 11
  18. 2023Decentralized Randomly Distributed Multi-agent Multi-armed Bandit with Heterogeneous Rewardscited by 11
  19. 2023Provable Representation with Efficient Planning for Partial Observable Reinforcement Learningcited by 10
  20. 2023Cooperative Multi-Agent Reinforcement Learning: Asynchronous Communication and Linear Function Approximationcited by 9
  21. 2024Efficient Reinforcement Learning for Global Decision Making in the Presence of Local Agents at Scalecited by 8
  22. 2024Online Policy Optimization in Unknown Nonlinear Systemscited by 8
  23. 2024Truncated Variance Reduced Value Iterationcited by 8
  24. 2024Peer-to-Peer Learning Dynamics of Wide Neural Networkscited by 8
  25. 2023Efficient Planning in Combinatorial Action Spaces with Applications to Cooperative Multi-Agent Reinforcement Learningcited by 6
  26. 2024Locally Interdependent Multi-Agent MDP: Theoretical Framework for Decentralized Agents with Dynamic Dependenciescited by 6
  27. 2024Derandomizing Multi-Distribution Learningcited by 5
  28. 2024The Role of Inherent Bellman Error in Offline Reinforcement Learning with Linear Function Approximationcited by 4

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2025: 3; 2026: 6.

9 papers.

  1. 2025The Structural Complexity of Matrix-Vector Multiplicationcited by 4
  2. 2025Feel-Good Thompson Sampling for Contextual Bandits: a Markov Chain Monte Carlo Showdowncited by 4
  3. 2026Unsupervised Decomposition and Recombination with Discriminator-Driven Diffusion Modelscited by 3
  4. 2026Continuous Latent Contexts Enable Efficient Online Learning in Transformerscited by 3
  5. 2025Finite-Sample Convergence Bounds for Trust Region Policy Optimization in Mean-Field Gamescited by 2
  6. 2026Learning Approximate Nash Equilibria in Cooperative Multi-Agent Reinforcement Learning via Mean-Field Subsamplingcited by 2
  7. 2026Graphon Mean-Field Subsampling for Cooperative Heterogeneous Multi-Agent Reinforcement Learningcited by 1
  8. 2026Operator-Theoretic Foundations and Policy Gradient Methods for General MDPs with Unbounded Costscited by 1
  9. 2026Role Steering of Language Models for Social Simulationscited by 1

Similar, not cited

Close in wording, no citation either way

  1. 2025Centralized Adaptive Sampling for Reliable Co-Training of Independent Multi-Agent Policies
  2. 2024Independent RL for Cooperative-Competitive Agents: A Mean-Field Perspective
  3. 2024Robust Cooperative Multi-Agent Reinforcement Learning:A Mean-Field Type Game Perspective
  4. 2026Mean Field Reinforcement Learning
  5. 2024MFC-EQ: Mean-Field Control with Envelope Q-Learning for Moving Decentralized Agents in Formation
  6. 2024MARL-LNS: Cooperative Multi-agent Reinforcement Learning via Large Neighborhoods Search
  7. 2024Fully Decentralized Cooperative Multi-Agent Reinforcement Learning: A Survey
  8. 2026Multi-Agent Reinforcement Learning with Submodular Reward