Optimism Without Regularization: Constant Regret in Zero-Sum Games
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 $\Omega(\sqrt{T})$ for Alternating Fictitious Play. In the unregularized regime, this separates the ability of optimism and alternation in achieving $o(\sqrt{T})$ regret.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Fast and Furious Symmetric Learning in Zero-Sum Games: Gradient Descent as Fictitious Play
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 sett…
On the Dynamic Regret of Following the Regularized Leader: Optimism with History Pruning
We revisit the Follow the Regularized Leader (FTRL) framework for Online Convex Optimization (OCO) over compact sets, focusing on achieving dynamic regret guarantees. Prior work has highlighted the framework's limitation…
Cautious Optimism: A Meta-Algorithm for Near-Constant Regret in General Games
Recent work [Soleymani et al., 2025] introduced a variant of Optimistic Multiplicative Weights Updates (OMWU) that adaptively controls the learning pace in a dynamic, non-monotone manner, achieving new state-of-the-art r…
Randomised Optimism via Competitive Co-Evolution for Matrix Games with Bandit Feedback
Learning in games is a fundamental problem in machine learning and artificial intelligence, with numerous applications~\citep{silver2016mastering,schrittwieser2020mastering}. This work investigates two-player zero-sum ma…
Evolutionary AlgorithmsEntropic Risk-Sensitive Reinforcement Learning: A Meta Regret Framework with Function Approximation
We study risk-sensitive reinforcement learning with the entropic risk measure and function approximation. We consider the finite-horizon episodic MDP setting, and propose a meta algorithm based on value iteration. We the…
Efficient Explorationreinforcement-learningReinforcement Learning (RL)