5.4 — Off-policy Prediction via Importance Sampling¶

Chapter 5: Monte Carlo Methods · Book sections: §5.5–§5.6 Previous: 5.3 — MC Control without Exploring Starts · Next: 5.5 — Off-policy MC Control & Summary

🌱 The Big Picture¶

The problem: we want to learn the values of a target policy π (say, the greedy/optimal one), but our episodes were generated by a different behavior policy b (say, an exploratory ε-soft one). Can we still learn $v_\pi$ from b's episodes? Yes — by re-weighting the observed returns. This re-weighting trick is called importance sampling, and it's the engine of nearly all off-policy learning.

Requirement (coverage): every action that π might take must have some chance under b: $\pi(a|s) > 0 \Rightarrow b(a|s) > 0$. (You can't learn about actions you never see.)

⚖️ The importance sampling ratio¶

Given a trajectory starting at $S_t$: how much more (or less) likely was this exact trajectory under π than under b?

\[\rho_{t:T-1} \doteq \prod_{k=t}^{T-1} \frac{\pi(A_k \mid S_k)}{b(A_k \mid S_k)}\]

(The environment's transition probabilities appear in both numerator and denominator and cancel out — beautifully, the ratio depends only on the two policies, not on the unknown MDP! 🪄)

The observed return $G_t$ came from following b, so its expectation is $v_b(s)$ — wrong target. The ratio fixes it:

\[\mathbb{E}[\rho_{t:T-1} G_t \mid S_t = s] = v_\pi(s) \quad ✅\]

Intuition 🧠: if π would have taken these actions more often than b did, the trajectory is under-represented in our data → weight it up (ρ > 1). If π would rarely do this, weight it down (ρ < 1). If π would never take some action in the trajectory, ρ = 0 — that trajectory tells us nothing about π.

🧮 Two ways to average the weighted returns¶

Let $\{G_t\}_{t \in \mathcal{T}(s)}$ be returns from time steps where $s$ was visited, each with its ratio $\rho_t$ (shorthand).

1. Ordinary importance sampling¶

\[V(s) \doteq \frac{\sum_{t} \rho_t\, G_t}{|\mathcal{T}(s)|}\]

(simple average of weighted returns)

2. Weighted importance sampling¶

\[V(s) \doteq \frac{\sum_{t} \rho_t\, G_t}{\sum_{t} \rho_t}\]

(weighted average — divides by the sum of ratios)

The trade-off (exam favorite ⭐)¶

	Ordinary IS	Weighted IS
Bias	Unbiased ✅	Biased (bias → 0 as samples grow)
Variance	Unbounded in general 😱 (ratios can be huge)	Bounded (each weight ≤ 1 of total); much lower
First sample behavior	can be wild (ρ·G could be 10× the plausible value)	equals the observed return (ratio cancels)
In practice	rarely preferred	strongly preferred

Blackjack experiment (book Example 5.4): weighted IS produces far lower error from the start; ordinary IS needs orders of magnitude more episodes. And Example 5.5 shows ordinary IS estimates can have infinite variance when loops make ratios explode.

🔧 Incremental implementation (§5.6)¶

We'd like the usual New ← Old + StepSize(Target − Old) form. For weighted IS, keep a cumulative sum of weights $C(s,a)$ alongside $Q(s,a)$. For each step of an episode (processed backwards, with weight $W = \rho$ built up incrementally):

\[C \leftarrow C + W$$ $$Q \leftarrow Q + \frac{W}{C}\,\big[G - Q\big]$$ $$W \leftarrow W \cdot \frac{\pi(A_t|S_t)}{b(A_t|S_t)}\]

If $W$ hits 0 (π would never take an observed action), the rest of the episode is uninformative → break out of the loop.

🎯 Key Takeaways¶

Off-policy learning: learn target policy π's values from behavior policy b's episodes; requires coverage.
The importance sampling ratio $\rho = \prod \pi(A_k|S_k)/b(A_k|S_k)$ corrects returns; environment dynamics cancel out.
Ordinary IS: unbiased, possibly infinite variance. Weighted IS: small (vanishing) bias, much lower variance → the practical choice.
Incremental update with cumulative weights makes weighted IS cheap to run.
High variance from long products of ratios is THE recurring pain of off-policy methods — it returns in Chapters 7, 11, 12.

➡️ Next: 5.5 — Off-policy MC Control & Chapter Summary — putting it together: learn the optimal policy while behaving exploratorily.