Zero‐Variance Importance Sampling Estimators for Markov Process Expectations

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.