Concepts / Off-policy Prediction with Importance Sampling

Off-policy Prediction with Importance Sampling

The central question is not whether a trajectory was observed. It is how likely that same trajectory would be under the target policy compared with the behavior policy.

  • Programming

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.

Key point

The central question is not whether a trajectory was observed. It is how likely that same trajectory would be under the target policy compared with the behavior policy.

Behavior policyObserved trajectoryImportance-samplingratioWeighted returnTarget-policyestimategeneratescompare probabilitiesadjust influencecontributes to
How can data generated by the behavior policy be reweighted so that it estimates the return associated with 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.

Formula, step by step
  1. 1
    Pr(S_t) represents the initial-state factor when the starting state is probabilistic.
  2. 2
    Each π(A | S) factor is the probability that the policy selects the observed action in the observed state.
  3. 3
    Each transition factor represents the MDP probability of reaching the observed next state after the observed state-action pair.
  4. 4
    The product continues through the state-action trajectory until its endpoint.
Initial statePr(S_t)Observed actionπ(A_t | S_t)Next statePr(S_{t+1} | S_t, A_t)Next actionπ(A_{t+1} | S_{t+1})Following statetransition factorEndpointthenenvironment transitionthenenvironment transitioncontinue
What factors make up the probability of a complete state-action trajectory, and how do the initial-state, transition, and policy probabilities combine over time?

Comparing Target and Behavior Likelihoods

Definition

The importance-sampling ratio is the probability of the observed trajectory under the target policy divided by the probability of that same trajectory under the behavior policy.

Formula, step by step
  1. 1
    Construct the complete trajectory probability under the target policy π.
  2. 2
    Construct the complete trajectory probability under the behavior policy b.
  3. 3
    Divide the target-policy probability by the behavior-policy probability.
  4. 4
    A ratio greater than one means the trajectory is relatively more likely under the target policy; a ratio less than one means it is relatively less likely under the target policy.
Worked example

A Two-Action Ratio

For two observed action selections, the target policy assigns probabilities 0.8 and 0.2. The behavior policy assigns probabilities 0.4 and 0.5 to those same observed actions. Calculate the policy-probability part of the importance-sampling ratio.

  1. 1
    Write the target factors

    The target-policy contribution is 0.8 × 0.2.

  2. 2
    Write the behavior factors

    The behavior-policy contribution is 0.4 × 0.5.

  3. 3
    Form the ratio

    Divide the target contribution by the behavior contribution: (0.8 × 0.2) / (0.4 × 0.5).

  4. 4
    Evaluate

    The numerator is 0.16 and the denominator is 0.20, so the ratio is 0.8.

Result

The policy-probability ratio is 0.8. This observed action sequence is relatively less likely under the target policy than under the behavior policy, so its influence is reduced.

Ratio1First actiontarget ÷ behaviorPartial ratio0.8 ÷ 0.4 = 2Second actiontarget ÷ behaviorTrajectory ratio2 × (0.2 ÷ 0.5) = 0.8multiplyevaluatecontinuemultiply
How does the importance-sampling ratio accumulate as each action in a sampled trajectory contributes a target-policy probability divided by a behavior-policy probability?

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.

Formula, step by step
  1. 1
    Use the same starting state and the same observed state transitions in both trajectory probabilities.
  2. 2
    Place the target policy's action-selection factors in the numerator.
  3. 3
    Place the behavior policy's action-selection factors in the denominator.
  4. 4
    Cancel the matching initial-state and MDP transition factors.
  5. 5
    The remaining ratio compares only the policies' probabilities of selecting the observed actions.
Target trajectoryinitial × target actions ×transitionsPolicy-action ratiotarget actions ÷ behavioractionsBehavior trajectoryinitial × behavior actions× transitionsdivide by behavior trajectorymatching initial and transition factors cancel
When the target-policy trajectory probability is divided by the behavior-policy trajectory probability, which factors cancel and why do only policy-action probabilities remain?

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.

Worked example

Interpreting a Ratio

Interpret the ratio 0.8 from the two-action trajectory example.

  1. 1
    Compare likelihoods

    The target-policy probability for the observed action sequence is 0.8 times the behavior-policy probability for that sequence.

  2. 2
    Adjust influence

    Because the ratio is below one, the behavior-policy return from this trajectory receives less influence when estimating the target-policy quantity.

  3. 3
    Connect to prediction

    Applying this relative weighting allows behavior-policy samples to contribute to an estimate associated with the target policy.

Result

The ratio is a reweighting factor: it indicates how strongly the observed behavior-policy trajectory should influence target-policy prediction.

Behavior policysupplies trajectoriesTarget policydefines quantityImportance-samplingratioTarget-policyestimateobserved probabilitycomparison probabilityreweights returns
Which policy supplies the experience, and which policy determines the quantity being estimated?

Practice Check

MEDIUM

A trajectory contains two observed actions. The target policy assigns probabilities 0.6 and 0.5 to them. The behavior policy assigns probabilities 0.3 and 0.5. Calculate the policy-action part of the importance-sampling ratio and state whether the trajectory receives greater or lesser influence for target-policy prediction.

Hints
  • Multiply the two target-policy probabilities.
  • Multiply the two behavior-policy probabilities.
  • Divide the target product by the behavior product.
  • Compare the result with 1.

What do you think happens?

Before calculating, predict whether the ratio will be greater than, equal to, or less than 1.

  • Greater than 1

  • Equal to 1

  • Less than 1

Reveal answer
Answer:

Greater than 1

The target product is 0.6 × 0.5 = 0.30, while the behavior product is 0.3 × 0.5 = 0.15. Their ratio is 0.30 / 0.15 = 2, so the trajectory is relatively more likely under the target policy and receives greater influence.

Mistakes to Avoid

  • Common mistake

    Using only the target-policy probability.

    What it looks like

    Treating 0.8 as the importance-sampling ratio in the source example.

    Why it fails

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

    Do this instead

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

  • Common mistake

    Keeping the MDP transition probabilities in the final ratio.

    What it looks like

    Writing a final ratio that still contains unmatched transition terms for the same observed trajectory.

    Why it fails

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

    Do this instead

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

  • Common mistake

    Assuming the behavior policy must estimate its own value.

    What it looks like

    Ignoring the target policy because the samples were generated by the behavior policy.

    Why it fails

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

    Do this instead

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

  • Common mistake

    Comparing different trajectories in the numerator and denominator.

    What it looks like

    Using the target probability of one action sequence and the behavior probability of another.

    Why it fails

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

    Do this instead

    Use identical observed states and actions in both trajectory probabilities.

Best practice

When calculating a ratio, write the full trajectory structure before simplifying it. This makes it clear which factors come from action selection, which come from the MDP, and why the shared environment factors cancel.

Key Takeaways

  1. 1
    Importance sampling lets behavior-policy samples support estimates for a target policy.
  2. 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. 3
    The importance-sampling ratio is the target-policy trajectory probability divided by the behavior-policy trajectory probability.
  4. 4
    Because the same trajectory is evaluated in the same MDP, matching initial-state and transition factors cancel.
  5. 5
    The remaining policy-action ratio determines whether the trajectory receives greater or lesser influence in target-policy prediction.

At a glance

  • Importance sampling addresses the mismatch between the policy that generates samples and the policy whose value is being estimated.
  • A state-action trajectory probability combines policy action-selection factors with MDP transition factors.
  • The importance-sampling ratio compares the same trajectory under the target and behavior policies.
  • Common initial-state and transition factors cancel, leaving a ratio of policy-action probabilities.
  • This ratio reweights behavior-policy returns so they can contribute to target-policy prediction.

Related Topics

Related concepts

More concepts starting with O