← Notes

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

\[ I = \mathbb{E}_{x\sim p}[f(x)] = \int p(x) f(x)\,dx, \]

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\):

\[ \hat{I}_{\mathrm{MC}} = \frac{1}{N}\sum_{i=1}^{N} f(x_i), \qquad x_i\sim p. \]

This estimator is unbiased:

\[ \mathbb{E}[\hat{I}_{\mathrm{MC}}] = \mathbb{E}_{x\sim p}[f(x)]. \]

Its variance is

\[ \operatorname{Var}(\hat{I}_{\mathrm{MC}}) = \frac{1}{N}\operatorname{Var}_{x\sim p}(f(x)). \]

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.

\[ \hat{I}_{\mathrm{MC}} = \frac{1}{N}\sum_{i=1}^{N} f(x_i). \]

By the central limit theorem, for large \(N\),

\[ \hat{I}_{\mathrm{MC}} \approx \mathcal{N} \left( \mu,\, \sigma^2 \right), \qquad \mu=\mathbb{E}_{x\sim p}[f(x)], \qquad \sigma^2=\frac{1}{N}\operatorname{Var}_{x\sim p}(f(x)). \]

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)\):

\[ \mathbb{E}_{x\sim p}[f(x)] = \int p(x)f(x)\,dx = \int q(x)\frac{p(x)}{q(x)}f(x)\,dx = \mathbb{E}_{x\sim q} \left[ \frac{p(x)}{q(x)}f(x) \right]. \]

Define the importance weight

\[ w(x)=\frac{p(x)}{q(x)}. \]

Then the importance sampling estimator is

\[ \hat{I}_{\mathrm{IS}} = \frac{1}{N} \sum_{i=1}^{N} w(x_i)f(x_i), \qquad x_i\sim q. \]

It is still unbiased:

\[ \mathbb{E}[\hat{I}_{\mathrm{IS}}] = \mathbb{E}_{x\sim q}[w(x)f(x)] = \mathbb{E}_{x\sim p}[f(x)]. \]

Its variance becomes

\[ \operatorname{Var}(\hat{I}_{\mathrm{IS}}) = \frac{1}{N} \operatorname{Var}_{x\sim q} \left( \frac{p(x)}{q(x)}f(x) \right). \]

The hope is that

\[ \operatorname{Var}_{x\sim q} \left( \frac{p(x)}{q(x)}f(x) \right) < \operatorname{Var}_{x\sim p}(f(x)). \]

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

\(p(x)\) \(f(x)\) (scaled for display)

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

\(p(x)\) \(f(x)\) (scaled) \(q(x)\)

The proposal \(q(x)\) is chosen to sample the important region more often.

Weighting Corrects for the Change in Sampling

\(q(x)\) \(\frac{p(x)}{q(x)}f(x)\) (scaled)

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:

\[ q(x) > 0 \qquad \text{whenever} \qquad p(x)f(x)\neq 0. \]

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:

In the idealized scalar setting, the variance-minimizing choice is proportional to \(|p(x)f(x)|\):

\[ q^\star(x)\propto |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)\),

\[ \mathbb{E}_{\tau\sim p_\theta}[f(\tau)] = \mathbb{E}_{\tau\sim p_{\theta_{\mathrm{old}}}} \left[ \frac{p_\theta(\tau)}{p_{\theta_{\mathrm{old}}}(\tau)} f(\tau) \right]. \]

At the policy level, this gives the familiar likelihood ratio

\[ r_t(\theta) = \frac{\pi_\theta(a_t\mid s_t)} {\pi_{\theta_{\mathrm{old}}}(a_t\mid s_t)}, \]

which is exactly an importance weight. PPO, for example, builds directly on this ratio.