EXTENSIONS AND GENERALIZATIONS OF SMOOTHED PERTURBATION ANALYSIS IN A GENERALIZED SEMI-MARKOV PROCESS FRAMEWORK

Smoothed perturbation analysis is a technique for estimating derivatives of performance measures of a stochastic discrete-event system. The key idea is the use of conditional expectation to "smooth" certain discontinuities which prevent the use of infinitesimal perturbation analysis. The source of these discontinuities may be the performance measure or the underlying stochastic processes. Previous work has considered special classes of performance measures under a structural condition on the system called the commuting condition. The resulting estimators are very attractive, in that they can be easily estimated from a single sample path (or simulation) of the system. However, most multiclass queueing networks, as well as systems as simple as the GI/G/1/K queue, cannot be handled. Under a generalized semi-Markov process (GSMP) framework allowing a wide class of performance measures for systems that do not necessarily satisfy the commuting condition, we derive two derivative estimators (a left-hand derivative estimator and a right-hand derivative estimator, equal in expectation) and prove their unbiasedness. However, the gain in generality comes at a cost, in that the derivative estimator contains terms which may not be easily estimated from a single sample path, and thus may require additional simulation. The framework is such that upon application of the commuting condition and restriction to certain classes of performance measures, we readily recover as special cases of our estimators the estimators of previous researchers.