Function approximation is necessary in large state spaces, but it changes exact dynamic programming into projected or approximate fixed-point problems.
Approximate value classes
A value function is represented by parameters rather than a table.
Definition. A parametric value approximation has the form \(v_\theta(s)\). In the linear case, \(v_\theta(s)=\phi(s)^\top\theta\), where \(\phi(s)\in\mathbb R^d\).
Remark. Approximation error is unavoidable when \(v_\pi\) is not in the chosen class. Estimation and bootstrapping errors then sit on top of that approximation error.
Projected Bellman equation
With linear approximation, TD seeks a projected fixed point.
Definition. Let \(\Phi\) be the feature matrix and \(D\) a state weighting distribution. The \(D\)-orthogonal projection onto the feature span is \(\Pi_D\). The projected Bellman equation is \[ \Phi\theta=\Pi_DT_\pi(\Phi\theta). \]
Theorem. If \(\Phi^\top D(I-\gamma P_\pi)\Phi\) is nonsingular, the projected Bellman equation has a unique solution satisfying \[ \Phi^\top D\{r_\pi+\gamma P_\pi\Phi\theta-\Phi\theta\}=0. \]
Proof. The projection residual is orthogonal to the feature span in the \(D\)-inner product. Thus \(\Phi\theta=\Pi_DT_\pi\Phi\theta\) is equivalent to \(\Phi^\top D(T_\pi\Phi\theta-\Phi\theta)=0\). Expanding \(T_\pi\) gives the displayed linear system. Nonsingularity gives uniqueness.
Deadly triad
Function approximation, bootstrapping, and off-policy learning can break contraction.
Remark. In the tabular on-policy discounted case, Bellman operators are contractions in sup norm. With projection and off-policy weighting, the composed operator \(\Pi_DT_\pi\) need not be a contraction in the relevant norm, so iterative methods may diverge.
Gradient versus semi-gradient
Many practical updates are not gradients of a true objective.
Definition. A semi-gradient TD update differentiates only the current estimate \(v_\theta(S_t)\), treating the bootstrap target \(R_{t+1}+\gamma v_\theta(S_{t+1})\) as fixed.
Remark. This shortcut is computationally convenient but changes the optimization geometry. Gradient-TD methods were designed to optimize well-defined projected Bellman-error objectives.
Projection geometry
Let \(\mathcal V=\{\Phi w:w\in\mathbb R^d\}\) and let \(\Pi_D\) be orthogonal projection in a state distribution \(D\). Three distinct targets are often confused:
- best value approximation \(\Pi_DV^\pi\);
- projected Bellman fixed point \(\widehat V=\Pi_DT^\pi\widehat V\);
- Bellman-residual minimizer \(\arg\min_{V\in\mathcal V}\|T^\pi V-V\|_D^2\).
They generally differ because \(\Pi_D\) and \(T^\pi\) do not commute.
On-policy stability
Theorem. If \(D\) is stationary for \(P_\pi\), then \(P_\pi\) is nonexpansive in \(L_2(D)\), so \(\Pi_DT^\pi\) is a \(\gamma\)-contraction. The projected Bellman equation has a unique solution, and linear TD converges under standard stochastic approximation assumptions.
Proof. Conditional Jensen gives \[ \|P_\pi f\|_D^2 =E\{E[f(S_{t+1})\mid S_t]^2\} \le E f(S_{t+1})^2=\|f\|_D^2. \] Orthogonal projection is nonexpansive, hence \[ \|\Pi_DT^\pi V-\Pi_DT^\pi W\|_D \le\gamma\|V-W\|_D. \]
The deadly triad
Off-policy sampling replaces \(D\) by a behavior distribution not stationary for \(P_\pi\). The nonexpansiveness proof breaks, and the matrix \[ A=\Phi^\top D_\mu(I-\gamma P_\pi)\Phi \] may have eigenvalues with negative real part. Semi-gradient TD then follows an unstable mean ODE. Baird's counterexample constructs a seven-state linear system where bounded features, deterministic dynamics, and zero rewards still produce divergence under off-policy bootstrapping.
Gradient temporal-difference methods
The mean-squared projected Bellman error is \[ \operatorname{MSPBE}(w) =(b-Aw)^\top C^{-1}(b-Aw), \quad C=\Phi^\top D_\mu\Phi. \] Introducing \(h\approx C^{-1}(b-Aw)\) yields two-time-scale stochastic gradients without double sampling: \[ h_{t+1}=h_t+\beta_t\{\delta_t-\phi_t^\top h_t\}\phi_t, \] \[ w_{t+1}=w_t+\alpha_t \{\phi_t-\gamma\rho_t\phi_{t+1}\}(\phi_t^\top h_t). \] Exact forms vary between GTD2 and TDC, but their purpose is to optimize a true stable objective off-policy.
Nonlinear approximation
For neural \(V_w\) or \(Q_w\), projection is onto a nonconvex manifold and the target changes with \(w\). Target networks freeze the bootstrap target for several steps; replay changes correlation and coverage; double estimators reduce maximization bias. These devices can stabilize training but offer no general replacement for the linear contraction theorem. Approximation, optimization, and statistical errors must be analyzed separately.