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

Emile Anand, Guannan Qu

Abstract

We study reinforcement learning for global decision-making in the presence of many local agents, where a global decision-maker makes decisions affecting all local agents. The objective is to learn a policy that maximizes the rewards of both the global and the local agents. In this setting, scalability has been a long-standing challenge due to a state/action space that grows exponentially with the number of agents. This work proposes the SUB-SAMPLE-Q algorithm, where the global agent subsamples $k \leq n$ local agents to compute an optimal policy. This approach achieves an exponential speedup over standard methods, reducing computation time from exponential in $n$ to exponential in $k$. We prove that the learned policy converges to the optimal policy at a rate of $\tilde{O}(1/\sqrt{k}+\epsilon_{k,m})$ as the number of sub-sampled agents $k$ increases. Numerical simulations in demand-response and queueing settings validate the theoretical findings.

Introduction

In many real-world infrastructure systems—such as electric vehicle charging stations, demand-response power grids, or massive server clusters—a single "global" agent must make decisions that affect thousands of "local" agents. The goal is typically to maximize the total reward across the entire system. However, these systems face the Curse of Dimensionality. In a standard Markov Decision Process (MDP), the state space grows exponentially with the number of agents ($n$). Even if each agent has only two possible states, the global state space encompasses $2^n$ combinations, making traditional Reinforcement Learning (RL) algorithms like Q-learning computationally intractable at scale.

While "Mean-Field RL" attempts to address this by treating agents as a collective distribution, it often still requires computations that scale with the total number of agents, which remains a bottleneck for truly massive systems. This paper introduces SUBSAMPLE-Q to bridge this gap by leveraging statistical sampling techniques to achieve global coordination with local observations.

The SUBSAMPLE-Q Algorithm

SUBSAMPLE-Q is based on the intuition that a global controller does not need to observe every single agent to make an informed decision—similar to how a political pollster can predict an election by surveying a representative subset of the population. The algorithm operates in two primary phases:

  1. Learning Phase (Offline): Instead of learning a Q-function for all $n$ agents, the algorithm randomly selects a small subset of $k$ agents. It utilizes an "empirically adapted Bellman operator" to learn a policy based solely on the states of these $k$ agents. This reduces the Q-table size from a value scaling with $n$ to one scaling with $k$, providing an exponential reduction in complexity.
  2. Execution Phase (Online): At each timestep, the global agent randomly subsamples $k$ agents from the population, observes their current states, and applies the learned policy to choose a global action.

To ensure the validity of this approach, the authors generalized the Dvoretzky–Kiefer–Wolfowitz (DKW) inequality to the regime of sampling without replacement. This mathematical innovation allows for a provable bound on the error introduced by observing a sample rather than the entire population.

Key Insights and Theoretical Results

The Power of Logarithmic Sampling

A striking insight from the research is that if the sample size $k$ is chosen to be logarithmic relative to the total population $n$, the algorithm runs in polylogarithmic time. This represents an exponential speedup over traditional methods while still providing a policy that improves as $n$ grows.

Exploiting Symmetry and Topology

The method is particularly effective because local agents are "pseudo-heterogeneous." While they may be in different states or have different "types," they share the same transition and reward logic. This symmetry implies that the global agent primarily cares about the distribution of states rather than the specific identity of an agent in a given state. Furthermore, the paper identifies the Star-Graph Topology—one central node connected to many peripheral nodes—as a "dense" graph structure that SUBSAMPLE-Q can handle effectively, whereas previous "networked RL" methods often required sparse connections.

Convergence Guarantees

The authors prove that the performance gap between the subsampled policy and the true optimal policy is $O(1/\sqrt{k} + \epsilon_{k,m})$, where $\epsilon$ represents Bellman noise. This confirms that as the sample size $k$ increases, the learned policy converges toward optimality.

Experimental Validation

The algorithm was evaluated using two simulated environments designed to mimic real-world infrastructure challenges:

  • Demand-Response (DR) Simulation: A power system model where a regulator (global agent) moderates electricity supply while local users (agents) have fluctuating consumption needs. In these experiments, SUBSAMPLE-Q demonstrated a significant polynomial speedup in training time. For $n=8$, computation time dropped significantly as $k$ decreased, following the predicted theoretical curve.
  • Queueing System: A job allocation problem where a dispatcher must send tasks to $n$ different queues to minimize wait times. In large-scale tests with $n=50$ agents, the algorithm's rewards grew monotonically as the sample size $k$ increased, suggesting that the theoretical "worst-case" guarantees are conservative and that the algorithm performs even better in practice.

Limitations and Future Directions

While SUBSAMPLE-Q provides a robust framework for scalable global decision-making, several avenues for future work remain:

  • Generative Oracle: The current learning phase assumes a simulator (oracle) is available to sample transitions. Future iterations could explore purely "model-free" settings.
  • Function Approximation: The work focuses on tabular MDPs with finite state spaces. Integrating Deep Q-Networks (DQN) would allow the algorithm to handle continuous state and action spaces.
  • Complex Topologies: The current theory is optimized for a single global controller (star-graph). Extending this to more complex graph topologies using expander-graph decomposition is a promising next step.

Summary updated

Abstract

We study reinforcement learning for global decision-making in the presence of many local agents, where the global decision-maker makes decisions affecting all local agents, and the objective is to learn a policy that maximizes the rewards of both the global and the local 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/action space which can be exponential in the number of agents. This work proposes the SUB-SAMPLE-Q algorithm where the global agent subsamples $k\leq n$ local agents to compute an optimal policy in time that is only exponential in $k$, providing an exponential speedup from standard methods that are exponential in $n$. We show that the learned policy converges to the optimal policy in the order of $\tilde{O}(1/\sqrt{k}+\epsilon_{k,m})$ as the number of sub-sampled agents $k$ increases, where $\epsilon_{k,m}$ is the Bellman noise. We also conduct numerical simulations in a demand-response setting and a queueing setting.
BibTeX
@misc{anand2024efficient,
  author = {Emile Anand and Guannan Qu},
  title = {{Efficient Reinforcement Learning for Global Decision Making in the Presence of Local Agents at Scale}},
  year = {2024},
  eprint = {2403.00222},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2403.00222},
}
Figure