This technical note addresses gradient estimation for the cost performance of a two-component maintenance system with respect to the threshold parameter of an age replacement policy. We derive a new gradient estimator based on the measure-valued differentiation (MVD) approach. The performance of the phantom estimator is compared with that of the known smoothed perturbation analysis (SPA) estimator. We show that the phantom estimator has a lower variance, and requires less computational effort than the SPA estimator. © 2007 IEEE.