Fast and Furious Symmetric Learning in Zero-Sum Games: Gradient Descent as Fictitious Play
Preprint
Abstract
This paper investigates the sublinear regret guarantees of two non-no-regret algorithms in zero-sum games: Fictitious Play, and Online Gradient Descent with constant stepsizes. In general adversarial online learning settings, both algorithms may exhibit instability and linear regret due to no regularization (Fictitious Play) or small amounts of regularization (Gradient Descent). However, their ability to obtain tighter regret bounds in two-player zero-sum games is less understood. In this work, we obtain strong new regret guarantees for both algorithms on a class of symmetric zero-sum games that generalize the classic three-strategy Rock-Paper-Scissors to a weighted, n-dimensional regime. Under symmetric initializations of the players' strategies, we prove that Fictitious Play with any tiebreaking rule has $O(\sqrt{T})$ regret, establishing a new class of games for which Karlin's Fictitious Play conjecture holds. Moreover, by leveraging a connection between the geometry of the iterates of Fictitious Play and Gradient Descent in the dual space of payoff vectors, we prove that Gradient Descent, for almost all symmetric initializations, obtains a similar $O(\sqrt{T})$ regret bound when its stepsize is a sufficiently large constant. For Gradient Descent, this establishes the first "fast and furious" behavior (i.e., sublinear regret without time-vanishing stepsizes) for zero-sum games larger than 2x2.
Keywords
All Related Versions
This publication has 22 references indexed in Scilit:
- Family of chaotic maps from game theoryDynamical Systems, 2020
- Cycle frequency in standard Rock–Paper–Scissors games: Evidence from experimental economicsPhysica A: Statistical Mechanics and its Applications, 2013
- Hamiltonian flows with random-walk behaviour originating from zero-sum games and fictitious playNonlinearity, 2011
- Fictitious play in 2×n gamesJournal of Economic Theory, 2005
- Volunteering leads to rock–paper–scissors dynamics in a public goods gameNature, 2003
- Fictitious play in 'one-against-all' multi-player gamesEconomic Theory, 1999
- Adaptive Game Playing Using Multiplicative WeightsGames and Economic Behavior, 1999
- On the Rate of Convergence of Continuous-Time Fictitious PlayGames and Economic Behavior, 1998
- A2 ×2Game without the Fictitious Play PropertyGames and Economic Behavior, 1996
- Fictitious Play Property for Games with Identical InterestsJournal of Economic Theory, 1996