Optimal Learning in Games with Arbitrary Delays: Best-of-Both-Worlds for Self-Play and Adversarial OpponentsResearch Paper
Two players repeatedly playing a zero-sum game with no-regret learning algorithms approach a Nash equilibrium: a social regret of makes the averaged strategies an -approximate equilibrium (Freund–Schapire 1999). Standard algorithms have regret , but optimistic algorithms, which predict the next gradient, reach constant regret, and hence…