mlsanityData to 7 Oct 2026

Efficient Reinforcement Learning for Global Decision Making in the Presence of Local Agents at Scale

arXiv 2403.00222 ↗First posted 1 Mar 2024cs.LG cs.MAcited by 8

Not on the map. Why?

Abstract (arXiv)

We study reinforcement learning for global decision-making in the presence of local agents, where the global decision-maker makes decisions affecting all local agents, and the objective is to learn a policy that maximizes the joint rewards of all the agents. Such problems find many applications, e.g. demand response, EV charging, queueing, etc. In this setting, scalability has been a long-standing challenge due to the size of the state space which can be exponential in the number of agents. This work proposes the textttSUBSAMPLE-Q algorithm where the global agent subsamples k≤ n local agents to compute a policy in time that is polynomial in k. We show that this learned policy converges to the optimal policy in the order of tildeO(1/√k+εk,m) as the number of sub-sampled agents k increases, where εk,m is the Bellman noise. Finally, we validate the theory through numerical simulations in a demand-response setting and a queueing setting.

Key facts. Cited by 8 papers in the map (data through 7 Oct 2026). Builds on 35 of its 76 references that are in the map. First posted on arXiv 1 Mar 2024.

Builds on

35 of 76 references.

References · 35

  1. 2020Deep Reinforcement Learning for Autonomous Driving: A Surveycited by 698
  2. 2019Multi-Agent Reinforcement Learning: A Selective Overview of Theories and Algorithmscited by 555
  3. 2018Is Q-learning Provably Efficient?cited by 485
  4. 2018Mean Field Multi-Agent Reinforcement Learningcited by 202
  5. 2021V-Learning -- A Simple, Efficient, Decentralized Algorithm for Multiagent RLcited by 111
  6. 2020Sample Complexity of Asynchronous Q-Learning: Sharper Analysis and Variance Reductioncited by 93
  7. 2017Thinking Fast and Slow: Optimization Decomposition Across Timescalescited by 60
  8. 2019Model-Free Mean-Field Reinforcement Learning: Mean-Field MDP and Mean-Field Q-Learningcited by 56
  9. 2021Decentralized Q-Learning in Zero-sum Markov Gamescited by 53
  10. 2020Multi-agent Reinforcement Learning for Networked System Controlcited by 51
  11. 2020Scalable Multi-Agent Reinforcement Learning for Networked Systems with Average Rewardcited by 46
  12. 2020Mean-Field Controls with Q-learning for Cooperative MARL: Convergence and Complexity Analysiscited by 44
23 more
  1. 2018Q-learning with Nearest Neighborscited by 37
  2. 2022Scaling Laws for a Multi-Agent Reinforcement Learning Modelcited by 37
  3. 2022On the Complexity of Adversarial Decision Makingcited by 32
  4. 2021On the Approximation of Cooperative Heterogeneous Multi-Agent Reinforcement Learning (MARL) using Mean Field Control (MFC)cited by 31
  5. 2020Multi-Agent Reinforcement Learning in Stochastic Networked Systemscited by 30
  6. 2021A Statistical Analysis of Polyak-Ruppert Averaged Q-learningcited by 29
  7. 2021Learning Graphon Mean Field Games and Approximate Nash Equilibriacited by 28
  8. 2021Mean-Field Multi-Agent Reinforcement Learning: A Decentralized Network Approachcited by 27
  9. 2014Control of Robotic Mobility-On-Demand Systems: a Queueing-Theoretical Perspectivecited by 24
  10. 2018Near-Optimal Time and Sample Complexities for Solving Discounted Markov Decision Process with a Generative Modelcited by 22
  11. 2019Dynamic Programming Principles for Mean-Field Controls with Learningcited by 22
  12. 2022Online Adaptive Policy Selection in Time-Varying Systems: No-Regret via Contractive Perturbationscited by 14
  13. 2020Novel Policy Seeking with Constrained Optimizationcited by 11
  14. 2022Model-Free Reinforcement Learning with the Decision-Estimation Coefficientcited by 11
  15. 2022Graphon Mean-Field Control for Cooperative Multi-Agent Reinforcement Learningcited by 10
  16. 2023Cooperative Multi-Agent Reinforcement Learning: Asynchronous Communication and Linear Function Approximationcited by 9
  17. 2022Efficient Offline Policy Optimization with a Learned Modelcited by 8
  18. 2023Beyond Black-Box Advice: Learning-Augmented Algorithms for MDPs with Q-Value Predictionscited by 8
  19. 2024Sampling from the Mean-Field Stationary Distributioncited by 7
  20. 2023Learning non-Markovian Decision-Making from State-only Sequencescited by 6
  21. 2023Towards Optimal Effective Resistance Estimationcited by 3
  22. 2022Distributed Cooperative Multi-Agent Reinforcement Learning with Directed Coordination Graphcited by 2
  23. 2023Online Nonstochastic Model-Free Reinforcement Learningcited by 2

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2024: 2; 2025: 3; 2026: 3.

8 papers.

  1. 2024Mean-Field Sampling for Cooperative Multi-Agent Reinforcement Learningcited by 9
  2. 2024Peer-to-Peer Learning Dynamics of Wide Neural Networkscited by 8
  3. 2025The Structural Complexity of Matrix-Vector Multiplicationcited by 4
  4. 2025Feel-Good Thompson Sampling for Contextual Bandits: a Markov Chain Monte Carlo Showdowncited by 4
  5. 2026Continuous Latent Contexts Enable Efficient Online Learning in Transformerscited by 3
  6. 2025Bayesian Ego-graph Inference for Networked Multi-Agent Reinforcement Learningcited by 2
  7. 2026Learning Approximate Nash Equilibria in Cooperative Multi-Agent Reinforcement Learning via Mean-Field Subsamplingcited by 2
  8. 2026Graphon Mean-Field Subsampling for Cooperative Heterogeneous Multi-Agent Reinforcement Learningcited by 1