# Exploiting Approximate Symmetry for Efficient Multi-Agent Reinforcement Learning

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 30 of its 60 references that are in the map.
- First posted on arXiv 27 Aug 2024.

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

- [Proximal Policy Optimization Algorithms](https://mlsanity.com/paper/1707.06347/) (2017)
- [High-Dimensional Continuous Control Using Generalized Advantage Estimation](https://mlsanity.com/paper/1506.02438/) (2015)
- [The StarCraft Multi-Agent Challenge](https://mlsanity.com/paper/1902.04043/) (2019)
- [On the Global Convergence Rates of Softmax Policy Gradient Methods](https://mlsanity.com/paper/2005.06392/) (2020)
- [Provably Efficient Exploration in Policy Optimization](https://mlsanity.com/paper/1912.05830/) (2019)
- [Policy Mirror Descent for Reinforcement Learning: Linear Convergence, New Sampling Complexity, and Generalized Problem Classes](https://mlsanity.com/paper/2102.00135/) (2021)
- [Global Convergence of Multi-Agent Policy Gradient in Markov Potential Games](https://mlsanity.com/paper/2106.01969/) (2021)
- [Approximately Solving Mean Field Games via Entropy-Regularized Deep Reinforcement Learning](https://mlsanity.com/paper/2102.01585/) (2021)
- [Fictitious Play for Mean Field Games: Continuous Time Analysis and Applications](https://mlsanity.com/paper/2007.03458/) (2020)
- [The Complexity of Markov Equilibrium in Stochastic Games](https://mlsanity.com/paper/2204.03991/) (2022)
- [Q-Learning in Regularized Mean-field Games](https://mlsanity.com/paper/2003.12151/) (2020)
- [Scalable Deep Reinforcement Learning Algorithms for Mean Field Games](https://mlsanity.com/paper/2203.11973/) (2022)
- [Markov-Nash Equilibria in Mean-Field Games with Discounted Cost](https://mlsanity.com/paper/1612.07878/) (2016)
- [Generalization in Mean Field Games by Learning Master Policies](https://mlsanity.com/paper/2109.09717/) (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)
- [Breaking the Curse of Many Agents: Provable Mean Embedding Q-Iteration for Mean-Field Reinforcement Learning](https://mlsanity.com/paper/2006.11917/) (2020)
- [Oracle-free Reinforcement Learning in Mean-Field Games along a Single Sample Path](https://mlsanity.com/paper/2208.11639/) (2022)
- [On the Statistical Efficiency of Mean-Field Reinforcement Learning with General Function Approximation](https://mlsanity.com/paper/2305.11283/) (2023)
- [Finite State Graphon Games with Applications to Epidemics](https://mlsanity.com/paper/2106.07859/) (2021)
- [Model-Based RL for Mean-Field Games is not Statistically Harder than Single-Agent RL](https://mlsanity.com/paper/2402.05724/) (2024)
- [Graphon games: A statistical framework for network games and interventions](https://mlsanity.com/paper/1802.00080/) (2018)
- [Mean Field Control and Mean Field Game Models with Several Populations](https://mlsanity.com/paper/1810.00783/) (2018)
- [MFGLib: A Library for Mean-Field Games](https://mlsanity.com/paper/2304.08630/) (2023)
- [Markov α-Potential Games](https://mlsanity.com/paper/2305.12553/) (2023)
- [Master equation of discrete time graphon mean field games and teams](https://mlsanity.com/paper/2001.05633/) (2020)
- [Multi-population Mean Field Games with Multiple Major Players: Application to Carbon Emission Regulations](https://mlsanity.com/paper/2309.16477/) (2023)

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

- [Operator Learning for Families of Finite-State Mean-Field Games](https://mlsanity.com/paper/2602.13169/) (2026)
- [Last Iterate Convergence in Monotone Mean Field Games](https://mlsanity.com/paper/2410.05127/) (2024)

## Abstract (arXiv)

Mean-field games (MFG) have become significant tools for solving large-scale multi-agent reinforcement learning problems under symmetry. However, the assumption of exact symmetry limits the applicability of MFGs, as real-world scenarios often feature inherent heterogeneity. Furthermore, most works on MFG assume access to a known MFG model, which might not be readily available for real-world finite-agent games. In this work, we broaden the applicability of MFGs by providing a methodology to extend any finite-player, possibly asymmetric, game to an "induced MFG". First, we prove that N-player dynamic games can be symmetrized and smoothly extended to the infinite-player continuum via explicit Kirszbraun extensions. Next, we propose the notion of α,β-symmetric games, a new class of dynamic population games that incorporate approximate permutation invariance. For α,β-symmetric games, we establish explicit approximation bounds, demonstrating that a Nash policy of the induced MFG is an approximate Nash of the N-player dynamic game. We show that TD learning converges up to a small bias using trajectories of the N-player game with finite-sample guarantees, permitting symmetrized learning without building an explicit MFG model. Finally, for certain games satisfying monotonicity, we prove a sample complexity of widetildeO(varepsilon-6) for the N-agent game to learn an varepsilon-Nash up to symmetrization bias. Our theory is supported by evaluations on MARL benchmarks with thousands of agents.