Abstract
Motivated by the problem of efficient estimation of expected cumulative rewards or cashflows, this paper proposes and analyzes a variance reduction technique for estimating the expectation of the sum of sequentially simulated random variables. In some applications, simulation effort is of greater value when applied to early time steps rather than shared equally among all time steps; this occurs, for example, when discounting renders immediate rewards or cashflows more important than those in the future. This suggests that deliberately stopping some paths early may improve efficiency. We formulate and solve the problem of optimal allocation of resources to time horizons with the objective of minimizing variance subject to a cost constraint. The solution has a simple characterization in terms of the convex hull of points defined by the covariance matrix of the cashflows. We also develop two ways to enhance variance reduction through early stopping. One takes advantage of the statistical theory of missing data. The other redistributes the cumulative sum to make optimal use of early stopping.