Importance Sampling

Importance sampling is a Monte Carlo technique for estimating the expected value of a function under a target distribution p when sampling directly from p is hard or inefficient. The idea is to draw samples from a more convenient distribution —the proposal distribution q— and correct each sample with an importance weight equal to the ratio p(x)/q(x), so that the estimate stays unbiased.

In plain terms: if we draw n independent samples x1, …, xn from q, the estimator is the average of f(xi) multiplied by its weight p(xi)/q(xi). Reweighting makes each sample count as much as it should under p, even though it was generated under q. Thomas Kloek and Herman van Dijk formalized the method in 1978; Art B. Owen gives the modern treatment in his text Monte Carlo theory, methods and examples.

The idea: sample from q and reweight

Many questions in statistics and physics reduce to computing an average —the expected value of f under p. When p is intractable, or when almost all of its mass lives in tiny regions, sampling from p wastes effort. Importance sampling sidesteps the obstacle by choosing a q that is easy to sample and undoing the introduced bias with the weight p(x)/q(x). Hence the name: if q places samples where the integrand is important —where f(x)p(x) is large— a handful of well-aimed samples suffices for a precise estimate. The weighting guarantees that, on average, the answer does not drift from the truth.

When it cuts variance and when it blows up

Importance sampling leaves the expected value untouched but changes its variance, and that is the whole game. With a well-chosen q —ideally proportional to |f(x)|p(x)— variance drops sharply against naive Monte Carlo. The catch is that this optimal q depends on the very quantity we are trying to compute, so in practice it is out of reach and can only be approximated. Trouble strikes when q neglects regions where p holds mass: there the ratio p(x)/q(x) explodes and a few enormous weights dominate the sum. The weights become heavy-tailed, variance grows —sometimes to infinity— and the estimate turns unstable. Choosing a good q is therefore the central, unresolved problem of the method; approaches such as the Pareto smoothed importance sampling of Vehtari and colleagues aim to diagnose and tame those tails.

Uses: from Bayesian integrals to off-policy RL

The technique cuts across fields: numerical integration, rare-event estimation in reliability and physics, and the computation of normalizing constants in Bayesian statistics, where Christopher Bishop presents it as a staple of approximate inference. In natural language processing, Yoshua Bengio and Jean-Sébastien Sénécal used it to speed up language-model training, avoiding a sweep over the full vocabulary at every step. In reinforcement learning it underpins off-policy learning: evaluating one policy from data generated by another. Each transition is corrected by the ratio of the action probability under the target policy to that under the behavior policy; Sutton and Barto lay out the ordinary and weighted variants, with their bias-variance trade-off. In every case the same warning holds: the method lives and dies by the quality of q.