A Direct Second-Order Method for Solving Two-Player Zero-Sum Games
By: David Yang , Yuan Gao , Tianyi Lin and more
We introduce, to our knowledge, the first direct second-order method for computing Nash equilibria in two-player zero-sum games. To do so, we construct a Douglas-Rachford-style splitting formulation, which we then solve with a semi-smooth Newton (SSN) method. We show that our algorithm enjoys local superlinear convergence. In order to augment the fast local behavior of our SSN method with global efficiency guarantees, we develop a hybrid method that combines our SSN method with the state-of-the-art first-order method for game solving, Predictive Regret Matching$^+$ (PRM$^+$). Our hybrid algorithm leverages the global progress provided by PRM$^+$, while achieving a local superlinear convergence rate once it switches to SSN near a Nash equilibrium. Numerical experiments on matrix games demonstrate order-of-magnitude speedups over PRM$^+$ for high-precision solutions.
Similar Papers
ε-Optimally Solving Two-Player Zero-Sum POSGs
CS and Game Theory
Lets computers play games they can't fully see.
Quadratic Programming Approach for Nash Equilibrium Computation in Multiplayer Imperfect-Information Games
CS and Game Theory
Finds best moves in complex games.
A Parallelizable Approach for Characterizing NE in Zero-Sum Games After a Linear Number of Iterations of Gradient Descent
CS and Game Theory
Solves tough math puzzles faster than before.