LLM & VLM courseBlog
64Track 4: Post-training and RL · session 12 of 25

Policy gradient and REINFORCE

How do you train a language model from a score instead of from a correct example? The answer is the policy gradient: push up the log-probability of answers that scored well, push down the ones that scored badly. This session derives it with the log-derivative trick, builds REINFORCE for whole generated answers, and shows why baselines and advantages are needed to make it work in practice.

Time: 2.5 to 3 hours (reading 2 hours, exercises 45 minutes)Level: BeginnerBefore this: Sessions 3, 4 and 63

What you will learn

  • Why we cannot backpropagate through sampling and a reward, and what the policy gradient does instead
  • The log-derivative trick, step by step: the gradient of an expected reward is an expected reward times a gradient of a log-probability
  • REINFORCE for a whole generated answer: one reward, many tokens, one surrogate loss
  • Why the estimate is so noisy, and how a reward shift can make the noise more than 400 times larger
  • Baselines: why subtracting them adds no bias, and which baseline gives the lowest variance
  • The advantage, and the group baselines used for LLMs: mean, leave-one-out (RLOO) and GRPO normalization

Why this matters

In session 63 we described text generation as a game: the language model is a policy, each next token is an action, and at the end of the answer a reward says how good the answer was. This session answers the next question: how do we change the weights so that the reward goes up?

In supervised fine-tuning (session 54) we had a correct answer to copy, so the loss was a simple cross-entropy. Now we only have a score: “this answer to the math problem is right (1)” or “wrong (0)”, or a number from a reward model. The score comes from a checker or another network, not from a formula we can differentiate. And the answer itself was sampled: the model drew random tokens. There is no gradient through a random draw.

The policy gradient solves both problems with one identity, the log-derivative trick. The result is surprisingly simple: sample answers, score them, and do weighted maximum likelihood on your own samples, with a large weight for good answers and a negative weight for bad ones. The oldest version of this idea is REINFORCE (Williams, 1992). [Certain] Every RL method for LLMs that you will meet later in this track is built on it: PPO (session 66), the RLHF pipeline of InstructGPT, RLOO, ReMax, and GRPO, the method used to train DeepSeek’s reasoning models (session 70).

The plan: first the goal (an expected reward), then the trick that gives its gradient, then REINFORCE for a whole generated answer. Then we see the big weakness, variance, and fix it with baselines and the advantage. The next session, session 65, replaces the simple baselines here with a learned critic.

The goal: maximize the expected reward

Write \(\pi_\theta(y \mid x)\) for the probability that the model with weights \(\theta\) writes the answer \(y\) to the prompt \(x\). The answer \(y = (y_1, \dots, y_T)\) is a sequence of tokens. A reward function \(R(x, y)\) gives one number for the finished answer. We want weights that make good answers likely. Because answers are random, “good on average” is the right goal:

\[ J(\theta) = \E_{x \sim \mathcal{D}}\ \E_{y \sim \pi_\theta(\cdot \mid x)} \big[ R(x, y) \big] = \E_{x \sim \mathcal{D}} \sum_{y} \pi_\theta(y \mid x)\, R(x, y) \tag{64.1} \]
Read the symbols
\(J(\theta)\)
the objective: the average reward the model gets; we want to make it larger (gradient ascent)
\(\mathcal{D}\)
the set of prompts we train on
\(\pi_\theta(y \mid x)\)
the policy: the language model’s probability of the whole answer \(y\)
\(R(x, y)\)
the reward of the finished answer: a correctness check, a unit test, or a reward model score
\(\sum_y\)
a sum over all possible answers. There are astronomically many, so we can never compute it exactly

Look at where \(\theta\) appears. It is not inside \(R\): the reward does not care how the answer was produced, it only reads the text. It is inside the probabilities \(\pi_\theta(y \mid x)\). So the gradient must flow through the probabilities of the answers, and never through the reward. This is why the reward can be any black box: a Python checker, a compiler, a human click.

The log-derivative trick

We want \(\nabla_\theta J\). Take one prompt and drop \(x\) to keep the notation short. The gradient of a sum is the sum of gradients, and \(R\) does not depend on \(\theta\):

\[ \nabla_\theta J = \sum_y R(y)\, \nabla_\theta \pi_\theta(y). \]

This is correct but useless as it stands: it is a sum over all answers, not an average we can estimate by sampling. The trick is one line of calculus. Since \(\nabla \log f = \nabla f / f\), we can write

\[ \nabla_\theta \pi_\theta(y) = \pi_\theta(y)\, \nabla_\theta \log \pi_\theta(y) \tag{64.2} \]

Put this back into the sum. The factor \(\pi_\theta(y)\) appears again, and a sum weighted by \(\pi_\theta(y)\) is an expectation:

\[ \nabla_\theta J(\theta) = \sum_y \pi_\theta(y)\, R(y)\, \nabla_\theta \log \pi_\theta(y) = \E_{y \sim \pi_\theta} \Big[ R(y)\, \nabla_\theta \log \pi_\theta(y) \Big] \tag{64.3} \]
Read the symbols
\(\nabla_\theta \log \pi_\theta(y)\)
the score function: the direction in weight space that makes the answer \(y\) more likely. It is the same gradient that SFT computes when \(y\) is the target
\(R(y)\)
a plain number that scales that direction: large reward, big push up; zero reward, no push; negative reward, push down
\(\E_{y \sim \pi_\theta}\)
an average over answers sampled from the current model, so we can estimate it with a few samples

This is the whole idea. To estimate the gradient, sample answers from the model, compute the log-probability gradient of each one (ordinary backprop), multiply by its reward, and average. No gradient of the reward is needed, and no gradient through the sampling either. The same identity is also called the score-function estimator or the likelihood-ratio gradient. Its general form for many-step problems is the policy gradient theorem (Sutton et al., 1999). [Certain]

What the score looks like for a softmax

A language model’s last layer is a softmax over logits \(\mathbf{z}\). For one choice \(a\) with \(\pi = \softmax(\mathbf{z})\), the gradient of \(\log \pi_a\) with respect to the logits is very simple (you met it as the cross-entropy gradient in session 3):

\[ \nabla_{\mathbf{z}} \log \pi_a = \mathbf{e}_a - \pi, \qquad \text{so} \qquad \nabla_{\mathbf{z}} J = \E_{a \sim \pi}\big[ R(a)\,(\mathbf{e}_a - \pi) \big] \tag{64.4} \]

Here \(\mathbf{e}_a\) is the one-hot vector of the chosen answer. In words: raise the logit of the chosen answer by \((1 - \pi_a)\), lower every other logit by its probability, and scale all of it by the reward.

Worked example: the trick on three answers

A prompt has three possible answers A, B, C with probabilities \(\pi = (0.2, 0.5, 0.3)\). Only A is correct: \(R = (1, 0, 0)\). So the expected reward is \(J = 0.2\).

Exact gradient. For a softmax, \(\partial J / \partial z_j = \pi_j (R_j - J)\). This gives \((0.2 \times 0.8,\ 0.5 \times (-0.2),\ 0.3 \times (-0.2)) = (0.16, -0.10, -0.06)\): raise A, lower B and C.

The REINFORCE view. If we sample A, the score is \(\mathbf{e}_A - \pi = (0.8, -0.5, -0.3)\) and the reward is 1, so this sample’s estimate is \((0.8, -0.5, -0.3)\). If we sample B or C, the reward is 0, so the estimate is \((0, 0, 0)\). Average over the three cases with their probabilities: \(0.2 \times (0.8, -0.5, -0.3) = (0.16, -0.10, -0.06)\). Exactly the true gradient, as formula (64.3) promises.

But notice the cost: 80% of the samples give a gradient of zero, and the other 20% give a gradient five times larger than the mean. Each single estimate is far from the truth. This is the variance problem we fix later.

exact gradient \(\partial J / \partial \mathbf{z}\)REINFORCE estimate from \(N\) samples
Figure 1. The log-derivative trick as a Monte Carlo estimate. The policy is \(\pi = (0.2, 0.5, 0.3)\) over three answers and only answer A has reward 1. The grey bars are the exact gradient with respect to the three logits; the blue bars are the average of \(R(a)\,(\mathbf{e}_a - \pi)\) over \(N\) sampled answers.
How to read Figure 1

With \(N = 1\) the estimate is either \((0.8, -0.5, -0.3)\) or exactly zero; press “Draw new samples” a few times. As \(N\) grows, the blue bars settle on the grey ones: the estimator is unbiased, and its error shrinks like \(1/\sqrt{N}\). Now tick the baseline box. Wrong answers now give a gradient too, and the mean is still the same. On average over many sample sets the error is smaller (the per-sample variance drops from 0.157 to 0.103), although one particular sample set can still be unlucky. That is the topic of the baseline section.

Figure 2 turns the trick into a learning algorithm on the simplest RL problem, a multi-armed bandit: a machine with four arms A–D. Pulling arm \(a\) pays 1 with probability \(\mu_a = (0.2, 0.5, 0.8, 0.4)\) and 0 otherwise. The policy is a softmax over four logits, it starts uniform, and it does not know \(\mu\). Each iteration samples a batch of pulls, builds the estimate (64.4) from them, and takes one gradient step. One episode is one pull, so a bandit is exactly the answer-level view of an LLM: prompt in, one whole answer out, one score. The baseline switch is explained in the section on baselines below; leave it off for now.

Baseline
Algorithm in the figure: REINFORCE on a bandit
  1. \(\pi \leftarrow \softmax(\mathbf{z})\)
  2. sample \(a_1, \dots, a_B \sim \pi\); pull each arm: \(R_i \in \{0, 1\}\), plus the shift \(c\)
  3. for each \(i\): \(\mathbf{g}_i \leftarrow (R_i - b)\,(\mathbf{e}_{a_i} - \pi)\) // (64.4), (64.10)
  4. \(\mathbf{g} \leftarrow \frac{1}{B} \sum_i \mathbf{g}_i\)
  5. \(\mathbf{z} \leftarrow \mathbf{z} + \eta\, \mathbf{g}\) // gradient ascent
  6. if baseline on: \(b \leftarrow 0.9\, b + 0.1\, \bar R\) // else \(b = 0\)
Reward per iteration
batch meanmoving average (50)expected \(J\)best arm
Policy \(\pi\) over iterations
A (0.2)B (0.5)C (0.8)D (0.4)
Figure 2. REINFORCE learning live on a four-armed bandit. Each Step runs one highlighted line; the boxes show that line’s formula with the current numbers (\(\mathbf{e}_{a}\) is the one-hot vector of the pulled arm). The expected reward \(J = \sum_a \pi_a \mu_a + c\) is exact, computed from the current policy; the grey dots are what the algorithm actually sees. All random numbers come from a seeded generator.
How to read Figure 2

Step slowly through one iteration. In line 3 the pulled arm’s logit gets \(+(1 - \pi_a)\) times the reward and every other logit gets \(-\pi_j\) times the reward: with \(R = 0\) and no baseline, the sample changes nothing. Then press Play at Fast. The green line (arm C) climbs, and the expected reward approaches 0.8. Now set the reward shift \(c = 5\) and keep the baseline off: every pull now pushes its own arm up, even the bad ones, and the policy wanders; often it locks onto a wrong arm for a long time (try a few seeds). Turn the running-mean baseline on: \(b\) climbs toward the average reward, after which only “better or worse than usual” matters and learning looks like \(c = 0\) again. A larger batch \(B\) makes every step less noisy; a larger \(\eta\) makes it faster but more erratic.

REINFORCE for a whole generated answer

For a language model, an “action” in formula (64.3) is a whole answer of many tokens. The model writes it one token at a time, so its probability is a product, and its log-probability is a sum:

\[ \log \pi_\theta(y \mid x) = \sum_{t=1}^{T} \log \pi_\theta\big(y_t \mid x, y_{\lt t}\big) \tag{64.5} \]

This is the same sum of token log-probabilities that SFT uses. Each term comes from one softmax, at one position, with the prompt and the tokens written so far as context. Put it into (64.3) and replace the expectation by an average over \(N\) sampled answers \(y^{(1)}, \dots, y^{(N)}\):

\[ \hat{\mathbf{g}} = \frac{1}{N} \sum_{i=1}^{N} R\big(x, y^{(i)}\big) \sum_{t=1}^{T_i} \nabla_\theta \log \pi_\theta\big(y^{(i)}_t \mid x, y^{(i)}_{\lt t}\big) \tag{64.6} \]
Read the symbols
\(\hat{\mathbf{g}}\)
our estimate of \(\nabla_\theta J\); the hat means “estimated from samples”
\(y^{(i)}\)
the \(i\)-th answer sampled from the current model for the prompt \(x\)
\(T_i\)
the length of that answer in tokens, including the end-of-sequence token
\(R(x, y^{(i)})\)
one number for the whole answer, used as the weight of every token in it

In code nobody writes the gradient (64.6) by hand. We build a surrogate loss: a scalar whose ordinary gradient equals \(-\hat{\mathbf{g}}\). The rewards are constants (no gradient flows into them), so

\[ \mathcal{L}_{\text{PG}}(\theta) = -\frac{1}{N} \sum_{i=1}^{N} R\big(x, y^{(i)}\big)\, \log \pi_\theta\big(y^{(i)} \mid x\big) \tag{64.7} \]

Compare it with the SFT loss \(-\log \pi_\theta(y^{\ast} \mid x)\) for a human-written answer \(y^{\ast}\). REINFORCE is SFT on the model’s own samples, with each sample weighted by its reward. With rewards in \(\{0, 1\}\) it is exactly “SFT on the answers that passed the check”. This is why the method is also called reward-weighted maximum likelihood.

Algorithm 1: REINFORCE for a language model (no baseline yet)
  1. input: policy \(\pi_\theta\), prompts \(\mathcal{D}\), reward function \(R\), samples per prompt \(N\), learning rate \(\eta\)
  2. repeat:
  3.   pick a batch of prompts \(x\) from \(\mathcal{D}\)
  4.   for each \(x\): sample \(N\) answers \(y^{(i)} \sim \pi_\theta(\cdot \mid x)\) token by token // no gradient while sampling
  5.   score each answer: \(r_i \leftarrow R(x, y^{(i)})\) // a black box; treat as a constant
  6.   run one forward pass on prompt + answer and sum the token log-probabilities, formula (64.5)
  7.   \(\mathcal{L} \leftarrow -\frac{1}{N}\sum_i r_i \log \pi_\theta(y^{(i)} \mid x)\) // formula (64.7)
  8.   \(\theta \leftarrow \theta - \eta \nabla_\theta \mathcal{L}\) // ascent on \(J\)
  9.   throw the samples away: they came from the old \(\theta\) // on-policy

The last line matters. Formula (64.3) is an expectation under the current policy. After one update, the old samples come from a slightly different policy, and reusing them gives a biased gradient. PPO (session 66) adds an importance ratio and clipping so that each batch can be used for several updates.

Figure 3 walks through one sampled answer. Watch how the single reward becomes a weight on every token.

Figure 3. REINFORCE on one sampled answer to “Q: 2 + 3 = ?”. Each box is a token with its probability \(\pi(y_t \mid \dots)\) under the model. At the end the reward arrives, and every token gets the same weight \(A = R - b\). The bar under each token is the gradient on that token’s own logit, \(A\,(1 - \pi_t)\).
How to read Figure 3

Step through the sampling, then the reward, then the update. With the correct answer and no baseline, every token is pushed up, even “The” and “answer”, which had nothing to do with being right. With the wrong answer and no baseline, nothing happens at all: a reward of 0 gives zero gradient, so the model does not learn to avoid the mistake. Tick the baseline: now the wrong answer is pushed down, and the right one is pushed up a little less. Tokens the model was unsure about (small \(\pi_t\)) get the largest push.

Worked example: one answer, four tokens

The model writes “The answer is 5” with token probabilities \(0.9, 0.6, 0.8, 0.5\). The answer’s probability is \(0.9 \times 0.6 \times 0.8 \times 0.5 = 0.216\), and its log-probability is \(-0.105 - 0.511 - 0.223 - 0.693 = -1.532\) (formula 64.5).

The answer is correct, \(R = 1\). The gradient on each chosen token’s logit is \(R\,(1 - \pi_t) = 0.1, 0.4, 0.2, 0.5\). The uncertain final token “5” gets the biggest push, and the confident “The” the smallest.

Now suppose this answer came from a group of 8 samples where 2 were correct, and we subtract the group mean \(b = 0.25\). The weight becomes \(A = 0.75\) and the pushes become \(0.075, 0.3, 0.15, 0.375\). A wrong answer with the same probabilities except a final “6” at 0.3 gets \(A = -0.25\) and pushes \(-0.025, -0.1, -0.05, -0.175\): it is now made less likely, which plain REINFORCE with 0/1 rewards never does.

Credit assignment, and the reward-to-go

Every token of an answer gets the same weight. The model cannot see which token made the answer right or wrong: that must be learned from many samples, where good tokens appear more often in good answers. This is the credit assignment problem, and it is one big reason for the noise.

One free improvement comes from causality: an action at step \(t\) cannot change rewards that came before it. If rewards \(r_{t'}\) arrive at several steps, each token only needs the rewards after it, the reward-to-go:

\[ \nabla_\theta J = \E\Big[ \sum_{t=1}^{T} \nabla_\theta \log \pi_\theta(y_t \mid s_t)\ \hat{G}_t \Big], \qquad \hat{G}_t = \sum_{t'=t}^{T} r_{t'} \tag{64.8} \]

Here \(s_t = (x, y_{\lt t})\) is the state: the prompt and the text so far. The past rewards that we dropped have expectation zero in the gradient, so this is still unbiased, with less noise. For an LLM with one reward at the end, \(\hat{G}_t = R\) for every token, and (64.8) is the same as (64.6). It starts to matter when there are rewards along the way, for example a per-token KL penalty that keeps the model close to its SFT starting point (used in RLHF, session 67), or rewards for each step of a solution (session 73). LLM work usually uses no discount, \(\gamma = 1\). [Likely]

Why REINFORCE is so noisy

The estimator (64.6) is unbiased: on average it points in the right direction. But one batch can point almost anywhere. Three things make the variance large for LLMs:

  • Sampling. Each answer is one random draw from a huge space. Two runs of the same prompt can give very different answers and rewards.
  • One reward for hundreds of tokens. The whole sum of token scores is multiplied by one number, so the noise of every token adds up. Long reasoning answers have thousands of tokens.
  • The reward’s offset. If all rewards are large and positive, every sample is pushed up, good and bad alike. Only the small differences between the pushes carry the signal; the large common part is pure noise.

The third point is surprising, so let us measure it. Shift every reward by a constant \(c\): \(R'(y) = R(y) + c\). The expected gradient does not change, because \(\E[c\, \nabla \log \pi] = c \cdot 0 = 0\) (we prove this in the next section). But the variance can change enormously.

Worked example: how a constant ruins the estimate

Take the three-answer problem again: \(\pi = (0.2, 0.5, 0.3)\), \(R = (1, 0, 0)\). For a single sample, the estimate \(R(a)(\mathbf{e}_a - \pi)\) has mean \((0.16, -0.10, -0.06)\) and total variance (the sum of the variances of the three components) \(0.1568\).

Now add \(c = 10\) to every reward, so the rewards are \((11, 10, 10)\). The mean is still \((0.16, -0.10, -0.06)\), but the total variance is \(66.08\): about 421 times larger. You would need about 421 times more samples for the same accuracy. Figure 4 lets you try any shift.

This is why reward scale and centering are never details in RL for LLMs. A reward model that outputs scores around +5 for every answer would make plain REINFORCE nearly useless. The fix is to subtract something.

Baselines that add no bias

A baseline \(b\) is a number we subtract from the reward before using it as a weight. The key fact: the score function has mean zero. The probabilities sum to 1 for every \(\theta\), so

\[ \E_{y \sim \pi_\theta}\big[ \nabla_\theta \log \pi_\theta(y) \big] = \sum_y \pi_\theta(y)\, \frac{\nabla_\theta \pi_\theta(y)}{\pi_\theta(y)} = \nabla_\theta \sum_y \pi_\theta(y) = \nabla_\theta 1 = 0 \tag{64.9} \]

So for any \(b\) that does not depend on the sampled answer \(y\), subtracting it changes nothing on average:

\[ \E_{y \sim \pi_\theta}\big[ (R(y) - b)\, \nabla_\theta \log \pi_\theta(y) \big] = \nabla_\theta J(\theta) - b \cdot 0 = \nabla_\theta J(\theta) \tag{64.10} \]

The baseline may depend on the prompt \(x\) (or the state \(s_t\)), on the weights, on other samples, but not on the answer whose gradient it multiplies. If it does, (64.9) no longer applies and the gradient becomes biased.

Which baseline is best?

Every valid baseline keeps the mean, but they reduce the variance by different amounts. Minimizing the total variance of \((R - b)\,\mathbf{s}\), with \(\mathbf{s} = \nabla_\theta \log \pi_\theta(y)\), over \(b\) is a one-variable quadratic problem. Its solution is (Greensmith et al., 2004) [Certain]:

\[ b^{\ast} = \frac{\E\big[ R(y)\, \lVert \mathbf{s}(y) \rVert^2 \big]}{\E\big[ \lVert \mathbf{s}(y) \rVert^2 \big]} \tag{64.11} \]

It is the average reward, weighted by how large each answer’s score vector is. In practice nobody computes it: the plain average reward \(b = \E[R] = J\) is almost as good and easy to estimate. That average, for the current prompt, is exactly the state value \(V(x)\) of the next session.

Worked example: three baselines on the same problem

Same three answers, \(\pi = (0.2, 0.5, 0.3)\), \(R = (1, 0, 0)\). The squared lengths of the score vectors \(\mathbf{e}_a - \pi\) are \(0.98, 0.38, 0.78\).

  • No baseline, \(b = 0\): total variance \(0.1568\).
  • Mean reward, \(b = J = 0.2\): total variance \(0.1032\), a 34% reduction.
  • Optimal, \(b^{\ast} = (0.2 \times 1 \times 0.98) / (0.2 \times 0.98 + 0.5 \times 0.38 + 0.3 \times 0.78) = 0.196 / 0.62 = 0.316\): total variance \(0.0948\).
  • A bad baseline, \(b = 1\): total variance \(0.3848\). Too large a baseline is worse than none.

With the reward shift \(c = 10\) from before, the mean baseline \(b = 10.2\) brings the variance from \(66.08\) back down to \(0.1032\). A baseline makes the method insensitive to the reward’s offset.

Figure 4. Exact variance of the single-sample REINFORCE estimate \((R(a) + c - b)(\mathbf{e}_a - \pi)\) for the three-answer problem. The curve is the total variance as a function of the baseline \(b\), drawn around the current rewards. The mean of the estimate never changes.
How to read Figure 4

The curve is a parabola in \(b\). Its lowest point is the optimal baseline \(b^{\ast}\) of formula (64.11) (green dot); the mean reward (orange tick) is close to it. Move \(c\) to 10 with no baseline: the variance at \(b = 0\) goes off the chart. Press “Set \(b\) to mean reward”: it returns to 0.1032, the same value as with \(c = 0\). The readout always shows the mean gradient, which stays \((0.160, -0.100, -0.060)\) for every \(b\) and \(c\): the baseline adds no bias.

Figure 5 makes the variance visible during learning. Two copies of the same policy learn on the bandit of Figure 2, with one pull per step and the reward shift \(c\). Run A uses no baseline. Run B subtracts a running mean \(b\). They use the same random numbers, so the only difference is the baseline. Line 7 computes the exact variance of each run’s one-sample estimate at its current policy, from the formula in the second box (the expectation over the arm and over the 0/1 payout); the dashed lines measure the same thing from the samples actually drawn.

Algorithm in the figure: two runs, one difference
  1. each run: \(\pi \leftarrow \softmax(\mathbf{z})\) // each run has its own \(\mathbf{z}\)
  2. each run: sample \(a \sim \pi\), pull it, get \(R\) // same random numbers
  3. run A: \(\mathbf{g} \leftarrow R\, (\mathbf{e}_a - \pi)\) // no baseline
  4. run B: \(\mathbf{g} \leftarrow (R - b)(\mathbf{e}_a - \pi)\) // (64.10)
  5. each run: \(\mathbf{z} \leftarrow \mathbf{z} + \eta\, \mathbf{g}\)
  6. run B: \(b \leftarrow 0.9\, b + 0.1\, R\)
  7. each run: \(\operatorname{Var}[\mathbf{g}] = \E\lVert \mathbf{g} \rVert^2 - \lVert \E\, \mathbf{g} \rVert^2\) at the new \(\pi\) // for the chart

Run A: no baseline

Run B: running-mean baseline

Expected reward \(J\) (without the shift)
A: no baselineB: baselinebest arm
Variance of one gradient sample (log scale)
A exactB exactmeasured, last 50 steps
Figure 5. The same bandit, learned twice with the same random numbers: without a baseline (grey) and with a running-mean baseline (blue). The variance is the total variance (sum over the four logits) of the one-sample estimate. The solid lines are exact; the dashed lines average \(\lVert \mathbf{g} - \E\,\mathbf{g} \rVert^2\) over the last 50 real samples, so they are noisy measurements of the same quantity.
How to read Figure 5

With the default shift \(c = 2\), both runs start with a variance of 4.77 (run B’s \(b\) also starts at 0). Run A stays high: every pull, good or bad, gives a big push. In run B, \(b\) catches up with the average reward within a few dozen steps, and its variance drops far below A’s; with seed 1 it is 0.219 against 3.268 at iteration 20, 15 times smaller. Run B also learns faster: with seed 1 its expected reward is 0.736 after 200 iterations, while run A is still at 0.406. The variance of A also falls later, but for a bad reason: once the policy is nearly sure of one arm, \(\mathbf{e}_a - \pi\) is small. Over seeds 1–20, run A ends (after 500 iterations) on a wrong arm in 10 runs, run B in 1. Set \(c = 0\): the runs are much closer, because the 0/1 rewards are already almost centered. This is formula (64.10) in action: the baseline never changes the mean of \(\mathbf{g}\), only its spread.

The advantage: how much better than expected

With the mean baseline, the weight on an answer is \(R - V\): the reward we got minus the reward we expected. This quantity has a name, the advantage. In RL terms, for a state \(s\) and an action \(a\):

\[ A(s, a) = Q(s, a) - V(s), \qquad \text{for a whole LLM answer:} \quad A(x, y) = R(x, y) - V(x) \tag{64.12} \]
Read the symbols
\(Q(s, a)\)
the expected return if we take action \(a\) in state \(s\) and then follow the policy
\(V(s)\)
the expected return from state \(s\) when the policy chooses the action itself; the average of \(Q\) over actions
\(A(s, a)\)
positive: this action was better than the policy’s average, so make it more likely. Negative: worse than average, make it less likely. Zero: as expected, no change
\(V(x)\)
for an LLM: the expected reward of a fresh answer to the prompt \(x\), for example the fraction of answers to this math problem that are correct

The advantage fixes two problems at once. It centers the weights, which cuts the variance. And it makes the signal relative: an easy prompt where 90% of answers are right and a hard one where 10% are right both give useful pushes, toward what is better than usual for that prompt. Without it, the easy prompts would dominate the gradient.

The policy gradient with an advantage, \(\E[A \,\nabla \log \pi]\), is the form used by almost every modern method. They differ in how they estimate \(V\):

  • A learned critic. A second network predicts \(V(s_t)\) for every token. This is the actor–critic idea and PPO’s choice for RLHF; it needs memory for a second large model. Next session: session 65.
  • A group of samples. Sample \(N\) answers for the same prompt and use the other answers’ rewards to estimate \(V(x)\). No critic at all. RLOO and GRPO do this.
  • One extra greedy answer. ReMax uses the reward of the greedy (most likely) answer as the baseline. [Likely] Self-critical sequence training did the same for image captioning in 2017, with the reward of the model’s own test-time output. [Certain] ReMax reports about 46% less GPU memory than PPO for a 7B model, because there is no value network. [Certain]

Group baselines: mean, leave-one-out and GRPO

For one prompt with \(N\) sampled answers and rewards \(r_1, \dots, r_N\), the three common group advantages are:

\[ \begin{aligned} A^{\text{mean}}_i &= r_i - \bar{r}, \qquad \bar{r} = \frac{1}{N}\sum_{j=1}^{N} r_j \\ A^{\text{RLOO}}_i &= r_i - \frac{1}{N-1} \sum_{j \ne i} r_j = \frac{N}{N-1}\,\big(r_i - \bar{r}\big) \\ A^{\text{GRPO}}_i &= \frac{r_i - \bar{r}}{\operatorname{std}(r_1, \dots, r_N) + \varepsilon} \end{aligned} \tag{64.13} \]

RLOO (REINFORCE leave-one-out; Kool et al., 2019; used for RLHF by Ahmadian et al., 2024) is the clean one: the baseline for answer \(i\) uses only the other answers, so it does not depend on \(y^{(i)}\), and (64.10) holds exactly. The plain mean includes \(r_i\) itself, which looks like a bias, but the second line of (64.13) shows it is just RLOO times \((N-1)/N\): the same direction, slightly smaller. GRPO (from DeepSeekMath) also divides by the group’s standard deviation. [Certain] That makes every prompt’s advantages the same size, so prompts with nearly all-same rewards are pushed as hard as mixed ones; it is no longer exactly the policy gradient of (64.1), and Dr. GRPO argues this scaling (and the per-length averaging) adds a bias. [Likely] GRPO is covered in depth in session 70.

Ahmadian et al. report that such simple REINFORCE-style methods outperform PPO, DPO and RAFT in their RLHF experiments. [Certain] That is one result from one setup, not a general law, but it shows that a good baseline does much of the work of a critic when the reward comes once per answer.

Worked example: a group of 8 answers

A math prompt, 8 samples, 2 correct: \(r = (1, 0, 0, 1, 0, 0, 0, 0)\). The mean is \(\bar{r} = 0.25\).

  • Mean baseline: correct answers get \(+0.75\), wrong ones \(-0.25\). The advantages sum to 0.
  • RLOO: a correct answer is compared with the other 7, which have 1 correct: \(1 - 1/7 = 0.857\). A wrong answer is compared with 7 that have 2 correct: \(0 - 2/7 = -0.286\). Both are \(8/7\) times the mean-baseline values.
  • GRPO: the standard deviation (dividing by \(N\)) is \(\sqrt{0.25 \times 0.75} = 0.433\), so the advantages are \(+1.732\) and \(-0.577\).

If all 8 answers are wrong (or all right), every advantage is 0. The prompt gives no learning signal, which is why RL training sets for reasoning are filtered to prompts that the model sometimes, but not always, solves. [Likely]

Click an answer to mark it correct or wrong.

Figure 6. Group advantages for 8 answers to one prompt, formula (64.13). Green cells are correct answers (reward 1). Bars above the line make an answer more likely, bars below make it less likely.
How to read Figure 6

Start with 2 correct answers. Make more answers correct: the correct ones get smaller positive advantages (being right is less surprising), and the few wrong ones get large negative advantages. With 1 correct answer out of 8, RLOO gives it the full \(+1\) and each wrong answer gets only \(-1/7\). Make all 8 the same and every bar goes to zero. Switch to GRPO to see how dividing by the standard deviation scales the bars up.

Putting it together

Here is REINFORCE as it is used for LLMs today: a group of samples per prompt, a leave-one-out baseline, and the surrogate loss with the advantage in place of the reward.

Algorithm 2: REINFORCE with a group (leave-one-out) baseline
  1. input: policy \(\pi_\theta\), prompts, reward \(R\), group size \(N \ge 2\), optimizer
  2. repeat:
  3.   for each prompt \(x\) in the batch: sample \(y^{(1)}, \dots, y^{(N)} \sim \pi_\theta(\cdot \mid x)\)
  4.     \(r_i \leftarrow R(x, y^{(i)})\)
  5.     \(A_i \leftarrow r_i - \frac{1}{N-1}\sum_{j \ne i} r_j\) // formula (64.13); a constant, no gradient
  6.     \(\ell_i \leftarrow \sum_t \log \pi_\theta(y^{(i)}_t \mid x, y^{(i)}_{\lt t})\) // formula (64.5); mask out prompt and padding
  7.   \(\mathcal{L} \leftarrow -\operatorname{mean}_{x, i}\, A_i\, \ell_i\) // formula (64.7) with \(A\) in place of \(R\)
  8.   one optimizer step on \(\mathcal{L}\); then discard the samples

Figure 7 runs this on a tiny “language model”. The answer has 4 tokens from a vocabulary of 5, and each position has its own softmax (it starts uniform). The reward is the fraction of the 4 tokens that match a hidden target, plus a constant shift \(c\). So the reward comes once per answer, and the expected reward starts at 0.2.

no baselinemoving-average baselineleave-one-out (RLOO)
Figure 7. Live REINFORCE training, 150 steps of plain gradient ascent on the logits. Each line is the expected reward (without the shift), averaged over 6 runs with fixed random seeds; the shaded band spans the worst and best of the 6 runs. All three variants see the same random numbers.
How to read Figure 7

At the default shift \(c = 2\), plain REINFORCE (grey) learns slowly and its runs spread widely: every answer gets a large positive weight, and only the small differences carry signal. The moving-average baseline (orange, \(b \leftarrow 0.9b + 0.1\bar{r}\), starting at 0) is slow during the first steps while \(b\) catches up with the shift, then learns well. RLOO (blue) does not care about \(c\) at all: move the slider and its line does not change. Set \(c = 0\): rewards are already small, and the three methods are close. Raise \(N\): all methods get less noisy. Raise \(\eta\) to 2: RLOO learns much faster, but without a baseline several runs lock onto wrong tokens and stop improving (a final value of 0.25 or 0.5 means the policy is sure of only 1 or 2 of the 4 target tokens). Big, noisy steps make the policy confident too early.

Figure 7 averages many runs and hides the mechanics. Figure 8 slows one run down to single tokens. It uses the token toy of session 63: the prompt is “2+3=”, the vocabulary is 5, 6, 7, “.” and the end token ⏎, answers have at most 4 tokens, and the checker gives 1 only to answers that end with ⏎ and whose digits are exactly “5”. The policy is a tiny language model: a table of logits, one row per previous token (25 weights), like a bigram model. It starts uniform, where only 6.08% of answers are correct.

Baseline
Algorithm in the figure: one REINFORCE iteration for a tiny LM
  1. for \(i = 1..N\): sample \(y^{(i)}\) token by token, \(y_t \sim \pi_\theta(\cdot \mid s_t)\); keep \(\log \pi_\theta(y_t \mid s_t)\) // (64.5)
  2. \(R_i \leftarrow \text{checker}(y^{(i)}) + c\)
  3. \(A_i \leftarrow R_i - b_i\) for all \(i\) // none, mean or leave-one-out (64.13)
  4. for each \(i\) and token \(t\): \(\mathbf{g}[s_t] \mathrel{+}= \frac{A_i}{N}\,(\mathbf{e}_{y_t} - \pi_\theta(\cdot \mid s_t))\) // (64.4), (64.6)
  5. \(\theta \leftarrow \theta + \eta\, \mathbf{g}\)
  6. \(J \leftarrow \sum_y \pi_\theta(y \mid x)\, R(y)\) // exact, for the chart only
Fraction of correct answers
batchmoving average (20)exact \(J\)
The policy table \(\pi_\theta(\text{next token} \mid \text{state})\)
Figure 8. REINFORCE on a tiny language model, one token at a time. Each row of the batch is one sampled answer; under each token is its log-probability \(\log \pi_\theta(y_t \mid s_t)\). After scoring, every token of an answer is colored by the sign of that answer’s advantage: green tokens are pushed up, red ones down. The table on the right is the whole policy; darker cells are more likely next tokens. \(J\) is exact, computed by enumerating all answers of up to 4 tokens.
How to read Figure 8

Step through the first batch. Line 1 adds tokens one at a time with their log-probabilities; line 2 scores the finished answer; line 3 turns the scores into advantages. With RLOO and 8 answers, a correct answer in a batch with one success gets \(A = 1\), and each wrong one gets \(A = -1/7 = -0.143\). Line 4 shows the per-token gradient: every token of an answer gets the same \(A_i\), the token-level form of (64.6). Then press Play. The row “x” of the table turns dark under “5”, and the row “after 5” turns dark under ⏎: the model learns to say “5⏎”. With the default settings \(J\) passes 0.9 within about 50 iterations (between iteration 36 and 51 for seeds 1–8). Now choose “none” and set \(c = 2\): every answer gets a positive weight, including wrong ones, and a run can lock onto a wrong answer: with seeds 3 and 6, \(J\) is still about 0.01 and 0.00 after 300 iterations. Switch back to RLOO: the shift has no effect at all, because a constant cancels in \(R_i - b_i\).

The same loop in PyTorch. Part 1 checks the log-derivative trick against autograd on the three-answer example. Part 2 trains a tiny autoregressive policy with RLOO; it is deterministic (fixed seed, CPU).

import torch
torch.manual_seed(0)

# 1) The log-derivative trick on a 3-answer "policy" (formula 64.3)
z = torch.log(torch.tensor([0.2, 0.5, 0.3])).requires_grad_(True)  # logits
R = torch.tensor([1.0, 0.0, 0.0])                                  # reward of each answer
pi = torch.softmax(z, -1)
J = (pi * R).sum()                                  # exact expected reward
exact, = torch.autograd.grad(J, z)
a = torch.multinomial(pi.detach(), 100_000, replacement=True)    # sample answers
logp = torch.log_softmax(z, -1)[a]
est, = torch.autograd.grad((R[a] * logp).mean(), z)              # REINFORCE estimate
print(exact, est)   # tensor([0.1600, -0.1000, -0.0600]) tensor([0.1602, -0.1001, -0.0601])

# 2) REINFORCE with a leave-one-out baseline on a tiny autoregressive policy
V, T, N = 5, 4, 8                      # vocab, answer length, samples per prompt
target = torch.tensor([2, 0, 3, 1])
class TinyLM(torch.nn.Module):
    def __init__(self):
        super().__init__()
        self.emb = torch.nn.Embedding(V + 1, 16)      # token V = start token
        self.pos = torch.nn.Embedding(T, 16)
        self.out = torch.nn.Linear(16, V)
    def forward(self, prev, t):                       # next-token logits
        return self.out(torch.tanh(self.emb(prev) + self.pos(t)))

policy = TinyLM()
opt = torch.optim.Adam(policy.parameters(), lr=0.05)

def sample(n):
    prev = torch.full((n,), V); toks, logps = [], []
    for t in range(T):
        logits = policy(prev, torch.full((n,), t))
        dist = torch.distributions.Categorical(logits=logits)
        y = dist.sample()
        toks.append(y); logps.append(dist.log_prob(y)); prev = y
    return torch.stack(toks, 1), torch.stack(logps, 1)    # (n, T) each

for step in range(61):
    y, logp = sample(N)
    r = (y == target).float().mean(1)                     # one reward per answer
    baseline = (r.sum() - r) / (N - 1)                    # leave-one-out mean, formula (64.13)
    adv = (r - baseline).detach()                         # advantage: a constant
    loss = -(adv * logp.sum(1)).mean()                    # formula (64.7) with A in place of R
    opt.zero_grad(); loss.backward(); opt.step()
    if step % 10 == 0:
        print(step, round(r.mean().item(), 3))
# 0 0.188 | 10 0.719 | 20 0.969 | 30 1.0 | ... the policy learns the target

Note what is not in the code: no gradient of the reward, and no gradient through dist.sample(). The gradient flows only through dist.log_prob(y), exactly as in formula (64.3). In a real LLM, sampling is done by a fast inference engine (such as vLLM), and the log-probabilities are recomputed by the training model in one forward pass over prompt + answer.

Where this is used

SettingRewardHow the policy gradient is used
RLHF for chat models (InstructGPT and later)A reward model’s score, minus a KL penalty to the SFT modelPPO: the policy gradient with a learned critic as the baseline and clipped updates (session 66) [Certain]
RLHF without a critic (RLOO, ReMax)Reward model scoreREINFORCE with a leave-one-out or greedy-answer baseline, less memory than PPO [Certain]
Reasoning with verifiable rewards (math, code)1 if the final answer or unit tests pass, else 0GRPO-style group advantages, many samples per prompt (session 70) [Certain]
Image and video captioningA caption metric such as CIDEr on the sampled captionSelf-critical sequence training: REINFORCE with the greedy caption’s score as baseline [Certain]
Video summarization and key-moment selectionDiversity and representativeness of the chosen framesA policy picks frames (a discrete, non-differentiable choice); trained with a policy gradient [Likely]
Frame or glimpse selection for long videos and Video-RAGAccuracy of the downstream answer or classifierHard attention: where to look is an action, trained with REINFORCE, as in recurrent visual attention models [Likely]
Video QA and temporal grounding with VLMsCorrect answer, or overlap (IoU) of the predicted time span with the true oneThe VLM writes the answer or the timestamps as text; rewards are checked by a script; group advantages as for math [Likely]
Tool use and agentsTask success at the end of many stepsThe whole trajectory is one “answer”; the sparse final reward multiplies every action’s log-probability [Likely]

The pattern is always the same: a discrete, sampled choice (tokens, frames, timestamps, tool calls) and a score that we cannot differentiate. Whenever you see both, the log-derivative trick is the tool.

Common mistakes

  • Letting gradient flow into the advantage. The reward, the baseline and the advantage must be constants (.detach()). If the baseline is computed from the policy’s outputs with gradient attached, the loss optimizes something else.
  • A baseline that depends on the answer itself. Using a quantity computed from \(y^{(i)}\) (for example, a value model that reads the full answer and is evaluated on the same answer) breaks formula (64.9) and biases the gradient. A per-token value \(V(s_t)\) is fine because it only reads the text before token \(t\).
  • Reusing old samples as if they were fresh. REINFORCE is on-policy. Several optimizer steps on one batch without an importance ratio drift away from the true gradient. That is the problem PPO’s ratio and clipping solve.
  • Including the prompt or padding in the log-probability. Only the generated tokens are actions. Mask the prompt and the padding, as in SFT; otherwise you “reward” the model for the prompt.
  • Forgetting the end-of-sequence token. It is an action too. If it is masked out, the model never learns when to stop, and answers grow without limit.
  • Changing the normalization without noticing. Averaging the loss per token instead of per answer gives long answers a smaller weight per token, which changes the objective and can bias the length of answers. [Likely] Pick one on purpose and keep it the same across runs.
  • Uncentered rewards. A reward model whose scores are all around +5, used without a baseline, gives the high-variance regime of Figure 4. Always center: a baseline, group advantages, or at least reward normalization.
  • Reading the surrogate loss as progress. The value of (64.7) can rise or fall while the policy improves. Track the mean reward, its spread, the KL to the starting model and the answer length.

Interview questions

Derive the policy gradient \(\nabla_\theta \E_{y \sim \pi_\theta}[R(y)]\).basic
Write the expectation as \(\sum_y \pi_\theta(y) R(y)\). The reward does not depend on \(\theta\), so the gradient is \(\sum_y R(y) \nabla_\theta \pi_\theta(y)\). Use \(\nabla \pi = \pi \nabla \log \pi\) (the log-derivative trick) to get \(\sum_y \pi_\theta(y) R(y) \nabla_\theta \log \pi_\theta(y) = \E_{y \sim \pi_\theta}[R(y)\nabla_\theta \log \pi_\theta(y)]\). It is an expectation under the policy, so we estimate it by sampling answers and averaging \(R \nabla \log \pi\).
Why can’t we just backpropagate the reward, as we do with a loss?basic
Two reasons. The answer is produced by sampling discrete tokens, and a random discrete draw has no useful derivative with respect to the logits. And the reward is often a black box: a checker, unit tests, a human rating, or a separate model whose input is discrete text. The policy gradient puts \(\theta\) only in \(\log \pi_\theta(y)\), which is differentiable, and treats the reward as a constant weight.
How does REINFORCE for an LLM relate to SFT?core
The surrogate loss is \(-\frac{1}{N}\sum_i R_i \log \pi_\theta(y^{(i)} \mid x)\). SFT is \(-\log \pi_\theta(y^{\ast} \mid x)\) on a human answer. So REINFORCE is SFT on the model’s own samples, each weighted by its reward (or advantage). With 0/1 rewards and no baseline, it is SFT on the samples that passed, which is close to rejection-sampling fine-tuning. The difference: the data comes from the current policy and changes every step, and with a baseline, bad samples get negative weight.
Prove that subtracting a baseline does not bias the gradient. What must the baseline not depend on?core
\(\E_{y}[\nabla \log \pi_\theta(y)] = \sum_y \nabla \pi_\theta(y) = \nabla \sum_y \pi_\theta(y) = \nabla 1 = 0\). So for a constant \(b\), \(\E[(R - b)\nabla \log \pi] = \E[R \nabla \log \pi] - b \cdot 0\). The same holds if \(b\) depends on the prompt or state, or on other independent samples, but not if it depends on the action \(y\) whose score it multiplies. At token level, \(b\) may depend on \(s_t = (x, y_{\lt t})\) but not on \(y_t\) or later tokens.
Why is REINFORCE high-variance, and name three ways to reduce the variance.core
Each estimate uses a few random answers, one reward multiplies the sum of scores of hundreds or thousands of tokens, and any common offset in the rewards adds noise without signal (in the three-answer example, a shift of 10 makes the variance about 421 times larger). Fixes: a baseline (mean reward, leave-one-out, greedy answer, or a learned value), more samples per prompt and bigger batches, reward-to-go when rewards arrive during the answer, reward normalization, and lower-variance advantage estimators such as GAE with a critic.
What is the advantage and why is it a better weight than the raw reward?core
\(A(s, a) = Q(s, a) - V(s)\): how much better this action was than what the policy does on average from that state. For one LLM answer, \(A = R(x, y) - V(x)\). It is centered (mean zero under the policy), so variance is much lower, and it is relative to the prompt: a correct answer to a hard prompt gets a big push and a correct answer to an easy prompt a small one, so easy prompts do not dominate. Its expected gradient is the same as with the raw reward.
Explain RLOO. Why use the leave-one-out mean rather than the plain group mean?core
Sample \(N\) answers per prompt and use, as answer \(i\)’s baseline, the mean reward of the other \(N - 1\) answers. That baseline is independent of answer \(i\), so the estimator is exactly unbiased, and no value network is needed. The plain mean includes \(r_i\), but \(r_i - \bar r = \frac{N-1}{N}(r_i - \bar r_{-i})\), so it only scales the gradient by \((N-1)/N\); in practice both work, RLOO is the clean form.
GRPO divides the centered rewards by the group standard deviation. What does this change?advanced
It gives every prompt advantages of similar size regardless of how mixed its rewards are. For 0/1 rewards with fraction \(p\) correct, the std is \(\sqrt{p(1-p)}\), so prompts with \(p\) near 0 or 1 get their small differences amplified. This acts like per-prompt adaptive weighting; it is no longer the plain gradient of the expected reward, and Dr. GRPO argues the std division and per-length averaging introduce biases (for example toward question difficulty and answer length). When all rewards in the group are equal, the advantage is 0 (the \(\varepsilon\) prevents division by zero).
What is the optimal constant baseline, and why is the mean reward used instead?advanced
Minimizing the trace of the covariance of \((R - b)\mathbf{s}\) over \(b\) gives \(b^{\ast} = \E[R\lVert\mathbf{s}\rVert^2] / \E[\lVert\mathbf{s}\rVert^2]\), a reward average weighted by the squared score norm. Computing per-sample score norms for billions of parameters is expensive, and the gain over \(b = \E[R]\) is usually small (0.1032 vs 0.0948 in the session’s example, against 0.1568 with no baseline). The mean reward is cheap to estimate and is also the value \(V(x)\) that a critic would learn.
For an LLM with only an end-of-answer reward, what does reward-to-go change? When does it matter?advanced
With a single terminal reward and \(\gamma = 1\), the reward-to-go at every token equals \(R\), so nothing changes. It matters when rewards arrive at many tokens: a per-token KL penalty \(-\beta \log(\pi_\theta/\pi_{\text{ref}})\) as in PPO-based RLHF, process rewards for each reasoning step, or multi-turn agents with rewards per turn. Then each token should be weighted only by rewards that come after it, which drops noise from earlier rewards it could not influence.
Your RL run’s reward stays flat. Many prompts give all-wrong answers. What is going on, and what do you do?core
With group advantages, a prompt whose \(N\) samples all fail (or all succeed) gives advantage 0 for every sample, so it contributes no gradient. If most prompts are like that, the effective batch is tiny. Fixes: filter or curriculum the prompts to ones the model solves sometimes, increase \(N\), start from a better SFT model, or add partial-credit rewards (format, intermediate checks) while making sure they cannot be gamed.

Exercises

  1. Two answers with \(\pi = (0.5, 0.5)\) and rewards \(R = (1, 0)\). Compute \(J\), the exact gradient with respect to the two logits, and the single-sample REINFORCE estimate for each of the two outcomes. Check that their average is the exact gradient.
  2. Show that \(\E_{a \sim \pi}[\mathbf{e}_a - \pi] = \mathbf{0}\) for a softmax policy. Which formula of this session is this a special case of?
  3. An answer has token probabilities \(0.8, 0.5, 0.25\). Compute its log-probability. With \(A = -0.5\), what is the gradient on each chosen token’s logit?
  4. A group of 4 answers has rewards \((1, 1, 1, 0)\). Compute the mean-baseline, RLOO and GRPO advantages (std dividing by \(N\)).
  5. In Figure 7, set \(c = 0\) and then \(c = 5\). Which line does not move, and why?
  6. Someone uses as the baseline for answer \(i\) the reward model’s score of answer \(i\) after removing its last sentence. Is the gradient still unbiased? Explain.
  7. In Figure 2, a pull with \(R = 0\) and no baseline leaves \(\mathbf{z}\) unchanged. What does the same pull do when \(b = 0.5\)? Which arms gain?
Answerscheck
1. \(J = 0.5\). Exact: \(\pi_j(R_j - J) = (0.25, -0.25)\). Sample answer 1: \(R = 1\), score \((0.5, -0.5)\), estimate \((0.5, -0.5)\). Sample answer 2: \(R = 0\), estimate \((0, 0)\). Average: \(0.5 \times (0.5, -0.5) + 0.5 \times 0 = (0.25, -0.25)\). 2. \(\sum_a \pi_a (\mathbf{e}_a - \pi) = \pi - \pi \sum_a \pi_a = \mathbf{0}\). It is formula (64.9) for one softmax. 3. \(\log 0.8 + \log 0.5 + \log 0.25 = -0.223 - 0.693 - 1.386 = -2.303\) (the answer has probability 0.1). The pushes are \(A(1 - \pi_t) = -0.1, -0.25, -0.375\). 4. Mean \(0.75\): mean baseline \((0.25, 0.25, 0.25, -0.75)\). RLOO: \(1 - 2/3 = 0.333\) for each correct answer and \(0 - 1 = -1\) for the wrong one. Std \(= \sqrt{0.75 \times 0.25} = 0.433\): GRPO \((0.577, 0.577, 0.577, -1.732)\). 5. The RLOO line: a constant shift appears in \(r_i\) and in the leave-one-out mean and cancels exactly, so the advantages, and therefore every update, are identical. The moving-average baseline needs steps to catch up, and no baseline suffers most. 6. No. That baseline depends on the sampled answer \(y^{(i)}\) itself, so formula (64.9) does not apply and the estimate can be biased. A valid baseline may use the prompt and other samples, not the answer it weights. 7. Without a baseline, \(\mathbf{g}_i = (0 - 0)(\mathbf{e}_a - \pi) = \mathbf{0}\): a failure teaches nothing. With \(b = 0.5\), \(\mathbf{g}_i = -0.5\,(\mathbf{e}_a - \pi)\): the pulled arm’s logit goes down by \(0.5(1 - \pi_a)\) and every other arm’s logit goes up by \(0.5\,\pi_j\). With a baseline, failures carry information too, which is one reason the baseline run in Figure 5 learns faster.

Key takeaways

  • RL for LLMs maximizes the expected reward \(J(\theta)\) (64.1). The weights appear only in the probabilities of the answers, never in the reward.
  • The log-derivative trick (64.2) turns the gradient into an expectation, \(\E[R\,\nabla \log \pi]\) (64.3), which we estimate by sampling. No gradient of the reward or through sampling is needed.
  • For a whole answer, \(\log \pi\) is the sum of token log-probabilities (64.5). REINFORCE is reward-weighted SFT on the model’s own samples (64.7). It is on-policy: fresh samples every step.
  • The estimate is unbiased but very noisy. A constant shift in the rewards keeps the mean and can multiply the variance by hundreds.
  • Because \(\E[\nabla \log \pi] = 0\) (64.9), any baseline that does not depend on the answer adds no bias (64.10). The mean reward is nearly optimal (64.11).
  • The advantage \(A = R - V(x)\) (64.12) is the reward relative to what was expected. LLM methods estimate \(V\) with a critic (PPO), with the other samples in the group (RLOO, GRPO, 64.13), or with a greedy answer (ReMax).

Key formulas

\[ \nabla_\theta J = \E_{y \sim \pi_\theta}\big[ (R(x, y) - b(x))\, \nabla_\theta \log \pi_\theta(y \mid x) \big], \qquad \log \pi_\theta(y \mid x) = \sum_t \log \pi_\theta(y_t \mid x, y_{\lt t}) \]
\[ \mathcal{L}_{\text{PG}} = -\frac{1}{N}\sum_i A_i \log \pi_\theta(y^{(i)} \mid x), \qquad A^{\text{RLOO}}_i = r_i - \frac{1}{N-1}\sum_{j \ne i} r_j \]

References for this session

  1. Williams (1992). Simple statistical gradient-following algorithms for connectionist reinforcement learning
  2. Sutton & Barto, Reinforcement Learning: An Introduction, 2nd ed., chapter 13: Policy Gradient Methods
  3. Weng (2018). Policy Gradient Algorithms (blog)
  4. Sutton, McAllester, Singh and Mansour (1999). Policy Gradient Methods for Reinforcement Learning with Function Approximation
  5. Greensmith, Bartlett and Baxter (2004). Variance Reduction Techniques for Gradient Estimates in Reinforcement Learning
  6. Kool, van Hoof and Welling (2019). Buy 4 REINFORCE Samples, Get a Baseline for Free!
  7. Ahmadian et al. (2024). Back to Basics: Revisiting REINFORCE Style Optimization for Learning from Human Feedback in LLMs
  8. Li et al. (2023). ReMax: A Simple, Effective, and Efficient Reinforcement Learning Method for Aligning Large Language Models
  9. Shao et al. (2024). DeepSeekMath: Pushing the Limits of Mathematical Reasoning in Open Language Models
  10. Liu et al. (2025). Understanding R1-Zero-Like Training: A Critical Perspective
  11. Ouyang et al. (2022). Training language models to follow instructions with human feedback
  12. Rennie et al. (2017). Self-critical Sequence Training for Image Captioning
  13. Mnih et al. (2014). Recurrent Models of Visual Attention
  14. Zhou, Qiao and Xiang (2018). Deep Reinforcement Learning for Unsupervised Video Summarization with Diversity-Representativeness Reward