Introduction
Monte Carlo (MC) methods are the workhorse of modern science, used to approximate complex integrals in everything from physics to finance. However, practitioners often face a "paradox of choice": for any given problem, there are dozens of specialized techniques (Importance Sampling, Stratified Sampling, etc.), each with its own tunable parameters. Traditionally, selecting the most efficient estimator requires manual pilot studies or expert intuition. This paper introduces an automated "meta-strategy" that learns to allocate samples to the best estimators on the fly by framing the selection as a Multi-Armed Bandit (MAB) problem.
Methodology: The Bandit Reduction
The authors' core contribution is a formal reduction of adaptive Monte Carlo estimation to the stochastic multi-armed bandit problem. They prove a "Regret Identity": if you define the payoff of an arm (estimator) as the negative square of the sampled estimate ($-X^2$), the standard "bandit-regret" is exactly equal to the "MSE-regret" (the extra error incurred by not knowing the best estimator from the start).
This identity allows the use of established bandit algorithms like UCB-V, KL-UCB, and Thompson Sampling (TS) to manage sample allocation. The framework also accounts for non-uniform computational costs, where some estimators are slower than others, by defining the budget in terms of elapsed CPU time rather than just sample count.
Experimental Evaluation
The approach was evaluated across three distinct scenarios:
- Synthetic Scaled-Bernoulli: A controlled environment to test how algorithms handle different variance scales.
- Option Pricing (Finance): Estimating European call option prices using the Cox-Ingersoll-Ross (CIR) model, comparing bandit approaches against Population Monte Carlo (PMC).
- Bayesian Logistic Regression: Approximating the normalization constant for a logistic regression model using the Pima Indian diabetes dataset, allocating resources between different Annealed Importance Sampling (AIS) estimators.
Key Results and Insights
The experiments demonstrated that bandit-based strategies, particularly Thompson Sampling, significantly outperform traditional methods. Thompson Sampling's Bayesian nature allows it to handle high-variance estimators more gracefully than "optimistic" UCB-style algorithms.
In the option pricing task, bandit strategies consistently achieved lower Mean Squared Error (MSE) than the state-of-the-art PMC method for the same computational budget. Furthermore, the authors found that weighting samples by the inverse of their estimator's variance provided a massive performance boost in non-uniform cost experiments, often reducing regret by orders of magnitude.
Conclusion
By bridging the gap between MC estimation and bandit theory, this research provides a principled way to automate parameter tuning and estimator selection. This "meta-strategy" makes Monte Carlo methods more hardware-agnostic and efficient, allowing researchers to focus on developing estimators while the bandit algorithm handles the optimal allocation of resources.
Summary updated