Measure-Valued Differentiation for Markov Chains

This paper addresses the problem of sensitivity analysis for finite-horizon performance measures of general Markov chains. We derive closed-form expressions and associated unbiased gradient estimators for the derivatives of finite products of Markov kernels by measure-valued differentiation (MVD). In the MVD setting, the derivatives of Markov kernels, called -derivatives, are defined with respect to a class of performance functions such that, for any performance measure , the derivative of the integral of g with respect to the one-step transition probability of the Markov chain exists. The MVD approach (i) yields results that can be applied to performance functions out of a predefined class, (ii) allows for a product rule of differentiation, that is, analyzing the derivative of the transition kernel immediately yields finite-horizon results, (iii) provides an operator language approach to the differentiation of Markov chains and (iv) clearly identifies the trade-off between the generality of the performance classes that can be analyzed and the generality of the classes of measures (Markov kernels). The -derivative of a measure can be interpreted in terms of various (unbiased) gradient estimators and the product rule for -differentiation yields a product-rule for various gradient estimators. Part of this work was done while the first author was with EURANDOM, Eindhoven, Netherlands, where he was supported by Deutsche Forschungsgemeinschaft under Grant He3139/1-1. The work of the second author was partially supported by NSERC and FCAR grants of the Government of Canada and Québec.