Abstract
We investigate the exploration-exploitation trade-off in large multiplayer coordination games where agents employ Q-Learning. While Q-Learning is a staple of multi-agent reinforcement learning (MARL), it often suffers from non-convergence and equilibrium selection issues in complex payoff landscapes. By applying dynamical mean-field theory from statistical physics, we characterize a critical exploration rate $T_{crit}$ that ensures convergence to a unique Quantal Response Equilibrium (QRE). Our analysis reveals a phenomenon termed "asymptotic extinction," where a constant fraction of actions are played with zero probability as the game size increases.
Introduction
In multi-agent reinforcement learning, the environment is non-stationary because agents' strategies evolve simultaneously. Q-Learning, which balances exploration (trying new actions) and exploitation (choosing high-reward actions), faces significant challenges in coordination games with multiple fixed points. As the number of players ($p$) and actions ($N$) scales, understanding the stability of these systems becomes critical. This study seeks to identify the "tipping point" of exploration required to guarantee a unique, stable equilibrium in high-dimensional action spaces.
Methodology
The research utilizes the generating-functional method, a technique from the physics of disordered systems, to derive the effective dynamics of a "typical" action in the limit of infinite actions ($N \to \infty$). To ensure generalizability, the authors analyze games with payoff matrices drawn from multivariate Gaussian distributions, allowing for the tuning of payoff alignment via a correlation parameter $\Gamma$. Theoretical results are validated against numerical simulations of games with up to $N=320$ actions across varying player counts ($p=2, 3, 5$).
Asymptotic Extinction and Scaling Laws
A primary finding is asymptotic extinction: in the large-action limit, even with exploration, a constant fraction of actions are effectively abandoned, receiving vanishingly small probability ($o(1/N)$). This suggests that large-scale coordination naturally narrows the effective strategy space. Furthermore, the study identifies that the exploration rate $T$ must be rescaled by $\sqrt{N^{p-1}}$ to maintain meaningful learning dynamics as the action space grows.
Stability and the Critical Exploration Rate
The authors identify a critical exploration rate ($T_{crit}$) above which the system is guaranteed to converge to a unique fixed point. Interestingly, coordination games ($\Gamma > 0$) are harder to stabilize than competitive ones, requiring roughly twice the exploration rate of zero-sum games for perfectly aligned payoffs. In the limit of many players, $T_{crit}$ follows a linear relationship: $T_{crit} \approx (\hat{\Gamma} + 1)\sqrt{e(p-1)}$.
Conclusion
This work provides a rigorous framework for understanding Q-Learning in large-scale multi-agent systems. While the theoretical $T_{crit}$ provides a safe bound for convergence, it assumes an infinite action space; in practice, finite-sized games may converge at slightly lower rates. Future research should explore the implications of these exploration rates on social welfare and the total utility achieved by the coordinating agents.
Summary updated