Skip to content
Tutorials Center
My learning

Topics

Lesson 16 of 37 ยท Monte Carlo and Temporal Difference

Off-Policy Learning and Importance Sampling

Learn the difference between on-policy and off-policy learning, behavior and target policies, importance sampling ratios, ordinary versus weighted importance sampling and their variance, with Python.

Every method so far learned about the policy that generated the data. That is on-policy learning, and it forces a compromise: to explore you must behave randomly, but to be optimal you must behave greedily. Off-policy learning removes the conflict by using two policies:

  • The behavior policy b generates the experience. It is exploratory.
  • The target policy pi is the one we want to evaluate or improve. It can be greedy, or deterministic.

The learner uses data from b to estimate things about pi. This also lets you learn from old data, from other agents, from human demonstrations, or about many policies from one data stream. The price is a statistical problem: the data come from the "wrong" distribution. Importance sampling is the standard fix.

Coverage

For this to work, b must be able to do everything pi does: if pi(a | s) > 0, then b(a | s) > 0. This is the assumption of coverage. A greedy pi is fine because a random or epsilon-greedy b covers it. The reverse fails: you cannot learn about exploring actions from a purely greedy behavior.

Importance sampling in one picture

Suppose you want E_pi[X] but only have samples from b. Reweight each sample by how much more (or less) likely pi was to produce it than b:

E_pi[X] = E_b[ rho * X ] with rho = pi(x) / b(x)

For a whole trajectory S_t, A_t, ..., S_T, the importance-sampling ratio is the product over steps (the environment's transition probabilities cancel, which is why this works without a model):

rho_{t:T-1} = product for k = t to T-1 of pi(A_k | S_k) / b(A_k | S_k)

Ordinary versus weighted importance sampling

Given n episodes with ratios rho_i and returns G_i, there are two estimators of v_pi:

  • Ordinary IS: V = (sum of rho_i * G_i) / n. Unbiased, but variance can be unbounded (one rare huge ratio can wreck the estimate).
  • Weighted IS: V = (sum of rho_i * G_i) / (sum of rho_i). Biased (the bias vanishes as n grows), but its variance is far lower, so it is preferred in practice.
flowchart LR
    B["behavior policy b (explores)"] -->|"episodes"| D["data: (s, a, r) sequences"]
    D -->|"multiply by rho = product of pi/b"| W["weighted returns"]
    W --> V["estimate of v_pi"]

Try it on a one-step problem

Start with the smallest case: one random outcome. There are three possible returns (1, 2 and 10). The target policy produces the big one with 80% probability, but the behavior picks all three equally. The true value is 0.1*1 + 0.1*2 + 0.8*10 = 8.3. Repeat the experiment 300 times for several sample sizes and look at the average and the spread of each estimator.

Python Ordinary versus weighted IS, one step

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Both estimators converge to 8.3. For small n the weighted estimator has a smaller spread, and its small bias disappears as n grows. Here the ratios are bounded, so ordinary IS behaves well; in sequential problems ratios multiply, and the picture changes.

Off-policy Monte Carlo prediction on the grid world

Now the real thing: episodes with many steps. The behavior is the uniform random policy on our 4x4 grid. The target is a good policy: with probability 0.7 it moves along a shortest path to the nearest terminal corner, otherwise it moves randomly. We estimate the target's value at square 3 (a far corner) from random-behavior data only, and compare against the exact answer from the Bellman linear system.

Python Off-policy MC prediction with importance sampling

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Both estimates approach the exact value of about -4.24, but they behave differently along the way: the weighted estimate is already close after a few hundred episodes, while the ordinary estimate swings more from checkpoint to checkpoint, because the few episodes in which the random behavior happened to act like the target carry large ratios and dominate the sum. Here the largest ratio is only about 16 because episodes are short. Ratios are products, so they grow exponentially with episode length, and in long tasks this variance problem of importance sampling becomes severe.

Practical notes

  • Discounting-aware and per-decision IS reduce variance by not multiplying ratios for rewards that arrived before the ratio could matter. They are refinements of the same idea.
  • Off-policy MC control learns a deterministic greedy target from epsilon-soft behavior. It only learns from the tail of each episode after the last non-greedy action, which makes it slow. This is one reason TD methods like Q-learning became the standard off-policy approach: they correct step by step without long products.
  • Truncate or clip ratios in deep RL (for example in V-trace and PPO) to keep variance in check.

Common mistakes

  • Using a behavior policy that gives zero probability to an action the target might take (breaks coverage).
  • Forgetting that ordinary IS is unbiased but can have infinite variance, and that weighted IS is biased for finite samples.
  • Multiplying the ratio by the transition probabilities. They cancel, so you need only the policies.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. What is the difference between a behavior policy and a target policy?

    Off-policy learning separates the policy that acts (exploring) from the policy that is learned about.
  2. 2. What does the coverage assumption require?

    pi(a|s) > 0 implies b(a|s) > 0; otherwise some target trajectories can never be observed.
  3. 3. Which is true of weighted importance sampling compared with ordinary?

    Normalizing by the sum of ratios reduces variance, at the cost of small bias that vanishes with data.
  4. 4. Why do transition probabilities not appear in the importance sampling ratio?

    Both policies face the same environment, so the dynamics cancel in the ratio of trajectory probabilities.

Summary

  • Off-policy learning separates the exploratory behavior policy from the target policy being learned.
  • Importance sampling reweights returns by the product of pi / b along the trajectory; no model is needed.
  • Ordinary IS is unbiased but can be wildly variable; weighted IS is biased but far more stable.
  • Long episodes make ratios explode, which motivates step-by-step off-policy methods such as Q-learning.

Next: Temporal-Difference Learning: TD(0)