Importance sampling

Importance sampling is a technique for estimating an average under a target distribution $p$ using samples drawn from a different distribution $q$. Each sample is weighted by the ratio $p(x)/q(x)$, which corrects for how much more or less often $q$ produces it. In reinforcement learning it lets you evaluate or improve one policy using data collected by another.

Definition

valid whenever $q(x)>0$ wherever $p(x)f(x)\ne 0$. In RL, $p$ is the target policy $\pi$ and $q$ is the behaviour policy $\mu$ that generated the data. For a whole trajectory the environment's transition probabilities cancel, leaving the product of per-step policy ratios:

Worked example

A behaviour policy picks action 1 with probability 0.8 and action 2 with 0.2. The target policy reverses this: 0.2 and 0.8. Action 1 pays 1, action 2 pays 0, so the target's true value is 0.2. Samples of action 1 get weight $0.2/0.8=0.25$ and samples of action 2 get weight $0.8/0.2=4$. The expected weighted reward is $0.8\times 0.25\times 1+0.2\times 4\times 0=0.2$, correct on average.

The catch is variance. If every step of a 10-step trajectory has a ratio of 2, the trajectory weight is $2^{10}=1024$: a few rare trajectories dominate the estimate.

Variants that control variance

• Weighted (self-normalised) importance sampling: divide by the sum of weights. Slightly biased, much lower variance.
• Per-decision importance sampling: weight each reward only by the ratios of the steps before it.
• Doubly robust estimators: combine importance weights with a learned value model used as a control variate, so the estimate stays accurate if either the weights or the model is good.
• Truncation and clipping: cap the ratios, as in Retrace and V-trace, or as PPO does in its objective.

Where it appears

Importance ratios are the core of off-policy evaluation, of the surrogate objectives in TRPO and PPO, which reuse data from the previous policy, and of corrections for stale samples in asynchronous training of language models.

Why it matters

Whenever the data you have was generated by a different policy than the one you care about, importance sampling is the tool that keeps estimates honest, and its variance is the reason many such estimates are far less certain than they look. When evaluating a new policy from logged data, report the effective sample size of the weights alongside the estimate.

Related terms

• On-policy vs off-policy
• PPO (Proximal Policy Optimization)
• Trust region (TRPO)
• Offline reinforcement learning
• Monte Carlo methods (RL)

Sources

1. Richard S. Sutton, Andrew G. Barto. Reinforcement Learning: An Introduction (2nd edition), 2018. incompleteideas.net
2. Nan Jiang, Lihong Li. Doubly Robust Off-policy Value Evaluation for Reinforcement Learning, 2015. arxiv.org