A Unified View of Large-scale Zero-sum Equilibrium Computation
This work addresses the challenge of equilibrium computation in game theory, particularly for AI in competitive settings like poker, but it is incremental as it unifies existing methods rather than introducing a new paradigm.
The paper tackles the problem of computing approximate Nash equilibria in large zero-sum extensive-form games, which has been a focus due to the Annual Computer Poker Competition, by unifying two previously isolated approaches: no-regret online learning and a gradient method for convex-concave saddle-point problems.
The task of computing approximate Nash equilibria in large zero-sum extensive-form games has received a tremendous amount of attention due mainly to the Annual Computer Poker Competition. Immediately after its inception, two competing and seemingly different approaches emerged---one an application of no-regret online learning, the other a sophisticated gradient method applied to a convex-concave saddle-point formulation. Since then, both approaches have grown in relative isolation with advancements on one side not effecting the other. In this paper, we rectify this by dissecting and, in a sense, unify the two views.