Zero-Variance Importance Sampling Estimators for Markov Process ExpectationsH. Awad, P. W. Glynn, and R. Y. Rubinstein Mathematics of Operations Research 38(2):358-388. 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. |