Fixed-policy linear evaluation

Sutton and colleagues’ ICML 2009 work studies Vθ(s)=ϕ(s)⊤θV_\theta(s)=\phi(s)^\top\theta. Ordinary off-policy TD with approximation can be unstable; residual-gradient approaches have distinct objective and sampling difficulties. GTD2/TDC use MSPBE and an auxiliary vector for linear-time updates.

Projected error

With ϕ′=ϕ(s′)\phi'=\phi(s') and δ=r+γθ⊤ϕ′−θ⊤ϕ\delta=r+\gamma\theta^\top\phi'-\theta^\top\phi, appropriately weighted expectations give

A=E[ϕ(ϕ−γϕ′)⊤],b=E[rϕ],C=E[ϕϕ⊤],MSPBE=(b−Aθ)⊤C−1(b−Aθ).A=\mathbb E[\phi(\phi-\gamma\phi')^\top],\quad b=\mathbb E[r\phi],\quad C=\mathbb E[\phi\phi^\top],\qquad \mathrm{MSPBE}=(b-A\theta)^\top C^{-1}(b-A\theta).

Explicit off-policy ratios are omitted for readability here. This is not an uncorrected arbitrary-replay recipe. Coverage, invertibility, and expectation definitions belong to the assumptions.

Auxiliary and primary recursions

Track w≈C−1E[δϕ]w\approx C^{-1}\mathbb E[\delta\phi] through

w←w+β(δ−ϕ⊤w)ϕ.w\leftarrow w+\beta(\delta-\phi^\top w)\phi.

Common simplified GTD2 and TDC directions are respectively (ϕ−γϕ′)(ϕ⊤w)(\phi-\gamma\phi')(\phi^\top w) and δϕ−γϕ′(ϕ⊤w)\delta\phi-\gamma\phi'(\phi^\top w). With accurate tracking, their expectations relate to the same MSPBE gradient; finite-step recursions differ.

The auxiliary recursion avoids per-step matrix inversion and a naive product of correlated single-sample estimates. Timescale and stability assumptions remain important.

Scope of the guarantees

The notes emphasize linear complexity and off-policy stability, but the guarantees concern fixed-policy linear evaluation. They are not universal global-convergence results for neural networks, changing target policies, or control. Runtime comparisons are configuration-specific.

Reading and a proposed check

Start with Bellman errors and projection geometry, then stochastic approximation. A Baird-style example could compare TD, residual gradients, and GTD2/TDC with explicit sampling and step sizes. No such experiment was rerun here.

Selected references from the source notes