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

Reinforcement learning words, for LLMs

Reinforcement learning (RL) has its own words: agent, environment, state, action, reward, return, episode, policy. This session explains each word with a language model as the example: the LLM is the policy, the prompt plus the text so far is the state, the next token is the action, and a score often arrives only at the end of the answer. It also shows why we want RL after SFT: RL learns from a score of the model’s own answers, not from a copy of someone else’s.

Time: 2 to 2.5 hours (reading 1.5 hours, exercises 40 minutes)Level: BeginnerBefore this: Sessions 3, 6, 53 and 54

What you will learn

  • The RL loop and its words: agent, environment, state, action, reward, return, episode, policy, value
  • How text generation becomes RL: state = prompt + text so far, action = next token, policy = the LLM, and a deterministic transition that appends the token
  • Why the probability of a whole answer is a sum of token log-probabilities, and why the number of possible answers is astronomically large
  • Sparse rewards that arrive only at the end of an answer, the credit assignment problem, discounting, and the per-token KL penalty used in RLHF
  • The token view (an MDP) and the answer view (a contextual bandit) of the same problem
  • Why RL after SFT: SFT copies demonstrations, RL raises the expected score of the model’s own samples, with the gradients side by side

Why this matters

In session 54 we trained a model by showing it good answers and asking it to copy them, token by token. That works, but it has a ceiling: the model can only become as good as the answers we can write down. Many things we want are easier to score than to write. We can check that a math answer is right, that code passes its tests, or that a human prefers answer A to answer B. Reinforcement learning (RL) is the family of methods that learns from such scores.

The next sessions of this track (session 64, session 65, session 66, session 70) use the language of RL all the time. Papers write “policy”, “rollout”, “return”, “advantage”, “sparse reward” and “episode” without explaining them. This session is the dictionary. We define every word with a language model as the running example, and we write the few formulas that the next sessions build on.

Real systems use exactly this framing. InstructGPT (OpenAI described ChatGPT as its sibling model) describes its RL stage as “a bandit environment which presents a random customer prompt and expects a response to the prompt”; the reward comes from a learned reward model, and a “per-token KL penalty from the SFT model” is added. [Certain] DeepSeek-R1-Zero applied RL “directly to the base model without relying on supervised fine-tuning (SFT) as a preliminary step”, with rule-based rewards for a correct final answer and for the right format, and its AIME 2024 pass@1 went from 15.6% to 71.0%. [Certain]

The RL loop and its words

RL describes a learner that acts, sees what happens, and gets a number that says how good the result was. There is no teacher who shows the right action. The learner must find good actions by trying them. Here are the words, in the order they appear in the loop (they follow Sutton and Barto, chapter 1, and OpenAI’s Spinning Up):

  • Agent: the learner and decision maker. For us, the language model.
  • Environment: everything outside the agent that reacts to its actions. For us, the program that appends the chosen token to the text and, at the end, a reward model or a checker that scores the answer.
  • State \(s_t\): what the agent knows at step \(t\) when it chooses. For us, the prompt plus all tokens written so far.
  • Action \(a_t\): what the agent chooses at step \(t\). For us, the next token.
  • Policy \(\pi_\theta(a \mid s)\): the rule that maps a state to a probability for each action. \(\theta\) are the weights. For us, the LLM itself: its softmax over the vocabulary is the policy.
  • Transition: how the state changes after an action. In general it can be random (a robot slips). For us it is deterministic: the new state is the old text with the token appended.
  • Reward \(r_t\): a number the environment gives after an action. It says how good that step was. For us, it is usually 0 for every token except the last one.
  • Episode: one run from a start state to a terminal state, where it ends. For us, one answer: it starts at the prompt and ends at the end-of-turn token or at the length limit.
  • Trajectory \(\tau\) (also called a rollout): the sequence of states, actions and rewards in one episode. For us, one generated answer together with its scores.
  • Return \(G_t\): the total reward from step \(t\) to the end of the episode, maybe with discounting. The agent wants a large return, not a large reward at one step.
  • Value \(V^\pi(s)\): the return we expect from state \(s\) if we follow policy \(\pi\). It is a prediction, not an observation.
Figure 1. The agent–environment loop of RL. Bold words are the RL terms; the lighter text says what each one is for a language model. One trip around the loop is one token. One episode is one whole answer.

Spinning Up writes the loop as a trajectory and its probability. Starting from \(s_0\), the policy picks \(a_0\), the environment returns \(r_0\) and \(s_1\), and so on until a terminal state at step \(T\):

\[ \tau = (s_0, a_0, r_0, s_1, a_1, r_1, \dots, s_{T-1}, a_{T-1}, r_{T-1}, s_T), \qquad a_t \sim \pi_\theta(\cdot \mid s_t), \quad s_{t+1} \sim P(\cdot \mid s_t, a_t) \tag{63.1} \]
Read the symbols
\(\tau\)
one trajectory: everything that happened in one episode
\(T\)
the number of actions in the episode (for us, the number of generated tokens)
\(a_t \sim \pi_\theta(\cdot \mid s_t)\)
the action is sampled from the policy’s distribution in state \(s_t\)
\(P(s_{t+1} \mid s_t, a_t)\)
the transition probability, given by the environment; the agent does not control it
\(r_t\)
the reward received after action \(a_t\) (Sutton and Barto call it \(R_{t+1}\); same thing, shifted index)

The return from step \(t\) adds up the rewards that come after it. A discount factor \(\gamma\) between 0 and 1 can make far-away rewards count less:

\[ G_t = \sum_{k=t}^{T-1} \gamma^{\,k-t}\, r_k = r_t + \gamma\, G_{t+1}, \qquad G_T = 0 \tag{63.2} \]
Read the symbols
\(G_t\)
the return from step \(t\): the reward of this step plus the (discounted) rewards of all later steps
\(\gamma\)
the discount factor. \(\gamma = 1\) means “all future rewards count fully”; \(\gamma = 0.9\) means a reward 10 steps later counts \(0.9^{10} \approx 0.35\)
\(G_t = r_t + \gamma G_{t+1}\)
the same sum written as a recursion; code computes returns this way, from the last step backward

The goal of RL is to find weights \(\theta\) that make the expected return large. The expectation is over everything random: the start state, the sampled actions and the transitions:

\[ J(\theta) = \E_{\tau \sim \pi_\theta}\!\left[ G_0(\tau) \right], \qquad \theta^\star = \argmax_\theta J(\theta) \tag{63.3} \]
Read the symbols
\(J(\theta)\)
the objective: the average return over many episodes played with policy \(\pi_\theta\)
\(\tau \sim \pi_\theta\)
trajectories produced by running the policy in the environment; when \(\theta\) changes, the data changes too

That last point is the deepest difference from supervised learning. In SFT the data is fixed: a list of demonstrations. In RL the data is generated by the model being trained. Change the weights, and the answers you learn from change. This is why RL training needs a generation engine inside the training loop (session 75).

We almost never know \(J(\theta)\) exactly. We estimate it: play \(N\) episodes, compute each return, and average. This is a Monte Carlo estimate (“Monte Carlo” means: use random samples to estimate an average):

\[ \hat J_N = \frac{1}{N} \sum_{i=1}^{N} G_0\big(\tau^{(i)}\big), \qquad \E\big[\hat J_N\big] = J(\theta), \qquad \text{typical error} \approx \frac{\sigma}{\sqrt{N}} \tag{63.4} \]
Read the symbols
\(\tau^{(i)}\)
the \(i\)-th episode, played with the current policy; the episodes are independent
\(\sigma\)
the standard deviation of one return \(G_0\): how much one episode’s return differs from the average
\(\sigma / \sqrt{N}\)
the standard error: four times more episodes halve the error

Figure 2 runs this loop for real, one line of the algorithm at a time. It has two environments with the same code. The corridor is classic RL: a robot in cell 3 of a corridor moves left or right at random; reaching the right end gives +1, the left end −1. The token toy is an LLM in miniature: the prompt is “2+3=”, the vocabulary has 5 tokens (5, 6, 7, “.”, and the end token ⏎), the answer is at most 4 tokens long, and a checker gives \(R = 1\) only if the answer ends with ⏎ and its digits are exactly “5” (so “5⏎” and “5.⏎” are correct). The token policy is a fixed table: it depends only on the previous token, like a bigram model (session 5).

Algorithm in the figure: one episode, then its return
  1. \(s_0 \leftarrow\) start state (the prompt \(x\), or cell 3); \(t \leftarrow 0\)
  2. repeat:
  3. sample \(a_t \sim \pi(\cdot \mid s_t)\) // the policy acts
  4. \(r_t,\ s_{t+1} \leftarrow\) environment\((s_t, a_t)\); \(t \leftarrow t + 1\)
  5. until \(s_t\) is terminal or \(t = T_{\max}\)
  6. \(G_T \leftarrow 0\)
  7. for \(t = T-1\) down to 0: \(G_t \leftarrow r_t + \gamma\, G_{t+1}\) // (63.2)
  8. add \(G_0\) to the list; \(\hat J \leftarrow\) mean of all \(G_0\) // (63.4)
Return \(G_0\) of every episode
one episoderunning mean \(\hat J\)exact \(J\)
Error \(|\hat J - J|\) (log scale)
this run\(\sigma/\sqrt{N}\)
Figure 2. The RL loop, running in your browser. Each Step executes one highlighted line of the algorithm; the boxes on the right show the formula of that line with the live numbers. The table is the trajectory \(\tau\) of (63.1). The exact \(J\) is computed by enumerating every possible episode (all \(5^4\) token sequences, or every corridor path up to \(T_{\max} = 40\) steps), so you can watch the estimate (63.4) converge to it. Random numbers come from a seeded generator, so the same seed gives the same episodes.
How to read Figure 2

Start with the token toy at Slow and press Step a few times. Line 3 samples a token: the bars show \(\pi(a \mid s_t)\) and the random number \(u\) that picked one. Line 4 appends it to the state and gives reward 0, until the answer ends; only then does the checker give \(R\). Lines 6–7 then walk backward and fill the \(G_t\) column with \(r_t + \gamma G_{t+1}\). With \(\gamma = 1\) every token of a correct answer gets \(G_t = 1\): the sparse reward of the next sections. Now switch to Turbo. The blue running mean settles on the orange exact \(J = 0.2685\), and its error follows the \(\sigma/\sqrt{N}\) line. Lower the temperature to 0.5: the policy becomes greedier, “5⏎” gets more likely, and \(J\) rises to 0.548. Lower \(\gamma\) to 0.9: correct answers that took 3 tokens are worth \(0.9^2 = 0.81\), so \(J\) drops. In the corridor, \(\pi(\text{right}) = 0.5\) gives \(J = 0\) with \(\gamma = 1\) (the two ends are equally likely), and moving it to 0.6 gives \(J = 0.542\).

Two more words complete the dictionary. Sutton and Barto list four main elements of an RL system: a policy, a reward signal, a value function and, optionally, a model of the environment. [Certain] The value function is the expected return from a state:

\[ V^{\pi}(s) = \E_{\tau \sim \pi}\!\left[ G_t \mid s_t = s \right], \qquad A^{\pi}(s_t, a_t) = \E\!\left[ G_t \mid s_t, a_t \right] - V^{\pi}(s_t) \tag{63.5} \]
Read the symbols
\(V^\pi(s)\)
the value: how much return we expect from state \(s\) on average, if we keep following \(\pi\). For an LLM: “how likely is this half-written answer to end up correct?”
\(A^\pi(s_t, a_t)\)
the advantage: how much better action \(a_t\) is than the average action in that state. Positive means “better than expected”

We only name these here. Session 65 explains how to estimate them, and session 64 shows why the advantage, not the raw reward, is what the update should use.

Text generation as RL

Now we map the words onto an LLM exactly. Take a prompt \(x\) (the chat template, the system prompt and the user’s message, as tokens) and an answer \(y = (y_1, \dots, y_T)\) that the model writes. Then:

\[ s_t = (x,\, y_1, \dots, y_{t}), \qquad a_t = y_{t+1}, \qquad \pi_\theta(a_t \mid s_t) = \softmax\!\big(f_\theta(s_t)\big)_{a_t}, \qquad s_{t+1} = s_t \oplus a_t \tag{63.6} \]
Read the symbols
\(s_t\)
the state after \(t\) generated tokens: the prompt followed by the answer so far; \(s_0 = x\)
\(a_t\)
the action: the next token, one of the \(|\mathcal{V}|\) entries of the vocabulary
\(f_\theta(s_t)\)
the logits the transformer outputs at the last position of \(s_t\)
\(\oplus\)
“append”. The transition is deterministic: no randomness comes from the environment, only from sampling the token

So the policy is the LLM, with no change at all. Sampling a token at temperature 1 (session 79) is “taking an action”. Generating an answer is “playing an episode”. The episode ends when the model emits its end-of-turn token or hits the length limit.

Because the transitions are deterministic, the probability of a whole answer is just the product of the token probabilities, and its log is a sum. This is the same chain rule as in session 6:

\[ \log \pi_\theta(y \mid x) = \sum_{t=0}^{T-1} \log \pi_\theta(a_t \mid s_t) = \sum_{t=1}^{T} \log p_\theta(y_t \mid x, y_{\lt t}) \tag{63.7} \]
Read the symbols
\(\pi_\theta(y \mid x)\)
the probability that the model writes exactly the answer \(y\) for prompt \(x\)
\(p_\theta(y_t \mid x, y_{\lt t})\)
the usual next-token probability of the language model

Every RL algorithm for LLMs computes (63.7). It is one forward pass over the prompt and answer with teacher forcing, then a gather of the log-probabilities of the tokens that were actually sampled. This is cheap, and it is the same code as the SFT loss without the minus sign and the mean.

State \(s_t\)
Figure 3. One episode, step by step. The prompt (grey) is the start state. At each step the policy gives a probability to each candidate token (a real model spreads probability over its whole vocabulary; here only a few candidates are shown, with probabilities that sum to 1), one token is sampled (blue bar), and it joins the state (orange). The probabilities are made up for illustration, but the bookkeeping is exactly what an RL trainer does.
How to read Figure 3

Press Next. Each step is one action: watch the chosen token join the state, the reward stay at 0, and the running log-probability (63.7) go down, because every token has probability below 1. At the last step the episode ends and the checker gives the whole answer a reward of 1, because it contains the correct number 51. Notice that the reward says nothing about which token deserved it. That question, credit assignment, is the subject of the next section.

Worked example: the probability of one answer, and how many answers exist

In Figure 3 the six sampled tokens have probabilities 0.45, 0.70, 0.90, 0.62, 0.80 and 0.85. The log-probabilities are −0.799, −0.357, −0.105, −0.478, −0.223 and −0.163. Their sum is \(\log \pi_\theta(y \mid x) = -2.124\), so \(\pi_\theta(y \mid x) = e^{-2.124} = 0.1195\). Even this likely, short answer comes out only about 12% of the time; the model spreads the rest over other answers.

How many answers are there? Llama 3 has a vocabulary of 128,256 tokens. [Certain] An answer of 100 tokens is one of \(128{,}256^{100} \approx 10^{510.8}\) possible sequences. In RL words: at each step the action space has 128,256 actions, and the episode tree has more leaves than there are atoms in the universe. Nobody can try them all, so the model can only learn from the answers it actually samples. That makes the starting policy (the SFT model) very important: RL mostly re-weights answers the model can already produce.

Two views of the same problem: token MDP and answer bandit

The formal object behind (63.1) is a Markov decision process (MDP): a set of states, a set of actions, transition probabilities, a reward function and a discount. “Markov” means the next state depends only on the current state and action. For an LLM this is true by construction: the state is the whole text so far.

There is a second, simpler view. Treat the whole answer \(y\) as one action. Then each episode has a single step: see a prompt, give an answer, get a score, done. A problem with one step per episode is a bandit; when the step depends on an observed input (the prompt), it is a contextual bandit. Lambert’s RLHF book puts it this way: in RLHF “no state transitions exist”, because the completion does not define the next prompt, and this single-step structure “is sometimes called a bandit problem”. [Certain]

ViewStateActionEpisode lengthRewardUsed by
Token-level MDPprompt + tokens so farone token\(T\) steps0 until the end, then the score (plus per-token KL terms)PPO-style RLHF with a value model (session 66)
Answer-level contextual banditthe promptthe whole answer1 stepthe score of the answerREINFORCE-style and GRPO-style methods that give one advantage to all tokens (session 70)
Multi-turn agent MDPthe conversation, tool results, the screena token, or a whole turnmany turnsat the end of the task, sometimes per turntool-use and computer-use agents (session 154)

Both views have the same objective. They differ in how they assign credit to tokens. The token view can, in principle, learn which token made the difference. The answer view gives every token of a good answer the same push.

Sparse rewards: the score comes at the end

A sparse reward is zero almost everywhere and nonzero only at a few steps. For an LLM answer, the reward is usually computed once, from the finished text:

\[ r_t = \begin{cases} 0 & t \lt T-1 \\ R(x, y) & t = T-1 \end{cases} \qquad \Longrightarrow \qquad G_t = \gamma^{\,T-1-t}\, R(x, y) \tag{63.8} \]
Read the symbols
\(R(x, y)\)
the score of the whole answer: a reward model’s output (RLHF), or 1/0 from a checker (math answer correct, code tests pass)
\(T-1\)
the index of the last action, usually the end-of-turn token
\(G_t\)
the return at step \(t\): with \(\gamma = 1\) it is the same number \(R(x, y)\) for every token

Why is it sparse? Because most scores only make sense for a finished answer. A math checker cannot grade half of a number. A human or a reward model judges the whole reply. A unit test needs complete code. Rewards for partial answers exist (process rewards, which score each reasoning step; see session 73), but they are expensive to build and easier to fool.

Sparse rewards create two problems. The first is credit assignment: an answer of 500 tokens got a reward of 0. Which tokens were the mistake? With (63.8) every token sees the same return, so a single wrong digit and 499 good tokens all get the same blame. Only by comparing many answers, some good and some bad, can training find out which choices matter. The second is exploration: if the model almost never produces a correct answer, almost every reward is 0, and there is nothing to learn from. The code below shows this: a random tiny model gets the reward in about 1% of episodes.

How does “comparing many answers” find the important token? Through the value function (63.5). Every prefix of an answer is a state. Its value is the average return of the answers that pass through it, and we can estimate it from samples, just like \(\hat J\) in (63.4). The difference between the values before and after a token tells us how much that token changed the chances. With \(\gamma = 1\), rewards of 0 before the end, and the deterministic transition \(s_{t+1} = s_t \oplus a_t\), the expected return after choosing \(a_t\) is just the value of the next state, so the advantage (63.5) becomes a difference of two values:

\[ \hat V(s) = \frac{1}{N(s)} \sum_{i:\ s \in \tau^{(i)}} G^{(i)}, \qquad \hat A(s_t, a_t) = \hat V(s_{t+1}) - \hat V(s_t) \tag{63.9} \]
Read the symbols
\(N(s)\)
how many sampled answers passed through the prefix \(s\)
\(G^{(i)}\)
the return of answer \(i\) from that prefix on; here it is just the final score \(R\) of answer \(i\)
\(\hat V(s_{t+1})\)
for a finished answer, the value is its score \(R\) itself
Algorithm in the figure: Monte Carlo values of prefixes
  1. sample an answer \(y \sim \pi(\cdot \mid x)\), one token at a time
  2. \(R \leftarrow R(x, y)\); with \(\gamma = 1\), every step has \(G_t = R\) // (63.8)
  3. for each prefix \(s_t\) on the path: \(N(s_t) \mathrel{+}= 1\); \(S(s_t) \mathrel{+}= R\)
  4. \(\hat V(s_t) \leftarrow S(s_t) / N(s_t)\) // (63.9)
  5. \(\hat A_t \leftarrow \hat V(s_{t+1}) - \hat V(s_t)\) for each token // (63.9)
Estimated values \(\hat V(s)\) as answers accumulate
prompt “2+3=”“2+3= 5”“2+3= .”“2+3= 6”“2+3= 7”exact values (thin lines)
Figure 4. Credit assignment from samples, on the token toy of Figure 2 (temperature 1, \(\gamma = 1\)). Every sampled answer updates the running averages of all prefixes it passed through. Under the answer, each token shows its advantage \(\hat A_t\) from (63.9): green if it raised the chance of a correct answer, red if it lowered it. The table compares the estimates with the exact values, computed by enumerating all answers; its last column is the advantage of the first token, \(\hat A(x, a) = \hat V(x \oplus a) - \hat V(x)\).
How to read Figure 4

Press Step: the tokens appear one by one, then the checker scores the answer, then the counts and averages of every prefix on the path are updated, and finally each token gets its advantage. One answer alone tells you little: the reward is the same number for every token. After many answers (try Turbo) the table shows the real structure. Starting with “5” has value 0.654 while the prompt has 0.2685, so the token “5” has advantage 0.654 − 0.2685 = +0.3855: it is the decision that matters. Starting with “6” or “7” makes the answer certainly wrong (value 0, advantage −0.2685), and ⏎ as the first token gives an empty answer. A “.” first is also bad (0.069): the model must still write a 5 after it. This is exactly what a critic (a value model) learns in session 65, with a network instead of a table.

Discounting and the per-token KL penalty

Classic RL uses \(\gamma \lt 1\) so that infinite episodes have finite returns and quick rewards are preferred. LLM episodes are finite, and the answer is judged as a whole, so RLHF implementations usually use \(\gamma = 1\). [Certain] With \(\gamma \lt 1\) and a reward only at the end, the first tokens would see a much smaller return than the last ones, for no good reason.

Many RLHF setups do add a small reward at every token: a penalty for moving away from a reference policy \(\pi_{\text{ref}}\) (usually the SFT model). InstructGPT’s objective is the reward model score minus \(\beta \log\big(\pi^{\text{RL}}(y \mid x)/\pi^{\text{SFT}}(y \mid x)\big)\), implemented as a per-token KL penalty. [Certain] Because of (63.7), the log-ratio of the whole answer splits into a sum over tokens:

\[ r_t = -\beta \,\log \frac{\pi_\theta(a_t \mid s_t)}{\pi_{\text{ref}}(a_t \mid s_t)} \;+\; \mathbb{1}[t = T-1]\; R(x, y) \tag{63.10} \]
Read the symbols
\(\pi_{\text{ref}}\)
the frozen reference model (a copy of the SFT model); it is never trained
\(\beta\)
the strength of the penalty; larger \(\beta\) keeps the policy closer to the reference
\(\log \frac{\pi_\theta}{\pi_{\text{ref}}}\)
for the sampled token: positive if the policy now likes this token more than the reference did. Its average over samples is the KL divergence (session 3)
\(\mathbb{1}[t = T-1]\)
1 at the last token and 0 elsewhere: the task reward still arrives only at the end

Summing (63.10) over the episode (with \(\gamma = 1\)) gives exactly the InstructGPT objective for one answer, \(R(x, y) - \beta \log \frac{\pi_\theta(y \mid x)}{\pi_{\text{ref}}(y \mid x)}\). Why the penalty? The reward is only a proxy. A learned reward model has blind spots, and a policy that is free to change will find them: it writes answers that score high but are not good. This is reward hacking (also called reward over-optimization). DeepSeek-R1 avoided neural reward models for this reason: they found “the neural reward model may suffer from reward hacking in the large-scale reinforcement learning process”. [Certain] The KL term keeps the policy near the text distribution where the reward model was trained.

reward \(r_t\) of each token (63.10)return \(G_t\) seen by each token (63.2)
Figure 5. Rewards and returns for one answer of \(T\) tokens. The final score arrives at the last token. With \(\beta \gt 0\), each token also gets a small KL term; the per-token log-ratios \(\log \pi_\theta/\pi_{\text{ref}}\) here are fixed seeded numbers (drawn around 0.05 with a spread of 0.15, so some are negative), as if the policy had already moved a little away from the reference.
How to read Figure 5

Start with \(\beta = 0\) and \(\gamma = 1\): only the last bar is nonzero, and the blue return line is flat. Every token sees the same number, which is what “sparse reward” means in practice. Lower \(\gamma\) to 0.95: the return now shrinks toward the start of the answer, so the first tokens get much less credit for a final result they helped to cause. Raise \(\beta\): small negative bars appear at every token, and the return at the first token is the final score minus the KL cost of the whole answer. Make the answer longer and watch the KL cost grow with length.

Worked example: returns with a sparse score and a KL penalty

Discounting. An answer has 200 tokens and a final score \(R = 1\). With \(\gamma = 1\), every token has return 1. With \(\gamma = 0.99\), the first token has return \(0.99^{199} = 0.135\): it gets 7 times less credit than the last token, for the same final result.

KL penalty. A 4-token answer has log-ratios \(\log \pi_\theta/\pi_{\text{ref}} = 0.2, -0.1, 0.4, 0.3\), \(\beta = 0.1\) and \(R = 0.8\). By (63.10) the rewards are \(r = (-0.02,\ 0.01,\ -0.04,\ -0.03 + 0.8) = (-0.02,\ 0.01,\ -0.04,\ 0.77)\). With \(\gamma = 1\) the returns are \(G = (0.72,\ 0.74,\ 0.73,\ 0.77)\). Check: \(G_0 = 0.8 - 0.1 \times (0.2 - 0.1 + 0.4 + 0.3) = 0.8 - 0.08 = 0.72\). The second token’s log-ratio is negative (the policy likes it less than the reference), so it earns a small bonus.

Why RL and not only SFT

SFT and RL can be written side by side. SFT maximizes the log-probability of demonstrations \(y^\star\) from a fixed dataset \(\mathcal{D}\). RL maximizes the expected score of the model’s own answers, often with the KL term of (63.10):

\[ J_{\text{SFT}}(\theta) = \E_{(x, y^\star) \sim \mathcal{D}}\big[ \log \pi_\theta(y^\star \mid x) \big], \qquad J_{\text{RL}}(\theta) = \E_{x \sim \mathcal{D}}\, \E_{y \sim \pi_\theta(\cdot \mid x)}\big[ R(x, y) \big] - \beta\, \E_{x}\big[\KL\big(\pi_\theta(\cdot \mid x)\,\|\,\pi_{\text{ref}}(\cdot \mid x)\big)\big] \tag{63.11} \]
Read the symbols
\(y^\star\)
a demonstration written by a person or a stronger model; it never changes during training
\(y \sim \pi_\theta(\cdot \mid x)\)
an answer sampled from the current model; it changes as \(\theta\) changes
\(R(x, y)\)
a score: a reward model, a checker, a preference judgment
\(\KL(\cdot \,\|\, \cdot)\)
how far the policy has moved from the reference, as in (63.10)

Their gradients show the difference most clearly. Ignore the KL term for a moment. The SFT gradient pushes up one fixed answer. The RL gradient (derived in session 64; we only state it here) pushes up every sampled answer in proportion to its score:

\[ \nabla_\theta J_{\text{SFT}} = \E_{\mathcal{D}}\big[\nabla_\theta \log \pi_\theta(y^\star \mid x)\big], \qquad \nabla_\theta J_{\text{RL}} = \E_{x}\, \E_{y \sim \pi_\theta}\big[ R(x, y)\, \nabla_\theta \log \pi_\theta(y \mid x) \big] \tag{63.12} \]

Read the RL side as “SFT on the model’s own samples, weighted by their score”. A sample with a high score is pushed up; with a negative score (or a negative advantage, once we subtract a baseline) it is pushed down. SFT has no way to push an answer down: it only ever says “more of this”.

That gives the four reasons to do RL after SFT:

  1. Scoring is easier than writing. A checker for “is 51 the answer?” is one line of code. A great chain of reasoning that reaches 51 is hard to write by hand for millions of problems. RL can use the checker directly.
  2. No ceiling from the demonstrations. SFT copies the data, including its mistakes. If 30% of the demonstrations are wrong, a perfect SFT fit is wrong 30% of the time. RL climbs toward whatever the reward prefers. Figure 6 shows this.
  3. It learns from its own mistakes. SFT trains on states the model may never reach (the demonstrator’s text). At inference the model walks on its own text, and small errors pile up. This mismatch is called exposure bias. RL trains exactly on the model’s own text, including its errors, and can push the bad continuations down. [Likely]
  4. Preferences that are hard to demonstrate. “Helpful but not long-winded”, “refuse only when needed”: people can compare two answers much more easily than they can write the ideal one. Comparisons train a reward model (session 67), and RL optimizes it. Christiano et al. (2017) introduced this recipe for RL from human preferences. [Certain]

The price is real. RL needs generation in the training loop (slow), a reward that can be hacked, many samples because the gradient estimate is noisy, and care to keep the model from drifting away (the KL term). It also tends to reduce diversity: the policy concentrates on the high-reward answers it already finds. That is why the usual order is SFT first, then RL. SFT puts good answers into the model’s reach; RL sharpens the choice among them. [Likely]

SFT is a special case, almost

Take a reward that is 1 only for the exact demonstration: \(R(x, y) = \mathbb{1}[y = y^\star]\). Then \(J_{\text{RL}} = \pi_\theta(y^\star \mid x)\) and its gradient is \(\pi_\theta(y^\star \mid x)\,\nabla_\theta \log \pi_\theta(y^\star \mid x)\). So the SFT gradient is the RL gradient for this “copy reward”, divided by \(\pi_\theta(y^\star \mid x)\). SFT is RL with the narrowest possible reward, re-scaled so that unlikely demonstrations get a strong push. The re-scaling matters: for a long demonstration \(\pi_\theta(y^\star \mid x)\) is tiny, and RL with the copy reward would almost never sample \(y^\star\) at all.

A tiny example makes (63.12) concrete. Treat six whole answers as six actions (the bandit view) with logits \(z\), so \(p = \softmax(z)\). For SFT on demonstration \(k\) and for RL with rewards \(R_i\), the gradients with respect to the logits are

\[ \frac{\partial \log p_k}{\partial z_i} = \mathbb{1}[i = k] - p_i, \qquad \frac{\partial J}{\partial z_i} = p_i\,\big(R_i - J\big), \qquad J = \sum_j p_j R_j \tag{63.13} \]
Read the symbols
\(p_i\)
the probability of answer \(i\); \(z_i\) its logit
\(k\)
the index of the demonstrated answer
\(R_i\)
the score of answer \(i\); \(J\) is the expected score
\(R_i - J\)
already an advantage: answers better than the average go up, worse ones go down

The SFT gradient lifts only answer \(k\) and lowers everything else, good or bad. The RL gradient lifts every answer that is better than average, in proportion to how often the model produces it.

Answer to “17 × 3 = ?”RewardSFT dataProbability now
SFTRL, exactRL, 8 samples
Figure 6. SFT versus RL on one prompt, in the answer-level (bandit) view. The policy is a softmax over six whole answers; it starts from the same logits in every mode. SFT does gradient ascent on (63.13, left) toward the SFT data. RL uses the exact expected gradient (63.13, right), or an estimate from 8 sampled answers per step (seeded), with no baseline. The chart shows the expected reward \(J\) of each method over 300 steps.
How to read Figure 6

With one clean demonstration, SFT and RL both reach a high expected reward, but in different ways: SFT puts almost all probability on the one answer it was shown, while RL rewards whatever correct answer the model already liked best (here the short “51”). Now switch the SFT data to the noisy human demos: SFT now converges to the data distribution, wrong answers included, and its expected reward stops near 0.70. RL does not care what people wrote; it only follows the score. Try the sampled RL mode: the curve is noisy but follows the exact one, and the sampling noise decides which correct answer wins (here “17 × 3 = 51.”, not “51”). Look at the entropy in the readout too: RL concentrates the policy, which is the loss of diversity mentioned above.

Worked example: the first gradient step in Figure 6

The starting logits are \(z = (0.5, 0.2, -0.5, 1.0, 0.8, 0.3)\), so \(p = (0.169, 0.125, 0.062, 0.278, 0.228, 0.138)\). Answers 1 to 3 are correct (\(R = 1\)), answers 4 to 6 are wrong (\(R = 0\)), so \(J = 0.169 + 0.125 + 0.062 = 0.356\). The model is wrong about two times out of three.

SFT on demonstration 3 (the long explained answer): the gradient is \((-0.169, -0.125, 0.938, -0.278, -0.228, -0.138)\). It pushes down the correct answers 1 and 2 as hard as the wrong ones.

RL: the gradient is \(p_i (R_i - J) = (0.109, 0.081, 0.040, -0.099, -0.081, -0.049)\). All correct answers go up, all wrong ones go down, and the components sum to zero.

After 100 steps at learning rate 0.5 (the default in the figure): SFT on the clean demo gives \(J = 0.989\), with 98.2% of the probability on answer 3 and entropy 0.17 bits. RL gives \(J = 0.975\), with 86.2% on answer 1 and entropy 0.79 bits (it started at 2.45 bits). SFT on the noisy demos gives only \(J = 0.691\), and its limit is 0.70, the share of correct demonstrations.

Putting it together: the RL loop for an LLM

Every RL method in the next sessions fits the same outer loop. They differ in step 4: how the scores become an update.

Algorithm 1: one episode (a rollout) for an LLM
  1. input: policy \(\pi_\theta\) (the LLM), reference \(\pi_{\text{ref}}\), prompt \(x\), reward function \(R\), length limit \(T_{\max}\)
  2. \(s_0 \leftarrow x\); \(t \leftarrow 0\) // the start state is the rendered prompt
  3. repeat:
  4.   sample \(a_t \sim \pi_\theta(\cdot \mid s_t)\); store \(\log \pi_\theta(a_t \mid s_t)\) and \(\log \pi_{\text{ref}}(a_t \mid s_t)\) // action and its log-probs
  5.   \(s_{t+1} \leftarrow s_t \oplus a_t\); \(t \leftarrow t + 1\) // deterministic transition (63.6)
  6. until \(a_{t-1}\) is the end-of-turn token or \(t = T_{\max}\) // terminal state
  7. \(y \leftarrow (a_0, \dots, a_{t-1})\); score it once: \(R(x, y)\) // sparse reward (63.8)
  8. per-token rewards \(r_k \leftarrow -\beta(\log \pi_\theta - \log \pi_{\text{ref}})_k\), and add \(R(x, y)\) to the last one // (63.10)
  9. return tokens, log-probs, rewards
Algorithm 2: the outer RL fine-tuning loop
  1. input: SFT model \(\pi_{\text{SFT}}\), prompt set \(\mathcal{D}\), reward function \(R\)
  2. \(\pi_\theta \leftarrow \pi_{\text{SFT}}\); \(\pi_{\text{ref}} \leftarrow\) frozen copy of \(\pi_{\text{SFT}}\)
  3. for each iteration:
  4.   draw a batch of prompts from \(\mathcal{D}\); for each, run Algorithm 1 (often several times) // on-policy data
  5.   turn rewards into returns (63.2), and returns into advantages // next sessions: baselines, GAE, group means
  6.   update \(\theta\) to raise the log-probs (63.7) of tokens with positive advantage and lower the others // REINFORCE, PPO, GRPO
  7.   log the mean reward, the KL to \(\pi_{\text{ref}}\), the answer length and a few sample answers // watch for reward hacking
  8. return \(\pi_\theta\)

The PyTorch code below builds all the pieces for a tiny model: an environment with a verifier, a rollout, the check that (63.7) matches a teacher-forced forward pass, returns with a discount, the per-token KL reward (63.10), a Monte Carlo estimate of \(J\) (63.3), and the SFT and RL gradients of (63.13). It runs on a CPU in about a second and prints the same numbers every time.

import copy, torch, torch.nn.functional as F
torch.manual_seed(0)

# 1) a tiny "LLM": vocabulary of digits plus an end token; it reads the last token
VOCAB = list("0123456789+=") + ["<eos>"]
ID = {t: i for i, t in enumerate(VOCAB)}
EOS, V = ID["<eos>"], len(VOCAB)

class TinyPolicy(torch.nn.Module):
    def __init__(s, d=16):
        super().__init__()
        s.emb, s.rnn, s.head = torch.nn.Embedding(V, d), torch.nn.GRU(d, d, batch_first=True), torch.nn.Linear(d, V)
    def forward(s, ids):                         # ids: (B, T) -> logits (B, T, V)
        h, _ = s.rnn(s.emb(ids))
        return s.head(h)

policy = TinyPolicy()
ref = copy.deepcopy(policy).eval()                # frozen reference policy (the SFT model)

# 2) the environment: state = prompt + text so far, action = next token
def reward_fn(text):                              # a verifier: reward only at the very end
    return 1.0 if text == "5" else 0.0            # the question is "2+3="

def rollout(prompt, max_new=4, gen=None):
    state = [ID[c] for c in prompt]               # s_0 = the prompt
    actions, logps = [], []
    for t in range(max_new):
        logits = policy(torch.tensor([state]))[0, -1]
        dist = torch.distributions.Categorical(logits=logits)       # pi_theta(. | s_t)
        a = torch.multinomial(dist.probs, 1, generator=gen).item()  # action a_t
        actions.append(a); logps.append(dist.log_prob(torch.tensor(a)))
        state = state + [a]                       # deterministic transition (63.6)
        if a == EOS: break                        # terminal state: the episode ends
    text = "".join(VOCAB[a] for a in actions if a != EOS)
    T = len(actions)
    rewards = [0.0] * (T - 1) + [reward_fn(text)]                   # sparse reward (63.8)
    return state, actions, torch.stack(logps), rewards

gen = torch.Generator().manual_seed(1)
state, actions, logps, rewards = rollout("2+3=", gen=gen)
print([VOCAB[a] for a in actions], rewards)       # ['0', '1', '0', '<eos>'] [0.0, 0.0, 0.0, 0.0]

# 3) the log-probability of the whole answer is the sum over tokens (63.7)
prompt_len = 4
with torch.no_grad():
    lp_all = F.log_softmax(policy(torch.tensor([state[:-1]]))[0], -1)
    tok_lp = lp_all[prompt_len - 1:].gather(1, torch.tensor(actions)[:, None]).squeeze(1)
print(torch.allclose(tok_lp, logps.detach(), atol=1e-6), round(tok_lp.sum().item(), 4))  # True -9.989

# 4) returns with a discount, and per-token rewards with a KL penalty (63.2, 63.10)
def returns(r, gamma=1.0):
    G, out = 0.0, []
    for x in reversed(r):
        G = x + gamma * G; out.append(G)
    return out[::-1]
print([round(g, 3) for g in returns([0, 0, 0, 1.0], 0.9)])      # [0.729, 0.81, 0.9, 1.0]
with torch.no_grad():
    ref_lp = F.log_softmax(ref(torch.tensor([state[:-1]]))[0], -1)[prompt_len - 1:]
    ref_tok = ref_lp.gather(1, torch.tensor(actions)[:, None]).squeeze(1)
beta = 0.1
shaped = (-beta * (tok_lp - ref_tok)).tolist(); shaped[-1] += rewards[-1]
print([round(x, 3) + 0.0 for x in shaped])         # [0.0, 0.0, 0.0, 0.0]: policy == ref, no KL yet

# 5) the RL objective J = E[R], estimated by sampling many episodes (63.3)
gen = torch.Generator().manual_seed(2)
with torch.no_grad():
    Rs = [rollout("2+3=", gen=gen)[3][-1] for _ in range(2000)]
print("J estimate:", sum(Rs) / len(Rs))            # J estimate: 0.01 (the reward is very sparse)

# 6) SFT versus RL on six whole answers: the gradients point to different places (63.13)
logits = torch.tensor([0.5, 0.2, -0.5, 1.0, 0.8, 0.3], requires_grad=True)
R = torch.tensor([1., 1., 1., 0., 0., 0.])          # answers 0, 1, 2 are correct
g_sft, = torch.autograd.grad(torch.log(logits.softmax(-1)[2]), logits)   # copy demonstration 2
g_rl, = torch.autograd.grad((logits.softmax(-1) * R).sum(), logits)      # raise expected reward
print([round(x, 3) for x in g_sft.tolist()])      # [-0.169, -0.125, 0.938, -0.278, -0.228, -0.138]
print([round(x, 3) for x in g_rl.tolist()])       # [0.109, 0.081, 0.04, -0.099, -0.081, -0.049]

Two outputs deserve a second look. The sampled episode got reward 0, like 99 of every 100 episodes from this untrained model: that is a sparse reward problem in miniature, and why RL starts from a model that is already good. And the last two lines are the worked example above, computed by autograd. (The tokens and numbers are from PyTorch 2.8 on a CPU; other versions may sample different tokens. [Likely])

Where this is used

SettingState and actionRewardNotes
RLHF for chat assistants (InstructGPT, many open models)prompt + text so far; next tokena learned reward model at the end, plus a per-token KL penalty (63.10)Reward hacking is the main risk; see session 67 and session 66
RL with verifiable rewards: math, code (DeepSeek-R1)prompt + reasoning so far; next token1/0 from a checker (answer match, unit tests), plus a format rewardVery sparse; works because the start model already solves some problems (session 70)
Reasoning models and test-time computelong chains of thoughtfinal-answer correctness, sometimes process rewards per stepLong episodes make credit assignment hard (session 72)
Tool use and agentsconversation + tool results; a tool call or a replytask success at the end of many turnsThe environment is no longer deterministic: tools and web pages answer back (session 154)
VLM alignment (for example RLHF-V)image tokens + prompt + text so far; next tokenhuman or model feedback on hallucinated detailsSame words, the state now contains visual tokens (session 190)
Video temporal grounding and key-moment detectionvideo tokens + question; the answer with start and end timesoverlap (IoU) between predicted and true time span, computed by a checkerA verifiable reward for video; several 2025 video-LLM papers use it with GRPO-style training [Likely] (session 205)
Video QA, action recognition and classification as textvideo tokens + question; a short label or option1 if the label matches, else 0Answers are very short, so each episode is close to a one-step bandit [Likely]
Video-RAG and retrieval agentsquestion + retrieved clips so far; a search query or the final answeranswer correctness at the endA multi-turn MDP: each retrieval is an action whose value is known only at the end [Speculation]

Common mistakes

  • Confusing reward and return. The reward is one step’s number; the return is the sum from that step to the end. With a sparse reward, most rewards are 0 but every return is the final score.
  • Thinking the environment is random for LLMs. In plain text generation the transition is deterministic (append the token). All randomness comes from sampling the policy. Tools and users bring real environment randomness back in agents.
  • Using greedy decoding for rollouts. RL needs samples from \(\pi_\theta\) itself (temperature 1, no top-k tricks), or the log-probs in (63.7) do not describe how the data was produced. If you change the sampling, account for it. [Likely]
  • Discounting by habit. A \(\gamma\) like 0.99 copied from game RL quietly gives the first tokens of a long answer much less credit (0.135 after 200 tokens). LLM setups usually use \(\gamma = 1\).
  • Forgetting the end-of-turn token in the episode. It is an action too. If its log-prob is left out, the model gets no signal about when to stop, and answer length drifts.
  • Treating the reward model as the truth. It is a proxy. A rising reward with a fast-rising KL, or answers that get longer and stranger, usually means reward hacking. Read samples.
  • Starting RL from a model that never succeeds. If the reward is 0 in nearly every episode, there is no signal (the code’s \(J \approx 0.01\)). Start from a good SFT model, or make the tasks easier first.
  • Expecting RL to add knowledge. RL re-weights answers the model can already produce; it is weak at teaching facts the model has never seen. [Likely]

Interview questions

Define agent, environment, state, action, reward, return and episode for an LLM.basic
The agent is the LLM; its softmax over the vocabulary is the policy. The state is the prompt plus all tokens generated so far. An action is the next token. The environment appends that token (a deterministic transition) and, when the answer ends, scores it with a reward model or a checker. The reward is usually 0 for every token except the last, where it is the score of the whole answer. The return of a token is the sum of rewards from it to the end, so with a sparse reward and \(\gamma = 1\) it equals the final score. An episode is one full answer, from the prompt to the end-of-turn token or the length limit.
What is the difference between reward, return and value?basic
The reward \(r_t\) is the number received after one action. The return \(G_t = \sum_{k \ge t} \gamma^{k-t} r_k\) is the total (discounted) reward from step \(t\) to the end of one particular episode: it is observed after the episode. The value \(V^\pi(s)\) is the expected return from state \(s\) under policy \(\pi\): a prediction averaged over all episodes that could follow. For an LLM: the reward is 0 or 1 at the end, the return of every token in a correct answer is 1, and the value of a half-written answer is the probability that it ends up correct.
Why is the log-probability of an answer a sum over tokens, and why does RL care?core
The transitions are deterministic, so the trajectory probability is just the product of the policy probabilities of the chosen tokens: \(\pi_\theta(y \mid x) = \prod_t \pi_\theta(y_t \mid x, y_{\lt t})\), and the log is a sum (63.7). RL updates need \(\nabla \log \pi_\theta(y \mid x)\) (63.12), so this sum is what every RL trainer computes, with one teacher-forced forward pass. The same sum, applied to the reference model, gives the KL penalty of the whole answer and lets it be split per token (63.10). In general MDPs the trajectory probability also includes environment transition probabilities, but they do not depend on \(\theta\) and drop out of the gradient.
Is RLHF a full RL problem or a bandit?core
Both views are used. At the token level it is an MDP: states are prefixes, actions are tokens, the transition appends the token, and the reward comes at the end. At the answer level it is a contextual bandit: the context is the prompt, the action is the whole answer, and the episode has one step; there are no state transitions between prompts. InstructGPT describes its environment as a bandit environment. The token view allows per-token credit (a value model, as in PPO); the answer view gives the same advantage to every token (as in REINFORCE-style methods and GRPO). The objective is the same.
What is a sparse reward, and what two problems does it cause?core
A sparse reward is zero at almost every step; for LLMs it is nonzero only at the last token of the answer (63.8). Problem 1, credit assignment: every token of the answer sees the same return, so training cannot tell from one episode which token was good or bad; it must compare many episodes (baselines, advantages, value functions). Problem 2, exploration: if the model rarely succeeds, almost all rewards are 0 and the gradient carries almost no information. Fixes include starting from a good SFT model, easier curricula, several samples per prompt, and denser signals such as process rewards (which are costly and can be hacked).
Why do RLHF setups usually use \(\gamma = 1\)?core
Discounting exists to keep returns finite in infinite tasks and to prefer quick rewards. LLM episodes are finite, and the score judges the whole answer, so there is no reason to prefer the last tokens. With \(\gamma \lt 1\) and a reward only at the end, the return of token \(t\) is \(\gamma^{T-1-t} R\): after 200 tokens at \(\gamma = 0.99\) the first token gets 0.135 of the credit. Long reasoning answers would be hurt the most. (PPO’s GAE also has a separate parameter \(\lambda\) that trades bias for variance; that is a different knob, covered in the session on GAE.)
Why add a KL penalty to the reference model, and why is it per token?core
The reward model is a learned proxy with blind spots; a policy optimized freely against it drifts to strange text that scores high (reward hacking) and can lose fluency and general skills. The penalty \(\beta \log(\pi_\theta/\pi_{\text{ref}})\) keeps the policy near the SFT model, where the reward model is reliable. It can be per token because the log-ratio of the whole answer is a sum of per-token log-ratios (63.7), so it becomes a dense reward term (63.10) added to the sparse final score. Summed over the answer it recovers InstructGPT’s objective.
Why do RL at all, if SFT already works?basic
SFT copies demonstrations: its quality is capped by the data, including the data’s mistakes, and it can only say “more of this”. RL learns from a score of the model’s own samples: it can use signals that are easy to check but hard to demonstrate (a math checker, unit tests, human comparisons), it pushes bad answers down as well as good answers up, and it trains on the model’s own text, which reduces exposure bias. The costs: generation inside training, noisy gradients, reward hacking, and less diversity. So the usual recipe is SFT first, then RL.
Write the SFT and RL gradients side by side. How is SFT a special case of RL?advanced
\(\nabla J_{\text{SFT}} = \E_{\mathcal{D}}[\nabla \log \pi_\theta(y^\star \mid x)]\) and \(\nabla J_{\text{RL}} = \E_{y \sim \pi_\theta}[R(x, y)\nabla \log \pi_\theta(y \mid x)]\) (63.12). With the copy reward \(R = \mathbb{1}[y = y^\star]\), \(J_{\text{RL}} = \pi_\theta(y^\star \mid x)\) and \(\nabla J_{\text{RL}} = \pi_\theta(y^\star \mid x)\nabla \log \pi_\theta(y^\star \mid x)\). So the SFT gradient equals the RL gradient for the copy reward divided by \(\pi_\theta(y^\star \mid x)\). The division matters: the demonstration is evaluated directly instead of waiting for the policy to sample it, which for long answers would essentially never happen. This is why SFT is sample-efficient and RL is not, and why RL needs a starting policy that already samples good answers.
In a softmax bandit, what is the exact policy gradient, and what does it do to diversity?advanced
With \(p = \softmax(z)\) and \(J = \sum_i p_i R_i\), \(\partial J / \partial z_i = p_i (R_i - J)\) (63.13). Every answer better than the mean goes up, every worse answer goes down, and the step for an answer is scaled by its current probability. Among equally good answers, the one the model already likes most grows fastest (“rich get richer”), so the policy concentrates: in Figure 6 the entropy falls from 2.45 to 0.79 bits in 100 steps although three answers are equally correct. Real RL for LLMs shows similar loss of diversity, which is one reason for the KL term and for entropy monitoring. [Likely]
What is exposure bias, and how does RL address it?advanced
In SFT (teacher forcing), the model always conditions on the demonstrator’s prefix. At inference it conditions on its own prefix, which may contain small errors it never saw during training; errors can then compound. RL samples from the model, so the states it trains on are exactly the states it visits at inference, including after its own mistakes, and the reward tells it which continuations recover. In RL words, SFT is off-policy imitation on the expert’s state distribution, and RL is on-policy learning on the agent’s own. [Likely] The vocabulary of on- and off-policy is covered in session 71.

Exercises

  1. A prompt has 30 tokens and the model writes an answer of 12 tokens, the last one being the end-of-turn token. How many actions are in the episode? What is \(s_0\), and how many tokens does \(s_{12}\) contain?
  2. The sampled tokens of a 3-token answer have probabilities 0.5, 0.8 and 0.9. Compute \(\log \pi_\theta(y \mid x)\) and \(\pi_\theta(y \mid x)\).
  3. An answer of 50 tokens gets \(R = 1\) at the end, and nothing else. Give the return of the first token for \(\gamma = 1\) and for \(\gamma = 0.98\).
  4. A 3-token answer has log-ratios \(\log \pi_\theta/\pi_{\text{ref}} = 0.5, 0.1, -0.2\), \(\beta = 0.2\) and final score \(R = 2\). Write the per-token rewards (63.10) and the returns with \(\gamma = 1\).
  5. Three answers have probabilities \(p = (0.5, 0.3, 0.2)\) and rewards \(R = (0, 1, 1)\). Compute \(J\) and the RL gradient (63.13) with respect to the logits. Then compute the SFT gradient for demonstration 3.
  6. A model’s vocabulary has 50,257 tokens (GPT-2). Roughly how many possible answers of exactly 100 tokens are there? Give the power of 10.
  7. In Figure 2 (token toy, \(\tau = 1\), \(\gamma = 1\)) one return has standard deviation \(\sigma = 0.443\). About how many episodes do you need for a typical error of 0.01 in \(\hat J\)? Check it with Turbo.
Answerscheck
1. 12 actions (one per generated token, the end-of-turn token included). \(s_0\) is the 30-token prompt; \(s_{12}\) has \(30 + 12 = 42\) tokens and is terminal. 2. \(\log 0.5 + \log 0.8 + \log 0.9 = -0.693 - 0.223 - 0.105 = -1.022\); \(\pi = 0.5 \times 0.8 \times 0.9 = 0.36\). 3. \(\gamma = 1\): 1. \(\gamma = 0.98\): \(0.98^{49} = 0.372\). 4. Rewards: \(-0.2 \times 0.5 = -0.10\), \(-0.2 \times 0.1 = -0.02\), \(-0.2 \times (-0.2) + 2 = 2.04\). Returns: \(G_2 = 2.04\), \(G_1 = 2.02\), \(G_0 = 1.92\) (check: \(2 - 0.2 \times 0.4 = 1.92\)). 5. \(J = 0.3 + 0.2 = 0.5\). RL gradient: \(0.5(0 - 0.5) = -0.25\), \(0.3(1 - 0.5) = 0.15\), \(0.2(1 - 0.5) = 0.10\); it sums to 0. SFT for demo 3: \((-0.5, -0.3, 0.8)\): it also pushes down the correct answer 2. 6. \(50{,}257^{100} = 10^{100 \log_{10} 50257} \approx 10^{470.1}\). 7. By (63.4) the typical error is \(\sigma/\sqrt{N}\), so \(N \approx (0.443/0.01)^2 \approx 1{,}960\): about 2,000 episodes. Halving the error to 0.005 needs four times as many, about 7,900. This slow \(1/\sqrt{N}\) rate is why RL for LLMs needs so many samples.

Key takeaways

  • RL words: an agent with a policy acts in an environment; states, actions and rewards form a trajectory (63.1); the return (63.2) sums future rewards; the goal is the expected return (63.3); value and advantage (63.5) are predictions of it.
  • For an LLM: state = prompt + text so far, action = next token, policy = the LLM, transition = append the token (63.6). The answer’s log-probability is a sum of token log-probabilities (63.7).
  • The same problem is a token-level MDP or an answer-level contextual bandit; RLHF is usually described as a bandit with a per-token KL penalty.
  • Rewards are sparse: one score at the end (63.8). This makes credit assignment and exploration hard; \(\gamma = 1\) is the usual choice, and a per-token KL term (63.10) keeps the policy near the reference against reward hacking.
  • SFT copies a fixed dataset; RL raises the expected score of the model’s own samples (63.11, 63.12), can push bad answers down, and is not capped by the demonstrations. It costs generation, noisy gradients and diversity, so it comes after SFT.

Key formulas

\[ G_t = \sum_{k=t}^{T-1} \gamma^{k-t} r_k, \qquad J(\theta) = \E_{\tau \sim \pi_\theta}[G_0], \qquad \log \pi_\theta(y \mid x) = \sum_{t} \log \pi_\theta(y_t \mid x, y_{\lt t}) \]
\[ r_t = -\beta \log \frac{\pi_\theta(a_t \mid s_t)}{\pi_{\text{ref}}(a_t \mid s_t)} + \mathbb{1}[t = T-1]\, R(x, y), \qquad \nabla J_{\text{RL}} = \E_{y \sim \pi_\theta}\big[R(x, y)\, \nabla \log \pi_\theta(y \mid x)\big] \]

References for this session

  1. Sutton & Barto, Reinforcement Learning: An Introduction, 2nd ed., chapter 1: Introduction
  2. OpenAI (Achiam) (2018). Spinning Up in Deep RL
  3. Lambert (2025). Reinforcement Learning from Human Feedback (book)
  4. Sutton & Barto, Reinforcement Learning: An Introduction, 2nd ed., chapter 1: Introduction
  5. OpenAI (Achiam) (2018). Spinning Up in Deep RL
  6. Lambert (2025). Reinforcement Learning from Human Feedback (book)
  7. Ouyang et al. (2022). Training language models to follow instructions with human feedback
  8. DeepSeek-AI (2025). DeepSeek-R1: Incentivizing Reasoning Capability in LLMs via Reinforcement Learning
  9. Christiano et al. (2017). Deep Reinforcement Learning from Human Preferences
  10. Jurafsky & Martin, Speech and Language Processing, 3rd ed. draft, chapter 8: Post-training
  11. Noyan, Farré, Marafioti, Zohar, Vision Language Models (O’Reilly, 2026), chapter 5: Post-Training Vision Language Models