Skip to content
Tutorials Center
My learning

Topics

Lesson 24 of 37 ยท Function Approximation and Deep RL

Function Approximation: Why Tables Run Out

See why Q-tables fail on big problems and how function approximation generalizes: state aggregation, semi-gradient TD, features and the deadly triad, with runnable Python.

A Q-table stores one number per state-action pair. That is perfect for a 5-by-5 grid and hopeless for almost everything else. A chess position has more possibilities than there are atoms to write them on. A robot arm's joint angles are real numbers, so there are infinitely many states. Even if you had enough memory, the agent would have to visit each state to learn about it, and in a huge space it never will.

The way out is function approximation: instead of a table, use a parametrized function v(s; w) or q(s, a; w) with far fewer parameters than states. Nearby or similar states share parameters, so learning about one state teaches the agent about its neighbors. This is generalization, and it is what lets RL scale. It is also what makes RL hard to get stable, as you will see at the end of this lesson.

From tables to weight vectors

A table is a special case of a function: one parameter per state, v(s) = w[s]. Replace it with a general function and keep the idea of "nudge the estimate toward a target":

TEXT
w <- w + alpha * (target - v(s; w)) * grad_w v(s; w)

This is stochastic gradient descent on the squared error between the target and the current prediction. The target depends on the method:

Method Target for v(s)
Monte Carlo the return G_t (an unbiased sample of the true value)
TD(0) r + gamma * v(s'; w) (a bootstrapped estimate)

When the target uses the current weights (TD), we ignore its dependence on w when we take the gradient. That makes the update a semi-gradient method. It is not true gradient descent on any fixed objective, but it works well in practice and learns much faster than Monte Carlo.

Linear function approximation

The simplest useful family is linear: v(s; w) = w . x(s), where x(s) is a feature vector you design. The gradient is just x(s), so the semi-gradient TD(0) update is:

TEXT
w <- w + alpha * (r + gamma * w . x(s') - w . x(s)) * x(s)

Linear methods are easy to analyze, quick to run and converge reliably under on-policy training. Their power depends entirely on the features.

State aggregation

The crudest feature scheme is state aggregation: split the states into groups and give each group one weight. The feature vector is one-hot over groups. Let us try it on a 100-state random walk. From state s the agent jumps to a random state within 5 steps to the left or right (never staying put). Walking off the left edge ends the episode with reward -1; off the right edge, +1. The true value function is a smooth ramp from about -1 on the left to +1 on the right. We compute the exact values with a linear solve so we can measure our error.

Python State aggregation with semi-gradient TD(0)

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Look at the trade-off. With group size 1 you have a table: no error from coarse features, but each weight gets few updates, so learning is noisy and slow. With group size 50 you only have two weights: learning is fast but the staircase cannot follow the ramp, so a large error is built in. Medium groups often win. This bias versus data-efficiency trade-off appears in every approximator you will meet.

Better features

Aggregation is a piecewise constant approximation. Better feature sets for continuous states include:

  • Polynomial features: 1, x, x^2, ... (and cross terms in several dimensions).
  • Fourier features: cos(pi * k * x) for k = 0, 1, 2, ...; smooth and easy to tune.
  • Radial basis functions: bumps centered on a grid; value decays with distance.
  • Tile coding: several overlapping grids shifted a little; each state activates exactly one tile per grid. This is fast and sparse, and the next lesson builds a full agent on it.

Here is a quick comparison of how well different feature sets can fit a smooth "value function" shape using the same gradient update (a regression problem you can solve exactly with SGD):

Python Which features fit a smooth value curve?

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Fourier features capture the curve with eight weights, far better than eight aggregation cells would. Polynomial features can represent it too, but their columns are badly scaled (x^7 is tiny almost everywhere), so plain gradient descent converges slowly and the error is still high after 3,000 epochs. Feature design and feature scaling matter as much as the feature count.

The deadly triad

Tabular TD is guaranteed to converge. With function approximation, three ingredients together can make learning diverge: the weights grow without bound.

  1. Function approximation (generalization across states).
  2. Bootstrapping (targets built from the current estimates, as in TD).
  3. Off-policy training (learning about a policy different from the one that generates data, as in Q-learning).

Any two are usually fine; all three together are the deadly triad. Deep Q-networks use all three, which is why they need stabilizers such as replay buffers and target networks, covered in the neural Q-network lesson and DQN improvements.

flowchart TD
    FA["Function approximation"] --> D["Possible divergence"]
    B["Bootstrapping"] --> D
    O["Off-policy learning"] --> D

Drop any one of the three and the danger mostly disappears; deep RL keeps all three and adds tricks.

Common mistakes

  • Using features that cannot represent the answer (a straight line cannot fit a curve); no amount of data fixes that.
  • Forgetting to scale features; one huge feature dominates the update and causes oscillation.
  • Treating the semi-gradient update as true gradient descent, and differentiating through the bootstrapped target.
  • Judging an approximator by training error only; check on states it rarely visits.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. What is the main benefit of function approximation in RL?

    Sharing parameters between states lets the agent generalize and handle huge or continuous state spaces.
  2. 2. Why is TD(0) with function approximation called a semi-gradient method?

    The target r + gamma v(s'; w) depends on w, but the update treats it as a constant, so it is not a true gradient.
  3. 3. In state aggregation, what happens when the groups are very large?

    Few weights get many updates, so learning is quick, but a staircase cannot follow a smooth value function.
  4. 4. Which combination is the 'deadly triad'?

    Together these three can make value estimates diverge; deep Q-learning needs extra stabilizers.

Summary

  • Tables do not scale; a parametrized value function lets similar states share what the agent learns.
  • Semi-gradient TD(0) nudges weights along the feature vector toward a bootstrapped target.
  • State aggregation, polynomial, Fourier, RBF and tile-coding features trade accuracy against learning speed.
  • Function approximation plus bootstrapping plus off-policy training (the deadly triad) can diverge.

Next: Tile Coding and Mountain Car