value-function approximation error bounds

Once you replace an exact value table with a function approximator — a linear model, a neural net — you accept some fitting error at every step. The frightening question is whether those small per-step errors stay small, or whether the bootstrapping in dynamic programming amplifies them into a large gap between the policy you end up with and the optimal one. Approximation-error bounds answer exactly how the local error budget translates into final performance loss.

The classic result for approximate value or policy iteration says the performance gap of the greedy policy is bounded by the worst per-iteration approximation error, amplified by a factor of roughly 2γ/(1−γ)². That squared-horizon term is the warning: in long-horizon problems even tiny approximation errors can blow up. Sharper analyses replace the max-norm error with weighted L2 norms tied to the state-visitation distribution, which is why training on the right distribution of states matters so much in practice.

These bounds are worst-case and often loose, but their structure is the lesson: error compounds through bootstrapping, the horizon is the amplifier, and the distribution you evaluate error under is part of the bound, not an afterthought.