kth.sePublications
Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
A Slingshot Approach to Learning in Monotone Games
KTH, School of Electrical Engineering and Computer Science (EECS), Intelligent systems, Decision and Control Systems (Automatic Control).ORCID iD: 0000-0002-7106-3039
(English)Manuscript (preprint) (Other academic)
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.

National Category
Computer and Information Sciences
Identifiers
URN: urn:nbn:se:kth:diva-333935OAI: oai:DiVA.org:kth-333935DiVA, id: diva2:1787756
Note

QC 20230815

Available from: 2023-08-14 Created: 2023-08-14 Last updated: 2023-08-15Bibliographically approved

Open Access in DiVA

No full text in DiVA

Authority records

Ariu, Kaito

Search in DiVA

By author/editor
Ariu, Kaito
By organisation
Decision and Control Systems (Automatic Control)
Computer and Information Sciences

Search outside of DiVA

GoogleGoogle Scholar

urn-nbn

Altmetric score

urn-nbn
Total: 52 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf