Value Function Approximation in RL

A table stores one value per state and runs out of rows the moment states turn continuous. Function approximation stores a short list of weights instead, so one update teaches every similar state at once.

One linear update moves shared weights to [4.0, 2.0], lifting the visited state to 5.0 and a never-visited neighbour to 5.2

Why Does This Exist?

Tabular methods keep one number per state. That works while states are countable, and it breaks twice once they are not. First, memory scales with the number of states, so board games with astronomical state counts and robots with continuous joint angles simply have no table big enough. Second, tables never generalize: a car that learns the value of driving 60.00 mph in the center lane learns nothing about 60.01 mph, because that is a different row and its entry is still zero.

Function approximation replaces the table with a parameterized function $\hat{v}(s, \mathbf{w})$ governed by a short weight vector $\mathbf{w}$ . Updating the weights after visiting one state shifts predictions for every similar state, turning memorization into generalization.

This page covers the shared-weight idea, the objective it optimizes, and the semi-gradient update, with one hand-computed step. The linear details live in linear methods, the prediction algorithm in semi-gradient TD(0), and the tabular origin in tabular solution methods.

The one idea you need first

A value function scores a state by expected future reward. Approximation keeps that meaning and changes only the storage: instead of looking up $V(s)$ in a table, you compute $\hat{v}(s, \mathbf{w})$ from features of $s$ and shared weights.

Think of It Like This

Appraising houses instead of memorizing addresses

You must price two million homes. The tabular approach keeps a spreadsheet with one row per address. When 742 Evergreen Terrace sells for $450,000 you fill in that row, but asked about number 744 next door, which last sold fifty years ago, you answer zero. You never saw that exact row.

The approximation approach fits a formula from features: square footage, bedrooms, school rating. One sale adjusts the shared weights, and instantly every similar house gets a better estimate, including homes built yesterday with no sales history at all.

Where the analogy stops: house prices come from a fixed pile of past sales, while the agent learns online from a policy that keeps changing. As behavior shifts, the states it visits shift too, so the target the weights chase moves while learning runs.

How It Actually Works

Write the approximate value as $\hat{v}(s, \mathbf{w})$ , where $s$ is a state and $\mathbf{w}$ in $\mathbb{R}^d$ holds $d$ weights with $d$ far smaller than the number of states. The linear form is $\hat{v}(s, \mathbf{w}) = \mathbf{w}^T \mathbf{x}(s)$ , the dot product of weights with a feature vector $\mathbf{x}(s)$ describing the state. Because $d$ weights cannot fit every state exactly, the standard objective accepts a trade-off: the mean squared value error weights each state's squared error by how often the agent visits it, written $\mu(s)$ :

$\overline{\mathrm{VE}}(\mathbf{w}) = \sum_s \mu(s) \, [v_\pi(s) - \hat{v}(s, \mathbf{w})]^2$

Frequent states get accuracy, rare ones get whatever capacity is left. That weighting is a choice with consequences, and one of the pitfalls below is about it.

The true value $v_\pi(S_t)$ is unknown, so the update substitutes a bootstrapped target $U_t = R_{t+1} + \gamma \hat{v}(S_{t+1}, \mathbf{w}_t)$ , the reward plus the discounted next estimate. The weights then move along the gradient of the prediction, ignoring that the target itself depends on $\mathbf{w}$ , which is why the method is called semi-gradient:

$\mathbf{w}_{t+1} = \mathbf{w}_t + \alpha \, [U_t - \hat{v}(S_t, \mathbf{w}_t)] \, \nabla_{\mathbf{w}} \hat{v}(S_t, \mathbf{w}_t)$

Here $\alpha > 0$ is the step size and $\gamma$ in $[0, 1]$ discounts the future. For a linear model the gradient is just the feature vector $\mathbf{x}(S_t)$ .

Worked example

Two features, $\alpha = 0.4$ , weights $\mathbf{w} = [0.0, 0.0]$ . Visited state $S_A$ has features $[1.0, 0.5]$ , unvisited neighbour $S_B$ has $[1.0, 0.6]$ , and the target is $U = 10.0$ .

Prediction at $S_A$ : $0.0$ . Error: $10.0 - 0.0 = 10.0000$ .

Update: $[0.0, 0.0] + 0.4 \times 10.0 \times [1.0, 0.5] = [4.0000, 2.0000]$ .

Now evaluate both states under $\mathbf{w} = [4.0, 2.0]$ . Visited: $4.0 \times 1.0 + 2.0 \times 0.5 = 5.0000$ . Unvisited: $4.0 \times 1.0 + 2.0 \times 0.6 = 5.2000$ . A table would have left $S_B$ at zero. Shared weights lifted it to 5.2 without ever visiting it.

Code

The worked step in plain Python, with type hints, matching the numbers above:

1w: list[float] = [0.0, 0.0]2x_a: list[float] = [1.0, 0.5]3x_b: list[float] = [1.0, 0.6]4target, alpha = 10.0, 0.45
6v_a = sum(a * b for a, b in zip(w, x_a))7delta = target - v_a8w = [a + alpha * delta * b for a, b in zip(w, x_a)]9v_a_new = sum(a * b for a, b in zip(w, x_a))10v_b_new = sum(a * b for a, b in zip(w, x_b))11
12print(f"delta {delta:.4f}")  # -> delta 10.000013print(f"w [{w[0]:.4f}, {w[1]:.4f}]")  # -> w [4.0000, 2.0000]14print(f"visited {v_a_new:.4f}")  # -> visited 5.000015print(f"unvisited {v_b_new:.4f}")  # -> unvisited 5.2000

Watch Out For

Rare but critical states get starved of accuracy

Capacity is limited, so the objective spends accuracy where visits are frequent. If the agent mostly cruises straight highway miles, the weights fit cruising beautifully and sacrifice skid recovery or cliff edges it almost never sees. The symptom is low training loss paired with catastrophic values the first time a rare state appears.

Fix it by breaking the visitation monopoly: sample surprising transitions more often with prioritized replay, and prefer local features such as tile coding so updates to frequent states do not overwrite distant regions.

Treating the bootstrap target as ground truth

The semi-gradient update pretends the target $U_t$ is a fixed number, but it contains the same weights being updated. With linear models that shortcut usually converges; with nonlinear ones plus off-policy data it can diverge, the third leg of the deadly triad. The symptom is weights that grow without bound late in training while everything looked fine early on.

Fix it by earning the nonlinearity: keep step sizes small, prefer linear features until the pipeline is solid, and add a slowly updated target network before trusting a deep approximator.

The Quick Version

Function approximation stores $d$ shared weights instead of one value per state, which is the only way to handle continuous or massive state spaces.
One update generalizes: in the worked step, weights [4.0, 2.0] give 5.0 at the visited state and 5.2 at a neighbour never seen.
The objective weights errors by visit frequency $\mu(s)$ , so frequent states win capacity and rare ones lose it.
The TD update is semi-gradient because it ignores the target's dependence on the weights, which is safe for linear models and risky beyond them.
Starved rare states and bootstrapped targets are the two failures to check first when values look wrong.