Importance Sampling
Core Idea
Importance sampling estimates an expectation under one probability distribution using samples drawn from another. The point is simple: if the original distribution rarely visits the regions that matter most, plain Monte Carlo can have very high variance. Importance sampling changes where we sample, then corrects for that change with a density ratio.
First, Recall Monte Carlo Estimation
Suppose we want to compute
where \(x\) is a continuous random variable, \(p(x)\) is its density, and \(f(x)\) is a scalar function of interest.
In high dimensions, this integral is usually impossible to evaluate exactly. Monte Carlo replaces the integral with an average over samples \(x_1,\dots,x_N\sim p\):
This estimator is unbiased:
Its variance is
So increasing \(N\) reduces variance, but if \(f(x)\) is large only in regions that are rare under \(p\), then plain Monte Carlo can still be painfully noisy.
Sampling Distribution of the Monte Carlo Average
The Monte Carlo estimate itself is a random variable. If we repeat the whole sampling process many times, we get a distribution of estimates centered at the true expectation.
By the central limit theorem, for large \(N\),
Sampling Distribution of the Estimator
Repeating the Monte Carlo experiment many times produces a distribution of estimates centered at the true value \( \mathbb{E}_{x\sim p}[f(x)] \).
Derivation of Importance Sampling
Now introduce another density \(q(x)\). As long as \(q(x) > 0\) wherever \(p(x)f(x)\neq 0\), we can multiply and divide by \(q(x)\):
Define the importance weight
Then the importance sampling estimator is
It is still unbiased:
Its variance becomes
The hope is that
Why It Helps
If \(f(x)\) is large mostly in regions that are rare under \(p\), then plain Monte Carlo wastes most of its samples in unimportant regions. A better proposal \(q\) puts more mass where \(|p(x)f(x)|\) is large. We then correct for the bias introduced by sampling from \(q\) using the weight \(p(x)/q(x)\).
Plain Monte Carlo Can Miss the Important Region
Here \(f(x)\) is large mainly in a region where \(p(x)\) is small. Most samples from \(p\) miss that region, so the estimate varies a lot.
Choose a Proposal \(q(x)\) That Visits Important Regions
The proposal \(q(x)\) is chosen to sample the important region more often.
Weighting Corrects for the Change in Sampling
After weighting, we recover the correct expectation under the new sampling rule.
Support Condition and Failure Mode
Importance sampling only works if the proposal covers the support of the target:
If \(q(x)\) is tiny where \(p(x)f(x)\) is large, the weight \(p(x)/q(x)\) can explode. That is the main practical failure mode: a few samples get enormous weight, and the estimator becomes unstable.
What a Good Proposal Looks Like
In words, a good proposal \(q\) should:
- place mass where \(|p(x)f(x)|\) is large,
- avoid being too small in any important region, and
- be easy to sample from and evaluate.
In the idealized scalar setting, the variance-minimizing choice is proportional to \(|p(x)f(x)|\):
In practice, that exact choice is usually unavailable, but it gives the right intuition: sample more often where the integrand matters most.
Connection to Reinforcement Learning
In reinforcement learning, importance sampling appears whenever we estimate an expectation under one policy using data collected from another. If trajectories were collected under \(p_{\theta_{\mathrm{old}}}(\tau)\), then for a quantity \(f(\tau)\),
At the policy level, this gives the familiar likelihood ratio
which is exactly an importance weight. PPO, for example, builds directly on this ratio.