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
Last-Iterate Convergence with Full and Noisy Feedback in Two-Player Zero-Sum Games
CyberAgent, Inc..
KTH, School of Electrical Engineering and Computer Science (EECS), Intelligent systems, Decision and Control Systems (Automatic Control). CyberAgent, Inc..ORCID iD: 0000-0002-7106-3039
University of Electro-Communications.
Show others and affiliations
2023 (English)In: Proceedings of The 26th International Conference on Artificial Intelligence and Statistics, MLResearchPress , 2023, Vol. 206, p. 7999-8028Conference paper, Published paper (Refereed)
Abstract [en]

This paper proposes Mutation-Driven Multiplicative Weights Update (M2WU) for learning an equilibrium in two-player zero-sum normal-form games and proves that it exhibits the last-iterate convergence property in both full and noisy feedback settings. In the former, players observe their exact gradient vectors of the utility functions. In the latter, they only observe the noisy gradient vectors. Even the celebrated Multiplicative Weights Update (MWU) and Optimistic MWU (OMWU) algorithms may not converge to a Nash equilibrium with noisy feedback. On the contrary, M2WU exhibits the last-iterate convergence to a stationary point near a Nash equilibrium in both feedback settings. We then prove that it converges to an exact Nash equilibrium by iteratively adapting the mutation term. We empirically confirm that M2WU outperforms MWU and OMWU in exploitability and convergence rates.

Place, publisher, year, edition, pages
MLResearchPress , 2023. Vol. 206, p. 7999-8028
National Category
Computer and Information Sciences
Identifiers
URN: urn:nbn:se:kth:diva-333927Scopus ID: 2-s2.0-85162832254OAI: oai:DiVA.org:kth-333927DiVA, id: diva2:1787738
Conference
AISTATS 2023, International Conference on Artificial Intelligence and Statistics, 25-27 April 2023, Palau de Congressos, Valencia, Spain
Note

QC 20230815

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

Open Access in DiVA

No full text in DiVA

Other links

ScopusProceedings

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: 62 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