Function Approximation in RL
When states are too many to tabulate, value functions and policies are represented by parameterized functions that generalize across states.
Beyond tables
Tabular methods store one value per state or state-action pair, which is impossible when states are continuous or astronomically numerous. Function approximation replaces the table with a parameterized function — linear, tree-based, or neural — that maps state features to values or action probabilities and generalizes to states never seen exactly before.
What is approximated
- State-value V(s; w) or action-value Q(s, a; w) with parameters w.
- Policy pi(a | s; theta) directly, with parameters theta.
- Environment models P and R for model-based methods.
How parameters are learned
Value approximators are trained by minimizing the difference between predicted values and bootstrapped targets, typically by stochastic gradient descent on a squared TD error. Because the target itself depends on the parameters, the update is semi-gradient: only the prediction, not the target, is differentiated.
The deadly triad
Combining three ingredients — function approximation, bootstrapping, and off-policy training — can cause value estimates to diverge. This deadly triad explains why naive deep Q-learning is unstable and motivates stabilizers such as target networks and experience replay in the deep Q-network.
Generalization as a double-edged sword
Generalization is what makes large problems solvable: the approximator shares knowledge across similar states, so learning about one state improves estimates for others. But it also means an update for one state perturbs others, which can create interference and instability. Careful feature design, regularization, and normalization keep this in check. For continuous control tasks such as a simulated device with many real-valued sensors, function approximation is not optional but the only feasible representation.