Using Simulation to Approximate the Minimum Cost of a Finite Set of Alternatives

摘要

We consider the problem of approximating the minimum cost of a finite set of alternative systems. We can not directly observe the cost of the systems, but we can estimate the cost using simulation. The simulation run lengths are adaptively chosen for each system. We describe an optimization algorithm and establish a bound on the error convergence rate. Compared with a single system, the error grows by an additional factor of the square root of the logarithm of the number of systems and the simulation budget.