On-policy Prediction with Approximation

Function approximation also makes RL applicable to partially observable problems: if $\hat v$ cannot depend on some aspect of the state, it is as if that aspect is unobservable. (It cannot, however, augment the state with memories of past observations.)

9.1 Value-function approximation

Every prediction method shifts the estimate at some state toward an update target $u$: write $s\mapsto u$.

Each update is a supervised-learning training example (input $s$, desired output $u$) — "function approximation" when outputs are numbers. But not every supervised method suits RL; RL needs methods that:

• learn online from incrementally acquired data (not repeated passes over a static training set);
• handle nonstationary targets — the policy changes in GPI, and bootstrapped targets (DP, TD) change even for a fixed policy.

9.2 The prediction objective $\overline{\mathrm{VE}}$

With approximation, making one state more accurate makes others less accurate — so we must say which states we care about, via a distribution $\mu(s)\ge0$, $\sum_s\mu(s)=1$:

$\sqrt{\overline{\mathrm{VE}}}$ (root VE) is often plotted. Usually μ = fraction of time spent in $s$ — the on-policy distribution (stationary distribution under π for continuing tasks). For episodic tasks, with start distribution $h(s)$ and $\eta(s)$ = expected time steps in $s$ per episode:

With discounting, treat $1-\gamma$ as termination by putting a factor γ in the second term of (9.2).

• Is $\overline{\mathrm{VE}}$ the right objective? Our real goal is a better policy; the best value function for that need not minimise $\overline{\mathrm{VE}}$. But no clearly better alternative exists yet.
• Global optimum $\mathbf w^*$: possible for linear approximators. Local optimum: typically the best for nonlinear (ANNs, trees). Some methods may diverge ($\overline{\mathrm{VE}}\to\infty$).

9.3 Stochastic-gradient and semi-gradient methods

$\mathbf w=(w_1,\dots,w_d)^\top$; $\hat v(s,\mathbf w)$ differentiable in $\mathbf w$. Suppose each example gives the true value $S_t\mapsto v_\pi(S_t)$, with states drawn from μ. SGD takes a small step down the gradient of that example's squared error:

$\nabla f(\mathbf w)\doteq\big(\tfrac{\partial f}{\partial w_1},\dots,\tfrac{\partial f}{\partial w_d}\big)^\top$ (9.6). Why only a small step? We don't want zero error on one example — we want a balance of errors across states. Convergence results assume α decreases per (2.7) ⇒ SGD converges to a local optimum.

In practice $v_\pi(S_t)$ is unknown; substitute a target $U_t$:

If $U_t$ is unbiased ($\E[U_t|S_t=s]=v_\pi(s)$) — e.g. the MC return $G_t$ — convergence to a local optimum is guaranteed (decreasing α).

Input: the policy π to be evaluated
Input: a differentiable function v̂ : S × ℝᵈ → ℝ
Algorithm parameter: step size α > 0
Initialize value-function weights w ∈ ℝᵈ arbitrarily (e.g., w = 0)
Loop forever (for each episode):
    Generate an episode S₀, A₀, R₁, S₁, A₁, …, R_T, S_T using π
    Loop for each step of episode, t = 0, 1, …, T − 1:
        w ← w + α [G_t − v̂(S_t, w)] ∇v̂(S_t, w)

Input: the policy π to be evaluated
Input: a differentiable function v̂ : S⁺ × ℝᵈ → ℝ such that v̂(terminal,·) = 0
Algorithm parameter: step size α > 0
Initialize value-function weights w ∈ ℝᵈ arbitrarily (e.g., w = 0)
Loop for each episode:
    Initialize S
    Loop for each step of episode:
        Choose A ∼ π(·|S)
        Take action A, observe R, S'
        w ← w + α [R + γ v̂(S', w) − v̂(S, w)] ∇v̂(S, w)
        S ← S'
    until S is terminal

State aggregation: group states, one weight per group; $\nabla\hat v$ is 1 for the state's group component and 0 elsewhere — a special case of SGD (9.7).

Example 9.1 — the 1000-state random walk

States 1–1000, start at 500. Each step jumps to one of the 100 neighbours on the left or 100 on the right, uniformly; jumps past an edge terminate (−1 on the left, +1 on the right; e.g. state 1 terminates left w.p. ½). True $v_\pi$ is nearly a straight line, flattening slightly in the last 100 states at each end. State aggregation: 10 groups of 100 states.

• Staircase: value is constant within each group and jumps between groups; MC values are close to the global minimum of $\overline{\mathrm{VE}}$.
• Effect of μ: the start state 500 gets ≈1.37% of time steps; states one step away ≈0.17% each, falling almost linearly to ≈0.0147% at the ends. In the leftmost group, state 100 is weighted >3× state 1, so that group's value is shifted up toward $v_\pi(100)$ (and the rightmost group shifted down).
• TD's asymptotic values are farther from the truth than MC's (Fig 9.2 left) — the semi-gradient bias, cf. bound (9.14).

9.4 Linear methods

$\mathbf x(s)$ is the feature vector; each $x_i:\mathcal S\to\mathbb R$ is a feature (a basis function). The SGD update becomes $\mathbf w_{t+1}\doteq\mathbf w_t+\alpha\big[U_t-\hat v(S_t,\mathbf w_t)\big]\mathbf x(S_t)$.

• The linear case has one optimum (or one set of equally good optima) ⇒ local = global. Gradient MC converges to the global optimum of $\overline{\mathrm{VE}}$ (decreasing α).
• Semi-gradient TD(0) also converges, but needs a separate theorem — and to a point near the optimum: the TD fixed point.
• Exercise 9.1 — tabular methods are linear FA with one-hot features: $x_i(s)=1$ if $i=s$, else 0.

The TD fixed point

n-step semi-gradient TD

Input: the policy π to be evaluated
Input: a differentiable function v̂ : S⁺ × ℝᵈ → ℝ such that v̂(terminal,·) = 0
Algorithm parameters: step size α > 0, a positive integer n
Initialize value-function weights w arbitrarily (e.g., w = 0)
All store and access operations (S_t and R_t) can take their index mod n + 1
Loop for each episode:
    Initialize and store S₀ ≠ terminal
    T ← ∞
    Loop for t = 0, 1, 2, …:
        If t < T, then:
            Take an action according to π(·|S_t)
            Observe and store the next reward as R_{t+1} and the next state as S_{t+1}
            If S_{t+1} is terminal, then T ← t + 1
        τ ← t − n + 1
        If τ ≥ 0:
            G ← Σ_{i=τ+1}^{min(τ+n,T)} γ^{i−τ−1} R_i
            If τ + n < T, then: G ← G + γⁿ v̂(S_{τ+n}, w)          (G_{τ:τ+n})
            w ← w + α [G − v̂(S_τ, w)] ∇v̂(S_τ, w)
    Until τ = T − 1

9.5 Feature construction for linear methods

Features are how we add prior domain knowledge: they should correspond to aspects of the state along which generalisation is appropriate. Limitation of linear forms: no interactions between features (e.g. pole balancing: high angular velocity is good or bad depending on the angle) unless we add features for combinations.

9.5.1 Polynomials

E.g. $\mathbf x(s)=(1,s_1,s_2,s_1s_2)^\top$: the constant allows affine functions, the product captures interaction. Ex 9.2: each of the $k$ exponents independently takes $n+1$ values ⇒ $(n+1)^k$. Ex 9.3: $(1,s_1,s_2,s_1s_2,s_1^2,s_2^2,s_1s_2^2,s_1^2s_2,s_1^2s_2^2)$ is $n=2$, $k=2$ with $\mathbf c_i$ ranging over all of $\{0,1,2\}^2$. Exponential growth in $k$ ⇒ select subsets. Not recommended for online learning.

9.5.2 Fourier basis

• Set the period τ to twice the interval and use only cosines (even functions) — "half-even" functions are easier than "half-odd" ones (often discontinuous at the origin).
• $\mathbf c^i$ entries set the frequency along each dimension; a 0 means constant along that dimension; both non-zero ⇒ an interaction, with direction given by their ratio.
• Per-feature step sizes (Konidaris et al.): $\alpha_i=\alpha/\sqrt{(c^i_1)^2+\dots+(c^i_k)^2}$ (or α if all zero).
• Good performance vs polynomials and RBFs; trouble with discontinuities ("ringing"). Features are global (non-zero almost everywhere) ⇒ hard to represent local properties. Exponential in $k$, but for $k\le5$ you can use all order-n features.

9.5.3 Coarse coding

Features = overlapping receptive fields (e.g. circles); a binary feature is 1 ("present") if the state is inside. Training at one state changes the weights of all circles containing it, so the value changes over the union of those circles, more where more circles are shared (Fig 9.6).

• Receptive-field size → breadth of generalisation (narrow / broad); shape → direction (e.g. elongated ⇒ asymmetric generalisation) (Fig 9.7).
• Acuity — the finest discrimination possible — is controlled more by the total number of features than by their size.

9.5.4 Tile coding

Coarse coding for multi-dimensional continuous spaces, flexible and computationally efficient — "may be the most practical feature representation for modern sequential digital computers". Receptive fields are grouped into partitions (tilings) of tiles. One tiling = state aggregation; several offset tilings give true coarse coding (Fig 9.9: 4 tilings of 4×4 ⇒ 64 features, exactly 4 active).

• Tile shape controls generalisation: square ⇒ equal in all dimensions; stripes ⇒ along one dimension (ignoring others in that tiling); log stripes ⇒ finer resolution where needed; diagonal stripes ⇒ along a diagonal. Mix horizontal, vertical and conjunctive tilings to get both generalisation and the ability to learn specific conjunctions.
• Hashing: pseudo-randomly collapse a huge tiling into a much smaller set of (non-contiguous) tiles — memory matches the real demands of the task, not exponential in dimensions.
• Exercise 9.4 — if one dimension matters more, use tilings whose tiles are narrow across the important dimension and long along the unimportant one (stripes), so the value changes finely with the important variable and generalises broadly over the other.

9.5.5 Radial basis functions

Continuous-valued generalisation of coarse coding. Advantage: smooth, differentiable approximations — but rarely of practical significance; more computation than tile coding and often worse beyond 2 dimensions. An RBF network is linear; adapting centres/widths makes it nonlinear (more precise, but more computation and tuning).

9.6 Selecting step-size parameters manually

• Theory (2.7) gives sufficient conditions but too-slow learning; $\alpha_t=1/t$ is not appropriate for TD, nonstationary problems, or function approximation. RLS/LSTD-style optimal matrix step sizes cost $O(d^2)$.
• Tabular intuition: α = 1 eliminates the error after one target; $\alpha=1/\tau$ approaches the mean of targets after about τ experiences (recent ones weighted most).

Works best when feature vectors have similar length (ideally $\mathbf x^\top\mathbf x$ constant — as in tile coding, where it equals the number of tilings).

9.7 Nonlinear function approximation: artificial neural networks

• Feedforward ANN (no loops) vs recurrent. Units compute a weighted sum then an activation function — sigmoid $1/(1+e^{-x})$, rectifier $\max(0,x)$, or step (threshold unit).
• Universal approximation: one hidden layer with enough sigmoid units approximates any continuous function on a compact region (Cybenko 1989). Nonlinearity is essential — linear units stack to a linear function.
• Deep architectures learn hierarchical abstractions — automatic feature construction instead of hand-crafted features.
• Trained by SGD with backpropagation (forward pass for activations, backward pass for partial derivatives). In RL, ANNs can learn value functions from TD errors, or maximise reward (gradient bandit, policy gradient).
• Deep nets are hard to train: overfitting (many weights) and vanishing/exploding gradients. Remedies: cross-validation/early stopping, regularisation, weight sharing, dropout, unsupervised layer-wise pre-training (deep belief networks), batch normalisation, deep residual learning (skip connections).
• Deep convolutional networks: alternating convolutional (feature maps with shared weights over local receptive fields) and subsampling layers (spatial invariance) — trainable by backprop without special tricks; behind many impressive RL applications (Ch 16).

9.8 Least-squares TD

Why iterate toward $\mathbf w_{TD}=\mathbf A^{-1}\mathbf b$? Estimate $\mathbf A$ and $\mathbf b$ and solve directly:

Input: feature representation x : S⁺ → ℝᵈ such that x(terminal) = 0
Algorithm parameter: small ε > 0
Â⁻¹ ← ε⁻¹ I                      A d × d matrix
b̂ ← 0                            A d-dimensional vector
Loop for each episode:
    Initialize S; x ← x(S)
    Loop for each step of episode:
        Choose and take action A ∼ π(·|S), observe R, S'; x' ← x(S')
        v ← Â⁻¹ᵀ (x − γx')
        Â⁻¹ ← Â⁻¹ − (Â⁻¹x) vᵀ / (1 + vᵀx)
        b̂ ← b̂ + R x
        w ← Â⁻¹ b̂
        S ← S'; x ← x'
    until S' is terminal

9.9–9.10 Memory-based and kernel-based function approximation

• Memory-based (nonparametric, "lazy learning"): store examples $s'\mapsto g$; answer queries by retrieving relevant examples. Nearest neighbour, weighted average, locally weighted regression (fit a local surface, then discard it).
• Advantages: not limited to a fixed functional form (accuracy improves with data); focus on states actually visited along trajectories; immediate effect of experience; memory linear in the number of examples, not exponential in dimensions. Challenge: fast queries — k-d trees, parallel hardware, forgetting entries.
• Kernel $k(s,s')$: strength of generalisation from $s'$ to $s$. Kernel regression:

The kernel trick: construct kernels directly (no explicit features); many have compact forms that avoid computing in the high-dimensional feature space. Tile coding implicitly generalises according to a kernel (Fig 9.11). An RBF kernel differs from RBF features by being memory-based (centred on stored states) and nonparametric.

9.11 Interest and emphasis

Treating all states equally (the on-policy distribution) gives the strongest theory, but we may care more about some states (e.g. early states in discounted episodes). Interest $I_t\ge0$: how much we care about accurately valuing $S_t$ (any causal choice); it reweights μ. Emphasis $M_t\ge0$ multiplies the update:

Example 9.4: 4-state chain, reward +1 per step, true values 4, 3, 2, 1; parameters $w_1$ (states 1, 2) and $w_2$ (states 3, 4); interest 1 only on the first state.

9.12 Summary

• Generalisation via supervised function approximation: treat each update as a training example. Parameterised FA with $\mathbf w$; rank approximations with $\overline{\mathrm{VE}}$ under μ.
• n-step semi-gradient TD covers gradient MC (n = ∞) and semi-gradient TD(0) (n = 1). Semi-gradient methods aren't true gradient methods, but linear ones converge, to within a bound of the optimum that tightens as n grows. Some bootstrapping (finite n) usually learns fastest.
• Features: polynomials generalise poorly online; prefer Fourier or coarse coding — tile coding is especially efficient and flexible; RBFs for smooth 1–2-D tasks. LSTD is most data-efficient but $O(d^2)$. ANNs: deep RL.

Hyperparameters in this chapter

Self-test

Chapter quiz — check your understanding

Scored quiz: pick an answer (or type a number) to get instant feedback and an explanation. Questions marked Exam-style give you values to interpret (sweeps, logs, returns, learning curves), the way exam problems do. Your best score is saved in this browser and shown on the home page. "Shuffle & restart" re-orders the questions.