Optimism Without Regularization: Constant Regret in Zero-Sum Games
This provides new evidence on fast learning in games for researchers in game theory and online learning, though it is incremental as it extends known results to an unregularized setting.
The paper tackles the problem of achieving constant regret in two-player zero-sum games without regularization, showing that Optimistic Fictitious Play obtains only constant regret for two-strategy games, with a regret lower bound of Ω(√T) for Alternating Fictitious Play.
This paper studies the optimistic variant of Fictitious Play for learning in two-player zero-sum games. While it is known that Optimistic FTRL -- a regularized algorithm with a bounded stepsize parameter -- obtains constant regret in this setting, we show for the first time that similar, optimal rates are also achievable without regularization: we prove for two-strategy games that Optimistic Fictitious Play (using any tiebreaking rule) obtains only constant regret, providing surprising new evidence on the ability of non-no-regret algorithms for fast learning in games. Our proof technique leverages a geometric view of Optimistic Fictitious Play in the dual space of payoff vectors, where we show a certain energy function of the iterates remains bounded over time. Additionally, we also prove a regret lower bound of $Ω(\sqrt{T})$ for Alternating Fictitious Play. In the unregularized regime, this separates the ability of optimism and alternation in achieving $o(\sqrt{T})$ regret.