Abstract
This study identifies and analyzes the phenomenon of asymptotic extinction in large multi-agent coordination games. By applying tools from statistical physics and dynamical systems, the authors demonstrate that as the action space grows, a constant fraction of possible actions are effectively abandoned by Q-learning agents. The research derives a theoretical "critical exploration rate" ($T_{crit}$) that guarantees convergence to a unique stable equilibrium, providing a roadmap for managing the exploration-exploitation trade-off in complex multi-agent environments.
Introduction: The Challenges of Large-Scale MARL
In Multi-Agent Reinforcement Learning (MARL), agents typically employ Q-learning to navigate strategic environments. However, these systems often suffer from non-convergence (oscillations or chaos) and poor equilibrium selection, where agents settle on sub-optimal outcomes. While these issues are well-documented in competitive zero-sum games, the behavior in large coordination games—where players' interests are aligned—has remained poorly understood. Specifically, it was unclear how many actions remain viable as the number of possible actions ($N$) becomes very large.
Methodology
The authors utilize a sophisticated toolkit to analyze these dynamics:
- Continuous Q-Learning: Discrete learning steps are modeled as continuous-time differential equations to study long-term stability.
- Dynamical Mean-Field Theory: Borrowing from disordered systems theory in physics, the authors analyze "typical" game behavior using payoffs drawn from multivariate Gaussian distributions.
- Alignment Parameter ($\Gamma$): A correlation parameter controls the degree of payoff alignment, ranging from competitive ($\Gamma < 0$) to perfectly coordinated ($\Gamma > 0$).
The Phenomenon of Asymptotic Extinction
A striking insight from this work is that in the large-game limit ($N \to \infty$), a non-zero fraction of actions are played with a frequency of $o(1/N)$. Effectively, these actions "go extinct," mirroring biological evolution where less-fit species are pruned from the population. This suggests that even with high exploration, the equilibrium of a large coordination game naturally pushes toward the boundary of the action simplex.
Stability Thresholds and Scaling Laws
The research successfully maps the "stability boundary" for these games. To the right of this boundary (high exploration $T$), Q-learning always converges to a unique point. To the left (low exploration), the system can fall into multiple fixed points or limit cycles.
Key findings regarding these thresholds include:
- The Cost of Coordination: In perfectly aligned games, the exploration rate required for stability is roughly twice as high as in zero-sum games.
- Linear Scaling: The critical exploration rate follows a clean relationship: $T_{crit} \approx (\hat{\Gamma} + 1)\sqrt{e(p-1)}$, where $p$ is the number of players.
Conclusion and Future Directions
Numerical simulations with up to $N=160$ actions confirm that these theoretical $N \to \infty$ predictions hold remarkably well for finite games. While this work establishes the $T$ required for stability, the authors note that this may not be the same $T$ that maximizes total social welfare. Future research will investigate heterogeneous agents and the optimization of exploration rates for specific objective functions, such as system efficiency or minimum utility.
Summary updated