Minimax Number of Strata for Online Stratified Sampling Given Noisy Samples

Abstract

We consider the problem of online stratified sampling for Monte Carlo integration of a function given a finite budget of n noisy evaluations to the function. More precisely we focus on the problem of choosing the number of strata K as a function of the numerical budget n. We provide asymptotic and finite-time results on how an oracle that knows the smoothness of the function would choose the number of strata optimally. In addition we prove a lower bound on the learning rate for the problem of stratified Monte-Carlo. As a result, we are able to state, by improving the bound on its performance, that algorithm MC-UCB, defined in [1, is minimax optimal both in terms of the number of samples n and the number of strata K, up to a log factor. This enables to deduce a minimax optimal bound on the difference between the performance of the estimate output by MC-UCB, and the performance of the estimate output by the best oracle static strategy, on the class of Holder continuous functions, and up to a log factor.