On the Impossibility of Convergence of Mixed Strategies with Optimal No-Regret Learning: Mean-Based Monotonic Play Cannot Converge Almost Surely to the Nash Equilibrium of a Competitive 2×2 GameResearch Paper
No-regret algorithms such as multiplicative weights and online mirror descent are the standard model of learning agents in repeated games. A classical fact is that when two such agents play a zero-sum game, the time-average of their mixed strategies converges to a Nash equilibrium (Freund and Schapire, 1999), and in general games the average play converges…