Mean-Field Controls with Q-learning for Cooperative MARL: Convergence and Complexity Analysis

2020-02-10 · Haotian Gu, Xin Guo, Xiaoli Wei, Renyuan Xu

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

📄 PDF Abstract BibTeX arXiv:2002.04131

Code (0)

등록된 구현이 없습니다.

Tasks

Multi-agent Reinforcement LearningQ-LearningReinforcement Learning

Methods 이 논문이 사용한 방법론

Q-Learning Q-Learning is an off-policy temporal difference control algorithm: $$Q\left(S\_{t}, A\_{t}\right) \leftarrow Q\left(S\_{t}, A\_{t}\right) + \alpha\left[R_{t+1} +…

Major-Minor Mean Field Multi-Agent Reinforcement Learning

2023-03-19 · Kai Cui, Christian Fabian, Anam Tahir, Heinz Koeppl

Multi-agent reinforcement learning (MARL) remains difficult to scale to many agents. Recent MARL using Mean Field Control (MFC) provides a tractable and rigorous approach to otherwise difficult cooperative MARL. However,…

Multi-agent Reinforcement Learning reinforcement-learning Reinforcement Learning

A Principled Permutation Invariant Approach to Mean-Field Multi-Agent Reinforcement Learning

2021-09-29 · Yan Li, Lingxiao Wang, Jiachen Yang, Ethan Wang 외

Multi-agent reinforcement learning (MARL) becomes more challenging in the presence of more agents, as the capacity of the joint state and action spaces grows exponentially in the number of agents. To address such a chall…

Inductive Bias Multi-agent Reinforcement Learning reinforcement-learning Reinforcement Learning (RL)

Permutation Invariant Policy Optimization for Mean-Field Multi-Agent Reinforcement Learning: A Principled Approach

2021-05-18 · Yan Li, Lingxiao Wang, Jiachen Yang, Ethan Wang 외

Inductive Bias Multi-agent Reinforcement Learning

Graphon Mean-Field Subsampling for Cooperative Heterogeneous Multi-Agent Reinforcement Learning

2026-02-18 · Emile Anand, Richard Hoffmann, Sarah Liaw, Adam Wierman arxiv

Coordinating large populations of interacting agents is a central challenge in multi-agent reinforcement learning (MARL), where the size of the joint state-action space scales exponentially with the number of agents. Mea…

Multi-agent Reinforcement Learning

Can Mean Field Control (MFC) Approximate Cooperative Multi Agent Reinforcement Learning (MARL) with Non-Uniform Interaction?

2022-02-28 · Washim Uddin Mondal, Vaneet Aggarwal, Satish V. Ukkusuri

Mean-Field Control (MFC) is a powerful tool to solve Multi-Agent Reinforcement Learning (MARL) problems. Recent studies have shown that MFC can well-approximate MARL when the population size is large and the agents are e…