Repository logo

Infoscience

  • English
  • French
Log In
Logo EPFL, École polytechnique fédérale de Lausanne

Infoscience

  • English
  • French
Log In
  1. Home
  2. Academic and Research Output
  3. Conferences, Workshops, Symposiums, and Seminars
  4. Let’s be honest: An optimal no-regret framework for zero-sum games
 
conference paper

Let’s be honest: An optimal no-regret framework for zero-sum games

Asadi Kangarshahi, Ehsan
•
Hsieh, Ya-Ping
•
Sahin, Mehmet Fatih
Show more
2018
Proceedings of the 35th International Conference on Machine Learning
35th International Conference on Machine Learning (ICML)

We revisit the problem of solving two-player zero- sum games in the decentralized setting. We pro- pose a simple algorithmic framework that simulta- neously achieves the best rates for honest regret as well as adversarial regret, and in addition resolves the open problem of removing the logarithmic terms in convergence to the value of the game. We achieve this goal in three steps. First, we provide a novel analysis of the optimistic mirror descent (OMD), showing that it can be modified to guarantee fast convergence for both honest re- gret and value of the game, when the players are playing collaboratively. Second, we propose a new algorithm, dubbed as robust optimistic mir- ror descent (ROMD), which attains optimal ad- versarial regret without knowing the time horizon beforehand. Finally, we propose a simple signal- ing scheme, which enables us to bridge OMD and ROMD to achieve the best of both worlds. Numerical examples are presented to support our theoretical claims and show that our non-adaptive ROMD algorithm can be competitive to OMD with adaptive step-size selection.

  • Files
  • Details
  • Metrics
Type
conference paper
Author(s)
Asadi Kangarshahi, Ehsan
Hsieh, Ya-Ping
Sahin, Mehmet Fatih
Cevher, Volkan  orcid-logo
Date Issued

2018

Published in
Proceedings of the 35th International Conference on Machine Learning
Total of pages

9

Series title/Series vol.

Not Applicable

Subjects

Zero-Sum Games

•

No-Regret Algorithms

•

ml-ai

Editorial or Peer reviewed

REVIEWED

Written at

EPFL

EPFL units
LIONS  
Event nameEvent placeEvent date
35th International Conference on Machine Learning (ICML)

Stockholm, Sweden

July 10-15, 2018

Available on Infoscience
February 12, 2018
Use this identifier to reference this record
https://infoscience.epfl.ch/handle/20.500.14299/144783
Logo EPFL, École polytechnique fédérale de Lausanne
  • Contact
  • infoscience@epfl.ch

  • Follow us on Facebook
  • Follow us on Instagram
  • Follow us on LinkedIn
  • Follow us on X
  • Follow us on Youtube
AccessibilityLegal noticePrivacy policyCookie settingsEnd User AgreementGet helpFeedback

Infoscience is a service managed and provided by the Library and IT Services of EPFL. © EPFL, tous droits réservés