Monte Carlo Estimation and Importance Sampling

Lab 2: Monte Carlo Estimation and Importance Sampling

Monte Carlo methods turn intractable integrals into sample averages. This lab implements the estimators from r2 and r5 — expected value, variance, importance sampling, and effective sample size — and builds the intuition for when importance sampling helps and when it catastrophically fails.

What You'll Build

• A Monte Carlo estimator for $\mathbb{E}[f(X)]$: estimate $\mathbb{E}[X^2]$ for $X \sim \mathcal{N}(0,1)$ (true value: 1.0) using sample averages, plot the error vs sample size, and confirm the $1/\sqrt{N}$ convergence rate
• A linearity of expectation verifier: for dependent $X$ and $Y = X^2$ (where $X \sim \text{Uniform}(-1,1)$), verify empirically that $\mathbb{E}[X + Y] = \mathbb{E}[X] + \mathbb{E}[Y]$ even though $X$ and $Y$ are not independent
• An importance sampling estimator: estimate $\mathbb{E}_p[f(x)]$ for a target $p = \mathcal{N}(3, 1)$ using proposal $q = \mathcal{N}(0, 1)$, compare variance to direct sampling from $p$, and plot the weight distribution
• An ESS calculator: compute effective sample size $(\sum w_i)^2 / \sum w_i^2$ for several $(p, q)$ pairs with varying overlap, and plot ESS as a function of the KL divergence between $p$ and $q$
• A weight collapse demonstration: show what happens when the proposal has lighter tails than the target — a handful of samples get enormous weights, ESS collapses to nearly 1, and the estimator becomes unreliable even with many samples

Key Concepts Practiced

By the end you will understand why importance sampling is theoretically valid but practically fragile, what ESS is actually measuring, and why off-policy RL algorithms use clipped importance weights (as in PPO) to prevent collapse.