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.