Zero-Variance Importance Sampling Estimators for Markov Process Expectations

• 成果类型: Article
• 署名作者: Awad, Hernan P.; Glynn, Peter W.; Rubinstein, Reuven Y.
• 署名单位: University of Miami; Stanford University; Technion Israel Institute of Technology
• 刊物名称: MATHEMATICS OF OPERATIONS RESEARCH
• ISSN/ISSBN: 0364-765X
• DOI: 10.1287/moor.1120.0569
• 发表日期: 2013
• 页码: 358-388
• 关键词: simulation

摘要

We consider the use of importance sampling to compute expectations of functionals of Markov processes. For a class of expectations that can be characterized as positive solutions to a linear system, we show there exists an importance measure that preserves the Markovian nature of the underlying process, and for which a zero-variance estimator can be constructed. The class of expectations considered includes expected infinite horizon discounted rewards as a particular case. In this setting, the zero-variance estimator and associated importance measure can exhibit behavior that is not observed when estimating simpler path functionals (like exit probabilities). The zero-variance estimators are not implementable in practice, but their characterization can guide the design of a good importance measure and associated estimator by trying to approximate the zero-variance ones. We present bounds on the mean-square error of such an approximate zero-variance estimator, based on Lyapunov inequalities.