Share on Facebook Tweet on Twitter Share on LinkedIn Share by email
Coherent Inference on Optimal Play in Game Trees

Philipp Hennig, David Stern, and Thore Graepel


Round-based games are an instance of discrete planning problems. Some of the best contemporary game tree search algorithms use random roll-outs as data. Relying on a good policy, they learn on-policy values by propagating information upwards in the tree, but not between sibling nodes. Here, we present a generative model and a corresponding approximate message passing scheme for inference on the optimal, off-policy value of nodes in smooth AND/OR trees, given random roll-outs. The crucial insight is that the distribution of values in game trees is not completely arbitrary. We define a generative model of the on-policy values using a latent score for each state, representing the value under the random roll-out policy. Inference on the values under the optimal policy separates into an inductive, pre-data step and a deductive, post-data part. Both can be solved approximately with Expectation Propagation, allowing off-policy value inference for any node in the (exponentially big) tree in linear time.


Publication typeInproceedings
Published inProceedings of the Thirteenth Conference on Artificial Intelligence and Statistics AISTATS 2010 (to appear)
> Publications > Coherent Inference on Optimal Play in Game Trees