Exploiting Approximate Symmetry for Efficient Multi-Agent Reinforcement Learning

Abstract

Mean-field games (MFG) have become significant tools for solving large-scale multi-agent reinforcement learning problems under symmetry. However, the assumptions of access to a known MFG model (which might not be available for real-world games) and of exact symmetry (real-world scenarios often feature heterogeneity) limit the applicability of MFGs. 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 Kirszbraun extensions. Next, we define $\alpha,\beta$-symmetric games, a new class of dynamic games that incorporate approximate permutation invariance. We establish explicit approximation bounds for $\alpha,\beta$-symmetric games, demonstrating that the induced mean-field Nash policy is an approximate Nash of the $N$-player game. We analyze TD learning using sample trajectories of the $N$-player game, permitting learning without using an explicit MFG model or oracle. This is used to show a sample complexity of $\widetilde{\mathcal{O}}(\varepsilon^{-6})$ for $N$-agent monotone extendable games to learn an $\varepsilon$-Nash. Evaluations on benchmarks with thousands of agents support our theory of learning under (approximate) symmetry without explicit MFGs.