A Unification of Extensive-Form Games and Markov Decision Processes

Abstract

We describe a generalization of extensive-form games that greatly increases representational power while still allowing efficient computation in the zero-sum setting. A principal fea-ture of our generalization is that it places arbitrary convex op-timization problems at decision nodes, in place of the finite action sets typically considered. The possibly-infinite action sets mean we must “forget ” the exact action taken (feasible solution to the optimization problem), remembering instead only some statistic sufficient for playing the rest of the game optimally. Our new model provides an exponentially smaller representation for some games; in particular, we show how to compactly represent (and solve) extensive-form games with outcome uncertainty and a generalization of Markov decision processes to multi-stage adversarial planning games.