Optimal Unbiased Estimators for Evaluating Agent Performance

Martin Zinkevich, Michael Bowling, Nolan Bard, Morgan Kan, and Darse Billings. Optimal Unbiased Estimators for Evaluating Agent Performance. In Proceedings of the Twenty-First National Conference on Artificial Intelligence (AAAI), pp. 573–578, 2006.

Download

[PDF] [gzipped postscript] 

Abstract

Evaluating the performance of an agent or group of agents can be, by itself, a very challenging problem. The stochastic nature of the environment plus the stochastic nature of agents decisions can result in estimates with intractably large variances. This paper examines the problem of finding low variance estimates of agent performance. In particular, we assume that some agent-environment dynamics are known, such as the random outcome of drawing a card or rolling a die. Other dynamics are unknown, such as the reasoning of a human or other black-box agent. Using the known dynamics, we describe the complete set of all unbiased estimators, that is, for any possible unknown dynamics the estimate's expectation is always the agent's expected utility. Then, given a belief about the unknown dynamics, we identify the unbiased estimator with minimum variance. If the belief is correct our estimate is optimal, and if the belief is wrong it is at least unbiased. Finally, we apply our unbiased estimator to the game of poker, demonstrating dramatically reduced variance and faster evaluation.

BibTeX

@InProceedings(06aaai-divat,
  title = "Optimal Unbiased Estimators for Evaluating Agent Performance",
  author = "Martin Zinkevich and Michael Bowling and Nolan Bard and Morgan Kan and Darse Billings",
  booktitle = "Proceedings of the Twenty-First National Conference on Artificial Intelligence (AAAI)",
  year = "2006",
  pages = "573--578",
  AcceptRate = "30\%",
  AcceptNumbers = "236 of 774"
)

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