Simulation Optimization by Reusing Past Replications: Don’t Be Afraid of Dependence

Abstract

The main challenge of simulation optimization is the limited simulation budget because of the high computational cost of simulation experiments. One approach to overcome this challenge is to reuse simulation outputs from previous iterations in the current iteration of the optimization procedure. However, due to the dependence among iterations, simulation replications from different iterations are not independent, which leads to the lack of theoretical justification for the good empirical performance. In this paper, we fill this gap by theoretically studying the stochastic gradient descent method with reusing past simulation replications. We show that reusing past replications does not change the convergence of the algorithm, which implies the bias of the gradient estimator is asymptotically negligible. Moreover, we show that reusing past replications reduces the variance of gradient estimators conditioned on the history, which implies that the algorithm can use larger step size sequences to achieve faster convergence.