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

Emile Timothy Anand, Guannan QuSubmission to ICLR 2025 · Rejected

Abstract

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, and queueing. In this setting, scalability has been a long-standing challenge due to the size of the joint state space which can be exponential in the number of agents. This work proposes the \texttt{SUBSAMPLE-Q} algorithm, where the global agent subsamples $k\leq 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 on the order of $\tilde{O}(1/\sqrt{k}+\epsilon_{k,m})$ as the number of subsampled agents $k$ increases, where ${\epsilon}_{k,m}$ is the Bellman noise. Finally, we validate our theoretical results through numerical simulations in demand-response and queueing settings.
BibTeX
@misc{anand2024efficient,
  author = {Emile Timothy 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