S&B Chapters 9–10
Every algorithm in this book so far has maintained a table: one entry per state, or one entry per state-action pair. GridWorld has 16 states. Blackjack has 200. Windy gridworld has 70. These fit in memory, run instantly, and converge to exact solutions.
Real problems don't cooperate. A chess position has roughly \(10^{43}\) legal states. A continuous robot joint angle lives in \(\mathbb{R}^n\). kdb+/q tick data has state spaces that combine position, inventory, market regime, and a dozen other features—functionally infinite.
Function approximation replaces the table with a parameterised function \(\hat{v}(s; \mathbf{w}) \approx v_\pi(s)\), where \(\mathbf{w}\) is a weight vector of manageable size. Updating one weight can affect estimates for many states simultaneously—generalisation. The cost: we lose exact convergence guarantees (mostly) and gain approximation error. In practice, for anything interesting, it's the only option.
The simplest and most tractable case: \(\hat{v}(s; \mathbf{w}) = \mathbf{w}^\top \mathbf{x}(s)\), where \(\mathbf{x}(s)\) is a feature vector for state \(s\). The update rule under gradient descent:
\[\mathbf{w} \leftarrow \mathbf{w} + \alpha \left[v_\pi(s) - \hat{v}(s;\mathbf{w})\right] \mathbf{x}(s)\]
We don't know \(v_\pi(s)\), so we substitute a target: for semi-gradient TD(0), the target is \(R + \gamma \hat{v}(S';\mathbf{w})\).
\[\mathbf{w} \leftarrow \mathbf{w} + \alpha \left[R + \gamma \hat{v}(S';\mathbf{w}) - \hat{v}(S;\mathbf{w})\right] \mathbf{x}(S)\]
"Semi-gradient" because we treat the target \(R + \gamma \hat{v}(S';\mathbf{w})\) as fixed (not differentiating through it). This is the same trick deep Q-networks use with a "target network."
The simplest feature representation: group states into clusters, and use a one-hot vector indicating which cluster \(s\) belongs to. States in the same group share a single weight. It's coarse approximation, but it scales.
We'll use the 1000-state random walk (S&B Example 9.1): states 1–1000, uniform transitions \(\pm 100\), rewards \(-1\) at the left terminal and \(+1\) at the right. Aggregate into 10 groups of 100 states each.
/ ============================================================
/ State Aggregation + Semi-Gradient TD — 1000-State Random Walk
/ S&B Example 9.1
/ ============================================================
nStates1k:1002 / 0 and 1001 are terminals; 1-1000 are real states
leftTerm1k:0; rightTerm1k:1001
/ Random walk: jump uniform in [-100, 100], clamp to [0,1001]
rw1kStep:{[s]
delta:first[1?201]-100; / uniform in {-100,...,100}
s2:0|1001&s+delta;
r:$[s2=rightTerm1k;1f;$[s2=leftTerm1k;-1f;0f]];
done:(s2=leftTerm1k) or s2=rightTerm1k;
`s`r`done!(s2;r;done)
}
/ State aggregation: 10 groups of 100 states
nGroups:10; groupSize:100
/ Feature vector: one-hot over groups (length nGroups)
stateFeature:{[s]
$[(s=leftTerm1k) or s=rightTerm1k;
nGroups#0f; / terminal: zero features
[g:(s-1) div groupSize; / group index 0-9
@[nGroups#0f;g;:;1f]] / one-hot
]}
/ Value estimate: w . x(s)
vHat:{[w;s] w dot stateFeature s}
/ Semi-gradient TD(0) with linear function approximation
semiGradTD:{[alpha;gamma;nEpisodes]
w:nGroups#0f; / weight vector
rmse_hist:();
do[nEpisodes;
s:500i; / start near centre
done:0b;
while[not done;
x:stateFeature s;
result:rw1kStep[s];
s2:result`s; r:result`r; done:result`done;
/ TD target
target:r + gamma*$[done;0f;vHat[w;s2]];
/ Semi-gradient update: w += alpha * delta * x(s)
delta:target - vHat[w;s];
w+:alpha*delta*x
];
/ RMSE against true values (linear from -1 to 1)
trueV_1k:{-1f + (2f*x%1001)} each 1+til 1000;
estV_1k:{vHat[w;x]} each 1+til 1000;
rmse_hist,:sqrt avg (estV_1k-trueV_1k) xexp 2
];
`w`rmse!(w;rmse_hist)
}/ Run semi-gradient TD with state aggregation
res_sgTD:semiGradTD[2e-4f;1f;100000];
/ Value estimates per group (S&B Figure 9.1)
/ Each weight corresponds to one group's value estimate
show res_sgTD`w
/ Should be approximately: -0.9 -0.7 -0.5 -0.3 -0.1 0.1 0.3 0.5 0.7 0.9
/ (staircase approximation to the linear true value)The staircase is the tell: state aggregation can only represent piecewise constant value functions. Each group's value is its weight; states within a group are treated identically. This is a strong assumption that's often wrong in practice, but it's mathematically clean and a useful first step.
Beyond one-hot encoding, we can use richer feature functions. Polynomial features: \(\mathbf{x}(s) = (1, s, s^2, \ldots, s^k)\). Fourier features: \(x_i(s) = \cos(i\pi s)\). Both expand the state into a basis that linear function approximation can use.
/ Fourier basis features for the 1000-state walk
/ State normalised to [0,1]
fourierFeatures:{[order;s]
sn:`float$s % 1001f; / normalise to [0,1]
cos each pi*sn*til order+1 / cos(0), cos(pi*s), cos(2*pi*s), ...
}
/ Semi-gradient TD with Fourier features
semiGradTDFourier:{[order;alpha;gamma;nEpisodes]
nFeats:order+1;
w:nFeats#0f;
do[nEpisodes;
s:500i; done:0b;
while[not done;
x:fourierFeatures[order;s];
result:rw1kStep[s];
s2:result`s; r:result`r; done:result`done;
target:r + gamma*$[done;0f;w dot fourierFeatures[order;s2]];
delta:target - w dot x;
w+:alpha*delta*x
]
];
w
}
/ Fourier order 5: 6 parameters to represent 1000 states
w_fourier:semiGradTDFourier[5i;5e-5f;1f;100000];
/ Plot estimated values (evaluate at each of 1000 states)
vEst:{[w;order;s] w dot fourierFeatures[order;s]}
show 50 cut {vEst[w_fourier;5i;x]} each 1+til 1000
/ Should show a smooth increasing curve from -1 to 1Fourier features have a useful property: the weight for each component has a direct interpretation as the magnitude of a frequency component in the value function. Low-frequency components (\(i\) small) capture broad trends; high-frequency components capture fine structure. This is analogous to spectral decomposition.
The practically most successful linear feature representation for RL (before neural networks took over) is tile coding: multiple overlapping tilings of the state space, each tiling a regular grid. For a 2D state space, imagine laying down multiple grids, each offset by a fraction of a tile width.
/ Tile coding for 1D state space [low, high]
/ nTilings: number of overlapping grids
/ nTiles: number of tiles per tiling
tileCoding:{[nTilings;nTiles;low;high;s]
/ Total features: nTilings * nTiles
width:(high-low)%nTiles;
/ Each tiling is offset by width/nTilings from the previous
offset:width % nTilings;
/ For each tiling, find which tile s falls into
features:nTilings#0i;
k:til nTilings;
/ Shift s by k*offset, then find tile index
shifted:s - k*offset;
tileIdx:`int$(shifted-low)%width;
tileIdx:0|nTiles-1&tileIdx; / clamp to valid range
/ One-hot index into flattened feature vector
base:nTiles*k;
base+tileIdx
}
/ Build full binary feature vector from tile indices
tilesToVector:{[nTilings;nTiles;indices]
v:nTilings*nTiles#0f;
v[indices]:1f;
v
}
/ Tile-coded linear approximation for Mountain Car
/ State: (position, velocity) in [-1.2,0.6] x [-0.07,0.07]
nMCTilings:8; nMCTiles:8
/ Tile code a (position, velocity) pair
mcFeatures:{[pos;vel]
posIdx:tileCoding[nMCTilings;nMCTiles;-1.2f;0.6f;pos];
velIdx:tileCoding[nMCTilings;nMCTiles;-0.07f;0.07f;vel];
/ Combine: offset velocity tiles by nTiles to avoid collision
combined:posIdx,velIdx+nMCTilings*nMCTiles;
tilesToVector[nMCTilings;nMCTiles*2;combined]
}
nMCFeats:nMCTilings*nMCTiles*2
/ Demonstrate: two similar positions should have overlapping features
x1:mcFeatures[-0.5f;0.01f];
x2:mcFeatures[-0.5f;0.015f];
sum x1 and x2 / number of shared active tiles (out of 8 tilings)Mountain Car (S&B Example 10.1): a car must drive up a steep hill, but the engine is too weak to climb directly. It must first drive left to build momentum, then accelerate right. Continuous state (position, velocity), 3 discrete actions (push left, neutral, push right), reward -1 per step.
/ ============================================================
/ Mountain Car Environment — S&B Section 10.1
/ ============================================================
mcMinPos:-1.2f; mcMaxPos:0.6f
mcMinVel:-0.07f; mcMaxVel:0.07f
mcGoalPos:0.5f
/ Actions: 0=reverse, 1=neutral, 2=forward
mcActionForce:-0.001 0f 0.001f
/ Step function: returns (next_pos; next_vel; reward; done)
mcStep:{[pos;vel;a]
force:mcActionForce[a];
/ Update velocity: add force and gravity component
vel2:mcMinVel|(mcMaxVel&vel+force+(-0.0025f*cos[3f*pos]));
/ Update position
pos2:mcMinPos|(mcMaxPos&pos+vel2);
/ If hit left wall, zero velocity
vel2:$[pos2=mcMinPos;0f;vel2];
done:pos2>=mcGoalPos;
`pos`vel`r`done!(pos2;vel2;-1f;done)
}
/ Semi-gradient SARSA for Mountain Car
/ Uses tile-coded linear Q-function approximation
mcSarsa:{[alpha;gamma;eps;nEpisodes]
/ Weight vector: nFeats * nActions
W:nMCFeats*3#0f; / flat: W[a*nMCFeats + i] = weight for action a, feature i
/ Approximate Q(s,a) = w_a . x(s)
qHat:{[W;pos;vel;a]
x:mcFeatures[pos;vel];
wA:W[a*nMCFeats + til nMCFeats];
wA dot x
};
/ Epsilon-greedy over 3 actions
selectMC:{[W;eps;pos;vel]
$[rand[1.0f]<eps;
first 1?3;
imax {qHat[W;pos;vel;x]} each 0 1 2
]};
epSteps:();
do[nEpisodes;
pos:mcMinPos+rand[mcMaxPos-mcMinPos]; / random start position
vel:0f; / zero initial velocity
a:selectMC[W;eps;pos;vel];
steps:0;
done:0b;
while[(not done) and steps<5000; / max 5000 steps per episode
x:mcFeatures[pos;vel];
result:mcStep[pos;vel;a];
pos2:result`pos; vel2:result`vel;
r:result`r; done:result`done;
a2:selectMC[W;eps;pos2;vel2];
/ Semi-gradient SARSA update
target:r + gamma*$[done;0f;qHat[W;pos2;vel2;a2]];
delta:target - qHat[W;pos;vel;a];
/ Update weights for action a only
base:a*nMCFeats;
W[base+til nMCFeats]+:alpha*delta*x;
pos:pos2; vel:vel2; a:a2; steps+:1
];
epSteps,:steps
];
`W`epSteps!(W;epSteps)
}/ Train: convergence is slow—this is a harder problem
/ alpha per-tiling: S&B uses alpha/8 where 8 = nTilings
res_mc:mcSarsa[0.5f%nMCTilings;1f;0.0f;500]; / eps=0 (greedy)
/ Episode lengths should decrease from ~5000 to ~100-200
res_mc[`epSteps][0] / first episode: usually max steps (5000)
last res_mc`epSteps / last episode: ~100-200 if converged
/ Show learning curve
show 50 cut res_mc`epSteps / display as 10x50 grid for readabilityWith tabular methods, every update is exact and local. Changing \(V(s)\) for state \(s\) affects only that state. With function approximation, updating weights \(\mathbf{w}\) changes the estimates for all states that share features—which is most of them.
This generalisation is the whole point: we're making the algorithm smarter about states it hasn't seen. It's also what makes convergence analysis hard. Semi-gradient TD doesn't necessarily converge to the global optimum of any loss function; it converges to a TD fixed point that trades off Bellman error and function approximation error.
The practical implications: start with the simplest feature representation that captures the structure you need. Tile coding is remarkably effective and well-understood. Neural networks are powerful but introduce non-convex optimisation, instability, and the need for replay buffers and target networks. If tile coding solves your problem, use tile coding. If it doesn't—that's what deep RL is for.