Timezone: »

 
Poster
Let’s be Honest: An Optimal No-Regret Framework for Zero-Sum Games
Ehsan Asadi Kangarshahi · Ya-Ping Hsieh · Mehmet Fatih Sahin · Volkan Cevher

Thu Jul 12 09:15 AM -- 12:00 PM (PDT) @ Hall B #58
in Posters Thu »

We revisit the problem of solving two-player zero-sum games in the decentralized setting. We propose a simple algorithmic framework that simultaneously 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 regret and value of the game, when the players are playing collaboratively. Second, we propose a new algorithm, dubbed as robust optimistic mirror descent (ROMD), which attains optimal adversarial regret without knowing the time horizon beforehand. Finally, we propose a simple signaling 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.

[ PDF] 

Author Information

Ehsan Asadi Kangarshahi (University of Cambridge)

I received my bachelors in electrical engineering and pure mathematics simultaneously from Sharif University of Technology, Iran in 2017. From October 2017 until January 2018 I was an intern in LIONS, EPFL. In January 2018 I joined Information Engineering Department, the University of Cambridge as a Ph.D. student.

Ya-Ping Hsieh (École Polytechnique Fédérale d)
Mehmet Fatih Sahin (Ecole Polytechnique Fédérale de Lausanne)
Volkan Cevher (EPFL)

Related Events (a corresponding poster, oral, or spotlight)

More from the Same Authors