A basic formula for performance gradient estimation of semi-Markov decision processes

This paper presents a basic formula for performance gradient estimation of semi-Markov decision processes (SMDPs) under average-reward criterion. This formula directly follows from a sensitivity equation in perturbation analysis. With this formula, we develop three sample-path-based gradient estimation algorithms by using a single sample path. These algorithms naturally extend many gradient estimation algorithms for discrete-time Markov systems to continuous time semi-Markov models. In particular, they require less storage than the algorithm in the literature.

► We present a basic formula for gradient estimation of SMDPs. ► The formula directly follows from a sensitivity equation in perturbation analysis. ► We develop three gradient estimation algorithms based on the basic formula. ► These algorithms are generalization of Markov cases. ► These algorithms require less storage than the existing algorithm.