Research map / Optimization / Nonconvex and smooth optimization
Last-iterate Convergence in Regularized Graphon Mean Field Game
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.
Gives the first last-iterate convergence rates for regularized mirror descent in monotone graphon mean-field games, under full information, tabular bandit, and linear bandit feedback.
Problem
Last-iterate convergence of discrete-time algorithms to Nash equilibrium in graphon mean-field games (GMFG), especially under bandit feedback where exact costs and transitions are unknown.
Approach
Applies KL-regularized online mirror descent to monotone GMFGs and proves last-iterate convergence (in KL to the NE policy weighted by NE state distribution), with importance-sampling gradient estimators and value estimation under bandit feedback, and ridge-regression-based value estimation in linear GMFGs.
Key results
- Tabular monotone GMFG under bandit feedback: last-iterate rate O(T^{-1/4}) for the KL-based distance D(pi_t).
- With exact cost and transition knowledge, the rate improves to O(T^{-1}), i.e., D(pi_{t+1}) <= H^3/(lambda t).
- Linear GMFG under bandit feedback achieves last-iterate rate O(T^{-1/5}); mirror descent matches fictitious play in two of four environments.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use exact cost and transition functions instead of bandit feedback | Tabular mirror descent for monotone GMFG · Tabular monotone GMFG | last-iterate convergence rate: O(T^{-1/4}) -> O(T^{-1}) | Helped |
Surprising findings
- Mirror descent matches or beats fictitious play in only two of four environments, despite much lower computational cost per iteration.
- The bandit-feedback tabular rate (T^{-1/4}) is derived with a learning rate schedule that is not the one used in the experiments (fixed eta=0.1, gamma=0.1).
Limitations
- Convergence is measured by a weighted KL metric and requires a weakly monotone (strictly monotone for uniqueness) game assumption.
- Experiments use fixed learning and exploration rates rather than the theoretical schedules, and only four small OpenSpiel environments are tested.
Experimental setup
Benchmarks: Crowd Modeling Crowd Avoidance Predator Prey Periodic Aversion
Metrics: exploitability
Baselines: fictitious play
Builds on: mirror descent fictitious play graphon mean field games
Closest papers by meaning
- Last Iterate Convergence in Monotone Mean Field Games (NeurIPS 2025 · similarity 0.93)
- Near-Optimal Last-Iterate Convergence for Zero-Sum Games with Bandit Feedback and Opponent Actions (NeurIPS 2026 · similarity 0.89)
- Learning Mean Field Games on Sparse Graphs: A Hybrid Graphex Approach (ICLR 2024 · similarity 0.89)
- From Average-Iterate to Last-Iterate Convergence in Games: A Reduction and Its Applications (NeurIPS 2025 · similarity 0.89)
- Graphon Mean Field Games with a Representative Player: Analysis and Learning Algorithm (ICML 2024 · similarity 0.88)
- Last-Iterate Convergence Properties of Regret-Matching Algorithms in Games (ICLR 2025 · similarity 0.88)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.