Temporal-difference learning evaluates a policy by bootstrapping: it uses observed rewards and the current estimate of the next state's value in the same update.
TD error
The TD error is a sample Bellman residual.
Definition. For policy evaluation, the one-step TD error is \[ \delta_t=R_{t+1}+\gamma v(S_{t+1})-v(S_t). \] Tabular TD(0) updates \[ v_{t+1}(S_t)=v_t(S_t)+\alpha_t\delta_t, \] leaving other states unchanged.
Proposition. Conditionally on \(S_t=s\), the expected TD target equals \((T_\pi v)(s)\).
Proof. Take conditional expectation of \(R_{t+1}+\gamma v(S_{t+1})\) given \(S_t=s\) under policy \(\pi\). The result is exactly \(r_\pi(s)+\gamma P_\pi v(s)=(T_\pi v)(s)\).
Stochastic approximation view
TD(0) is noisy fixed-point iteration for \(T_\pi\).
Theorem. In a finite on-policy discounted MDP with all states visited sufficiently often and stepsizes satisfying \(\sum_t\alpha_t=\infty\), \(\sum_t\alpha_t^2<\infty\), tabular TD(0) converges to \(v_\pi\) under standard irreducibility assumptions.
Proof. The conditional mean update is a contraction drift toward the Bellman fixed point, and the noise is a martingale difference with bounded second moment. Robbins-Monro stochastic approximation for contractions implies convergence to the unique fixed point \(v_\pi\).
Bias and variance
TD trades Monte Carlo unbiasedness for bootstrapping bias and lower variance.
Remark. The TD target uses the current value estimate, so it is biased unless \(v=v_\pi\). It often has lower variance than the full return because it does not include the entire future reward sequence.
Mean squared projected Bellman error
With function approximation, TD converges to a projected Bellman fixed point rather than the exact value.
Definition. For a linear value class \(\{v_\theta=\Phi\theta\}\) and weighting distribution \(d\), the projected Bellman equation is \[ \Phi\theta=\Pi_d T_\pi(\Phi\theta), \] where \(\Pi_d\) is \(L^2(d)\)-projection onto the feature span.
Remark. This projection is the source of both the usefulness and the pathology of TD with function approximation, especially off-policy.
TD(0) as stochastic approximation
For policy evaluation, the tabular update is \[ V_{t+1}(S_t) =V_t(S_t)+\alpha_t\delta_t,\qquad \delta_t=R_{t+1}+\gamma V_t(S_{t+1})-V_t(S_t). \] Conditionally on \(S_t=s\), \[ E(\delta_t\mid S_t=s) =(T^\pi V_t)(s)-V_t(s), \] so TD is a noisy asynchronous fixed-point iteration.
Theorem (tabular on-policy convergence). Assume a finite MDP, bounded reward noise, an ergodic Markov chain under \(\pi\), every state visited infinitely often, and step sizes for each state satisfying \[ \sum_t\alpha_t(s)=\infty,\qquad \sum_t\alpha_t(s)^2<\infty. \] Then tabular TD(0) converges almost surely to \(V^\pi\).
The proof is an asynchronous stochastic-approximation theorem: the mean field \(T^\pi V-V\) has a globally stable root because \(T^\pi\) is a contraction, while reward and transition fluctuations form a bounded-variance martingale difference after conditioning. The square-summable condition controls cumulative noise; the nonsummable condition prevents premature freezing.
Linear TD and projected Bellman equations
For \(V_w(s)=\phi(s)^\top w\), semi-gradient TD updates \[ w_{t+1} =w_t+\alpha_t\phi_t \{R_{t+1}+\gamma\phi_{t+1}^\top w_t-\phi_t^\top w_t\}. \] Under stationarity its mean drift is \(b-Aw\), where \[ A=E[\phi_t(\phi_t-\gamma\phi_{t+1})^\top], \qquad b=E(\phi_tR_{t+1}). \] The fixed point solves \(\Phi w=\Pi_D T^\pi\Phi w\), not generally the least-squares projection of \(V^\pi\).
Proposition (approximation bound). On policy, if \(\Pi_D T^\pi\) is a \(\gamma\)-contraction in \(L_2(D)\), its fixed point \(\widehat V\in\operatorname{span}(\Phi)\) satisfies \[ \|\widehat V-V^\pi\|_D \le\frac1{\sqrt{1-\gamma^2}} \|\Pi_DV^\pi-V^\pi\|_D. \]
This compares TD with the best representable value. The factor worsens with the effective horizon and is not available without the on-policy contraction structure.
TD error is not a gradient
The expected update \(E(\delta_t\phi_t)\) is a semi-gradient: the bootstrap target contains \(w\), but its derivative is ignored. It is not the gradient of mean-squared Bellman error. The mean-squared projected Bellman error \[ \operatorname{MSPBE}(w) =\|\Pi_D(T^\pi\Phi w-\Phi w)\|_D^2 =(b-Aw)^\top C^{-1}(b-Aw), \quad C=E(\phi\phi^\top), \] has genuine gradient methods such as GTD2 and TDC, designed especially for off-policy stability.
Asymptotic fluctuations
With \(\alpha_t=a/t\) and suitable stability/mixing conditions, \(\sqrt t(w_t-w^*)\) can satisfy a central limit theorem. Its covariance solves a Lyapunov equation involving \(A\) and the long-run covariance of TD noise. Polyak--Ruppert averaging often attains a better covariance and reduces sensitivity to \(a\). Thus convergence alone does not characterize statistical efficiency.