Model-Based RL for Mean-Field Games is not Statistically Harder than Single-Agent RL
<|reference_start|>Model-Based RL for Mean-Field Games is not Statistically Harder than Single-Agent RL: 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 \citet{huang2023statistical}. 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, \emph{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.<|reference_end|>
@article{huang2024model-based,
    title={Model-Based RL for Mean-Field Games is not Statistically Harder than
  Single-Agent RL},
    author={Jiawei Huang, Niao He, Andreas Krause},
    journal={arXiv preprint arXiv:2402.05724},
    year={2024},
    archivePrefix={arXiv},
    eprint={2402.05724},
    primaryClass={cs.LG cs.AI cs.GT stat.ML}
}