Weighted Importance Sampling

Off-policy learning separates two jobs. A behavior policy generates episodes, while a target policy is the policy whose value we want to estimate. Because the two policies may choose different actions, an observed return may not represent the target policy directly. Importance sampling corrects for this mismatch by assigning each return an importance-sampling weight based on how compatible its episode is with the target policy.

Consider the looping example. Some episodes end with end. Their importance-sampling ratio is zero because the target policy never chooses end, so they contribute nothing to the scaled quantity. Other episodes contain some number of back transitions that return to s and then finish with a back transition that terminates. Each of these episodes has return 1, but episodes with different loop lengths receive different importance-sampling corrections.

The important effect is multiplication across the episode. Longer looping trajectories accumulate a different correction from shorter trajectories. To determine the variance of the ordinary estimator, the analysis considers every possible loop length, multiplies each episode's occurrence probability by the square of its ratio, and adds the results. In this example, that total is infinite. Thus, ordinary importance sampling can have infinite variance even though the target-policy value is 1.

Ordinary importance sampling forms a simple average of the scaled returns. It is unbiased: across repeated sampling, its expected estimate is the target value. However, that guarantee does not limit the size of fluctuations in individual estimates. If importance-sampling ratios can become very large, the variance can be unbounded.

Weighted importance sampling instead divides the total of the weighted returns by the total of the weights. This is a normalized weighted average. Episodes with zero weight are ignored, while episodes with nonzero weight share the estimate according to their relative weights.

With one observed return and a nonzero importance-sampling ratio, weighted importance sampling returns the same value as the observed return because the ratio appears in both the numerator and the denominator and cancels. This does not mean that every one-return case is defined by cancellation. If the total weight is zero, the weighted estimate is defined to be zero.

Weighted importance sampling is usually preferred in practice because it generally has dramatically lower variance. No single return receives a normalized weight larger than one, and when returns are bounded, the variance converges to zero even when the importance-sampling ratios themselves have infinite variance. The price is bias, although that bias approaches zero as more data is collected.

Ordinary importance sampling still has a useful role. Its simpler form is easier to extend to approximate methods that use function approximation. Therefore, the choice is not that ordinary importance sampling is always incorrect. It is that weighted importance sampling is often the more practical choice when estimate stability matters most.