# Reinforcement Learning for SBM Graphon Games with Re-Sampling

arXiv: https://arxiv.org/abs/2310.16326 · HTML: https://mlsanity.com/paper/2310.16326/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 23 of its 37 references that are in the map.
- First posted on arXiv 25 Oct 2023.

## Builds on (most cited first, 23 of 23)

- [Playing Atari with Deep Reinforcement Learning](https://mlsanity.com/paper/1312.5602/) (2013)
- [Deep Reinforcement Learning with Double Q-learning](https://mlsanity.com/paper/1509.06461/) (2015)
- [Community Detection and Stochastic Block Models](https://mlsanity.com/paper/1703.10146/) (2017)
- [A Theory of Regularized Markov Decision Processes](https://mlsanity.com/paper/1901.11275/) (2019)
- [Fast Global Convergence of Natural Policy Gradient Methods with Entropy Regularization](https://mlsanity.com/paper/2007.06558/) (2020)
- [Policy Mirror Descent for Reinforcement Learning: Linear Convergence, New Sampling Complexity, and Generalized Problem Classes](https://mlsanity.com/paper/2102.00135/) (2021)
- [Learning in Mean Field Games: A Survey](https://mlsanity.com/paper/2205.12944/) (2022)
- [Q-Learning in Regularized Mean-field Games](https://mlsanity.com/paper/2003.12151/) (2020)
- [Simple and optimal methods for stochastic variational inequalities, I: operator extrapolation](https://mlsanity.com/paper/2011.02987/) (2020)
- [Scaling up Mean Field Games with Online Mirror Descent](https://mlsanity.com/paper/2103.00623/) (2021)
- [Learning Graphon Mean Field Games and Approximate Nash Equilibria](https://mlsanity.com/paper/2112.01280/) (2021)
- [Multi Type Mean Field Reinforcement Learning](https://mlsanity.com/paper/2002.02513/) (2020)
- [Policy Mirror Ascent for Efficient and Independent Learning in Mean Field Games](https://mlsanity.com/paper/2212.14449/) (2022)
- [A General Framework for Learning Mean-Field Games](https://mlsanity.com/paper/2003.06069/) (2020)
- [Simple and optimal methods for stochastic variational inequalities, II: Markovian noise and policy evaluation in reinforcement learning](https://mlsanity.com/paper/2011.08434/) (2020)
- [Neural Temporal-Difference and Q-Learning Provably Converge to Global Optima](https://mlsanity.com/paper/1905.10027/) (2019)
- [Oracle-free Reinforcement Learning in Mean-Field Games along a Single Sample Path](https://mlsanity.com/paper/2208.11639/) (2022)
- [Learning Sparse Graphon Mean Field Games](https://mlsanity.com/paper/2209.03880/) (2022)
- [Stochastic Graphon Games: I. The Static Case](https://mlsanity.com/paper/1911.10664/) (2019)
- [Graphon Mean Field Games and the GMFG Equations](https://mlsanity.com/paper/2008.10216/) (2020)
- [Finite State Graphon Games with Applications to Epidemics](https://mlsanity.com/paper/2106.07859/) (2021)
- [Linear Quadratic Graphon Field Games](https://mlsanity.com/paper/2006.03964/) (2020)
- [Model Free Reinforcement Learning Algorithm for Stationary Mean field Equilibrium for Multiple Types of Agents](https://mlsanity.com/paper/2012.15377/) (2020)

## Built on by (most cited first, 1 of 1)

- [Policy Optimization for Continuous-time Linear-Quadratic Graphon Mean Field Games](https://mlsanity.com/paper/2506.05894/) (2025)

## Abstract (arXiv)

The Mean-Field approximation is a tractable approach for studying large population dynamics. However, its assumption on homogeneity and universal connections among all agents limits its applicability in many real-world scenarios. Multi-Population Mean-Field Game (MP-MFG) models have been introduced in the literature to address these limitations. When the underlying Stochastic Block Model is known, we show that a Policy Mirror Ascent algorithm finds the MP-MFG Nash Equilibrium. In more realistic scenarios where the block model is unknown, we propose a re-sampling scheme from a graphon integrated with the finite N-player MP-MFG model. We develop a novel learning framework based on a Graphon Game with Re-Sampling (GGR-S) model, which captures the complex network structures of agents' connections. We analyze GGR-S dynamics and establish the convergence to dynamics of MP-MFG. Leveraging this result, we propose an efficient sample-based N-player Reinforcement Learning algorithm for GGR-S without population manipulation, and provide a rigorous convergence analysis with finite sample guarantee.