Importance Sampling (RL)

Imagine learning from a notebook of experiences collected by one decision-maker, while trying to judge how well a different decision-maker would have performed. Importance sampling is the accounting method that makes this possible: it reweights each recorded outcome according to how compatible it is with the policy being evaluated.

In off-policy Monte Carlo reinforcement learning, the behaviour policy b generated the episode, perhaps while exploring randomly. The target policy π is the policy whose value we want to estimate. For a trajectory beginning at time t, its importance-sampling ratio is:

ρ = ∏ [ π(A_k | S_k) / b(A_k | S_k) ]

The product runs over the actions whose probabilities differ between the two policies. A trajectory that follows actions the target policy strongly prefers receives more weight; one that the target policy would rarely choose receives less. The weighted return can then estimate Vπ(s) without collecting fresh episodes under π.

This separates data collection from evaluation. An agent can keep an exploratory policy for discovering useful actions while estimating a greedier policy from the same completed episodes. Two common estimators are:

• Ordinary importance sampling, which averages weighted returns. It is unbiased in principle, but a few huge ratios can make estimates extremely noisy.
• Weighted importance sampling, which normalizes by the total weights. It introduces bias in finite data but is usually far more stable.

The essential requirement is coverage: whenever π can choose an action in a state, b must assign that action nonzero probability. Otherwise the data contains no evidence for that choice, and the ratio is undefined or cannot correct the estimate.

Suppose an agent explores a gridworld with an ε-greedy policy, then evaluates a policy that always takes the estimated best move. Episodes that happen to take those greedy moves count heavily; wandering episodes count little. This is powerful, but long horizons multiply many probability ratios, causing variance to explode. That limitation is why practical off-policy methods use safeguards such as truncated ratios, and why replay-based algorithms such as DQN do not directly apply full-trajectory Monte Carlo importance sampling.