Importance Sampling

Two Policies, Two Roles

Imagine that an agent has already generated experience by following one policy, but you want to estimate the value of a different policy. Off-policy prediction addresses this situation. The policy that generated the episodes is the behavior policy. The policy whose value you want to estimate is the target policy.

The separation is important because the observed returns came from the behavior policy, not directly from the target policy. Importance sampling adjusts the influence of those returns so that the data can be used to estimate the target policy's value. The behavior policy determines what experience is available; the target policy determines how that experience is interpreted.

Weighting an Observed Action

For each action that actually occurred in an episode, importance sampling compares two probabilities: the probability that the target policy assigns to that action and the probability that the behavior policy assigns to it. The action's weight is based on the target-policy probability divided by the behavior-policy probability.

This comparison changes how strongly the observed return contributes to the estimate. If the target policy treats an observed action as relatively more likely than the behavior policy does, the return receives more influence. If the target policy treats it as relatively less likely, the return receives less influence. The ratio therefore adjusts behavior-policy experience toward the target policy being evaluated.

Accumulating a Trajectory Weight

The example uses a short episode to make the mechanism visible. In general, the learning process examines the actions that occurred in each episode, compares their probabilities under the two policies, uses the comparisons to weight returns, and combines the weighted information into an estimate of the target policy's value function.

Two Ways to Average

Ordinary importance sampling averages the weighted returns directly. Its key advantage is unbiasedness: in the description provided here, it produces unbiased estimates. Its drawback is variance. That variance can be larger and can possibly be infinite, so individual estimates may vary substantially.

Weighted importance sampling instead forms a weighted average. The weights affect both the returns' contributions and the normalization of the average. This estimator has finite variance and is preferred in practice, making it the usual practical choice when selecting between the two forms described here.

Why Practice Favors Weighted Estimates

The practical choice follows from the estimators' variance properties. Ordinary importance sampling is unbiased, but its variance may be large or even infinite. Weighted importance sampling has finite variance, so its estimates are more suitable for practical value estimation according to the source material.

Common Reasoning Errors

• Treating the behavior policy as the policy being evaluated

  Off-policy prediction separates the policy that supplies experience from the policy whose value is estimated.

  Fix: Identify the behavior policy as the data source and the target policy as the policy being evaluated.

• Ignoring the behavior-policy probability

  Importance sampling adjusts for the policy difference by comparing the target-policy probability with the behavior-policy probability.

  Fix: Use the target probability relative to the behavior probability for every observed action.

• Applying a ratio to only one action in a multi-action episode

  The action-probability comparisons accumulate across the sequence of decisions in the episode.

  Fix: Account for the observed actions across the trajectory before applying the resulting weight to the return.

• Claiming that ordinary importance sampling is always the practical choice because it is unbiased

  Ordinary importance sampling can have larger, possibly infinite, variance.

  Fix: Recognize that weighted importance sampling has finite variance and is preferred in practice.

Check Your Understanding

Key Takeaways

1. Off-policy prediction estimates a target policy's value using episodes generated by a behavior policy.
2. Importance sampling compares target-policy and behavior-policy probabilities for the actions that actually occurred.
3. The action-probability comparisons accumulate across an episode and determine how strongly its return contributes.
4. Ordinary importance sampling averages weighted returns directly and is unbiased, but its variance can be larger or possibly infinite.
5. Weighted importance sampling uses a weighted average, has finite variance, and is preferred in practice.