Importance Sampling

Definition

Importance Sampling

Importance sampling is a technique for estimating expected values under one distribution using samples from another distribution. In RL, it enables off-policy learning: learning about a target policy $\pi$ from data generated by a different behavior policy $b$.

The Problem

We want to estimate $v_{\pi }(s)={\mathbb{E}}_{\pi }[G_t\mid S_t=s]$, but our data comes from following behavior policy $b\ne \pi$. The returns $G_t$ observed under $b$ have the wrong distribution.

Importance Sampling Ratio

Importance Sampling Ratio

${\rho }_{t:T-1}={\prod }_{k=t}^{T-1}\frac{\pi (A_k\mid S_k)}{b(A_k\mid S_k)}$

where:

• $\pi (A_k|S_k)$ — probability of taking action $A_k$ in state $S_k$ under target policy
• $b(A_k|S_k)$ — probability under behavior policy
• The product is over all steps from $t$ to end of episode

What the Ratio Does

It reweights each trajectory to correct for the fact that it was generated under $b$ instead of $\pi$. If $\pi$ would have been more likely to take the observed actions, $\rho >1$ (upweight). If less likely, $\rho <1$ (downweight). If $\pi$ would never take an observed action ($\pi (a|s)=0$), then $\rho =0$ (ignore this trajectory entirely).

Coverage Requirement

Coverage Assumption

For importance sampling to work, the behavior policy must cover the target policy: $\pi (a|s)>0⟹b(a|s)>0\forall s,a$

If there’s an action $\pi$ might take that $b$ would never take, we can never estimate its value. ε-soft policies satisfy this automatically.

Two Variants

Ordinary Importance Sampling

Ordinary IS

$V(s)=\frac{{\sum }_{t\in \mathcal{T}(s)}{\rho }_{t:T(t)-1}{G}_t}{|\mathcal{T}(s)|}$

Simple average of importance-weighted returns.

• ✅ Unbiased
• ❌ High (potentially infinite) variance — a single large $\rho$ can dominate

Weighted Importance Sampling

Weighted IS

$V(s)=\frac{{\sum }_{t\in \mathcal{T}(s)}{\rho }_{t:T(t)-1}{G}_t}{{\sum }_{t\in \mathcal{T}(s)}{\rho }_{t:T(t)-1}}$

Weighted average where the denominator normalizes by the sum of ratios.

• ❌ Biased (for finite samples, bias → 0 asymptotically)
• ✅ Much lower variance — preferred in practice
• First-episode estimate is always $V(s)=G_t$ (ratio cancels), which has bounded error

Incremental Implementation

For weighted IS with per-episode updates: $V_{n+1}=V_n+\frac{W_n}{C_n}\left[G_n-V_n\right]$ where $C_n=C_{n-1}+W_n$ is the cumulative sum of weights.

In Off-Policy Methods

• Monte Carlo Methods: Multiply entire episode return by ${\rho }_{t:T-1}$
• Temporal Difference Learning: Per-step importance ratio ${\rho }_t=\frac{\pi (A_t|S_t)}{b(A_t|S_t)}$
• With Function Approximation: Semi-gradient off-policy TD uses per-step ${\rho }_t$

Variance Problem

Variance Explosion

The product ${\rho }_{t:T-1}$ can be astronomically large or zero, making ordinary IS highly unstable. This is a fundamental challenge of off-policy MC methods. Weighted IS helps, but variance remains an issue for long episodes with very different policies.

Connections

• Enables: Off-Policy learning
• Used in: Monte Carlo Methods (off-policy MC control), Semi-Gradient Methods (off-policy TD)
• Problem: variance → motivates alternatives like Q-Learning (which avoids IS entirely for control)
• Extended by: Per-decision IS, discounting-aware IS

Appears In

• RL-L03 - Monte Carlo Methods
• RL-L07 - Off-Policy RL with Approximation
• RL-Book Ch5 - Monte Carlo Methods
• RL-ES02 - Exercise Set Week 2, RL-ES03 - Exercise Set Week 3