Fast Convergence of Regularized Learning in Games II: If Every Player Runs Optimistic FTRL with Step Size (n−1)^{−1/2}T^{−1/4}, Each Player's Regret Is at Most (R+4)√(n−1)·T^{1/4}Research Paper
When every participant in a repeated game runs a no-regret learning algorithm, the time-averaged play converges to a coarse correlated equilibrium, and in smooth games the average welfare approaches the price-of-anarchy guarantee. These facts are a standard justification for equilibrium predictions in auctions, routing and markets, where agents learn rather…