Adaptive algorithms for Stratied Sampling Monte Carlo

We consider the problem of estimating the integral of a function f over a domain. Although no analytic expression for f is available, it is possible to obtain n samples from f, chosen anywhere in the domain. A popular method for computing the integral of the function is to stratify the space in strata and sample points in the strata. We propose an algorithm for returning a stratied estimate of the integral. We prove that this algorithm adapts online the number of samples in each stratum to the amount of variation of the function in the stratum. In particular, this enables to allocate more samples where the function varies more, and be almost as ecien t as an "oracle" strategy that has access to the variations of the functions in each stratum. More precisions on this aspect is in paper (Carpentier and Munos, 2011). We also provide some results on (i) how to choose the number of strata in an ecien t way and (ii) how to adapt the strata themselves to the specic shape of the function. We express those results with nite-time bounds on a proxy of the variance of the estimate (returned by the algorithms we present).