# Learning in Herding Mean Field Games: Single-Loop Algorithm with Finite-Time Convergence Analysis

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Placed in RL for games and combinatorial optimization, one of 15 directions in Deep reinforcement learning methods.
- Builds on 30 of its 48 references that are in the map.
- First posted on arXiv 8 Aug 2024.

## Placed in

- Deep reinforcement learning methods / [RL for games and combinatorial optimization](https://mlsanity.com/deeprl/rl-for-games-and-combinatorial-optimization/)

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

- [On the Global Convergence Rates of Softmax Policy Gradient Methods](https://mlsanity.com/paper/2005.06392/) (2020)
- [Global Convergence of Policy Gradient Methods to (Almost) Locally Optimal Policies](https://mlsanity.com/paper/1906.08383/) (2019)
- [A Finite Time Analysis of Two Time-Scale Actor Critic Methods](https://mlsanity.com/paper/2005.01350/) (2020)
- [Approximately Solving Mean Field Games via Entropy-Regularized Deep Reinforcement Learning](https://mlsanity.com/paper/2102.01585/) (2021)
- [An Improved Analysis of (Variance-Reduced) Policy Gradient and Natural Policy Gradient Methods](https://mlsanity.com/paper/2211.07937/) (2022)
- [Fictitious Play for Mean Field Games: Continuous Time Analysis and Applications](https://mlsanity.com/paper/2007.03458/) (2020)
- [Stochastic Policy Gradient Methods: Improved Sample Complexity for Fisher-non-degenerate Policies](https://mlsanity.com/paper/2302.01734/) (2023)
- [Concave Utility Reinforcement Learning: the Mean-Field Game Viewpoint](https://mlsanity.com/paper/2106.03787/) (2021)
- [Unified Reinforcement Q-Learning for Mean Field Game and Control Problems](https://mlsanity.com/paper/2006.13912/) (2020)
- [Q-Learning in Regularized Mean-field Games](https://mlsanity.com/paper/2003.12151/) (2020)
- [Scaling up Mean Field Games with Online Mirror Descent](https://mlsanity.com/paper/2103.00623/) (2021)
- [Finite-time analysis of single-timescale actor-critic](https://mlsanity.com/paper/2210.09921/) (2022)
- [Performative Reinforcement Learning](https://mlsanity.com/paper/2207.00046/) (2022)
- [Policy Mirror Ascent for Efficient and Independent Learning in Mean Field Games](https://mlsanity.com/paper/2212.14449/) (2022)
- [A Two-Time-Scale Stochastic Optimization Framework with Applications in Control and Reinforcement Learning](https://mlsanity.com/paper/2109.14756/) (2021)
- [A Small Gain Analysis of Single Timescale Actor Critic](https://mlsanity.com/paper/2203.02591/) (2022)
- [Oracle-free Reinforcement Learning in Mean-Field Games along a Single Sample Path](https://mlsanity.com/paper/2208.11639/) (2022)
- [Finite-Time Complexity of Online Primal-Dual Natural Actor-Critic Algorithm for Constrained Markov Decision Processes](https://mlsanity.com/paper/2110.11383/) (2021)
- [Order-Optimal Regret with Novel Policy Gradient Approaches in Infinite-Horizon Average Reward MDPs](https://mlsanity.com/paper/2404.02108/) (2024)
- [Reinforcement Learning in Non-Stationary Discrete-Time Linear-Quadratic Mean-Field Games](https://mlsanity.com/paper/2009.04350/) (2020)
- [Convergence of Multi-Scale Reinforcement Q-Learning Algorithms for Mean Field Game and Control Problems](https://mlsanity.com/paper/2312.06659/) (2023)
- [Fast Two-Time-Scale Stochastic Gradient Method with Applications in Reinforcement Learning](https://mlsanity.com/paper/2405.09660/) (2024)
- [MF-OMO: An Optimization Formulation of Mean-Field Games](https://mlsanity.com/paper/2206.09608/) (2022)
- [Learning Regularized Monotone Graphon Mean-Field Games](https://mlsanity.com/paper/2310.08089/) (2023)
- [On the Global Convergence of Policy Gradient in Average Reward Markov Decision Processes](https://mlsanity.com/paper/2403.06806/) (2024)
- [When is Mean-Field Reinforcement Learning Tractable and Relevant?](https://mlsanity.com/paper/2402.05757/) (2024)
- [Linear-Quadratic Zero-Sum Mean-Field Type Games: Optimality Conditions and Policy Optimization](https://mlsanity.com/paper/2009.00578/) (2020)
- [Value Iteration Algorithm for Mean-field Games](https://mlsanity.com/paper/1909.01758/) (2019)
- [Convergence to the Mean Field Game Limit: A Case Study](https://mlsanity.com/paper/1806.00817/) (2018)
- [Multiple equilibria in mean-field game models for large oligopolies with strategic complementarities](https://mlsanity.com/paper/2401.17034/) (2024)

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

- [Stochastic Semi-Gradient Descent for Learning Mean Field Games with Population-Aware Function Approximation](https://mlsanity.com/paper/2408.08192/) (2024)
- [Learning in Stackelberg Mean Field Games: A Non-Asymptotic Analysis](https://mlsanity.com/paper/2509.15392/) (2025)
- [Entropy-Regularized Mean-Field Games with Average-Reward Criterion: Span-Seminorm Contractions and Model-Free Learning](https://mlsanity.com/paper/2610.15871/) (2026)

## Abstract (arXiv)

We consider discrete-time stationary mean field games (MFG) with unknown dynamics and design algorithms for finding the equilibrium with finite-time complexity guarantees. Prior solutions to the problem assume either the contraction of a mean field optimality-consistency operator or strict weak monotonicity, which may be overly restrictive. In this work, we introduce a new class of solvable MFGs, named the "fully herding class", which expands the known solvable class of MFGs and for the first time includes problems with multiple equilibria. We propose a direct policy optimization method, Accelerated Single-loop Actor Critic Algorithm for Mean Field Games (ASAC-MFG), that provably finds a global equilibrium for MFGs within this class, under suitable access to a single trajectory of Markovian samples. Different from the prior methods, ASAC-MFG is single-loop and single-sample-path. We establish the finite-time and finite-sample convergence of ASAC-MFG to a mean field equilibrium via new techniques that we develop for multi-time-scale stochastic approximation. We support the theoretical results with illustrative numerical simulations. When the mean field does not affect the transition and reward, a MFG reduces to a Markov decision process (MDP) and ASAC-MFG becomes an actor-critic algorithm for finding the optimal policy in average-reward MDPs, with a sample complexity matching the state-of-the-art. Previous works derive the complexity assuming a contraction on the Bellman operator, which is invalid for average-reward MDPs. We match the rate while removing the untenable assumption through an improved Lyapunov function.