REASONING FROM SCRATCH · CHAPTER 06

Policy gradients
& REINFORCE

Stop storing a Q-table. Write a softmax, sample a door, and push the preferences toward the door that paid.

~20 min readOwn tiny REINFORCETested Python

What you'll learn

  • The trajectory log-derivative, and why the environment drops out
  • REINFORCE as \(\theta \leftarrow \theta + \alpha\, G\, \nabla\log\pi\)
  • Reward-to-go and a baseline, including the group mean GRPO will use
  • A worked two-door softmax you can do by hand

Before you start

Two doors under the harbor

One state: you stand at a fork. Left is a sure cellar, reward +1. Right is a vault: +4 with probability 0.4, else 0. Expected Right is 1.6, so Right is better. You do not know that. You hold two preferences \(\theta = (0.0, 0.5)\) and sample from a softmax.

A language-model head is this softmax. Tokens are doors. The return is a verifier score at the end. REINFORCE is “raise the log-prob of whatever you sampled, scaled by how well it paid.”

The dynamics drop out

A trajectory \(\tau\) is a sequence of states and actions. Its probability factors as \(p(\tau) = p(s_0)\prod_t \pi_\theta(a_t\mid s_t)\, P(s_{t+1}\mid s_t, a_t)\). Take \(\log\), then \(\nabla_\theta\). Every \(P\) is constant in \(\theta\). You are left with a sum of score functions:

doors · score · push · baseline

MANIM Policy gradient: log π × advantage; baseline cuts variance.

only the policy’s log-probs depend on θ. The cave, or the next-token append, does not.

The objective is \(J(\theta) = \mathbb{E}_{\tau\sim\pi_\theta}[G(\tau)]\). The log-derivative identity \(\nabla \pi = \pi\, \nabla\log\pi\) turns the gradient into an expectation you can sample:

sample a trajectory, multiply its return by the sum of score vectors, average.

Nothing “telescopes to zero.” We never needed \(\nabla\mu\). The factorization already hid the state distribution.

REINFORCE on the two doors

Softmax of \((0.0, 0.5)\):

e^{0} / (e^{0} + e^{0.5}) = 1 / (1 + 1.649) ≈ 0.378.

We sample Right and the vault pays \(G = 4\). The softmax score is \(1-\pi\) on the chosen door and \(-\pi\) on the other: \(\nabla\log\pi(R) = (-0.378, +0.378)\). Step size \(\alpha = 0.10\):

Right becomes more likely. Left becomes less. That is the whole algorithm.

Reward-to-go: only future rewards multiply \(\nabla\log\pi(a_t)\). Past oil you already burned should not credit the next token. In a one-action cellar it does not matter. In a long chain of thought it does.

Subtract a guess, keep the direction

A baseline \(b\) that does not depend on the sampled action is unbiased: \(\mathbb{E}[(G-b)\nabla\log\pi] = \nabla J\). It cuts variance. A running mean of recent returns is the simplest. A learned \(V(s)\) is an actor-critic. A group mean of several samples from the same prompt is what GRPO will use.

Same Right-and-4 sample, \(b = 2\). Advantage \(A = 2\). The step halves: \(\theta \leftarrow (-0.076, 0.576)\). Same sign, less jitter.

The loss you will implement is usually a minimize of \(-\sum A\log\pi\). Same gradient. Watch the sign.

One forward pass, every token log-prob

A causal model’s logits at each position are \(\log\pi(a_t\mid s_t)\). Teacher-forced SFT maximizes them toward a gold reply. REINFORCE multiplies the same log-probs by a scalar advantage from a sampled reply. PPO and GRPO keep this product and add a clip and a KL. The two-door update is the whole idea at one token.

Mistakes learners make

“∇μ telescopes to zero.” Wrong picture. The trajectory factorization never forms \(\nabla\mu\).

Credit the whole return to every token, including those after the answer. Use reward-to-go. Only the future multiplies this score.

A baseline that depends on the sampled action. Then the estimator is biased. The group mean is OK because it is computed from a set, then applied, but you must not include a differentiable dependence that you fail to account for.

What to remember

  • \(\nabla\log p(\tau) = \sum \nabla\log\pi\). Dynamics drop out.
  • Two-door softmax of (0.0, 0.5) is 0.378 / 0.622. A Right that pays 4 moves θ to (−0.151, 0.651).
  • A baseline of 2 halves that step and keeps it unbiased.
  • The group mean is a legal baseline. That is the GRPO preview.

Check yourself

1. Why can we ignore \(P(s'\mid s, a)\) in the policy gradient?

It does not depend on θ, so its log-derivative is zero.

2. \(\theta = (0, 0.5)\). What is \(\pi(\mathrm{Right})\)

0.622.

3. After Right pays 4 with \(\alpha = 0.10\) and no baseline, what is \(\theta_R\)

0.651.

4. Name three baselines, from crude to GRPO-like.

A constant or running mean; a learned \(V(s)\); the mean reward of a group of samples from the same prompt.

The code

two_door_reinforce.pysoftmax 0.378/0.622; update to 0.651
"""Tiny REINFORCE on the two-door cellar.

One state. Two actions.
  Left  — a sure +1 (the safe cellar).
  Right — +4 with probability 0.4, else 0 (the risky vault).

The policy is a softmax over two preferences θ. The numbers on the page
come from one sampled Right that paid +4, then the same update with a
baseline.
"""
import math

THETA = (0.0, 0.5)          # left, right
ALPHA = 0.10
REWARD_RIGHT = 4.0
BASELINE = 2.0              # a running mean of recent returns


def softmax(theta):
    """Two-class softmax. Written out so a reader can check it by hand."""
    m = max(theta)
    exps = [math.exp(t - m) for t in theta]
    z = sum(exps)
    return [e / z for e in exps]


def score(theta, action):
    """∇ log π(a). For softmax this is 1−π on the chosen arm, −π on the other."""
    pi = softmax(theta)
    return [ (1 - pi[i]) if i == action else (-pi[i]) for i in range(len(theta)) ]


def reinforce_update(theta, action, ret, alpha=ALPHA, baseline=0.0):
    """θ ← θ + α (G − b) ∇ log π(a). One step, one sample."""
    adv = ret - baseline
    g = score(theta, action)
    return tuple(t + alpha * adv * gi for t, gi in zip(theta, g)), adv, g


PI = softmax(THETA)
# Sampled action = Right (index 1), return = 4.
NEW_THETA, ADV_RAW, SCORE_R = reinforce_update(THETA, 1, REWARD_RIGHT, baseline=0.0)
NEW_THETA_B, ADV_B, _ = reinforce_update(THETA, 1, REWARD_RIGHT, baseline=BASELINE)

# Expected rewards under a greedy readout — for the page, not the update.
E_LEFT = 1.0
E_RIGHT = 0.4 * 4.0          # 1.6


if __name__ == "__main__":
    assert abs(PI[0] - 0.3775406688) < 1e-9
    assert abs(PI[1] - 0.6224593312) < 1e-9
    assert abs(E_RIGHT - 1.6) < 1e-12
    # Raw update: adv = 4, score_right = +π_left ≈ +0.3775
    assert abs(ADV_RAW - 4.0) < 1e-12
    assert abs(SCORE_R[1] - PI[0]) < 1e-12
    assert abs(NEW_THETA[1] - (0.5 + ALPHA * 4.0 * PI[0])) < 1e-12
    assert abs(ADV_B - 2.0) < 1e-12
    print("two-door reinforce ok")

Go to the source

Keep going