An Improved Exponential-Time Approximation Algorithm for Fully-Alternating Games Against Nature

"Games against Nature" [Papadimitriou '85] are two-player games of perfect information, in which one player's moves are made randomly. Estimating the value of such games (i.e., winning probability under optimal play by the strategic player) is an important goal in the study of decision-making under uncertainty.  The problem's PSPACE-completeness does not rule out non-trivial algorithms, a goal fulfilled in certain cases by Littman, Majercik, and Pitassi [LMP '01]. 

We study the case in which the players strictly alternate with binary moves, for which [LMP '01] does not give a general speedup. We give a randomized algorithm to approximate the value of such games (and to produce near-optimal play) . Our algorithm achieves exponential savings over brute-force, making 2^{(1-delta)n} queries to the input game's lookup table for some absolute constant delta > 0, and certifies a lower bound on the game value with exponentially-small expected additive error. (On the downside, delta is tiny and the algorithm uses exponential space.)

Our algorithm is recursive, and bootstraps a "base-case" algorithm for fixed-size inputs. The base-case algorithm and the form of recursive composition used are interesting and, we feel, likely to find uses beyond the present work.