Adaptive Monte Carlo via Bandit Allocation
arXiv:1405.3318
Abstract
We consider the problem of sequentially choosing between a set of unbiased Monte Carlo estimators to minimize the mean-squared-error (MSE) of a final combined estimate. By reducing this task to a stochastic multi-armed bandit problem, we show that well developed allocation strategies can be used to achieve an MSE that approaches that of the best estimator chosen in retrospect. We then extend these developments to a scenario where alternative estimators have different, 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.
arXiv commentThe 31st International Conference on Machine Learning (ICML 2014)
References in corpus (5)
- Analysis of Thompson Sampling for the multi-armed bandit problem
- Informational Confidence Bounds for Self-Normalized Averages and Applications
- Estimating Ratios of Normalizing Constants Using Linked Importance Sampling
- From Bandits to Experts: A Tale of Domination and Independence
- Adaptive Stratified Sampling for Monte-Carlo integration of Differentiable functions