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, LAGIS - Laboratoire d'Automatique, Génie Informatique et Signal, Inria Lille - Nord Europe
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.
Type de document :
Communication dans un congrès
NIPS - Twenty-Fifth Annual Conference on Neural Information Processing Systems, Dec 2011, Grenade, Spain. 2011
Liste complète des métadonnées

Littérature citée [15 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/inria-00636924
Contributeur : Alexandra Carpentier <>
Soumis le : lundi 27 février 2012 - 17:46:09
Dernière modification le : jeudi 11 janvier 2018 - 06:22:13
Document(s) archivé(s) le : jeudi 14 juin 2012 - 17:00:24

Fichier

mc-ucb_3.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : inria-00636924, version 3

Collections

Citation

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. 2011. 〈inria-00636924v3〉

Partager

Métriques

Consultations de la notice

470

Téléchargements de fichiers

143