Off-policy Prediction with Importance Sampling

One Experience, Two Policies

Off-policy prediction begins with a mismatch. Experience is collected under one policy, called the behavior policy, but the quantity we want to estimate belongs to another policy, called the target policy. Importance sampling makes those behavior-policy experiences useful by adjusting their influence according to how likely the same trajectories would have been under the target policy.

Building a Trajectory Probability

Start at a particular state S_t. A subsequent trajectory includes the action selected at that state, the next state, the next action, and continuing state-action pairs until the endpoint. The probability of this complete trajectory contains factors from two sources: the policy's probabilities for selecting the observed actions and the MDP's transition probabilities for reaching the observed next states. If the starting state is itself probabilistic, its initial-state factor is included as well.

Prπ(trajectory) = Pr(S_t) × π(A_t | S_t) × Pr(S_{t+1} | S_t, A_t) × π(A_{t+1} | S_{t+1}) × Pr(S_{t+2} | S_{t+1}, A_{t+1}) × ...

Comparing Target and Behavior Likelihoods

ρ = Prπ(trajectory) / Prb(trajectory)

Why Environment Factors Cancel

The target and behavior probabilities describe the same observed trajectory in the same MDP. Therefore, the initial-state and MDP transition factors appear in both complete trajectory probabilities. When the target probability is divided by the behavior probability, matching environment factors cancel. The policy-action factors differ because the policies differ, so those are the factors that remain in the final ratio.

ρ = [initial-state factor × target-action factors × transition factors] / [initial-state factor × behavior-action factors × transition factors] = target-action factors / behavior-action factors

Using the Ratio for Prediction

In off-policy learning, returns from behavior-policy trajectories are weighted according to the relative probability of those trajectories under the target and behavior policies. A trajectory that is relatively more likely under the target policy receives greater influence. A trajectory that is relatively less likely under the target policy receives less influence. The importance-sampling ratio is therefore the bridge between the distribution that supplied the samples and the distribution whose expected value is being estimated.

Practice Check

Mistakes to Avoid

• Using only the target-policy probability.

  The ratio compares target-policy likelihood with behavior-policy likelihood, so both probabilities are required.

  Fix: Divide the target-policy trajectory probability by the behavior-policy trajectory probability.

• Keeping the MDP transition probabilities in the final ratio.

  The matching transition factors occur in both complete trajectory probabilities and cancel.

  Fix: Show the complete probabilities first, then cancel the common initial-state and transition factors.

• Assuming the behavior policy must estimate its own value.

  Off-policy prediction specifically uses behavior-policy samples to estimate a quantity associated with a target policy.

  Fix: Keep the roles distinct: the behavior policy supplies experience, while the target policy defines the quantity being estimated.

• Comparing different trajectories in the numerator and denominator.

  The importance-sampling ratio compares the likelihood of the same observed trajectory under two policies.

  Fix: Use identical observed states and actions in both trajectory probabilities.

Key Takeaways

1. Importance sampling lets behavior-policy samples support estimates for a target policy.
2. A trajectory probability is built from an initial-state factor, policy probabilities for observed actions, and MDP transition probabilities for observed state changes.
3. The importance-sampling ratio is the target-policy trajectory probability divided by the behavior-policy trajectory probability.
4. Because the same trajectory is evaluated in the same MDP, matching initial-state and transition factors cancel.
5. The remaining policy-action ratio determines whether the trajectory receives greater or lesser influence in target-policy prediction.