Off-Policy Learning with Approximation

Training on data from one policy while chasing the values of another sounds efficient, until bootstrapping plus function approximation turns small errors into runaway weights.

With features 1 and 2 and discount 0.9, off-policy TD multiplies one weight by 1.08 each step toward infinity while on-policy sampling shrinks it by 0.96

Why Does This Exist?

Real agents almost never learn from the policy they are trying to evaluate. The data comes from an older policy, a safe exploratory policy, or a replay buffer full of last week's behavior, while the values being chased belong to the shiny new target policy. That mismatch is off-policy learning, and every practical system needs it.

Three conveniences make it scale, and each one is harmless on its own:

Function approximation stands in for giant state spaces. You cannot keep a table of every camera image, so a weight vector $\mathbf{w}$ plus features $\mathbf{x}(s)$ does the job.
Bootstrapping updates from the next state's estimate instead of waiting for an episode to end. That is temporal difference learning: fast, online, no waiting.
Off-policy data lets you reuse experience gathered under some behavior policy $b$ while evaluating a different target policy $\pi$ .

Pairs of these are safe. Tabular Q-learning is off-policy plus bootstrapping with no approximation, and it converges. Monte Carlo with linear features is approximation plus off-policy data with no bootstrapping, and it is just regression. On-policy TD is approximation plus bootstrapping with matching distributions, and it settles down.

Combine all three and the guarantees evaporate. This page shows exactly how, on the smallest example that breaks. For the name of the pattern, see the deadly triad. For a bigger demonstration, see Baird's counterexample. For the family of fixes, see gradient TD methods.

The one idea you need first

Semi-gradient TD(0) adjusts weights with $\mathbf{w} \leftarrow \mathbf{w} + \alpha \delta_t \mathbf{x}(S_t)$ , where the TD error $\delta_t = R_{t+1} + \gamma \hat{v}(S_{t+1}, \mathbf{w}) - \hat{v}(S_t, \mathbf{w})$ compares the current estimate against a bootstrapped target built from the same weights. On-policy, the states arrive in the target policy's own frequencies, and that weighting makes the update a contraction. Off-policy, the weighting belongs to someone else, and the contraction proof no longer applies. The full on-policy story is in semi-gradient TD.

Think of It Like This

Two surveyors sharing one map

Two surveyors share a single paper map of a valley. The first surveyor walks the north ridge every day and pencils in corrections, but only for the north ridge. The second surveyor never visits at all; she just reads the map and plans routes for the south face, trusting whatever is written down.

The catch is that the map is drawn on stretchy rubber with only a few printed grid lines, so each pencil correction tugs its neighbours along. The north surveyor's daily tweaks slowly drag the south face markings out of place. The south surveyor plans from those dragged markings, reports satisfaction, and the north surveyor keeps correcting against a map that keeps moving. Each round stretches the rubber a little further, and the elevations printed on the map climb toward nonsense.

Where it stops: surveyors can walk over and check a peak with their own eyes. Semi-gradient TD has no independent eyes. Its target is built from its own weights, so once the feedback loop turns positive there is nothing outside the loop to pull it back.

How It Actually Works

Use linear features, so $\hat{v}(s, \mathbf{w}) = \mathbf{w}^\top \mathbf{x}(s)$ . States arrive with behavior frequencies $\mu_b(s)$ , collected in a diagonal weight matrix $\mathbf{D}_b$ . TD wants to satisfy the projected Bellman equation $\mathbf{X}\mathbf{w} = \Pi_b T_\pi(\mathbf{X}\mathbf{w})$ , where $\Pi_b$ is the least-squares projection weighted by $\mathbf{D}_b$ and $T_\pi$ is the target policy's Bellman operator.

Unwrap that into a linear system $\mathbf{A}\mathbf{w} = \mathbf{b}$ with $\mathbf{A} = \mathbf{X}^\top \mathbf{D}_b (\mathbf{I} - \gamma \mathbf{P}_\pi) \mathbf{X}$ . The expected update is $\mathbb{E}[\Delta \mathbf{w}] = \alpha(\mathbf{b} - \mathbf{A}\mathbf{w})$ , which converges only if $\mathbf{A}$ is positive definite, meaning every eigenvalue has positive real part. On-policy, $\mathbf{D}_b$ equals the target stationary distribution and the math works out. Off-policy, $\mathbf{D}_b$ is the wrong weighting, $\mathbf{A}$ can grow a negative eigenvalue, and then the iteration matrix $(\mathbf{I} - \alpha \mathbf{A})$ has an eigenvalue bigger than 1. Every step multiplies the error by a number above 1. That is divergence, and no step size rescues it, because shrinking $\alpha$ only moves the multiplier closer to 1 from above.

Worked example

Two states, one weight $w$ , features $\mathbf{x}(s_1) = 1$ and $\mathbf{x}(s_2) = 2$ , discount $\gamma = 0.9$ , step size $\alpha = 0.1$ , start $w_0 = 10$ . All rewards are 0, so the true values are 0 and $w^* = 0$ . This is the Tsitsiklis and Van Roy setup from 1997.

Off-policy, only the transition $s_1 \to s_2$ is ever sampled. The TD error is $\delta_t = 0 + 0.9(2w_t) - 1w_t = 0.8w_t$ , and the update is $w_{t+1} = w_t + 0.1(0.8w_t)(1) = 1.08w_t$ . The multiplier 1.08 sits above 1, so:

$w_0 = 10$ , $\delta_0 = 8.0$ , $w_1 = 10.8$
$\delta_1 = 8.64$ , $w_2 = 11.664$
$\delta_2 = 9.3312$ , $w_3 = 12.5971$

After $k$ steps $w_k = 10(1.08)^k$ , marching to infinity while the truth sits at 0.

On-policy, only the absorbing transition $s_2 \to s_2$ is sampled. Then $\delta_t = 0.9(2w_t) - 2w_t = -0.2w_t$ and $w_{t+1} = w_t + 0.1(-0.2w_t)(2) = 0.96w_t$ :

$w_0 = 10$ , $\delta_0 = -2.0$ , $w_1 = 9.6$
$\delta_1 = -1.92$ , $w_2 = 9.216$
$\delta_2 = -1.8432$ , $w_3 = 8.8474$

Same features, same discount, same start. The only difference is which distribution feeds the updates, and it flips growth into shrinkage.

Code

This snippet replays both traces from the worked example so you can see the multiplier at work:

1def td_weight_trace(sampling: str, steps: int = 3) -> list[float]:2    """One-weight TD trace on the two-state example from the worked section."""3    w = 10.04    gamma, alpha = 0.9, 0.15    trace: list[float] = []6    for _ in range(steps):7        if sampling == "off":8            delta = gamma * 2.0 * w - 1.0 * w9            w = w + alpha * delta * 1.010        else:11            delta = gamma * 2.0 * w - 2.0 * w12            w = w + alpha * delta * 2.013        trace.append(round(w, 4))14    return trace15
16
17print(td_weight_trace("off"))  # -> [10.8, 11.664, 12.5971]18print(td_weight_trace("on"))  # -> [9.6, 9.216, 8.8474]

The off-policy trace grows every step while the on-policy trace shrinks, exactly as the hand computation says.

Watch Out For

Importance ratios do not fix the state weighting

When people meet this divergence, the first reflex is to weight each update by $\rho_t = \pi(A_t \mid S_t) / b(A_t \mid S_t)$ and call it fixed. It is not. Those ratios correct which actions get emphasized, but the states themselves still arrive in behavior frequencies $\mu_b$ . The matrix $\mathbf{D}_b$ stays wrong, $\mathbf{A}$ keeps its negative eigenvalue, and the weights still blow up, now with extra variance from the ratios on top.

If you need stability under all three conditions, reach for a true fix: gradient TD methods, emphatic weighting that repairs the state distribution, or target networks that slow the feedback loop.

A smaller step size only slows the explosion

Another reflex is to turn $\alpha$ down until the shaking stops. Check the multiplier: $1 + \alpha(0.8)$ stays above 1 for every positive $\alpha$ . At $\alpha = 0.001$ the weight still grows, just 80 times slower, so short runs look stable and long runs still overflow. A learning rate that only delays the blowup is not a cure. If your off-policy linear TD looks fine for a thousand steps and then drifts upward forever, suspect the distribution, not the step size.

The Quick Version

Off-policy learning with approximation combines three conveniences: linear features, bootstrapped TD targets, and data from a different behavior policy.
Any two of the three are safe, but all three together can make the projected Bellman operator expand instead of contract.
Convergence needs the matrix $\mathbf{A} = \mathbf{X}^\top \mathbf{D}_b (\mathbf{I} - \gamma \mathbf{P}_\pi) \mathbf{X}$ positive definite, and off-policy weighting can break exactly that.
In the two-state example the weight multiplies by 1.08 per step off-policy and 0.96 on-policy, from the same start of 10.
Action importance ratios do not repair the state distribution mismatch, and shrinking the step size only slows the growth.