Function approximation on a blackboard: share a value, share an errorSix panels. 1: doubling one sensor's bins doubles the rows, four finer sensors give 16 times the rows, and one visit fills one entry while every unvisited entry knows nothing. 2: training only A with features (1, 1) toward 2 moves the weights from (0, 0) to (0.2, 0.2), so A goes from 0 to 0.4 and the never visited B, features (1, 2), from 0 to 0.6. 3: C and D have true values 0 and 2 but the same features (1, 0), so the best single prediction is 1. 4: the target 0.9 times 0.6 = 0.54 is built from B's prediction and then held fixed, and the update pushes A's prediction, 0.4, toward it. 5: after fitting A once, A goes from 0.400 to 0.428, B from 0.600 to 0.642, and the next target for A, 0.9 times B, from 0.5400 to 0.5778. 6: saved transitions give a sampled batch to both networks, the target copy is held still and builds the target that trains the live network, and a periodic copy refreshes the target copy.1. The table growsFiner sensor bins create more table rows, and every unvisited row knows nothingOne sensor slice, two actions????????????????2× binsBlue: visited. ?: knows nothingFour finer sensors → 16× rows2. One update shares learningTraining A, features (1, 1), changes predictions at A and at the unvisited B, features (1, 2)Train A: features (1, 1), target 2Weights: (0, 0) → (0.2, 0.2)A(1, 1)B(1, 2)0 → 0.40 → 0.6VisitedNever visited3. Sharing can erase distinctionsTwo true values collapse to one shared predictionCDTrue value 0True value 2Same features (1, 0)One prediction: best fit 14. Hold the target stillSemi-gradient TD builds the target 0.54 from B, then holds it fixed while it pushes A toward itBuild the target, then freeze ittarget = 0.9 × 0.6 = 0.54moves upread onceA0.4B0.6The step pushes A toward 0.54as if 0.54 could not move.5. The target moves next timeA shared update raises both the current value and its next targetFit A once: both values riseABmove, r = 00.400 → 0.4280.600 → 0.642× 0.9next target for A0.5400 → 0.57786. Networks need steadier targetsReplay supplies a sampled batch to both networks. The target copy, held still, builds the target that trains the live network, whose weights move. A periodic copy refreshes the target copy from the live network.Saved transitionssample batchLive networkweights moveTarget copyheld stilltargetperiodic copy refreshesthe target copy

A table learns every state on its own, so a state you've never visited knows nothing, even when you've seen its neighbors many times. Function approximation fixes that by letting states share a few adjustable numbers. Sharing is the whole idea, and it cuts both ways: one example can teach many states, and one update can also move values you didn't mean to touch, including the target you're chasing.

Part 3. Previously: bootstrapping.

The table grows

A Q table stores one number per state and action. With continuous sensors you first cut each reading into bins, so dd sensors with bb bins each and aa actions give a bda\,b^d entries. Take an illustrative cart-balancing task with four sensors (position, speed, pole angle, angular speed). Six bins per sensor give 1,296 rows, or 2,592 entries with two actions. Twelve bins give 20,736 rows and 41,472 entries. Doubling the resolution multiplied the rows by sixteen, and every new row needs its own data, because the table learns each row separately.

One update shares learning

So let's store a few weights instead and predict a state's value as v^(s,w)=w⊤x(s)\hat v(s,w)=w^\top x(s), where x(s)x(s) lists the state's features. State A has features (1, 1) and state B has (1, 2), and both weights start at 0. Now train only A, toward a target of 2 with a step size of 0.1:

w←w+α [ y−v^(A,w) ] x(A)w\leftarrow w+\alpha\,[\,y-\hat v(\mathrm A,w)\,]\,x(\mathrm A)

The error is 2, so both weights become 0.2. A now predicts 0.4, and B, which you never trained, predicts 0.6. B moved because it uses the same weights. If B's true value is 3, that's a step in the right direction, but whether sharing helps a state you didn't train always depends on its features and its target.

Sharing can erase distinctions

Sharing has a limit. Say states C and D have true values 0 and 2, but both have the same features (1, 0). Then every weight setting gives them the same prediction. If you see both equally often, the best shared prediction is their average, 1, which is off by 1 for each. That's aliasing, and more training can't fix it, because the difference isn't in the input. Coarse sensor bins can do this when two states share every bin but their angular speeds imply very different futures.

Hold the target still

Now let the model build its own target, as bootstrapping does. A predicts 0.4, its successor B predicts 0.6, the reward is 0 and the discount is 0.9, so the target is 0+0.9×0.6=0.540 + 0.9 \times 0.6 = 0.54. Semi-gradient TD treats 0.54 as a fixed number and nudges only A's prediction toward it. It ignores the fact that 0.54 came from the same weights it's about to change.

The target moves next time

Holding the target still for one update doesn't keep it still afterward. The error is 0.54−0.4=0.140.54 - 0.4 = 0.14, so each weight grows by 0.1×0.14=0.0140.1 \times 0.14 = 0.014, to 0.214. A now predicts 0.428, but B rose too, to 0.642. Replay the same transition and the target is 0.9×0.642=0.57780.9 \times 0.642 = 0.5778 instead of 0.54. With a table, updating A would have left B alone.

This coupling doesn't prove anything diverges. Linear TD with on-policy sampling has convergence results under technical conditions, and other sampling distributions can break that stability (Sutton and Barto, Sections 9.4 and 11.2).

Networks need steadier targets

A neural network learns its own features, but it still shares parameters across inputs, so it has the same coupling. DQN (Mnih et al., 2015) adds two fixes. Replay memory reuses saved transitions and breaks up runs of consecutive, similar samples. A target network, a frozen copy refreshed only now and then, builds the targets so they don't shift after every update. Both help in practice, but neither gives a general convergence guarantee for neural Q-learning.

Which policy produced those transitions, and which policy does their target evaluate? Part 4: on-policy and off-policy learning explains the distinction, and Part 5 comes back to stability.

The exact updates, notation and sources

Table size. With dd sensor dimensions, bb bins per dimension and aa actions, the Q table has N=a bdN=a\,b^d entries, because bdb^d counts all combinations of binned readings. With function approximation, one observation can update predictions across several states without waiting for each to get its own data: the generalization problem of Sutton and Barto, Part II and Section 9.1.

Linear prediction. x(s)x(s) is a fixed vector of numerical features and ww a weight vector of the same length. w⊤x(s)w^\top x(s) multiplies matching coordinates and adds them, and the hat in v^(s,w)\hat v(s,w) marks an estimate. Given a target yy at state ss, the squared-error update is w←w+α[y−v^(s,w)]x(s)w\leftarrow w+\alpha[y-\hat v(s,w)]x(s). It moves in a direction that locally reduces that state's squared error, and every state that uses the same features moves with it (Sections 9.3 and 9.4).

Aliasing. If C and D share features (1,0)(1,0), then v^(C,w)=v^(D,w)=c\hat v(\mathrm C,w)=\hat v(\mathrm D,w)=c for the first weight cc. Sampling both equally and fitting squared error gives c=(0+2)/2=1c=(0+2)/2=1. If one state were sampled more often, the shared estimate would move toward its value (Sections 9.1 to 9.3). Giving the states different features allows different predictions, and adding parameters helps only if the inputs still carry the relevant information.

Semi-gradient TD. tt counts transitions, StS_t is the current state, Rt+1R_{t+1} the reward after the action and wtw_t the current weights. The one-step target, with terminal value zero, is held fixed while differentiating:

yt=Rt+1+γv^(St+1,wt),Lt(w)=12[yt−v^(St,w)]2,wt+1=wt+α δt ∇wv^(St,wt),δt=yt−v^(St,wt).\begin{aligned} y_t&=R_{t+1}+\gamma\hat v(S_{t+1},w_t),\qquad L_t(w)=\tfrac12[y_t-\hat v(S_t,w)]^2,\\ w_{t+1}&=w_t+\alpha\,\delta_t\,\nabla_w\hat v(S_t,w_t),\qquad \delta_t=y_t-\hat v(S_t,w_t). \end{aligned}

With linear features the gradient is x(St)x(S_t). Differentiating through the target as well would give a different update. Because later targets are recomputed with the new weights, this is not the same as minimizing one fixed loss throughout training (Sections 9.3 and 9.4).

DQN target. Qθ(s,a)Q_\theta(s,a) is the network's estimate for action aa in state ss, and θˉ\bar\theta are the target-network parameters, held fixed between scheduled refreshes:

zt=Rt+1+γmax⁡a′Qθˉ(St+1,a′).z_t=R_{t+1}+\gamma\max_{a'}Q_{\bar\theta}(S_{t+1},a').

When the transition terminates, the target is just the reward. The live network fits ztz_t on batches sampled from replay memory, and its parameters are copied to the target network periodically (Mnih et al., 2015).

The worked numbers in tables, and what sharing buys and costs

Training only A once, with w=(0,0)w=(0,0), target 2 and step size 0.1:

After training only A once A: features (1, 1) B: features (1, 2)
Before 0 0
After 0.4 0.6
Supplied comparison target 2 3

Then one semi-gradient update on the transition A to B, with weights (0.2,0.2)(0.2,0.2), reward 0, discount 0.9 and step size 0.1: w=(0.2,0.2)+0.1(0.14)(1,1)=(0.214,0.214)w=(0.2,0.2)+0.1(0.14)(1,1)=(0.214,0.214).

Same replayed A → B transition Before After one update
Prediction at A 0.4 0.428
Prediction at B 0.6 0.642
Target from B 0.54 0.5778

Sharing buys: compact storage, because parameters replace an entry for every input; transfer, because one example can improve related states; and, with networks, features learned from observations.

Sharing costs: representation error, because identical features force identical predictions; interference, because an update can worsen predictions elsewhere; and stability, because replay and target copies help but give no general convergence guarantee for neural Q-learning.

← All writing