linear time nash equilibirum aproximations for two player zero sum games
By choosing a different framework of thought that does not attempt to ensure a specific bound we can do well in practice using an algorithm called regret matching.. The paper introducing this is called &quot;A Simple Adaptive Procedure Leading to Correlated Equilibrium&quot; by Sergui Hart and Mas-Colell
.
Regret matching is ensured to almost certainly converge to a nash equilibrium for a zero sum gum. There does not seem to be a ton of literature on the convergence rate but in practice it seems that for small matrices it converges close to the equilibrium in a matter of thousands of iterations. Additionally there are many strategies for speeding up convergence that sacrifice guaranteed convergence such as shareholding, or incorporating negative regret along with some normalization procedure. Regret matching has the extreme benefit of being exceedingly simple as well.
Regret matching is the basis for counter-factual regret minimization which is the technique behind state of the art poker AIs.