Strategy Evaluation in Extensive Games with Importance Sampling

Michael Bowling, Michael Johanson, Neil Burch, and Duane Szafron. Strategy Evaluation in Extensive Games with Importance Sampling. In Proceedings of the Twenty-Fifth International Conference on Machine Learning (ICML), pp. 72–79, 2008.

Download

[PDF] [gzipped postscript] 

Abstract

Typically agent evaluation is done through Monte Carlo estimation. However, stochastic agent decisions and stochastic outcomes can make this approach inefficient, requiring many samples for an accurate estimate. We present a new technique that can be used to simultaneously evaluate many strategies while playing a single strategy in the context of an extensive game. This technique is based on importance sampling, but utilizes two new mechanisms for significantly reducing variance in the estimates. We demonstrate its effectiveness in the domain of poker, where stochasticity makes traditional evaluation problematic.

Additional Information

A video of Michael Johanson giving the talk at ICML is on videolectures.net.

BibTeX

@InProceedings(08icml-ispoker,
  Title = "Strategy Evaluation in Extensive Games with Importance Sampling",
  Author = "Michael Bowling and Michael Johanson and Neil Burch and Duane Szafron",
  Booktitle = "Proceedings of the Twenty-Fifth International Conference on Machine Learning (ICML)",
  Year = "2008",
  Pages = "72--79",
  AcceptRate = "27\%",
  AcceptNumbers = "155 of 583"
)

Generated by bib2html.pl (written by Patrick Riley) on Fri Feb 13, 2015 15:54:28