Scale-Invariant Fast Convergence in Games
Preprint
Abstract
Scale-invariance in games has recently emerged as a widely valued desirable property. Yet, almost all fast convergence guarantees in learning in games require prior knowledge of the utility scale. To address this, we develop learning dynamics that achieve fast convergence while being both scale-free, requiring no prior information about utilities, and scale-invariant, remaining unchanged under positive rescaling of utilities. For two-player zero-sum games, we obtain scale-free and scale-invariant dynamics with external regret bounded by $\tilde{O}(A_{\mathrm{diff}})$, where $A_{\mathrm{diff}}$ is the payoff range, which implies an $\tilde{O}(A_{\mathrm{diff}} / T)$ convergence rate to Nash equilibrium after $T$ rounds. For multiplayer general-sum games with $n$ players and $m$ actions, we obtain scale-free and scale-invariant dynamics with swap regret bounded by $O(U_{\mathrm{max}} \log T)$, where $U_{\mathrm{max}}$ is the range of the utilities, ignoring the dependence on the number of players and actions. This yields an $O(U_{\mathrm{max}} \log T / T)$ convergence rate to correlated equilibrium. Our learning dynamics are based on optimistic follow-the-regularized-leader with an adaptive learning rate that incorporates the squared path length of the opponents' gradient vectors, together with a new stopping-time analysis that exploits negative terms in regret bounds without scale-dependent tuning. For general-sum games, scale-free learning is enabled also by a technique called doubling clipping, which clips observed gradients based on past observations.
Keywords
All Related Versions
This publication has 9 references indexed in Scilit:
- Human-level play in the game ofDiplomacyby combining language models with strategic reasoningScience, 2022
- Scale-free online learningTheoretical Computer Science, 2018
- DeepStack: Expert-level artificial intelligence in heads-up no-limit pokerScience, 2017
- Heads-up limit hold’em poker is solvedScience, 2015
- Improved Second-Order Bounds for Prediction with Expert AdviceLecture Notes in Computer Science, 2005
- A Simple Adaptive Procedure Leading to Correlated EquilibriumEconometrica, 2000
- Adaptive Game Playing Using Multiplicative WeightsGames and Economic Behavior, 1999
- Interior-Point Polynomial Algorithms in Convex Programming1994
- Subjectivity and correlation in randomized strategiesJournal of Mathematical Economics, 1974