Speeding Up Gradient-Based Algorithms for Sequential Games

First-order (i.e., gradient-based) methods for solving two-person zero-sum sequential games of imperfect information have recently become important tools in the construction of game theory-based agents. The computation time per iteration is typically dominated by matrix-vector product operations involving the payoff matrix A. In this paper, we describe two techniques for scaling up this operation. The first is a randomized sampling technique that approximates A with a sparser matrix ˜A. Then an approximate equilibrium for the original game is found by finding an approximate equilibrium of the sampled game. The second technique involves the development of an algorithm and system for performing the matrix-vector product on a cache-coherent Non-Uniform Memory Access (ccNUMA) architecture. The two techniques can be applied together or separately, and they each lead to an algorithm that significantly outperforms the fastest prior gradient-based method.