2012/05/18 by Alexandra Carpentier, Rémi Munos, Carpentier, Alexandra +1
Computer Science · Decision Sciences · #Advanced Bandit Algorithms Research #FOS: Mathematics #Machine Learning and Algorithms #Optimization and Search Problems #Statistics Theory (math.ST)
paper · doi:10.48550/arxiv.1205.4095
openalex publication_date 2012/05/18 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 budget n. We provide asymptotic and finite-time results on how an oracle that has access to the function would choose the partition 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 \citepMC-UCB, is minimax optimal both in terms of the number of samples n and the number of strata K, up to a √(log(nK)). This enables to deduce a minimax optimal bound on the difference between the performance of the estimate outputted by MC-UCB, and the performance of the estimate outputted by the best oracle static strategy, on the class of Hölder continuous functions, and upt to a √(log(n)).