Stochastic Gradient Descent in RL

In RL, stochastic gradient descent chases a target that moves with the very weights being updated, so practical methods use semi-gradients that pretend the target stands still for one step.

Two semi-gradient steps on features [1,2] and [2,1] move the weights from zero to [0.9, 1.2], cutting the first error from 5.0 to 1.7

Why Does This Exist?

Big state spaces rule out lookup tables, so the value function becomes a parameterized approximation $\hat{v}(s, \mathbf{w})$ with weights $\mathbf{w}$ . The natural objective weights squared errors by how often each state is visited:

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

Here $\mu(s)$ is the fraction of time spent in $s$ and $v_\pi(s)$ is the true value. Stochastic gradient descent samples one transition at a time instead of summing over all states, which is the only affordable option when states are innumerable.

Three things break the supervised-learning story. The true value $v_\pi$ is unknown, so the target is a bootstrapped guess that moves with $\mathbf{w}$ . Transitions arrive along correlated trajectories, not as independent draws. And as the policy improves, the visitation distribution $\mu$ itself shifts. This page covers how SGD adapts: semi-gradient updates plus decaying step sizes. The linear features used below are taught in linear methods, and the Monte Carlo alternative with true gradients is gradient Monte Carlo.

Think of It Like This

Rowing toward a buoy tied to your own boat

You row toward a bright buoy to hold position in a current. In the supervised version the buoy is chained to the seabed: every stroke toward it is progress, and short steady strokes get you there.

In the RL version someone tied the buoy rope to the stern of your own boat. Each stroke still moves you toward where the buoy is right now, but the buoy slides forward as you pull. If you stop to compute exactly how your rowing drags the buoy, you will never row. So you cheat productively: aim at the buoy as if it were fixed, take one stroke, look again, and repeat.

The stroke is the gradient step, the rope is the target's dependence on your weights, and ignoring the rope is the semi-gradient. The cheat works because each single stroke barely moves the buoy.

Where it stops: a buoy slides in three dimensions and you can see it. Weights live in thousands of dimensions, the target surface can deform violently rather than slide, and with the wrong step size the boat can circle forever instead of settling.

How It Actually Works

Differentiating the objective gives an ideal update that needs the unknown true value:

\mathbf{w}_{t+1} = \mathbf{w}_t + \alpha\left[v_\pi(S_t) - \hat{v}(S_t, \mathbf{w}_t)\right]\nabla_{\mathbf{w}}\hat{v}(S_t, \mathbf{w}_t)

Here $\alpha$ is the step size and the bracket is the prediction error. Practice replaces $v_\pi(S_t)$ with a target $U_t$ . Monte Carlo uses the realized return $G_t$ , which is unbiased and weight-free, so that is true gradient descent. One-step TD uses $R_{t+1} + \gamma\hat{v}(S_{t+1}, \mathbf{w}_t)$ , whose second term depends on $\mathbf{w}_t$ . A full gradient would differentiate through that term too. The semi-gradient skips it:

\mathbf{w}_{t+1} = \mathbf{w}_t + \alpha\left[R_{t+1} + \gamma\hat{v}(S_{t+1}, \mathbf{w}_t) - \hat{v}(S_t, \mathbf{w}_t)\right]\nabla_{\mathbf{w}}\hat{v}(S_t, \mathbf{w}_t)

With linear features $\hat{v}(s, \mathbf{w}) = \mathbf{w}^T\mathbf{x}(s)$ the gradient is just the feature vector $\mathbf{x}(s)$ , so the update is $\mathbf{w} \leftarrow \mathbf{w} + \alpha\,\delta\,\mathbf{x}$ with scalar error $\delta$ . Convergence needs shrinking steps satisfying the Robbins-Monro conditions $\sum_t \alpha_t = \infty$ and $\sum_t \alpha_t^2 < \infty$ : large enough in total to reach far optima, decaying fast enough to drown out sampling noise. A constant step size never settles; it jitters forever in a noise ball around the fixed point.

Worked example

Linear model $\hat{v} = w_1x_1 + w_2x_2$ with $\mathbf{w}_0 = [0.0, 0.0]$ and $\alpha = 0.1$ .

Step 1: features $\mathbf{x} = [1.0, 2.0]$ , target $U_1 = 5.0$ . Prediction $0.0$ , error $\delta_1 = 5.0$ . Update: $\mathbf{w}_1 = [0.0, 0.0] + 0.1 \times 5.0 \times [1.0, 2.0] = [0.5, 1.0]$ .

Step 2: features $\mathbf{x} = [2.0, 1.0]$ , target $U_2 = 4.0$ . Prediction $0.5 \times 2.0 + 1.0 \times 1.0 = 2.0$ , error $\delta_2 = 2.0$ . Update: $\mathbf{w}_2 = [0.5, 1.0] + 0.1 \times 2.0 \times [2.0, 1.0] = [0.9, 1.2]$ .

Check both states under $\mathbf{w}_2$ : state 1 gives $0.9 + 2.4 = 3.3$ against target $5.0$ (error down from $5.0$ to $1.7$ ), state 2 gives $1.8 + 1.2 = 3.0$ against target $4.0$ (error down from $4.0$ to $1.0$ ). Shared weights improved both predictions at once, which is exactly what generalization buys and what tables cannot do.

Code

1def predict(w: list[float], x: list[float]) -> float:2    """Linear value estimate w dot x."""3    return w[0] * x[0] + w[1] * x[1]4
5
6def sgd_step(w: list[float], x: list[float], target: float, alpha: float) -> float:7    """One semi-gradient step; returns the prediction error."""8    error = target - predict(w, x)9    w[0] += alpha * error * x[0]10    w[1] += alpha * error * x[1]11    return error12
13
14w: list[float] = [0.0, 0.0]15alpha: float = 0.116e1 = sgd_step(w, [1.0, 2.0], 5.0, alpha)17e2 = sgd_step(w, [2.0, 1.0], 4.0, alpha)18print(f"{w[0]:.1f} {w[1]:.1f}")  # -> 0.9 1.219print(f"{e1:.1f} {e2:.1f}")  # -> 5.0 2.020print(f"{predict(w, [1.0, 2.0]):.1f}")  # -> 3.321print(f"{predict(w, [2.0, 1.0]):.1f}")  # -> 3.0

Watch Out For

Keeping a constant step size and calling the jitter convergence

With a fixed $\alpha$ the weights orbit the fixed point forever instead of landing on it, because every sample injects fresh noise that a constant step never damps. The symptom is a loss curve that falls, then flatlines into a fuzzy band, plus evaluation scores that wobble run to run. People respond by training longer, which changes nothing.

The fix is a schedule with $\alpha_t$ decaying roughly like $1/t$ , or an adaptive optimizer with decay, and to confirm the fix by watching the update magnitudes shrink toward zero late in training. If they do not shrink, the schedule is the bug.

Feeding correlated trajectory order straight into SGD

Updates drawn from one long trajectory pull the weights along whatever corridor the agent happens to be in, and the approximator quietly forgets distant states. The symptom is values that are accurate for recently visited regions and stale everywhere else, plus learning curves that sawtooth as the agent revisits areas.

The fix is an experience replay buffer: store transitions and sample mini-batches uniformly at random, which breaks the temporal correlation and restores something close to the independent sampling SGD assumes.

The Quick Version

Function approximation replaces tables with weights, and SGD updates them one sampled transition at a time.
Bootstrapped targets move with the weights, so TD methods use semi-gradients that differentiate the prediction but not the target.
Monte Carlo targets are weight-free, so Monte Carlo is true gradient descent while TD(0) is not.
Step sizes must satisfy the Robbins-Monro conditions; constant steps jitter forever instead of converging.
Correlated trajectories violate the independent-sampling assumption, which is why replay buffers shuffle transitions.
In the worked example two steps move weights from zero to [0.9, 1.2] and cut both prediction errors.