linear time nash equilibirum aproximations for two player zero sum games

Question

I'm working on an AI for a game where I'd like the game where each player has hundreds of moves to select from and so the game matrix has 10s of thousands of entries. The game is however zero sum. Given that I have 10s of thousands of entries I can't apply even an $O(n^2)$ algorithm or the result will take too long so I need a linear time algorithm. I've found this note which details an exceedingly simple $\frac{1}{2}$-approximation algorithm that works for any game, not just a zero sum game. It also does so by only looking at $O(\sqrt{N})$ entries in the table which is even faster than what I need.

Zero sum games can have their exact equilibrium computed in polynomial time via linear programming but this is too slow.

What I'm looking for is something in between; Something that uses more computational resources than the simple 1/2-aproximation algorithm but gives a better approximation; Something that uses fewer computational resources than linear programming but only gives an approximate answer. Does a linear time approximation algorithm exist for 2-player zero-sum games that is better than $\frac{1}{2}$-approximation?

Answer 1

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 "A Simple Adaptive Procedure Leading to Correlated Equilibrium" 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.