Randomized solutions to partial information dynamic zero-sum games

This paper presents randomized methods to solve partial information dynamic zero-sum games. We extend the recently introduced sampled saddle-point (SSP) algorithm, which provided probabilistic security guarantees in static zero-sum matrix games. A straightforward extension to partial information dynamic games is to apply the SSP algorithm to the matrix obtained by recording the outcomes of playing every policy of one player against every policy of the other player. However, the matrix so obtained has typically a very large size. This paper formalizes a novel extension of the SSP algorithm to partial information dynamic games, which does not require generating the entire matrix. We show that the bounds derived for the SSP algorithm in the static case, provide the same level of probabilistic security for a partial information dynamic game. The effectiveness of the procedure is demonstrated by solving a prototypical example of a board game with partial information, for which no deterministic security levels have been published.