Skip to Main content Skip to Navigation
Conference papers

Finite-Time Analysis of Stratified Sampling for Monte Carlo

Alexandra Carpentier 1 Rémi Munos 1
1 SEQUEL - Sequential Learning
LIFL - Laboratoire d'Informatique Fondamentale de Lille, Inria Lille - Nord Europe, LAGIS - Laboratoire d'Automatique, Génie Informatique et Signal
Abstract : We consider the problem of stratified sampling for Monte-Carlo integration. We model this problem in a multi-armed bandit setting, where the arms represent the strata, and the goal is to estimate a weighted average of the mean values of the arms. We propose a strategy that samples the arms according to an upper bound on their standard deviations and compare its estimation quality to an ideal allocation that would know the standard deviations of the strata. We provide two regret analyses: a distribution-dependent bound $\widetilde O(n^{-3/2})$ that depends on a measure of the disparity of the strata, and a distribution-free bound $\widetilde O(n^{-4/3})$ that does not.
Document type :
Conference papers
Complete list of metadata

Cited literature [15 references]  Display  Hide  Download
Contributor : Alexandra Carpentier Connect in order to contact the contributor
Submitted on : Monday, February 27, 2012 - 5:46:09 PM
Last modification on : Thursday, January 20, 2022 - 4:17:16 PM
Long-term archiving on: : Thursday, June 14, 2012 - 5:00:24 PM


Files produced by the author(s)


  • HAL Id : inria-00636924, version 3



Alexandra Carpentier, Rémi Munos. Finite-Time Analysis of Stratified Sampling for Monte Carlo. NIPS - Twenty-Fifth Annual Conference on Neural Information Processing Systems, Dec 2011, Grenade, Spain. ⟨inria-00636924v3⟩



Les métriques sont temporairement indisponibles