Randomized sampling for large zero-sum games

This paper addresses the solution of large zero-sum matrix games using randomized methods. We provide a procedure by which a player can compute mixed policies that, with high probability, are security policies against an adversary that is also using randomized methods to solve the game. The computational savings result from solving subgames that are much smaller than the original game and we provide bounds on how large these subgames should be to guarantee the desired high probability. We propose two methodologies to solve this problem. The first provides a game-independent bound on the size of the subgames that can be computed a-priori. The second procedure is useful when computation limitations prevent a player from satisfying the first a-priori bound and provides a high-probability a-posteriori bound on how much the outcome of the game can violate the precomputed security level. All our probabilistic bounds are independent of the size of the original game and could, in fact, apply to games with continuous action spaces. To demonstrate the usefulness of these results, we apply them to solve a hide-and-seek game that exhibits exponential complexity.