Adaptive Monte Carlo via Bandit Allocation

We consider the problem of sequentially choos-ing between a set of unbiased Monte Carlo estimators to minimize the mean-squared-error (MSE) of a final combined estimate. By reduc-ing this task to a stochastic multi-armed bandit problem, we show that well developed allocation strategies can be used to achieve an MSE that ap-proaches that of the best estimator chosen in ret-rospect. We then extend these developments to a scenario where alternative estimators have dif-ferent, possibly stochastic costs. The outcome is a new set of adaptive Monte Carlo strategies that provide stronger guarantees than previous approaches while offering practical advantages. 1