Importance Sampling

The fundamental operation of importance sampling is to assign an importance weight to each sample drawn from a proposal distribution q(x). This weight, calculated as w(x) = p(x) / q(x), corrects the bias introduced by not sampling from the target distribution p(x) directly. The weighted average of these samples provides an unbiased estimate of the expectation under p(x).

• Unbiased Estimator: E_p[f(x)] ≈ (1/N) Σ (p(x_i)/q(x_i)) f(x_i).
• Requirement: The support of q(x) must cover the support of p(x) (i.e., q(x) > 0 wherever p(x) > 0).

The efficiency of importance sampling is dictated by the variance of the importance weights. If q(x) is a poor match for p(x), weights can have high variance, leading to unstable estimates.

• Key Metric: Effective Sample Size (ESS) approximates the number of independent samples from p(x) that the weighted samples from q(x) are equivalent to. A low ESS indicates high variance and poor estimation.
• Formula: ESS ≈ (Σ w_i)^2 / Σ w_i^2. Practitioners often resample based on these weights (a step called importance resampling) to obtain unweighted samples.

In reinforcement learning, importance sampling is crucial for off-policy evaluation and learning. It estimates the value of a target policy π using trajectories generated by a different behavior policy μ. The importance weight for a trajectory is the product of probability ratios for each action taken.

• Per-decision importance sampling: Applies the correction at each timestep, typically lower variance.
• Enables learning from historical or exploratory data without deploying the new policy, a cornerstone of algorithms like Retrace and V-trace.

The art of importance sampling lies in designing a good proposal distribution q(x). The optimal proposal minimizes the variance of the estimator.

• Optimal q(x): For estimating E_p[f(x)], the theoretically optimal proposal is proportional to |f(x)| p(x). This is often unknown in practice.
• Common strategies: Use a distribution with heavier tails than p(x) to ensure coverage, or adapt q(x) based on previous samples (adaptive importance sampling).

When the normalizing constant of p(x) (its partition function) is unknown, we use the self-normalized importance sampling estimator. This is ubiquitous in machine learning for unnormalized probabilistic models.

• Self-Normalized Estimator: E_p[f(x)] ≈ Σ (w_i f(x_i)) / Σ w_i, where w_i = p*(x_i)/q(x_i) and p*(x) is the unnormalized target density.
• Property: This estimator is biased but consistent (bias vanishes as N → ∞). It is often more stable in practice than the raw, unnormalized estimator.

Importance sampling is a foundational idea that connects to several advanced ML methods:

• Prioritized Experience Replay (PER): Uses importance sampling to correct the bias introduced by non-uniform sampling from a replay buffer, where the sampling probability is based on Temporal-Difference (TD) error.
• Variational Inference: The Evidence Lower Bound (ELBO) can be derived as an importance-weighted bound, and Importance Weighted Autoencoders (IWAEs) use multiple importance samples for tighter bounds.
• Policy Gradient Methods: Algorithms like REINFORCE with baselines and Actor-Critic methods can be analyzed through an importance sampling lens.

This is the canonical use case. Importance sampling corrects the bias when evaluating or improving a target policy using data generated by a different behavior policy. The importance weight is the ratio of the probabilities of the sampled trajectory under the two policies. This enables:

• Efficient data reuse: A single dataset from an exploratory policy can be used to evaluate many potential target policies.
• Safe policy evaluation: Assessing a new policy's performance without deploying it in the real environment (Off-Policy Policy Evaluation).
• Algorithms like Retrace, V-trace, and Importance Sampling for Policy Gradient rely on this correction.

In standard Monte Carlo estimation, rare but high-impact events are undersampled, leading to high-variance estimates. Importance sampling addresses this by using a proposal distribution that oversamples these critical regions. The samples are then re-weighted. Key applications include:

• Rare event simulation: Estimating the probability of system failures or extreme financial losses.
• Bayesian inference: Calculating posterior expectations when direct sampling from the posterior is difficult. The proposal is often a variational approximation.
• Integrating complex functions: Evaluating integrals where the integrand is concentrated in a small region of the input space.

Importance sampling estimates counterfactual outcomes—what would have happened if a different action had been taken. This is fundamental to:

• Uplift modeling: Measuring the incremental effect of a treatment (e.g., a marketing campaign) by re-weighting observed outcomes from treated and control groups.
• Bandit algorithms with logged data: Evaluating a new recommendation policy using historical logs collected under a different, logging policy. The inverse propensity scoring method is a direct application of importance sampling.
• It separates correlation from causation by accounting for the propensity score (the probability of treatment given context).

Within the Experience Replay Buffer, importance sampling mitigates catastrophic forgetting. When sampling past experiences, not all are equally valuable for retaining old knowledge. Techniques include:

• Prioritized Experience Replay (PER): Samples transitions with probability proportional to their Temporal-Difference (TD) error, a proxy for 'surprise' or learning potential. Importance sampling corrects the bias this non-uniform sampling introduces into the expected gradient.
• Gradient Episodic Memory (GEM): Uses stored examples from past tasks to constrain new learning. The optimization involves calculating gradients on the memory buffer, where importance weights could be applied if the memory is not a perfect representation of the old data distribution.

When training a model on data from a source domain to perform well on a different target domain, importance sampling re-weights the source samples. The weight for a source data point is the ratio of the target and source domain probabilities for that point.

• This corrects for covariate shift, where the input distribution changes but the conditional distribution of the label given the input remains the same.
• It is used in importance-weighted autoencoders and to derive generalization bounds for models trained on biased data.
• The core challenge is estimating the density ratio, often learned via a discriminator network in an adversarial setup.

Importance sampling enhances Variational Autoencoders (VAEs) and other approximate Bayesian methods.

• Importance-Weighted Autoencoders (IWAEs): Use multiple samples from the variational posterior, weighted by their importance, to form a tighter lower bound (the ELBO) on the log-likelihood. This reduces the amortization gap and improves generative performance.
• Particle-Based Variational Inference: Methods like Stein Variational Gradient Descent can be viewed as importance sampling over a set of particles (model parameters) that are iteratively transported to match the target posterior.
• It provides a consistent, unbiased estimate of the marginal likelihood, even when the variational approximation is poor.