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

arXiv: https://arxiv.org/abs/2403.00222 · HTML: https://mlsanity.com/paper/2403.00222/

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- Placed in RL theory and sample complexity, one of 15 directions in Deep reinforcement learning methods.
- Builds on 35 of its 76 references that are in the map.
- First posted on arXiv 1 Mar 2024.

## Placed in

- Deep reinforcement learning methods / [RL theory and sample complexity](https://mlsanity.com/deeprl/rl-theory-and-sample-complexity/)

## Builds on (most cited first, 30 of 35)

- [Deep Reinforcement Learning for Autonomous Driving: A Survey](https://mlsanity.com/paper/2002.00444/) (2020)
- [Multi-Agent Reinforcement Learning: A Selective Overview of Theories and Algorithms](https://mlsanity.com/paper/1911.10635/) (2019)
- [Is Q-learning Provably Efficient?](https://mlsanity.com/paper/1807.03765/) (2018)
- [Mean Field Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/1802.05438/) (2018)
- [V-Learning -- A Simple, Efficient, Decentralized Algorithm for Multiagent RL](https://mlsanity.com/paper/2110.14555/) (2021)
- [Sample Complexity of Asynchronous Q-Learning: Sharper Analysis and Variance Reduction](https://mlsanity.com/paper/2006.03041/) (2020)
- [Thinking Fast and Slow: Optimization Decomposition Across Timescales](https://mlsanity.com/paper/1704.07785/) (2017)
- [Model-Free Mean-Field Reinforcement Learning: Mean-Field MDP and Mean-Field Q-Learning](https://mlsanity.com/paper/1910.12802/) (2019)
- [Decentralized Q-Learning in Zero-sum Markov Games](https://mlsanity.com/paper/2106.02748/) (2021)
- [Multi-agent Reinforcement Learning for Networked System Control](https://mlsanity.com/paper/2004.01339/) (2020)
- [Scalable Multi-Agent Reinforcement Learning for Networked Systems with Average Reward](https://mlsanity.com/paper/2006.06626/) (2020)
- [Mean-Field Controls with Q-learning for Cooperative MARL: Convergence and Complexity Analysis](https://mlsanity.com/paper/2002.04131/) (2020)
- [Scaling Laws for a Multi-Agent Reinforcement Learning Model](https://mlsanity.com/paper/2210.00849/) (2022)
- [Q-learning with Nearest Neighbors](https://mlsanity.com/paper/1802.03900/) (2018)
- [On the Complexity of Adversarial Decision Making](https://mlsanity.com/paper/2206.13063/) (2022)
- [Multi-Agent Reinforcement Learning in Stochastic Networked Systems](https://mlsanity.com/paper/2006.06555/) (2020)
- [On the Approximation of Cooperative Heterogeneous Multi-Agent Reinforcement Learning (MARL) using Mean Field Control (MFC)](https://mlsanity.com/paper/2109.04024/) (2021)
- [A Statistical Analysis of Polyak-Ruppert Averaged Q-learning](https://mlsanity.com/paper/2112.14582/) (2021)
- [Mean-Field Multi-Agent Reinforcement Learning: A Decentralized Network Approach](https://mlsanity.com/paper/2108.02731/) (2021)
- [Learning Graphon Mean Field Games and Approximate Nash Equilibria](https://mlsanity.com/paper/2112.01280/) (2021)
- [Control of Robotic Mobility-On-Demand Systems: a Queueing-Theoretical Perspective](https://mlsanity.com/paper/1404.4391/) (2014)
- [Dynamic Programming Principles for Mean-Field Controls with Learning](https://mlsanity.com/paper/1911.07314/) (2019)
- [Near-Optimal Time and Sample Complexities for Solving Discounted Markov Decision Process with a Generative Model](https://mlsanity.com/paper/1806.01492/) (2018)
- [Online Adaptive Policy Selection in Time-Varying Systems: No-Regret via Contractive Perturbations](https://mlsanity.com/paper/2210.12320/) (2022)
- [Novel Policy Seeking with Constrained Optimization](https://mlsanity.com/paper/2005.10696/) (2020)
- [Graphon Mean-Field Control for Cooperative Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2209.04808/) (2022)
- [Model-Free Reinforcement Learning with the Decision-Estimation Coefficient](https://mlsanity.com/paper/2211.14250/) (2022)
- [Cooperative Multi-Agent Reinforcement Learning: Asynchronous Communication and Linear Function Approximation](https://mlsanity.com/paper/2305.06446/) (2023)
- [Efficient Offline Policy Optimization with a Learned Model](https://mlsanity.com/paper/2210.05980/) (2022)
- [Beyond Black-Box Advice: Learning-Augmented Algorithms for MDPs with Q-Value Predictions](https://mlsanity.com/paper/2307.10524/) (2023)

## Built on by (most cited first, 8 of 8)

- [Mean-Field Sampling for Cooperative Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2412.00661/) (2024)
- [Peer-to-Peer Learning Dynamics of Wide Neural Networks](https://mlsanity.com/paper/2409.15267/) (2024)
- [The Structural Complexity of Matrix-Vector Multiplication](https://mlsanity.com/paper/2502.21240/) (2025)
- [Feel-Good Thompson Sampling for Contextual Bandits: a Markov Chain Monte Carlo Showdown](https://mlsanity.com/paper/2507.15290/) (2025)
- [Bayesian Ego-graph Inference for Networked Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2509.16606/) (2025)
- [Continuous Latent Contexts Enable Efficient Online Learning in Transformers](https://mlsanity.com/paper/2605.09867/) (2026)
- [Learning Approximate Nash Equilibria in Cooperative Multi-Agent Reinforcement Learning via Mean-Field Subsampling](https://mlsanity.com/paper/2603.03759/) (2026)
- [Graphon Mean-Field Subsampling for Cooperative Heterogeneous Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2602.16196/) (2026)

## 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.