A Slingshot Approach to Learning in Monotone Games

• In this paper, we address the problem of computing equilibria in monotone games.The traditional Follow the Regularized Leader algorithms fail to converge to anequilibrium even in two-player zero-sum games. Although optimistic versions ofthese algorithms have been proposed with last-iterate convergence guarantees, theyrequire noiseless gradient feedback. To overcome this limitation, we present a novelframework that achieves last-iterate convergence even in the presence of noise. Ourkey idea involves perturbing or regularizing the payoffs or utilities of the games.This perturbation serves to pull the current strategy to an anchored strategy, whichwe refer to as a slingshot strategy. First, we establish the convergence rates of ourframework to a stationary point near an equilibrium, regardless of the presenceor absence of noise. Next, we introduce an approach to periodically update theslingshot strategy with the current strategy. We interpret this approach as a proximalpoint method and demonstrate its last-iterate convergence. Our framework iscomprehensive, incorporating existing payoff-regularized algorithms and enablingthe development of new algorithms with last-iterate convergence properties. Finally,we show that our algorithms, based on this framework, empirically exhibit fasterconvergence.

Ämnesord

NATURVETENSKAP  -- Data- och informationsvetenskap (hsv//swe)

NATURAL SCIENCES  -- Computer and Information Sciences (hsv//eng)

Publikations- och innehållstyp

vet (ämneskategori)

ovr (ämneskategori)