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 \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, *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, genera

Stats

• citations0
• S2 citations—
• github stars0
• HF likes0
• heat score0.00
• arxiv keyhuang2024model

Related papers

• Reinforcement Learning For Mean Field Games With Strategic Complementarities (2020)0.00
• Efficient And Scalable Deep Reinforcement Learning For Mean Field Control Games (2024)0.00
• Oracle-free Reinforcement Learning In Mean-field Games Along A Single Sample Path (2022)0.00
• A Single Online Agent Can Efficiently Learn Mean Field Games (2024)0.00
• Reinforcement Learning In Non-stationary Discrete-time Linear-quadratic Mean-field Games (2020)10.07
• Population-aware Online Mirror Descent For Mean-field Games By Deep Reinforcement Learning (2024)0.00
• Approximately Solving Mean Field Games Via Entropy-regularized Deep Reinforcement Learning (2021)0.00
• Deep Reinforcement Learning For Infinite Horizon Mean Field Problems In Continuous Spaces (2023)3.58