A Unification of Extensive-Form Games and Markov Decision Processes

H. Brendan McMahan, Geoffrey J. Gordon

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 feature of our generalization is that it places arbitrary convex optimization 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.

Subjects: 1.8 Game Playing; 1.11 Planning

Submitted: Apr 24, 2007

This page is copyrighted by AAAI. All rights reserved. Your use of this site constitutes acceptance of all of AAAI's terms and conditions and privacy policy.