Fast computation of Nash Equilibria in Imperfect Information Games
Remi Munos,u00a0Julien Perolat,u00a0Jean-Baptiste Lespiau,u00a0Mark Rowland,u00a0Bart De Vylder,u00a0Marc Lanctot,u00a0Finbarr Timbers,u00a0Daniel Hennes,u00a0Shayegan Omidshafiei,u00a0Audrunas Gruslys,u00a0Mohammad Gheshlaghi Azar,u00a0Edward Lockhart,u00a0Karl Tuyls
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.
