JOVANA
Explore Library Glossary Getting Started Three Levels Fields How it works Mission
Join the mission
All guides

Theory with function approximation

When the state space is astronomical, what structure makes RL provably tractable — error bounds, the simulation lemma, linear MDPs, and Bellman rank.

Why tabular bounds do not transfer

Every bound so far scaled with the number of states S. For chess, Go, or pixels, S is effectively infinite, so those bounds are vacuous. We must use function approximation to generalise across states — and the price is that the comforting contraction of guide 2 can break. When bootstrapping, off-policy data, and function approximation combine — the deadly triad — value estimates can diverge, so naive tabular intuition is not just loose, it can be flat wrong.

When the state count S is effectively infinite, a function approximator generalizes across states instead of storing one value per state in a table.

A multilayer neural network mapping a state's features through hidden layers to a value output.

How approximation error propagates

Before assuming nice structure, you must know how much a small per-step approximation error costs in the final policy. The value-function approximation error bounds answer this: if every backup is off by at most ε, the resulting greedy policy is suboptimal by at most about 2εγ/(1−γ)². The 1/(1−γ)² amplification is the theoretical face of a practical pain — long-horizon problems are unforgiving, because tiny value errors compound over the effective horizon.

  1. Bound the per-iteration approximation error ε of your function class.
  2. Multiply by the horizon amplification ~1/(1−γ)² (or H² in episodic terms).
  3. Read off the worst-case suboptimality of the returned policy.
\limsup_{k\to\infty}\;\lVert V^{*}-V^{\pi_k}\rVert_\infty\;\le\;\frac{2\gamma}{(1-\gamma)^2}\,\varepsilon

Approximate value iteration: a per-step approximation error ε is amplified by the horizon factor 1/(1−γ)² in the final policy's suboptimality.

The simulation lemma: the field's workhorse

Most sample-complexity proofs lean on the simulation lemma: if a learned model is close to the true MDP in its transitions and rewards, then the value of any fixed policy under the learned model is close to its value under the true MDP — and the error again carries a 1/(1−γ) (or horizon) factor. It is the bridge that lets you reason about the real environment while only ever measuring your model, and it underlies both model-based analysis and many model-free reductions.

Linear MDPs: structure you can actually solve

The cleanest tractable structure is the linear MDP: assume the transition dynamics and reward are linear in a known d-dimensional feature map of each state-action pair. Then every action-value function is linear in those features too, so you can run optimistic least-squares value iteration and get regret and sample complexity that scale with the feature dimension d and the horizon — not with the number of states. This is the function-approximation analogue of UCRL, and the template result that PAC guarantees can survive infinite state spaces given the right structure.

P(s'\mid s,a)=\langle \phi(s,a),\,\mu(s')\rangle,\qquad r(s,a)=\langle \phi(s,a),\,\theta\rangle

The linear MDP: transition dynamics and reward are both linear in a known d-dimensional feature map φ(s,a).

Bellman rank: one knob for many structures

Linear MDPs are one structure; tabular MDPs, low-rank MDPs, and block MDPs are others. The Bellman rank is a unifying complexity measure: it captures, roughly, the rank of the matrix of average Bellman errors across policies, and low Bellman rank is sufficient for PAC-RL sample complexity polynomial in that rank, the horizon, and log(|function class|) — independent of the state count. It is the RL counterpart of the VC dimension: a single scalar that says 'how statistically hard is exploration here?'