Mean-Field Controls with Q-learning for Cooperative MARL: Convergence and Complexity Analysis
Preprint
Abstract
Multi-agent reinforcement learning (MARL), despite its popularity and empirical success, suffers from the curse of dimensionality. This paper builds the mathematical framework to approximate cooperative MARL by a mean-field control (MFC) approach, and shows that the approximation error is of $\mathcal{O}(\frac{1}{\sqrt{N}})$. By establishing an appropriate form of the dynamic programming principle for both the value function and the Q function, it proposes a model-free kernel-based Q-learning algorithm (MFC-K-Q), which is shown to have a linear convergence rate for the MFC problem, the first of its kind in the MARL literature. It further establishes that the convergence rate and the sample complexity of MFC-K-Q are independent of the number of agents $N$, which provides an $\mathcal{O}(\frac{1}{\sqrt{N}})$ approximation to the MARL problem with $N$ agents in the learning environment. Empirical studies for the network traffic congestion problem demonstrate that MFC-K-Q outperforms existing MARL algorithms when $N$ is large, for instance when $N>50$.
Keywords
All Related Versions
This publication has 25 references indexed in Scilit:
- Robust mean field social control problems with applications in analysis of opinion dynamicsInternational Journal of Control, 2021
- Multi-Agent Reinforcement Learning: A Selective Overview of Theories and Algorithms2021
- A survey and critique of multiagent deep reinforcement learningAutonomous Agents and Multi-Agent Systems, 2019
- Discrete Time McKean–Vlasov Control Problem: A Dynamic Programming ApproachApplied Mathematics & Optimization, 2016
- A multi-agent reinforcement learning approach to dynamic service compositionInformation Sciences, 2016
- Mastering the game of Go with deep neural networks and tree searchNature, 2016
- Lipschitz Continuity of Value Functions in Markovian Decision ProcessesMathematical Methods of Operations Research, 2005
- Learning Rates for Q-LearningLecture Notes in Computer Science, 2001
- Algorithms for optimization and stabilization of controlled Markov chainsSādhanā, 1999
- On the McKean‐Vlasov Limit for Interacting DiffusionsMathematische Nachrichten, 1988