REASONING FROM SCRATCH · CHAPTER 06
Stop storing a Q-table. Write a softmax, sample a door, and push the preferences toward the door that paid.
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.”
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
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.
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.
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.
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.
“∇μ 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.
It does not depend on θ, so its log-derivative is zero.
0.622.
0.651.
A constant or running mean; a learned \(V(s)\); the mean reward of a group of samples from the same prompt.
"""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")