Timezone: »

 
Poster
Fast computation of Nash Equilibria in Imperfect Information Games
Remi Munos · Julien Perolat · Jean-Baptiste Lespiau · Mark Rowland · Bart De Vylder · Marc Lanctot · Finbarr Timbers · Daniel Hennes · Shayegan Omidshafiei · Audrunas Gruslys · Mohammad Gheshlaghi Azar · Edward Lockhart · Karl Tuyls

Wed Jul 15 10:00 AM -- 10:45 AM & Wed Jul 15 11:00 PM -- 11:45 PM (PDT) @ None #None
in Poster Session 24 »

We introduce and analyze a class of algorithms, called Mirror Ascent against an Improved Opponent (MAIO), for computing Nash equilibria in two-player zero-sum games, both in normal form and in sequential form with imperfect information. These algorithms update the policy of each player with a mirror-ascent step to maximize the value of playing against an improved opponent. An improved opponent can be a best response, a greedy policy, a policy improved by policy gradient, or by any other reinforcement learning or search techniques. We establish a convergence result of the last iterate to the set of Nash equilibria and show that the speed of convergence depends on the amount of improvement offered by these improved policies. In addition, we show that under some condition, if we use a best response as improved policy, then an exponential convergence rate is achieved.

Keywords: Game Theory and Mechanism Design · Learning Theory

Author Information

Remi Munos (DeepMind)
Julien Perolat (DeepMind)
Jean-Baptiste Lespiau (DeepMind)
Mark Rowland (DeepMind)
Bart De Vylder (DeepMind)
Marc Lanctot (DeepMind)
Finbarr Timbers (DeepMind)
Daniel Hennes (DeepMind)
Shayegan Omidshafiei (DeepMind)
Audrunas Gruslys (DeepMind)
Mohammad Gheshlaghi Azar (Deepmind)
Edward Lockhart (DeepMind)
Karl Tuyls (DeepMind)

More from the Same Authors