Abstract  Applying the technique of smoothed perturbation analysis (SPA) to theGI/G/1/K queue, we derive gradient estimators for two performance measures: the mean steady-state system time of a served customer and the probability that an arriving customer is rejected. Unbiasedness of the estimators follows from results of a previous general framework on SPA estimators. However, in that framework, the estimators often require the simulation of numerous additional sample subpaths, possibly making the technique practically infeasible in applications. We exploit some of the special structure of theGI/G/1/K queue to come up with an estimator which requires at most the simulation of a single additional sample subpath. By establishing certain regenerative properties, we provide a strong consistency proof for the estimator.