Model-Based RL for Mean-Field Games Is Not Statistically Harder than Single-Agent RL

Abstract

We study the sample complexity of reinforcement learning (RL) in Mean-Field Games (MFGs) with model-based function approximation that requires strategic exploration to find a Nash Equilibrium policy. We introduce the Partial Model-Based Eluder Dimension (P-MBED), a more effective notion to characterize the model class complexity. Notably, P-MBED measures the complexity of the single-agent model class converted from the given mean-field model class, and potentially, can be exponentially lower than the MBED proposed by Huang et al. (2024). We contribute a model elimination algorithm featuring a novel exploration strategy and establish sample complexity results polynomial w.r.t. P-MBED. Crucially, our results reveal that, under the basic realizability and Lipschitz continuity assumptions, learning Nash Equilibrium in MFGs is no more statistically challenging than solving a logarithmic number of single-agent RL problems. We further extend our results to Multi-Type MFGs, generalizing from conventional MFGs and involving multiple types of agents. This extension implies statistical tractability of a broader class of Markov Games through the efficacy of mean-field approximation. Finally, inspired by our theoretical algorithm, we present a heuristic approach with improved computational efficiency and empirically demonstrate its effectiveness.

Cite

Text

Huang et al. "Model-Based RL for Mean-Field Games Is Not Statistically Harder than Single-Agent RL." International Conference on Machine Learning, 2024.

Markdown

[Huang et al. "Model-Based RL for Mean-Field Games Is Not Statistically Harder than Single-Agent RL." International Conference on Machine Learning, 2024.](https://mlanthology.org/icml/2024/huang2024icml-modelbased/)

BibTeX

@inproceedings{huang2024icml-modelbased,
  title     = {{Model-Based RL for Mean-Field Games Is Not Statistically Harder than Single-Agent RL}},
  author    = {Huang, Jiawei and He, Niao and Krause, Andreas},
  booktitle = {International Conference on Machine Learning},
  year      = {2024},
  pages     = {19816-19870},
  volume    = {235},
  url       = {https://mlanthology.org/icml/2024/huang2024icml-modelbased/}
}