Linear Methods in RL

Why Does This Exist?

Tables fail when states are many or continuous. A robot arm never sees the exact same joint angles twice, so a table entry per state wastes memory and shares nothing between near identical states. You need generalization across states.

Value function approximation replaces the table with a parameterized guess. Deep nets generalize well but bring a rugged loss with local dips, saddle points, and divergence when combined with bootstrapping and off policy data. Linear methods keep the generalization and drop the ruggedness. The value is a dot product, the error is a quadratic bowl, and on policy TD converges to a bounded fixed point. This page covers the dot product form, the gradient identity, and the TD bound. Feature construction covers where good features come from. Semi-gradient TD covers the bootstrapped update in full.

The one idea you need first

A feature vector $x(s)$ in $\mathbb{R}^d$ is a short numeric summary of state $s$, one number per property. The weight vector $w$ in $\mathbb{R}^d$ holds one tunable number per property. Their dot product $w^T x(s)$ is the sum of pairwise products. That sum is the whole model.

Think of It Like This

How It Actually Works

Map state $s$ to features $x(s)$. Call $w$ the weights. The estimate is:

$\hat{v}(s, w) = w^T x(s) = \sum_{i=1}^d w_i x_i(s)$

The gradient with respect to $w$ is just the features:

$\nabla_w \hat{v}(s, w) = x(s)$

In words: to raise the estimate fastest, push weights along the feature direction. No chain rule, no backward pass.

Why the bowl has one bottom

Mean squared error under state weighting $\mu(s)$ is:

$\overline{VE}(w) = \sum_s \mu(s)[v(s) - w^T x(s)]^2 = w^T A w - 2b^T w + c$

Here $A = \sum_s \mu(s)x(s)x(s)^T$ is the feature covariance, $b$ mixes features with true values, $c$ is constant. Because $A$ is positive semi definite, the surface is a paraboloid. One bottom, no traps. Monte Carlo SGD with target $G_t$ is:

$w_{t+1} = w_t + \alpha[G_t - w_t^T x(S_t)]x(S_t)$

Semi-gradient TD with reward $R_{t+1}$ and discount $\gamma$ uses the bootstrapped error:

$\delta_t = R_{t+1} + \gamma w_t^T x(S_{t+1}) - w_t^T x(S_t)$

$w_{t+1} = w_t + \alpha \delta_t x(S_t)$

On policy this converges to the TD fixed point $w_{TD}$ with error bounded by $1/(1-\gamma)$ times the best linear error.

Worked example

Features $x = [1.0, 0.5]$, weights $w_0 = [2.0, 1.0]$, rate $\alpha = 0.2$, target $U = 4.0$.

Prediction:

$\hat{v} = 2.0 \times 1.0 + 1.0 \times 0.5 = 2.5$

Error:

$\delta = 4.0 - 2.5 = 1.5$

Update along features:

$\Delta w = 0.2 \times 1.5 \times [1.0, 0.5] = [0.30, 0.15]$

$w_1 = [2.30, 1.15]$

New prediction:

$\hat{v}_{new} = 2.30 \times 1.0 + 1.15 \times 0.5 = 2.875$

Shift is $0.375$, which equals $\alpha \delta \|x\|^2 = 0.2 \times 1.5 \times 1.25$. The diagram draws this exact move from $2.5$ to $2.875$ on the bowl.

Code

This snippet replays the worked numbers and one TD step. It uses only the standard library.

1from typing import List2
3
4def predict(w: List[float], x: List[float]) -> float:5    """Dot product wT x."""6    return sum(wi * xi for wi, xi in zip(w, x))7
8
9if __name__ == "__main__":10    x = [1.0, 0.5]11    w = [2.0, 1.0]12    v0 = predict(w, x)13    print(f"v0 = {v0:.3f}")  # -> v0 = 2.50014    delta = 4.0 - v015    alpha = 0.216    w = [wi + alpha * delta * xi for wi, xi in zip(w, x)]17    print(f"w1 = {w}")  # -> w1 = [2.3, 1.15]18    v1 = predict(w, x)19    print(f"v1 = {v1:.3f}")  # -> v1 = 2.875

Watch Out For

The Quick Version

• Linear methods predict value as $\hat{v}(s,w) = w^T x(s)$, a weighted sum of features with learnable weights.
• The gradient equals the features, so each update is $w + \alpha \delta x(s)$ with no backprop.
• Squared error is a quadratic bowl with one global bottom, so there are no local minima.
• In the worked check features $[1.0, 0.5]$ and weights $[2.0, 1.0]$ give $2.5$, then move to $[2.30, 1.15]$ and $2.875$ after one step toward $4.0$.
• On policy semi-gradient TD converges to a fixed point within $1/(1-\gamma)$ of the best linear fit, but off policy use needs correction.

What to Read Next

• Value Function Approximation in RL
• Feature Construction in RL
• Semi-Gradient TD(0) in RL
• Information-Theoretic Regret Bounds