The table runs out of room
Tabular reinforcement learning keeps one estimate per state (or per state-action pair): a giant lookup table that you nudge after every step. That is wonderful when the state space is small — a 4×4 grid has 16 cells. But a backgammon board has more positions than there are atoms in your hand, and a robot reading joint angles lives in a continuous space with infinitely many states. You cannot store a number for each one. This is the curse of dimensionality in its plainest form.
An interactive gridworld where Q-learning stores a separate value in each cell.
Even when the table could fit, it learns too slowly: every state is an island. Visiting state 9,001 teaches you nothing about state 9,002, even if they are nearly identical. You would have to visit every state many times to learn anything everywhere. Function approximation is the escape hatch.
A value function with parameters
Instead of a table, we write the value function as a parameterized function v̂(s, w): you feed in a state, it returns an estimated value, and a vector of weights w controls its shape. Crucially w is far smaller than the number of states — maybe a thousand weights covering a billion states. Learning means adjusting those few weights so v̂ matches the true returns as closely as possible.
The supervised-learning loop: data feeds a model that makes predictions, a loss is computed, and the model updates.
What 'good' means: the value error
With a table you could make every entry exactly right. With limited weights you cannot — fixing one state's value perturbs its neighbours. So we need an objective: which states matter most to get right? The standard answer is the mean squared value error, the average squared gap between v̂(s, w) and the true value, weighted by how often the policy actually visits each state. States you rarely see are allowed to be wrong; states you live in must be accurate.
The mean squared value error weights each state's error by μ(s) — how often the policy actually visits that state.
This visitation-weighted objective ties approximation tightly to the return objective we ultimately care about, and it is why the distribution of training states — on-policy or off-policy — turns out to matter enormously (the subject of guide 4). Theory packages these gaps into approximation-error bounds that limit how good the final policy can be.
The simplest approximator: lumping states together
The gentlest way to shrink a table is state aggregation: partition the states into groups and store one shared value per group. A self-driving car might bucket 'distance to car ahead' into near / medium / far instead of tracking centimetres. Every state in a group gets the same estimate, and an update to any member updates them all at once — instant generalization.
Aggregation is really a special case of linear approximation where each state's feature vector is a single 'which bucket am I in' indicator. It is crude — values jump at bucket boundaries — but it already shows the whole trade-off: coarser buckets generalize more and learn faster, but cannot represent fine detail. Choosing how to carve up the world is the feature-design problem of the next guide.
Bias–variance trade-off curves trading memory for generalization.