REINFORCE, annotated

How to read this page

• Any dotted word explains itself when you hover it, tab to it, or tap it, and so does every symbol in every equation.
• The diagrams are live: hover or tap a part to read what it does. Two charts respond to you: one shows how a random unit's search narrows and widens, the other lets you watch a learner without a baseline lock onto the wrong answer.

Each idea climbs the same ladder: an everyday picture, a tiny example you can check by hand, a diagram, the math, and why it matters today. One small example runs through the whole page: a single random unit with two inputs, learning which of two actions pays better. The reinforcement learning lesson builds the same algorithm from scratch on a row of slot machines.

Abstract · original

“These algorithms, called REINFORCE algorithms, are shown to make weight adjustments in a direction that lies along the gradient of expected reinforcement …”Williams (1992), Abstract

Everyday picture

A dog learning a trick cannot be shown the answer. It tries something, gets a treat or doesn't, and does more of whatever earned treats. This paper turns that into arithmetic for a network of units that each flip a weighted coin: after every try, nudge each unit's weights so that what it just did becomes more likely, by an amount proportional to how good the outcome was. The paper proves that this simple nudge climbs, on average, exactly the hill we care about: the expected reward.

What the paper claims

• A whole family of learning rules, all of the form step = rate × (reward − baseline) × eligibility, whose average step points along the gradient of expected reward (Theorem 1).
• The rules need no model of the world and never compute the gradient explicitly: each unit uses only its own input, output and one broadcast reward number.
• It extends to rewards that arrive at the end of an episode (Theorem 2), to units whose randomness has several knobs, such as a bell curve with a mean and a spread, and it combines with backpropagation.

Why it matters today

This is the root of every policy-gradient method. When a language model is tuned with RLHF or trained to reason with GRPO, the gradient at the heart of the update is this paper's: reward, minus a baseline, times the gradient of the log-probability of what the model wrote.

1 Introduction · original

“Perhaps a more informative adjective would be non-model-based.”Williams (1992), §1, on why the algorithms are called simple

Everyday picture

Picture a vending machine that takes a coin and a button press and sometimes gives a snack. You can learn which button works best without ever opening the machine to see how it decides: you only need to try buttons and count snacks. The paper studies learners like that. They never build a model of the machine; they climb towards better behaviour using only the snacks.

The setting, in the paper's words decoded

• Associative: the learner maps inputs to outputs, so the best action can depend on the situation.
• Immediate reinforcement: each reward depends only on the latest input and output. Section 5 relaxes this.
• Search by randomness: the learner explores by being random: its outputs are drawn from a distribution its weights control.
• Gradient-following: the learning rules climb the gradient of a performance measure, on average, without ever writing the gradient down.

The introduction also places the work next to its neighbours: learners that pair an immediate-reward rule with a learned predictor, the critic, using temporal-difference methods; and Q-learning. REINFORCE is the immediate-reward half of such systems, studied on its own.

Why it matters

“Non-model-based” is still the defining property. A language model trained with a policy gradient never learns how the grader works; it only learns which of its own outputs the grader liked. That is why the same recipe works whether the reward comes from a unit test, a human, or another model.

2 Reinforcement-learning connectionist networks · original

Everyday picture

Each unit in the network is a coin whose bias you can adjust. The unit adds up its inputs, each multiplied by a weight, squashes the total into a probability, and flips a coin with that probability of heads. Heads means “output 1”, tails “output 0”. The environment sees the outputs and hands back one number, the reward, to every unit.

Tiny example: one unit, two inputs

The unit gets inputs x = (1, 2). The first input is always 1, so its weight acts as a bias. The weights are w = (−1, 1). The weighted sum is s = (−1)(1) + (1)(2) = 1. The logistic function squashes it: p = 1 / (1 + e⁻¹) = 0.731. The unit then outputs 1 with probability 0.731 and 0 with probability 0.269. On this trial the coin comes up 1.

Reading it: the left column is the unit acting, top to bottom. Inputs meet weights, the sum is squashed into a probability, a coin is flipped with that probability, and the environment scores what came out. The right column is the unit learning, bottom to top. The reward is compared with a baseline (r − b), the unit works out its eligibility from its own output and probability, the two are multiplied, and the result, scaled by a small rate α, is added to the weights. Notice what the learning column needs: the unit's own input, output and probability, plus one number broadcast from the environment. Nothing else in the network has to be known.

The math: a stochastic semilinear unit

In words: “multiply each input by its weight and add them up; squash the total with the logistic function; the result is the chance the unit outputs 1.”

With the numbers: s = (−1)(1) + (1)(2) = 1, and p = 1 / (1 + e⁻¹) = 1 / 1.368 = 0.731.

In Python:

import math
x = [1, 2]
w = [-1, 1]
# s_i = Σ_j w_ij x_j
s = sum(w_j * x_j for w_j, x_j in zip(w, x))
s  # → 1
# p_i = f_i(s_i), the logistic squash
p = 1 / (1 + math.exp(-s))
round(p, 3)  # → 0.731

The paper calls this a stochastic semilinear unit: a weighted sum, a smooth squash, then a random draw. With a coin flip as the draw it is a Bernoulli semilinear unit, and with the logistic squash, a Bernoulli-logistic unit. The chance of each output is written g:

In words: “the chance that unit i produces the output ξ is p_i if ξ is 1, and 1 − p_i if ξ is 0.” This is a Bernoulli distribution: a weighted coin.

With the numbers: g(1) = 0.731 and g(0) = 1 − 0.731 = 0.269. They add to 1, as the chances of all possible outputs must.

In Python:

import math
p = 1 / (1 + math.exp(-1))
# g_i(ξ): the chance of each output ξ
g = {0: 1 - p, 1: p}
round(g[1], 3), round(g[0], 3)  # → (0.731, 0.269)
round(g[0] + g[1], 3)  # → 1.0

The paper adds a useful observation: a unit that outputs 1 whenever its sum plus some random noise is positive (the form used by Barto and colleagues) is secretly the same kind of unit, with squashing function f(s) = 1 − Ψ(−s), where Ψ is the noise's cumulative distribution. So the results cover those learners too.

Why it matters

Swap “coin” for “die with one face per word” and this unit is a language model's output layer: a weighted sum per token (the logits), a squash into probabilities (softmax), and a random draw of the next token. The grad_log_prob function in the lesson is the many-sided version of this unit's eligibility.

3 The expected reinforcement performance criterion · original

Everyday picture

A single snack from the vending machine tells you little: you might have been lucky. What you care about is how many snacks a button gives on average, over many tries. The paper's goal for learning is exactly that average: the expected reward, as a function of the weights.

Tiny example

Say our environment pays reward 1 with chance 0.8 when the unit outputs 1, and with chance 0.4 when it outputs 0; otherwise it pays 0. Output 1 is the better action. With p = 0.731 the unit earns, on average, 0.731 × 0.8 + 0.269 × 0.4 = 0.585 + 0.108 = 0.692 per trial. Always choosing 1 would earn 0.8.

The math

The paper writes the goal as E{r | W}: the expected reward given the weights. Splitting it over the unit's possible outputs (the first step of its Appendix A) shows what it is made of:

In words: “the average reward is, for each output the unit could produce, the chance of producing it times the average reward it brings, added up.”

With the numbers: 0.731 × 0.8 + 0.269 × 0.4 = 0.692.

In Python:

import math
p = 1 / (1 + math.exp(-1))
g = {0: 1 - p, 1: p}
# E{r | W, y = ξ}: the chance each output pays 1
reward_if = {0: 0.4, 1: 0.8}
# Σ_ξ g(ξ) E{r | W, y = ξ}
round(sum(g[xi] * reward_if[xi] for xi in (0, 1)), 3)  # → 0.692

The paper notes this is only a fixed function of the weights if the world is steady: inputs drawn independently from a distribution that doesn't change, and rewards from a fixed rule. Under those assumptions learning is a search over weights for the highest point of this function, a function the learner can never see directly.

Why it matters

Modern papers write the same quantity as J(θ), the expected reward of a policy with parameters θ. The expected_reward function in the lesson is this equation for a row of slot machines.

4 REINFORCE algorithms · original

“The name is an acronym for ‘REward Increment = Nonnegative Factor times Offset Reinforcement times Characteristic Eligibility,’ which describes the form of the algorithm.”Williams (1992), §4

Everyday picture

A football coach reviews the tape. For each player, the coach asks two questions: was the result better or worse than usual, and how much would this player have to change to make what they just did more likely? Multiply the answers, and that is the player's adjustment. Players who did something unusual in a good game change the most.

Tiny example

Our unit output y = 1 with p = 0.731 and the environment paid r = 1. Take a baseline b = 0.5 (a guess at the typical reward) and rate α = 0.1. The eligibility of each weight turns out to be (y − p) × its input (derived in the special cases): (1 − 0.731) × (1, 2) = (0.269, 0.538). The update is 0.1 × (1 − 0.5) × (0.269, 0.538) = (0.0134, 0.0269). Both weights rise, which raises s and so raises the chance of output 1 next time.

Reading it: read the top row as a sentence and the bottom row as an equation; each column is one idea. The first column is what gets computed, the change to one weight. The other three are multiplied to make it: a step size that is never negative, the reward measured against a baseline, and the eligibility, which is where the unit's own randomness enters. Hover the third column and notice that it is the only one that depends on how the trial went, and the fourth the only one that depends on what this particular unit did.

The math: the REINFORCE update

In words: “change each weight by a step size, times how much better than the baseline the reward was, times how strongly that weight could raise the log-probability of the output the unit just produced.”

With the numbers: e = (0.269, 0.538), r − b = 1 − 0.5 = 0.5, α = 0.1, so Δw = 0.1 × 0.5 × (0.269, 0.538) = (0.0134, 0.0269).

In Python:

import math
x, w = [1, 2], [-1, 1]
p = 1 / (1 + math.exp(-sum(w_j * x_j for w_j, x_j in zip(w, x))))
# this trial: output 1, reward 1, baseline 0.5, rate 0.1
y, r, b, alpha = 1, 1, 0.5, 0.1
# e_ij = ∂ ln g_i / ∂ w_ij, which for this unit is (y − p) x_j
e = [(y - p) * x_j for x_j in x]
[round(e_j, 3) for e_j in e]  # → [0.269, 0.538]
# Δw_ij = α (r − b) e_ij
[round(alpha * (r - b) * e_j, 4) for e_j in e]  # → [0.0134, 0.0269]

The rules: α must not be negative and may depend only on the unit's weights and on time; b may be anything that does not depend on the unit's current output. Everything with this shape is a REINFORCE algorithm.

Why it matters

This is the update in reinforce_step, and, summed over the tokens of an answer, the core of every policy-gradient update used on language models. The log is what makes it work: dividing by the probability means a rare output that paid off gets a bigger push than a common one, which is exactly what keeps the average honest.

Theorem 1: the average step points uphill · original

Everyday picture

A hiker in fog cannot see the slope, but can take a step in a random-looking direction after each clue. Theorem 1 says: however jittery each step, the average step points uphill, and if everyone uses the same stride, the average step is exactly the slope times the stride.

Tiny example

Average our unit's update over everything random on a trial: which output it draws, and whether that output pays. The true slope of the expected reward is (0.0786, 0.1573) (the gap between the two actions' payouts, 0.4, times p(1 − p) = 0.197, times each input). The average update, with α = 0.1, comes out at (0.00786, 0.01573): exactly 0.1 times the slope. And it comes out the same with b = 0.5 or b = 0.

In words: “the average update never points downhill on the expected reward (it is zero only at a flat spot), and with one shared step size it is exactly the step size times the uphill direction.” Equivalently, each (r − b) e_ij is an unbiased estimate of the slope for w_ij.

With the numbers: the slope is (0.0786, 0.1573); the average update is (0.00786, 0.01573) = 0.1 × the slope; their dot product is 0.00309, positive.

In Python:

import math
x = [1, 2]
p = 1 / (1 + math.exp(-1))
alpha = 0.1
# chance of reward 1 after output 1 and after output 0
q1, q0 = 0.8, 0.4
# ∇ E{r|W}: payout gap × ∂p/∂w_j, and ∂p/∂w_j = p(1 − p) x_j
grad = [(q1 - q0) * p * (1 - p) * x_j for x_j in x]
[round(g_j, 4) for g_j in grad]  # → [0.0786, 0.1573]
# E{ΔW | W}: average α(r − b)(y − p)x over y = 1 (chance p) and y = 0 (chance 1 − p)
def average_update(b):
    return [alpha * (p * (q1 - b) * (1 - p) + (1 - p) * (q0 - b) * (0 - p)) * x_j for x_j in x]
[round(v, 5) for v in average_update(0.5)]  # → [0.00786, 0.01573]
[round(v, 5) for v in average_update(0.0)]  # → [0.00786, 0.01573]
# E{ΔW}ᵀ ∇E{r|W}
round(sum(a * g_j for a, g_j in zip(average_update(0.5), grad)), 5)  # → 0.00309

Why it matters

This is the guarantee every policy-gradient method leans on, and the reason the baseline is free: it changes how noisy each step is, never where the steps point on average. The appendix section below shows why in one line. The lesson's gradient_estimate_stats computes the same exact average and the noise around it.

Old algorithms that turn out to be REINFORCE · original

Everyday picture

Several learning rules already in use in 1992 had been invented separately, each with its own story. The paper shows that some of them are the same rule with particular choices of step size and baseline, so Theorem 1 covers them all at once.

A coin with no inputs: the learning automaton

First, a unit with no inputs at all, whose only adjustable number is p itself. The eligibility of p follows from the log of g:

In words: “the eligibility of p is 1/p after a 1 and −1/(1 − p) after a 0, which is one expression, (y − p)/(p(1 − p)). Choose the step size ρ p(1 − p) and baseline 0, and the p(1 − p) cancels: move p towards the output just produced, in proportion to the reward.”

With the numbers: at p = 0.731 the eligibility is (1 − 0.731)/0.197 = 1.368 after a 1, and (0 − 0.731)/0.197 = −3.718 after a 0. With ρ = 0.1, reward 1 and output 1, p moves up by 0.1 × 1 × 0.269 = 0.0269.

In Python:

import math
p = 1 / (1 + math.exp(-1))
# ∂ ln g / ∂p = (y − p) / (p (1 − p)), after a 1 and after a 0
[round((y - p) / (p * (1 - p)), 3) for y in (1, 0)]  # → [1.368, -3.718]
# Δp = ρ r (y − p)
rho, r, y = 0.1, 1, 1
round(rho * r * (y - p), 4)  # → 0.0269

With rewards of only 0 or 1, this is the two-action linear reward-inaction automaton (L_R−I) from the learning-automata literature: reward moves p towards what was done; no reward, no move.

The logistic unit

Now give the unit inputs and weights. The chain rule multiplies three slopes: log g by p, p by s (for the logistic, p(1 − p)), and s by w_ij (just x_j). The p(1 − p) on top cancels the one underneath:

In words: “for a Bernoulli-logistic unit, a weight's eligibility is the surprise in the output (what happened minus what was expected) times that weight's input. With baseline 0, the update is rate times reward times that.”

With the numbers: (1 − 0.731) × (1, 2) = (0.269, 0.538); the chain-rule product for the second weight is 1.368 × 0.197 × 2 = 0.538, the same. With α = 0.1 and r = 1, Δw = (0.0269, 0.0538).

In Python:

import math
x, y = [1, 2], 1
p = 1 / (1 + math.exp(-1))
# chain rule for w_1: ∂lng/∂p × ∂p/∂s × ∂s/∂w_1
round((y - p) / (p * (1 - p)) * p * (1 - p) * x[1], 3)  # → 0.538
# the shortcut: (y − p) x_j
[round((y - p) * x_j, 3) for x_j in x]  # → [0.269, 0.538]
# Δw_ij = α r (y − p) x_j
alpha, r = 0.1, 1
[round(alpha * r * (y - p) * x_j, 4) for x_j in x]  # → [0.0269, 0.0538]

This is the associative reward-inaction rule of Barto and colleagues: their reward-penalty rule with its penalty term switched off (λ = 0) reduces to exactly this update, so it is a REINFORCE algorithm and Theorem 1 covers it.

Why it matters

“Surprise times input” is the same shape as the error signal in ordinary supervised learning, (target − prediction) × input, with the sampled output playing the target. REINFORCE is supervised learning on your own samples, weighted by how well they turned out. The softmax version, one-hot minus probabilities, is grad_log_prob.

Reinforcement comparison: a baseline that learns · original

Everyday picture

A student who always scores between 70 and 80 learns nothing from “you got 76” unless they know their usual score is 74. Keep a running average of past rewards, and judge each new reward against it.

Tiny example

The running average stands at r̄ = 0.5. This trial pays r = 1, so the unit learns from r − r̄ = 0.5, exactly the update we computed earlier with b = 0.5. Only then does the average absorb the new reward: with γ = 0.2 it becomes 0.2 × 1 + 0.8 × 0.5 = 0.6.

In words: “use the running average of earlier rewards as the baseline; after each trial, move that average a fraction γ of the way towards the reward just received.”

With the numbers: r − r̄ = 1 − 0.5 = 0.5, so Δw = 0.1 × 0.5 × 0.269 × (1, 2) = (0.0134, 0.0269); then r̄ becomes 0.2 × 1 + 0.8 × 0.5 = 0.6.

In Python:

import math
x, y = [1, 2], 1
p = 1 / (1 + math.exp(-1))
alpha, gamma, r, r_bar = 0.1, 0.2, 1, 0.5
# Δw = α (r − r̄)(y − p) x_j, using the average from before this trial
[round(alpha * (r - r_bar) * (y - p) * x_j, 4) for x_j in x]  # → [0.0134, 0.0269]
# r̄(t) = γ r(t − 1) + (1 − γ) r̄(t − 1)
r_bar = gamma * r + (1 - gamma) * r_bar
round(r_bar, 2)  # → 0.6

It stays a REINFORCE algorithm as long as r̄ is never computed from the current output or the current reward, which is why the average is updated only after the step. The paper notes that the analysis offers no basis for comparing baselines, but that reinforcement comparison is generally believed to perform better; Section 8.3 returns to this.

Why it matters

A learned baseline became the critic of actor-critic methods and the value network of PPO. GRPO goes back to something closer to this paper: the baseline is simply the average reward of other answers to the same prompt (the DeepSeek-R1 companion shows it training a reasoning model). The lesson's train_reinforce uses a running-average baseline.

5 Episodic REINFORCE algorithms · original

Everyday picture

A chess player learns only at the end of the game whether they won. Which moves deserve the credit? With no other information, a fair rule is: every move shares the verdict, and each move's own “how would I make this more likely” is added up over the game. That is the credit assignment the paper proposes when a single reward arrives at the end of an episode.

Tiny example

An episode lasts k = 3 steps. A weight's eligibilities at the three steps are 0.3, −0.2 and 0.4, collected as the network runs. The episode ends with r = 1 against a baseline of 0.4. With α = 0.1, the weight changes by 0.1 × (1 − 0.4) × (0.3 − 0.2 + 0.4) = 0.1 × 0.6 × 0.5 = 0.03.

Reading it: on the left is a network whose unit feeds back into itself, so its output at one step affects the next. The paper's trick is to unfold it in time: draw one copy per step, all sharing the same weights, so the loop becomes a straight chain (right). Each copy works out its eligibility as it runs, and a single accumulator per weight adds them up, needing nothing from the future. Only at the end does the reward arrive, and the whole sum is multiplied by it once.

The math

In words: “add up a weight's eligibility over every step of the episode, then scale the total by the rate and by how much better than the baseline the final reward was.”

With the numbers: Σ e = 0.3 − 0.2 + 0.4 = 0.5; Δw = 0.1 × (1 − 0.4) × 0.5 = 0.03.

In Python:

# e_ij(t) for t = 1, 2, 3, accumulated as the episode runs
e = [0.3, -0.2, 0.4]
alpha, r, b = 0.1, 1, 0.4
# Σ_t e_ij(t)
round(sum(e), 2)  # → 0.5
# Δw = α (r − b) Σ_t e_ij(t)
round(alpha * (r - b) * sum(e), 3)  # → 0.03

Theorem 2 says the same as Theorem 1 for this episodic rule: the average update never points downhill, and with a shared rate it is the rate times the gradient. For rewards that arrive at every step, the paper suggests replacing r with the sum of rewards over the episode, and hints that when rewards depend only on the past, credit could be assigned more finely.

Why it matters

A generated answer is an episode: one token per step, one reward at the end. Summing the eligibilities over the steps is summing the gradients of every token's log-probability, which is exactly what policy-gradient training of language models does. The paper also names the weakness honestly: spreading the verdict evenly over every step is slow, which is why later methods add a critic that judges each step, and why GRPO normalises the one final reward against a group of answers.

6 REINFORCE with multiparameter distributions · original

Everyday picture

A treasure hunter with a metal detector chooses two things: where to dig and how wide a patch to try around that spot. A unit whose output is drawn from a bell curve has both knobs: the mean says where, the standard deviation says how widely it explores. Learning can turn both.

Tiny example

A Gaussian unit has mean μ = 0 and spread σ = 1. It draws y = 0.5, close to the mean. The eligibility of μ is (0.5 − 0)/1 = 0.5 (moving μ towards 0.5 makes it likelier). The eligibility of σ is (0.25 − 1)/1 = −0.75: shrinking the spread makes a close draw likelier. Had it drawn y = 2, far out, the eligibilities would be 2 and +3: widening makes far draws likelier.

In words: “the mean's eligibility is how far the draw landed from the mean, divided by the variance; the spread's eligibility is positive when the draw landed further out than one standard deviation and negative when it landed closer in.”

With the numbers: y = 0.5 gives (0.5, −0.75); y = 2 gives (2, 3). The REINFORCE updates are then Δμ = α_μ(r − b_μ) × the first and Δσ = α_σ(r − b_σ) × the second; the paper suggests α_μ = α_σ = ασ² and a reinforcement-comparison baseline. With α = 0.1, σ = 1 and a draw at y = 0.5 that beat the baseline by 1, μ moves up 0.05 and σ shrinks by 0.075.

In Python:

mu, sigma = 0.0, 1.0
def eligibilities(y):
    # ∂ ln g/∂μ = (y − μ)/σ², ∂ ln g/∂σ = ((y − μ)² − σ²)/σ³
    return (y - mu) / sigma**2, ((y - mu) ** 2 - sigma**2) / sigma**3
eligibilities(0.5)  # → (0.5, -0.75)
eligibilities(2.0)  # → (2.0, 3.0)
# Δμ, Δσ with α_μ = α_σ = α σ², and r − b = 1
alpha, advantage = 0.1, 1.0
e_mu, e_sigma = eligibilities(0.5)
round(alpha * sigma**2 * advantage * e_mu, 3), round(alpha * sigma**2 * advantage * e_sigma, 3)  # → (0.05, -0.075)

A footnote warns that nothing stops σ from being pushed below zero; learning log σ instead of σ keeps it positive.

Proposition 1: one pattern for many distributions

The mean's eligibility (y − μ)/σ² has the same shape as the Bernoulli unit's (y − p)/(p(1 − p)): output minus mean, over variance. The paper proves this is no accident. Every distribution of the exponential-family form below, with μ its mean, has this eligibility.

In words: “if the log-probability of an outcome is a straight-line function of the outcome (plus terms that don't involve both), then the eligibility of the mean is always output minus mean, divided by the variance.”

With the numbers: a Poisson unit with mean μ = 2 (its variance is also 2) outputs y = 3. The formula gives (3 − 2)/2 = 0.5. Differentiating its log-probability, y ln μ − μ − ln y!, directly gives y/μ − 1 = 1.5 − 1 = 0.5. They agree.

In Python:

import math
# a Poisson unit: ln g = y ln μ − μ − ln y!, and its variance equals its mean
def ln_g(mu, y):
    return y * math.log(mu) - mu - math.lgamma(y + 1)
mu, y = 2.0, 3
# the proposition: (y − μ) / σ²
(y - mu) / mu  # → 0.5
# the slope of ln g in μ, measured numerically
h = 1e-6
round((ln_g(mu + h, y) - ln_g(mu - h, y)) / (2 * h), 6)  # → 0.5

Why it matters

Controlling the spread separately is controlling exploration separately: a unit can search widely in one place and narrowly in another. Continuous-action policies in robotics still use this Gaussian eligibility, usually learning log σ, just as the footnote suggests.

7 Compatibility with backpropagation · original

Everyday picture

REINFORCE on its own is like a team where every member experiments independently and watches the scoreboard, ignoring how their work feeds into each other's. Backpropagation is the opposite: a manager who knows exactly how each person's work flows into the final product. The paper shows how to use the manager wherever the flow is known, and the scoreboard only where there is genuine chance.

7.1 Networks using deterministic hidden units · original

Everyday picture

Put all the randomness at the end: the hidden layers compute ordinary, predictable functions, and only the output units flip coins. Randomness at the outputs is enough exploration, and everything before them can be trained with the chain rule.

Tiny example

One hidden unit computes h = v × x with x = 1 and v = 0.5, so h = 0.5. The output is a Bernoulli-logistic unit with weight u = 2, so s = 1 and p = 0.731 again. It outputs y = 1. The eligibility of the hidden weight v is ∂ln g/∂p × ∂p/∂v = (1/0.731) × (0.197 × 2 × 1) = 1.368 × 0.393 = 0.538, which is (y − p) × u × x = 0.269 × 2.

In words: “because the output units flip their coins independently, the log-probability of the whole output is a sum over output units; so any weight's eligibility is, for each output unit, the Bernoulli eligibility (y − p)/(p(1 − p)) injected at that unit, carried back to the weight by backpropagation.”

With the numbers: one output unit: 1.368 × 0.393 = 0.538.

In Python:

import math
x, v, u, y = 1.0, 0.5, 2.0, 1
h = v * x
p = 1 / (1 + math.exp(-u * h))
# ∂ ln g_k / ∂p_k, injected just after the output's squash
inject = (y - p) / (p * (1 - p))
# ∂p_k / ∂v by the chain rule: p(1 − p) × u × x
dp_dv = p * (1 - p) * u * x
round(inject, 3), round(dp_dv, 3)  # → (1.368, 0.393)
round(inject * dp_dv, 3)  # → 0.538

Why it matters

This is how every modern policy is trained: a deep deterministic network computes logits, only the final draw is random, and one backward pass from “(one-hot − probabilities) × advantage” reaches every weight. The paper also notes the result extends to any mix of random and deterministic units: REINFORCE at each random unit, backpropagation everywhere else.

7.2 Backpropagating through random number generators · original

“Suppose instead that it were possible to somehow ‘backpropagate through a random number generator.’”Williams (1992), §7.2

Everyday picture

A coin flip has no slope: nudging the coin's bias a little does not nudge a heads into a slightly-more heads. But a bell-curve draw can be rewritten as “the mean, plus the spread times a fixed random number”. With the random number held still, the output moves smoothly with the mean and the spread, so ordinary backpropagation can pass through it.

Tiny example

Mean μ = 1, spread σ = 0.5, and the random number z = 0.8 from a standard bell curve. The output is y = 1 + 0.5 × 0.8 = 1.4. Nudge μ up by 0.01 with z held still: y rises by exactly 0.01. Nudge σ up by 0.01: y rises by 0.008, that is, by z.

Reading it: both routes want the same thing, how the average score changes as μ changes. The top route treats the draw as a black box and uses REINFORCE: it needs only the value of the score, which is why it works for coin flips and for graders with no slope at all. The bottom route moves the randomness to the side (the noise z) and makes the rest a smooth function, so it can use the score's slope directly. The shared J box lights up in both routes: the difference is not the score but how much each route asks of it.

The math

In words: “write the draw as mean plus spread times a standard random number; then the output's slope with respect to the mean is 1, and with respect to the spread it is the random number itself.”

With the numbers: y = 1 + 0.5 × 0.8 = 1.4; ∂y/∂σ = 0.8 = (1.4 − 1)/0.5.

In Python:

mu, sigma, z = 1.0, 0.5, 0.8
# y = μ + σz
y = mu + sigma * z
round(y, 2)  # → 1.4
# nudge μ, then σ, by 0.01 with z held still
round((mu + 0.01 + sigma * z) - y, 4), round((mu + (sigma + 0.01) * z) - y, 4)  # → (0.01, 0.008)
# ∂y/∂σ = z = (y − μ)/σ
round((y - mu) / sigma, 2)  # → 0.8

Worked comparison: why the second route is quieter

This is our example, not the paper's. Take the score J(y) = y², so the true slope of its average with respect to μ is 2μ = 2. Both routes estimate 2 on average, but one draw at a time they wobble very differently.

In words: “the REINFORCE estimate multiplies the score by the mean's eligibility; the backprop estimate multiplies the score's slope by how the output moves with the mean.”

With the numbers: with μ = 1 and σ = 0.5, both average 2. The REINFORCE estimate's variance is 21.75; the backprop estimate's is 1.0, about 22 times smaller.

In Python:

mu, sigma = 1.0, 0.5
# moments of a standard normal z: E[z²] = 1, E[z⁴] = 3, E[z⁶] = 15 (odd ones are 0)
Ez2, Ez4, Ez6 = 1, 3, 15
# REINFORCE: J(y)(y − μ)/σ² with y = μ + σz is (a z + b z² + c z³)/σ
a, b, c = mu**2, 2 * mu * sigma, sigma**2
second_moment = (a * a * Ez2 + b * b * Ez4 + c * c * Ez6 + 2 * a * c * Ez4) / sigma**2
# variance = E[ĝ²] − (true slope 2μ)²
second_moment - (2 * mu) ** 2  # → 21.75
# backprop: J′(y) = 2y = 2μ + 2σz, whose variance is (2σ)² E[z²]
(2 * sigma) ** 2 * Ez2  # → 1.0

Why it matters

Two decades later this became the reparameterization trick that makes variational autoencoders trainable (the reparameterize function in the autoencoders lesson). The split in this figure is still the basic choice: the backprop route is far quieter when the score has a slope, and REINFORCE is the only option when it doesn't, as with a language model's discrete tokens scored by a grader.

8 Algorithm performance and other issues · original

Everyday picture

Knowing that a compass points north on average does not tell you whether you will reach the pole, or how long it takes. Theorem 1 is the compass. Section 8 is the honest travel report: what simulations showed, where the learners get stuck, and which design choices the theory leaves open.

8.1 Convergence properties · original

Everyday picture

A drunk walker on a narrow bridge drifts, on average, towards the far end. But each step is random, and a few bad steps near the start can send them over the near edge. Drifting the right way on average does not guarantee arriving.

What the paper reports

• No general convergence theory exists; simulations are the main evidence. If a REINFORCE learner converges, one expects a local maximum, but it need not converge at all.
• REINFORCE with reinforcement comparison beat every other algorithm in Sutton's 1984 study of single units.
• The two-action L_R−I automaton converges to always choosing one action, and, even though its average motion always favours the better action, it has a nonzero chance of settling on the worse one: the biased random walk on the bridge. The explorer in 8.3 shows this happening.
• REINFORCE is “generally very slow even when it succeeds”, and the episodic version especially slow, because it spreads credit uniformly over every past step.
• Williams and Peng (1991) found that REINFORCE variants tend to converge to local optima, as any gradient-following method might; one variant that added an entropy term to the reinforcement signal helped certain networks on tasks where some hierarchical organisation during the search was useful.

Why it matters

Every item on this list is still true of plain policy gradients, and each has a modern repair: baselines and critics for the noise, clipped steps (PPO) for stability, entropy bonuses to keep exploring, and, for language models, starting from a pretrained model that is already good enough that the right answers get sampled.

8.2 Gaussian unit search behavior · original

Everyday picture

Searching for the top of a hill in the dark with a flashlight whose beam you can widen or narrow. Find a better spot close to where you stand: narrow the beam and settle in. Find a better spot far away: widen it. Find worse spots close by: widen, you are probably not at the top.

Tiny example

With μ = 0, σ = 1 and a sample that did better than usual (r − b > 0): a draw at y = 0.5 moves μ towards 0.5 and shrinks σ (eligibility −0.75); a draw at y = 2 moves μ towards 2 and grows σ (eligibility +3). A worse-than-usual draw reverses both.

Try it: hover the chart, or tab to it and use the arrow keys, to read both eligibilities at any draw. Watch where the dashed curve crosses zero.

Reading it: the x-axis is where the draw y landed, for a unit with μ = 0 and σ = 1, so it also counts standard deviations from the mean. The solid line is the mean's eligibility, (y − μ)/σ²: a straight line through zero, so μ always moves towards a good draw, harder the further away it was. The dashed line is the spread's eligibility, ((y − μ)² − σ²)/σ³: a U that is negative between −1 and +1 and positive outside. Multiplied by a positive r − b, a good draw inside one standard deviation narrows the search and a good draw outside widens it; a negative r − b flips the sign. Since draws land inside one standard deviation about twice as often as outside, a unit sitting on a hilltop, where most nearby draws are worse, keeps narrowing until it settles, which is the behaviour the paper describes.

What the paper found

Simulations with and without noise in the reward confirmed this: σ narrows onto a local peak. On a very flat peak σ can shrink until sampling worse values becomes vanishingly rare, and then stop changing. And if rewards are never negative and no baseline is used, σ can collapse to 0 before μ reaches any peak: the continuous cousin of the lock-in in 8.1. Gullapalli's alternative sets σ from the reward instead (wide when doing badly, narrow when doing well), and Schmidhuber and Huber reported Gaussian output units trained by backpropagating through the random number generator of 7.2.

Why it matters

This is automatic exploration control: the spread shrinks where confidence is earned and widens where it is not, driven by the same one-line rule. Modern continuous-control methods still learn a spread per action this way.

8.3 Choice of reinforcement baseline · original

“The use of an adaptive reinforcement baseline incorporating something like the reinforcement comparison strategy can greatly enhance convergence speed, and, in some cases, can lead to a big difference in qualitative behavior as well.”Williams (1992), §8.3

Everyday picture

If every dish you cook gets at least four stars, “four stars” sounds like praise, and you might keep cooking the mediocre dish you tried first. Only compared with your usual score does a four-star dish reveal itself as your worst.

Tiny example: the paper's single-unit case

A unit with only a bias weight chooses between two outputs. Output 1 always pays c + 1 and output 0 always pays c, so output 1 is better by 1 whatever c is. With no baseline and c = 4, a trial that happens to produce 0 still earns 4, and the update pushes firmly towards 0. With a running-average baseline, the average settles between 4 and 5, output 0 always scores below it, and every trial pushes towards output 1.

Try it: drag the learning rate. Watch the solid line (no baseline) against the dashed one (reinforcement comparison) as every reward is raised by the amount on the x-axis.

Reading it: each point summarises 200 simulated runs of 300 trials, all starting at p = 0.5; the runs are seeded, so the chart is the same every time. The x-axis is the offset c added to both rewards (at c = 0 the rewards are 1 and 0; at c = 4, 5 and 4). The y-axis is the share of runs that, after 300 trials, still prefer the worse output. The solid line, REINFORCE with no baseline, sits at zero while c is small (at c = 0 the worse output earns nothing, so it is never pushed up) and then rises: at the starting rate of 0.5, nearly a quarter of the runs (23.5%) prefer the worse output at c = 4, and a third at c = 6. The dashed line, with a running-average baseline (γ = 0.1, started at the first reward), stays at zero everywhere. Raise α and the solid line climbs faster: bigger steps make an early unlucky streak harder to escape. Both learners share Theorem 1's guarantee; only their noise differs, and noise is what locks the solid learner in.

Beyond the average reward

Any baseline between the two rewards fixes this example, so the theory does not single one out. One principled choice is the baseline that makes the updates least noisy (considered by Williams in 1986 and studied by Dayan in 1990); it turns out not to be the mean reward but something harder to estimate, and Dayan's simulations suggested only a slight speed-up over the mean.

Why it matters

This is why every practical policy-gradient method uses a baseline, and why the lesson's sampled_gradient_variance measures the noise it removes (the lesson's figure shows the same lock-in on a three-armed bandit with rewards offset by 5). GRPO's group mean is a baseline in exactly this sense.

8.4 Alternate forms for eligibility · original

Everyday picture

The eligibility measures surprise: what the unit did minus what it was expected to do. REINFORCE uses the unit's own probability as the expectation. An alternative uses what the unit has actually been doing lately, a running average of its outputs.

Tiny example

A bias-only unit has recently output 1 about 60% of the time (ȳ = 0.6). It outputs 1 and the reward beats its average by 0.5. With α = 0.1 the weight changes by 0.1 × 0.5 × (1 − 0.6) = 0.02. Then ȳ moves to 0.2 × 1 + 0.8 × 0.6 = 0.68 (γ = 0.2).

In words: “replace the unit's probability in the eligibility with a running average of its recent outputs, updated the same way as the reward average.”

With the numbers: Δw = 0.1 × 0.5 × (1 − 0.6) = 0.02; ȳ becomes 0.68.

In Python:

alpha, gamma = 0.1, 0.2
r_minus_r_bar, y, y_bar = 0.5, 1, 0.6
# Δw = α (r − r̄)(y − ȳ)
round(alpha * r_minus_r_bar * (y - y_bar), 3)  # → 0.02
# ȳ(t) = γ y(t − 1) + (1 − γ) ȳ(t − 1)
round(gamma * y + (1 - gamma) * y_bar, 2)  # → 0.68

Studied by Sutton and others only on tasks with no input (the paper says it is unclear how to extend it to the associative case), this variant was found to converge faster and more reliably than REINFORCE. It is not a REINFORCE algorithm, so Theorem 1 does not cover it; the paper offers a possible justification in 8.5 but says it has not been fully analysed.

Why it matters

It shows the two factors of the rule can be tuned separately, which later work did extensively: centring the reward is a baseline, and centring the eligibility is a close relative of the tricks that keep gradient estimates small and steady.

8.5 Use of other local gradient estimates · original

Everyday picture

You can learn which route to work is fastest either by trying routes and remembering how you felt (REINFORCE), or by building a map with travel times and planning on it (a model). The map costs effort but can answer questions you have never tried.

The paper's point

REINFORCE is “simple” in three senses: the rules are short, easy to derive for almost any random unit, and they climb the gradient without ever estimating it or storing what an estimate would need. The alternatives are model-based: learn a model of how the reward depends on the network's input and output, globally (Munro's backpropagation through a model) or locally at each unit (Thathachar and Sastry's automata that track each action's average reward, and, in a per-state sense, Q-learning). An interesting local option: at each unit, regress the reward on the unit's output; the paper suspects the ȳ variant of 8.4 is related.

Why it matters

This fork runs through all of reinforcement learning: model-free policy gradients on one side, learned value functions and world models on the other. A learned reward model in RLHF is a model of exactly this kind, and its flaws are what reward hacking exploits.

9 Conclusion · original

“The main disadvantages are the lack of a general convergence theory applicable to this class of algorithms and, as with all gradient algorithms, an apparent susceptibility to convergence to false optima.”Williams (1992), §9

Everyday picture

The paper hands over a recipe, not a finished dish: a way to derive a sensible learning rule for almost any random unit, which plugs into backpropagation because it is a gradient method.

Why it matters

The recipe outlived its setting. “Connectionist networks of stochastic units” became “neural network policies”, the reward broadcast to every unit became the reward for a whole generated answer, and the baseline became a critic, then a group average. The disadvantages it names, noise and local optima, are the problems every successor was built to fix.

Appendices A and B: why it works · original

Everyday picture

Imagine pushing up on every option of a menu at once. The chances must still add up to 1, so if you raise one option's chance, others must fall. Push them all “up” together and nothing can move. That single fact is why a baseline never biases the average update.

Tiny example

For our unit, raising w₁ a little raises g(1) at the rate p(1 − p) × x₁ = 0.393 and lowers g(0) at exactly the same rate, −0.393. Their sum is 0. So the baseline's contribution to the average update, b × (0.393 − 0.393), is 0 whatever b is.

In words: “the chances of all outputs add up to 1 whatever the weights are, so their slopes add up to 0.” This is the paper's Fact 2.

With the numbers: 0.393 + (−0.393) = 0.

In Python:

import math
x1 = 2
p = 1 / (1 + math.exp(-1))
# ∂g(1)/∂w_1 = ∂p/∂w_1 and ∂g(0)/∂w_1 = ∂(1 − p)/∂w_1
dg1 = p * (1 - p) * x1
dg0 = -p * (1 - p) * x1
round(dg1, 3), round(dg0, 3)  # → (0.393, -0.393)
# Σ_ξ ∂g(ξ)/∂w_1
dg1 + dg0  # → 0.0

The proof in four steps

1. Fact 1. The expected reward's slope is Σ_ξ E{r | y = ξ} × ∂g(ξ)/∂w: once the output is fixed, the weight has no further influence on the reward.
2. Lemma 1. Write the eligibility as (1/g) ∂g/∂w and average the update over outputs: the g's cancel, the reward part becomes α times Fact 1, and the baseline part is b × Σ ∂g/∂w = 0 by Fact 2 (above). So for each fixed input, the average update is α times the slope.
3. Lemma 2. Average over inputs as well. The unit's input does not depend on its own weights (the weight sits downstream), so the averages combine: the average update is α times the slope of E{r | W} (Fact 3).
4. Theorem 1. The inner product of the average update with the gradient is Σ α_ij × (slope)², a sum of non-negative terms. Theorem 2 repeats the argument on the unfolded network, where each weight's slope is the sum of its copies' slopes (Fact 4). Appendix B proves Proposition 1 by the same move: Σ g ∂ln g/∂μ = 0 and Σ (y − μ) g ∂ln g/∂μ = 1 pin down the eligibility as (y − μ)/σ².

Why it matters

Every modern derivation of the policy gradient, including the one in the reinforcement learning lesson, is this argument: ∇π = π ∇log π turns a sum weighted by probabilities into an average over samples, and probabilities summing to 1 makes the baseline free.

What changed since 1992

Glossary

Every term with hover guidance on this page, in one place.