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.
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.
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\):
- 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:
- 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:
- 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):
- 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).
- \(s_0 \leftarrow\) start state (the prompt \(x\), or cell 3); \(t \leftarrow 0\)
- repeat:
- sample \(a_t \sim \pi(\cdot \mid s_t)\) // the policy acts
- \(r_t,\ s_{t+1} \leftarrow\) environment\((s_t, a_t)\); \(t \leftarrow t + 1\)
- until \(s_t\) is terminal or \(t = T_{\max}\)
- \(G_T \leftarrow 0\)
- for \(t = T-1\) down to 0: \(G_t \leftarrow r_t + \gamma\, G_{t+1}\) // (63.2)
- add \(G_0\) to the list; \(\hat J \leftarrow\) mean of all \(G_0\) // (63.4)
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:
- 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:
- 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:
- 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.
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.
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]
| View | State | Action | Episode length | Reward | Used by |
|---|---|---|---|---|---|
| Token-level MDP | prompt + tokens so far | one token | \(T\) steps | 0 until the end, then the score (plus per-token KL terms) | PPO-style RLHF with a value model (session 66) |
| Answer-level contextual bandit | the prompt | the whole answer | 1 step | the score of the answer | REINFORCE-style and GRPO-style methods that give one advantage to all tokens (session 70) |
| Multi-turn agent MDP | the conversation, tool results, the screen | a token, or a whole turn | many turns | at the end of the task, sometimes per turn | tool-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:
- 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:
- 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
- sample an answer \(y \sim \pi(\cdot \mid x)\), one token at a time
- \(R \leftarrow R(x, y)\); with \(\gamma = 1\), every step has \(G_t = R\) // (63.8)
- for each prefix \(s_t\) on the path: \(N(s_t) \mathrel{+}= 1\); \(S(s_t) \mathrel{+}= R\)
- \(\hat V(s_t) \leftarrow S(s_t) / N(s_t)\) // (63.9)
- \(\hat A_t \leftarrow \hat V(s_{t+1}) - \hat V(s_t)\) for each token // (63.9)
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:
- 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.
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.
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):
- 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:
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:
- 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.
- 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.
- 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]
- 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
- 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 = ?” | Reward | SFT data | Probability now |
|---|
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.
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.
- input: policy \(\pi_\theta\) (the LLM), reference \(\pi_{\text{ref}}\), prompt \(x\), reward function \(R\), length limit \(T_{\max}\)
- \(s_0 \leftarrow x\); \(t \leftarrow 0\) // the start state is the rendered prompt
- repeat:
- 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
- \(s_{t+1} \leftarrow s_t \oplus a_t\); \(t \leftarrow t + 1\) // deterministic transition (63.6)
- until \(a_{t-1}\) is the end-of-turn token or \(t = T_{\max}\) // terminal state
- \(y \leftarrow (a_0, \dots, a_{t-1})\); score it once: \(R(x, y)\) // sparse reward (63.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)
- return tokens, log-probs, rewards
- input: SFT model \(\pi_{\text{SFT}}\), prompt set \(\mathcal{D}\), reward function \(R\)
- \(\pi_\theta \leftarrow \pi_{\text{SFT}}\); \(\pi_{\text{ref}} \leftarrow\) frozen copy of \(\pi_{\text{SFT}}\)
- for each iteration:
- draw a batch of prompts from \(\mathcal{D}\); for each, run Algorithm 1 (often several times) // on-policy data
- turn rewards into returns (63.2), and returns into advantages // next sessions: baselines, GAE, group means
- update \(\theta\) to raise the log-probs (63.7) of tokens with positive advantage and lower the others // REINFORCE, PPO, GRPO
- log the mean reward, the KL to \(\pi_{\text{ref}}\), the answer length and a few sample answers // watch for reward hacking
- 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
| Setting | State and action | Reward | Notes |
|---|---|---|---|
| RLHF for chat assistants (InstructGPT, many open models) | prompt + text so far; next token | a 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 token | 1/0 from a checker (answer match, unit tests), plus a format reward | Very sparse; works because the start model already solves some problems (session 70) |
| Reasoning models and test-time compute | long chains of thought | final-answer correctness, sometimes process rewards per step | Long episodes make credit assignment hard (session 72) |
| Tool use and agents | conversation + tool results; a tool call or a reply | task success at the end of many turns | The 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 token | human or model feedback on hallucinated details | Same words, the state now contains visual tokens (session 190) |
| Video temporal grounding and key-moment detection | video tokens + question; the answer with start and end times | overlap (IoU) between predicted and true time span, computed by a checker | A 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 text | video tokens + question; a short label or option | 1 if the label matches, else 0 | Answers are very short, so each episode is close to a one-step bandit [Likely] |
| Video-RAG and retrieval agents | question + retrieved clips so far; a search query or the final answer | answer correctness at the end | A 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
What is the difference between reward, return and value?basic
Why is the log-probability of an answer a sum over tokens, and why does RL care?core
Is RLHF a full RL problem or a bandit?core
What is a sparse reward, and what two problems does it cause?core
Why do RLHF setups usually use \(\gamma = 1\)?core
Why add a KL penalty to the reference model, and why is it per token?core
Why do RL at all, if SFT already works?basic
Write the SFT and RL gradients side by side. How is SFT a special case of RL?advanced
In a softmax bandit, what is the exact policy gradient, and what does it do to diversity?advanced
What is exposure bias, and how does RL address it?advanced
Exercises
- 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?
- 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)\).
- 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\).
- 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\).
- 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.
- 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.
- 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
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
References for this session
- Sutton & Barto, Reinforcement Learning: An Introduction, 2nd ed., chapter 1: Introduction
- OpenAI (Achiam) (2018). Spinning Up in Deep RL
- Lambert (2025). Reinforcement Learning from Human Feedback (book)
- Sutton & Barto, Reinforcement Learning: An Introduction, 2nd ed., chapter 1: Introduction
- OpenAI (Achiam) (2018). Spinning Up in Deep RL
- Lambert (2025). Reinforcement Learning from Human Feedback (book)
- Ouyang et al. (2022). Training language models to follow instructions with human feedback
- DeepSeek-AI (2025). DeepSeek-R1: Incentivizing Reasoning Capability in LLMs via Reinforcement Learning
- Christiano et al. (2017). Deep Reinforcement Learning from Human Preferences
- Jurafsky & Martin, Speech and Language Processing, 3rd ed. draft, chapter 8: Post-training
- Noyan, Farré, Marafioti, Zohar, Vision Language Models (O’Reilly, 2026), chapter 5: Post-Training Vision Language Models