Approximate dynamic programming studies how errors in Bellman backups, projections, simulations, and greedy steps propagate through control algorithms.
Approximate value iteration
Each Bellman backup may be followed by approximation error.
Definition. Approximate value iteration has the form \[ v_{k+1}=T_*v_k+\varepsilon_k. \]
Proposition. If \(\|\varepsilon_k\|_\infty\le\varepsilon\), then \[ \limsup_{k\to\infty}\|v_k-v_*\|_\infty\le\frac{\varepsilon}{1-\gamma}. \]
Proof. Use contraction: \[ \|v_{k+1}-v_*\|_\infty\le\gamma\|v_k-v_*\|_\infty+\varepsilon. \] Iterating this scalar recursion and letting \(k\to\infty\) gives the bound.
Approximate greedy policies
Control loss depends on both value approximation and greedy-step error.
Definition. A policy \(\pi\) is \(\eta\)-greedy with respect to \(v\) if \[ T_\pi v\ge T_*v-\eta\mathbf 1. \]
Theorem. If \(\pi\) is \(\eta\)-greedy with respect to \(v\), then \[ \|v_*-v_\pi\|_\infty \le \frac{2\gamma}{1-\gamma}\|v-v_*\|_\infty+\frac{\eta}{1-\gamma}. \]
Proof. Compare \(T_*v_*\) and \(T_\pi v_\pi\), adding and subtracting \(T_*v\) and \(T_\pi v\). The approximation terms are bounded by \(\gamma\|v-v_*\|_\infty\), the greedy error contributes \(\eta\), and the remaining \(T_\pi(v-v_\pi)\) term is absorbed by \(1-\gamma\).
Simulation error
Sampled Bellman backups introduce statistical error in addition to approximation error.
Remark. Fitted value iteration and fitted Q-iteration replace conditional expectations by regression estimates. Their analysis combines supervised-learning generalization error with Bellman error propagation.
Error norms
The norm in which approximation is small matters for control.
Remark. Sup-norm error gives clean worst-case control guarantees. \(L^2\)-type errors are often easier statistically but require concentrability coefficients to translate behavior-distribution accuracy into target-policy performance.
Approximate value iteration
Suppose \[ V_{k+1}=TV_k+\varepsilon_k, \qquad \|\varepsilon_k\|_\infty\le\varepsilon. \] Then contraction gives \[ \|V_k-V^*\|_\infty \le\gamma^k\|V_0-V^*\|_\infty +\sum_{j=0}^{k-1}\gamma^{k-1-j}\|\varepsilon_j\|_\infty, \] so \[ \limsup_k\|V_k-V^*\|_\infty\le\frac{\varepsilon}{1-\gamma}. \] If \(\pi_k\) is greedy with respect to \(V_k\), its eventual loss can be as large as order \(\gamma\varepsilon/(1-\gamma)^2\).
Approximate policy iteration
Let \(\widehat V_k\) approximate \(V^{\pi_k}\), and let \(\pi_{k+1}\) be \(\delta_k\)-greedy: \[ T\widehat V_k \le T^{\pi_{k+1}}\widehat V_k+\delta_k\mathbf1. \] The performance-difference identity and resolvent \((I-\gamma P_\pi)^{-1}\) propagate evaluation and greedification errors. Sup-norm analysis yields effective-horizon factors; distribution-dependent analysis can be sharper but needs coverage coefficients.
Fitted value and Q iteration
Given transitions \((S_i,A_i,R_i,S_i')\), fitted Q iteration forms targets \[ Y_i=R_i+\gamma\max_aQ_k(S_i',a) \] and regresses \(Y_i\) onto \((S_i,A_i)\) in a class \(\mathcal F\). A useful error decomposition is \[ \widehat Q_{k+1}-\mathcal TQ_k = \underbrace{\Pi_{\mathcal F}\mathcal TQ_k-\mathcal TQ_k}_{\text{approximation}} + \underbrace{\widehat Q_{k+1} -\Pi_{\mathcal F}\mathcal TQ_k}_{\text{estimation/optimization}}. \] Bellman propagation then converts one-step errors into policy loss.
Concentrability
Definition. A concentrability coefficient controls mismatch between state-action distributions generated by policies of interest and the data law \(\nu\), for example \[ C_\infty =\sup_{\pi,t} \left\|\frac{\mathrm{d}(\rho P_\pi^t)} {\mathrm{d}\nu_S}\right\|_\infty. \]
If this is infinite, a small \(L_2(\nu)\) Bellman error can hide arbitrarily large error where the learned policy visits. Offline RL is therefore impossible without some coverage, structural extrapolation assumption, or conservative restriction on the learned policy.
Simulation lemmas
Theorem (model perturbation). If two discounted MDPs satisfy \[ \|r-\tilde r\|_\infty\le\varepsilon_r,\qquad \sup_{s,a}\|P(\cdot\mid s,a)-\tilde P(\cdot\mid s,a)\|_{\mathrm{TV}} \le\varepsilon_P, \] and rewards are bounded by \(R_{\max}\), then for every policy, \[ \|V^\pi-\tilde V^\pi\|_\infty \le\frac{\varepsilon_r}{1-\gamma} +\frac{2\gamma R_{\max}\varepsilon_P}{(1-\gamma)^2}. \]
Proof. Subtract the two Bellman equations. The reward term contributes \(\varepsilon_r\); transition error against \(\tilde V^\pi\), whose sup norm is at most \(R_{\max}/(1-\gamma)\), contributes \(2\gamma R_{\max}\varepsilon_P/(1-\gamma)\). Move the remaining \(\gamma\|V^\pi-\tilde V^\pi\|\) term to the left.