On the Impossibility of Convergence of Mixed Strategies with No Regret Learning
arXiv:2012.02125
Abstract
We study the limiting behavior of the mixed strategies that result from optimal no-regret learning strategies in a repeated game setting where the stage game is any 2 by 2 competitive game. We consider optimal no-regret algorithms that are mean-based and monotonic in their argument. We show that for any such algorithm, the limiting mixed strategies of the players cannot converge almost surely to any Nash equilibrium. This negative result is also shown to hold under a broad relaxation of these assumptions, including popular variants of Online-Mirror-Descent with optimism and/or adaptive step-sizes. Finally, we conjecture that the monotonicity assumption can be removed, and provide partial evidence for this conjecture. Our results identify the inherent stochasticity in players' realizations as a critical factor underlying this divergence in outcomes between using the opponent's mixtures and realizations to make updates.
arXiv comment47 pages, 12 figures
References in corpus (8)
- Online Learning with Predictable Sequences
- Optimistic mirror descent in saddle-point problems: Going the extra (gradient) mile
- Fast Convergence of Regularized Learning in Games
- Learning in Games: Robustness of Fast Convergence
- Last-iterate convergence rates for min-max optimization
- Simultaneous Model Selection and Optimization through Parameter-free Stochastic Learning
- Last iterate convergence in no-regret learning: constrained min-max optimization for convex-concave landscapes
- Smooth Calibration, Leaky Forecasts, Finite Recall, and Nash Dynamics