Endre søk
RefereraExporteraLink to record
Permanent link

Direct link
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Annet format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annet språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf
A Slingshot Approach to Learning in Monotone Games
KTH, Skolan för elektroteknik och datavetenskap (EECS), Intelligenta system, Reglerteknik.ORCID-id: 0000-0002-7106-3039
(engelsk)Manuskript (preprint) (Annet vitenskapelig)
Abstract [en]

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.

HSV kategori
Identifikatorer
URN: urn:nbn:se:kth:diva-333935OAI: oai:DiVA.org:kth-333935DiVA, id: diva2:1787756
Merknad

QC 20230815

Tilgjengelig fra: 2023-08-14 Laget: 2023-08-14 Sist oppdatert: 2023-08-15bibliografisk kontrollert

Open Access i DiVA

Fulltekst mangler i DiVA

Person

Ariu, Kaito

Søk i DiVA

Av forfatter/redaktør
Ariu, Kaito
Av organisasjonen

Søk utenfor DiVA

GoogleGoogle Scholar

urn-nbn

Altmetric

urn-nbn
Totalt: 66 treff
RefereraExporteraLink to record
Permanent link

Direct link
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Annet format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annet språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf