Smoothed perturbation analysis for a class of discrete-event systems

This paper develops a gradient estimation procedure for a general class of stochastic discrete-event systems. In contrast to most previous work, the authors focus on performance measures whose realizations are inherently discontinuous (in fact, piecewise constant) functions of the parameter of differentiation. They consider two broad classes of finite-horizon discontinuous performance measures arising naturally in applications. Because of their discontinuity, these important classes of performance measures are not susceptible to infinitesimal perturbation analysis (IPA). Instead, the authors apply smoothed perturbation analysis, formalizing it and generalizing it along the way. Smoothed perturbation analysis uses conditional expectations to smooth jumps. The resulting gradient estimator involves two factors: the conditional ‘rate’ at which jumps occur and the expected effect of a jump. Among the types of performance measures to which the present methods can be applied are transient state probabilities, finite-horizon throughputs, distributions ‘on arrival,’ and expected terminal cost.