Optimal unbiased estimators for evaluating agent performance
- Martin Zinkevich
- Michael Bowling, University of Alberta
- Nolan Bard
- Morgan Kan
- Darse Billings, Department of Computing Science, University of Alberta
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 east unbiased. Finally, we apply our unbiased estimator to the game of poker, demonstrating dramatically reduced variance and faster evaluation.
Citation
M. Zinkevich, M. Bowling, N. Bard, M. Kan, D. Billings. "Optimal unbiased estimators for evaluating agent performance". National Conference on Artificial Intelligence (AAAI), Boston, Massachusetts, USA, pp 573-578, January 2006.| Keywords: | machine learning |
| Category: | In Conference |
BibTeX
@incollection{Zinkevich+al:AAAI06,
author = {Martin Zinkevich and Michael Bowling and Nolan Bard and Morgan Kan
and Darse Billings},
title = {Optimal unbiased estimators for evaluating agent performance},
Pages = {573-578},
booktitle = {National Conference on Artificial Intelligence (AAAI)},
year = 2006,
}Last Updated: January 25, 2010Submitted by Nolan Bard
