We consider the problem of sequentially allocating
samples between a set of unbiased Monte-Carlo estimators with unknown variance. To minimize the mean-squared-error (MSE) of the final estimate, we develop strategies that are guaranteed to approximate the MSE of the single best estimator chosen in retrospect. We achieve these results by reducing sample-allocation to a stochastic multi-armed bandit problem, which allows well developed allocation strategies and corresponding analyses to be applied. These developments are then extended to a scenario where alternative estimators have different costs, yielding novel allocation strategies with strong guarantees. Overall, our new adaptive Monte-Carlo methods provide stronger guarantees than alternatives, while offering empirical improvements.