Scale-Free Fast Convergence in Games

Scale-freeness in games, that is, invariance of learning dynamics under positive rescaling of utilities, has emerged as a desirable property. Yet, almost all fast convergence guarantees in learning in games require prior knowledge of the utility scale. To address this, we develop scale-free learning dynamics that achieve fast convergence without any prior information about utilities. For two-player zero-sum games, we obtain such 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, we obtain such dynamics with swap regret bounded by $O(U_{\max }\sqrt{\log T})$, where $U_{\max }$ is the utility scale and the dependence on the number of players and actions is ignored. This bound yields an $O(U_{\max }\sqrt{\log T}/T)$ convergence rate to correlated equilibrium. Our learning dynamics are based on optimistic follow-the-regularized-leader with adaptive learning rates, and our analyses exploit negative terms in regret bounds without scale-dependent tuning. Specifically, for two-player zero-sum games, we introduce a new analysis based on a stopping time, and for general-sum games, we combine a hybrid regularizer and clipped utilities based on past observations with a new analysis of the time-varying negative terms.