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

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.


Published in:
Proceedings of the 35th International Conference on Machine Learning
Presented at:
35th International Conference on Machine Learning (ICML), Stockholm, Sweden, July 10-15, 2018
Year:
2018
Keywords:
Laboratories:




 Record created 2018-02-12, last modified 2019-03-17

Fulltext:
ICML2018-game - Download fulltextPDF
ICML2018-gameAppendix - Download fulltextPDF
Rate this document:

Rate this document:
1
2
3
 
(Not yet reviewed)