When the Table Cannot Fit | Visual AI Learning Guide

Look at the two panels side by side. On the left, the table has one cell per state, and only the visited cells carry a learned value; the rest sit at their initial value, which is why a large or continuous state space is hopeless to tabulate. On the right, a parameterized function draws a smooth curve through the visited points. That curve gives an estimate for every state, including ones never visited, which is what makes large problems tractable. But notice the shaded region where the curve passes between two visited states that need opposite actions: the smoothness assumption forces a single value there, and if that assumption is wrong, the estimate is confidently wrong. Generalization is necessary for scale and risky for exactly the same reason.

0:00 / 0:00

Auto-play

A tabular method gives every state its own row. That is fine for a grid with a few hundred cells. It breaks down when the state is a continuous vector, such as a robot's joint angles and velocities, or when the state space is combinatorial, such as a board position in a large game. There are two distinct failures. First, storage: the table grows with the number of states, and for continuous states it is infinite. Second, and more damaging, coverage: each entry is only updated when that exact state is visited, so most entries stay at their initial value forever and the agent never learns them.

Function approximation replaces the table with a parameterized function \(\hat{v}(s; w)\) or \(\hat{q}(s, a; w)\), where \(w\) is a weight vector. The function maps any state, including ones never seen, to an estimate. When the agent visits a state and gets a better target, it updates \(w\), and because the function is smooth in its inputs, the change also shifts the estimates for nearby states. That is generalization: experience in one state improves estimates in similar states. It is exactly what makes learning feasible in large spaces, because the agent no longer needs to visit every state to have a usable estimate for it.

The same property is the risk. Generalization is a bet that similar states have similar values, and that bet can be wrong. If two states look close under the chosen features but require opposite actions, the shared weights will pull their estimates together and the agent will make a confident mistake in one of them. This is why feature design and the smoothness of the approximator matter: a linear function over well-chosen features generalizes conservatively, while a highly flexible function can fit the training states well and still produce wild estimates just off the visited region. The practical consequence is that function approximation trades the guaranteed correctness of a fully visited table for coverage of unvisited states, and the trade is only worth it when the state space is too large to tabulate.

References

[1]Reinforcement Learning: An Introduction, 2nd edition — Chapter 9: On-policy Prediction with Approximationincompleteideas.net