The Long-Run Distribution of Regularized Learning in Non-Concave Games: A Large Deviations Approach

In this paper, we investigate the long-run behavior of discounted regularized learning with stochastic gradient feedback in general, non-concave games. Specifically, we focus on a family of implicitly regularized exponential / multiplicative weight update schemes, and we seek to determine which actions\textemdash or, more generally, which recurrent patterns of play\textemdash are more likely to arise in the long run. We approach this question through the lens of large deviations theory and randomly perturbed dynamical systems, and we obtain a precise characterization of the distribution of the process: in the long run, it follows a Boltzmann-Gibbs law with temperature equal to the method's step-size, and energy levels determined by the game and the statistics of the noise. Concretely, we show that the distribution of play concentrates exponentially around the dynamics' internally chain transitive (ICT) sets - i.e., irreducible invariant sets containing no smaller attractors - and the probability of visiting such a set depends exponentially on its energy. As a result, unstable ICT sets are exponentially less likely to be visited than stable ones, and the sequence of play is exponentially concentrated around the problem's ``ground state'', where energy is minimized. In this manner, learning acts as a selection mechanism: with exponentially high probability, the ground state is the only outcome observed in the long run, even in the presence of multiple equilibria and other attractors.