Chapter 11: *Off-policy Methods with Approximation

The extension to function approximation is significantly different and harder for off-policy learning than for on-policy. Tabular off-policy methods extend to semi-gradient algorithms, but these do not converge as robustly as under on-policy training. This chapter explores convergence problems, linear theory, learnability, and new algorithms with stronger guarantees.

The challenge of off-policy learning has two parts:

• Part 1 (tabular): correcting the update target — addressed by importance sampling
• Part 2 (function approx only): the update distribution doesn't match on-policy — causes instability

To convert tabular off-policy algorithms to semi-gradient form, replace array updates with weight vector updates using approximate value functions and gradients. The per-step importance sampling ratio:

Semi-gradient off-policy TD(0) (state values):
w_t+1 = w_t + αρ_tδ_t∇v̂(S_t, w_t)

For action values, the one-step algorithm is semi-gradient Expected Sarsa (no importance sampling needed for the single action). Multi-step algorithms use ρ_t+1···ρ_t+n−1. The tree backup algorithm (from Ch.7) needs no importance sampling at all.

Simple w-to-2w example: Two states with values w and 2w. Transition from state 1→2 with reward 0. TD error = (2γ−1)w. Update: w_t+1 = (1+α(2γ−1))w_t. If γ > 0.5, the factor exceeds 1 and w diverges to infinity. This is only possible off-policy because ρ_t=0 on other transitions prevents counter-balancing updates.

Baird's Counterexample (Figure 11.1): A 7-state, 2-action MDP. Behavior policy selects dashed/solid actions with prob 6/7 and 1/7 (uniform next-state distribution). Target policy always takes solid action (→ state 7). Linear parameterization with 8 features. Semi-gradient TD(0) and even DP diverge for any positive step size! Changing to on-policy distribution guarantees convergence.

Tsitsiklis & Van Roy's Counterexample: Even finding the least-squares best approximation at each DP step doesn't prevent divergence. The w-to-2w example extended with a terminal state shows w_k+1 = (6−4ε)/(5−4ε) · w_k, which diverges when γ > 5/(6−4ε).

The danger of instability and divergence arises whenever all three of the following are combined:

The danger is not due to control, GPI, learning, or environmental uncertainty — it arises in the simpler prediction case and even in planning (DP) with known environments. If any two elements are present but not all three, instability can be avoided. Can any be given up?

With linear approximation, the representable value functions form a plane (subspace) in the |S|-dimensional space. Key geometric concepts:

• Projection operator Π: maps any value function to its closest representable one (in µ-norm)
• Bellman operator B_π: takes representable v_w to B_πv_w, generally outside the subspace
• VE = ‖v_w − v_π‖²_µ — minimized at Πv_π (MC solution)
• BE = ‖B_πv_w − v_w‖²_µ — Bellman error, minimized at a different point
• PBE = ‖Π(B_πv_w − v_w)‖²_µ — projected Bellman error, zero at TD fixed point w_TD

The Bellman error at state s is the expectation of the TD error: δ̄_w(s) = E_π[δ_t | S_t=s]. The TD fixed point w_TD = A⁻¹b always has zero PBE under linear approximation, but may not be stable off-policy.

True SGD methods always go downhill and have excellent convergence. Only MC methods are true SGD among algorithms seen so far. Can we do SGD on BE or TDE?

TDE minimization leads to the naive residual-gradient algorithm:
w_t+1 = w_t + αρ_tδ_t[∇v̂(S_t) − γ∇v̂(S_t+1)]. This converges robustly but to wrong values! Example: A-split problem — true values (½,1,0) vs learned (½,¾,¼).

BE minimization (residual-gradient algorithm): requires two independent samples of next state from the same state (double sampling). Works with deterministic environments or simulated environments (roll-back). But:

• Empirically much slower than semi-gradient methods
• Converges to wrong values with genuine function approximation (A-presplit example)
• BE is not learnable from data (next section)

Learnability: can a quantity be determined from the observable data distribution (feature vectors, actions, rewards)? Many quantities in RL are well-defined from the MDP but cannot be computed from observed data.

Summary of objectives:
Learnable: RE (and its optimal w*), TDE, PBE (and its optimal w*)
Not learnable: VE (but w* is learnable via RE), BE (and w* is also NOT learnable)

Gradient-TD methods are SGD methods for minimizing the PBE — they have robust convergence even under off-policy training and nonlinear function approximation. The PBE gradient (linear case):

Store a second learned vector v that approximates E[x_tx_t^T]⁻¹E[ρ_tδ_tx_t], learned by LMS rule: v_t+1 = v_t + βρ_t(δ_t−v_t^Tx_t)x_t

GTD2: w_t+1 = w_t + αρ_t(x_t − γx_t+1)x_t^Tv_t
TDC (GTD(0)): w_t+1 = w_t + αρ_t(δ_tx_t − γx_t+1x_t^Tv_t)

Both are O(d) per step (if x_t^Tv_t computed first). They involve two learning processes (a cascade): primary for w, secondary for v. Convergence proofs use two-time-scale analysis (β→0, α/β→0). Extensions: GQ (action values), GTD(λ), nonlinear, hybrid methods.

Second major strategy: reweight the states to return the update distribution to the on-policy distribution. Linear semi-gradient TD is stable under on-policy distribution due to positive definiteness of matrix A. Emphatic-TD restores this match using interest I_t and emphasis M_t:

On Baird's counterexample, Emphatic-TD converges to the optimal solution (VE→0) in expectation, with all weights converging. However, in practice, the variance is very high, making consistent results hard to obtain computationally.

Off-policy learning is inherently higher variance than on-policy. Importance sampling involves products of ratios — expected value is 1 but actual values can be extremely high or zero, causing occasional very large SGD steps. Strategies:

• Weighted importance sampling (harder with function approximation)
• Tree backup algorithm (no importance sampling needed)
• Constrain target policy to be close to behavior policy ("recognizers")
• Polyak-Ruppert averaging, adaptive per-component step sizes

Key takeaways:

• Off-policy + function approximation is a tempting but hard challenge
• The deadly triad: function approximation + bootstrapping + off-policy = potential divergence
• BE is not learnable from data — rules out residual-gradient methods in model-free settings
• VE is not learnable, but its optimal parameter w* IS learnable (via RE)
• Gradient-TD methods (GTD2, TDC): SGD on PBE, O(d), robust convergence
• Emphatic-TD: reweights updates to restore on-policy stability
• High variance remains a fundamental challenge for off-policy methods
• The whole area is relatively new and unsettled — best methods still unclear