Vol. XIX · Reinforcement Learning for Reasoning Plate 2 of 12policy gradient, REINFORCE, log-derivative trick, baseline, variance reduction, advantage, RLOOLE

The Policy Gradient.

Make rewarded samples more likely. Subtract the average reward first, and the same push is far less noisy.

The gradient of expected reward cannot be computed by back-propagating through sampling, but Williams’ REINFORCE (1992) gives an estimate that can: ∇J = E[R(y) ∇ log π(y)]. Sample responses, and push up the log-probability of each in proportion to its reward. The estimate is unbiased — on average it points the right way — but each batch’s estimate scatters widely around that average, because a reward of 1 pushes up every sampled response regardless of whether it was better than usual.

Subtracting a baseline b that does not depend on the sampled response leaves the expectation unchanged, since E[∇ log π] = 0, but reduces the scatter: the push becomes R − b, the advantage — positive for responses better than usual, negative for worse. A good baseline is the expected reward itself. The workshop isolates the effect on one prompt with eight candidate answers, one right, measuring the spread of the gradient estimate over 400 batches and the average learning curve over 40 runs.

Below: left, the probability of the right answer over training, averaged over 40 runs, with and without a baseline. Right, the spread of one batch’s gradient estimate around its mean.

What you will learn

Derive the REINFORCE estimator.
Explain why it is unbiased but noisy.
Show that a baseline reduces variance without bias.
Define the advantage.

Workshop

A softmax policy over eight answers, one right (reward 1); initial probability of the right answer as chosen. Each batch: n samples, the REINFORCE estimate with no baseline or with the batch-mean reward subtracted. Spread: standard deviation of the gradient on the right answer’s logit over 400 batches at the initial policy (its exact value is p(1 − p)). Curves: step size 1, 40 steps, averaged over 40 runs.

Unbiased, noisy, and less noisy

When the right answer starts at probability 0.2, the true gradient on its logit is p(1 − p) = 0.160. Averaged over 400 batches of 8, REINFORCE without a baseline estimates 0.155 — unbiased — but a single batch’s estimate scatters by 0.107. Subtracting the batch’s mean reward cuts the scatter to 0.076, 29% less, while the average moves to 0.144: the batch mean includes the sample being scored, which biases it by a factor (n − 1)/n — the reason the leave-one-out baseline (RLOO), which averages the other samples only, is preferred.

Variance matters because training follows single batches, not averages. Larger batches reduce it too: with 32 samples the spread without a baseline is 0.056. And it matters most when success is rare: at an initial probability of 0.05, 0.068 without a baseline against 0.065 with one. PPO adds a learned value function as the baseline (plate XIX.4); GRPO uses the mean reward of a group of answers to the same prompt (plate XIX.5). All are this one idea.

The log-derivative identity ∇π = π ∇ log π is what turns the gradient of an expectation into an expectation of something computable — the same trick behind every policy-gradient method.

Terms

REINFORCE: The policy-gradient estimator E[R ∇ log π].
Baseline: A quantity subtracted from the reward that does not depend on the sampled action.
Advantage: Reward minus baseline: how much better than usual a sample was.
Variance: How much a single estimate scatters around its expectation.

REINFORCE pushes up log π(y) in proportion to R(y) − b; a baseline leaves the gradient unbiased and makes it far less noisy.

Sources

Williams, “Simple Statistical Gradient-Following Algorithms for Connectionist Reinforcement Learning”, Machine Learning 8, 1992.
Ahmadian et al., “Back to Basics: Revisiting REINFORCE Style Optimization for Learning from Human Feedback in LLMs”, ACL 2024 (RLOO).