Research map / Reinforcement learning / MDPs and planning

Model-Based RL for Mean-Field Games is not Statistically Harder than Single-Agent RL

ICML 2024 · Reinforcement learning › MDPs and planning · approach: Function approximation in RL theory · 0 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Introduces Partial Model-Based Eluder Dimension (P-MBED) and a model elimination algorithm with bridge policies showing model-based RL for mean-field games needs samples polynomial in P-MBED, i.e., no harder than single-agent RL up to log|M| factors.

Problem

Sample complexity of model-based RL for finding Nash equilibria in mean-field games with function approximation; prior MBED complexity can be exponential even in the tabular case.

Approach

Define P-MBED as the eluder-type complexity of the single-agent model class obtained by fixing the state density of each mean-field model via a reference policy; combine model elimination with a constructed "bridge policy" that halves the model set each round or yields an approximate NE.

Key results

• P-MBED is bounded by |S||A| in the tabular setting, while MBED can be Omega(exp(|S|)) for some model classes.
• Theorem gives sample complexity tilde-O(H^7/eps^2 (1+L_r H)^2 dim_PE log^3(|M|/delta)) for finding an eps-NE, polynomial in P-MBED and log|M|.
• Learning MFCs can require Omega(exp(|S|)) samples in tabular settings, an exponential separation from MFGs.

Surprising findings

• Learning mean-field control (cooperative) can be exponentially harder than learning mean-field games in the tabular setting.

Limitations

• Main algorithm requires exponential computation over the policy space.
• Bridge-policy construction is non-constructive and computationally expensive.
• Results assume a model class with realizability and Lipschitz continuity and only consider trajectory sampling rather than value-function approximation.

Experimental setup

Datasets: synthetic linear MFG environment

Benchmarks: synthetic linear MFG

Metrics: NE-gap

Baselines: MBED-based algorithm for MFGs

Builds on: MBED (model-based eluder dimension) eluder dimension Multi-Type MFGs

Closest papers by meaning

• Finite-Sample Convergence Bounds for Trust Region Policy Optimization in Mean Field Games (ICML 2025 · similarity 0.90)
• Learning Discrete-Time Major-Minor Mean Field Games (AAAI 2024 · similarity 0.89)
• Bench-MFG: A Benchmark Suite for Learning in Stationary Mean Field Games (NeurIPS 2026 · similarity 0.89)
• Bounded Rationality Equilibrium Learning in Mean Field Games (AAAI 2025 · similarity 0.89)
• Solving Continuous Mean Field Games: Deep Reinforcement Learning for Non-Stationary Dynamics (NeurIPS 2025 · similarity 0.89)
• Incentivize without Bonus: Provably Efficient Model-based Online Multi-agent RL for Markov Games (ICML 2025 · similarity 0.89)