Value and discount

A reward often arrives many steps after the choice that earned it. A value function passes some of that credit back to earlier states.

Key idea: Value function V(s), action value Q(s, a), and discount γ
Real world: A chess engine's evaluation bar. "+2.5 for white" is a value: a prediction of how the game will end from this position, long before it does.
In an LLM: PPO trains a critic that predicts the final score from every prefix of an answer. GRPO skips it (GRPO).

The idea

V(s): the expected return if you start in state s and act well from there.
Q(s, a): the same, but you must take action a first. The best action is the one with the highest Q.
γ (gamma): a reward one step later is worth γ times as much. Ten steps later, γ¹⁰.

If you knew V for every state, acting well would be easy: move toward the state with the highest value. Values turn a delayed reward into an immediate signal at every step.

example · a corridor

Four rooms in a row: A → B → C → exit. Stepping from C into the exit pays +10, every other step pays 0, and γ = 0.9.

$V(C) = 10$ : one step from the reward.
$V(B) = 0 + 0.9 \times V(C) = 9$
$V(A) = 0 + 0.9 \times V(B) = 8.1$

Now add a trap door in B that drops you into a pit worth −10. In B, the two actions are worth:

Go right: $0 + 0.9 \times 10 = 9$
Take the trap door: $-10$

$V(B)$ is the better of the two, 9, and the policy in B is "go right". Nobody told the agent that at B; it followed from the values.

Value iteration

The corridor example is the whole algorithm. Set each state's value to "best action's reward plus γ times the value of where it lands", and repeat until nothing changes.

Try it: a 6 × 5 gridworld

γ0.90step reward-0.02slip0.10

sweep 4

-0.07

0.36

0.57

0.73

0.86

goal+1

-0.07

0.36

0.65

pit−1

-0.07

0.51

0.29

-0.07

0.33

-0.07

-0.07start

-0.07

After 4 sweeps, the goal’s value has reached cells up to 4 moves away. A dot means every move still looks the same from that cell.

Numbers are V(s). Arrows are the best move. Click a cell to add or remove a wall. Slip is the chance a move goes sideways.

Learning values from experience

Value iteration needs a full map of the world: every state, every move, every outcome. Usually you don't have one. Q-learning estimates Q from experience instead. After each step it nudges the old estimate toward "the reward I just got plus the value of where I landed".

example · one Q-learning update

The agent is in B, goes right, gets reward 0 and lands in C. Its current estimates: $Q(B, \text{right}) = 5$ , and the best action in C is worth 10. The learning rate α = 0.5 sets how big a step to take, and γ = 0.9.

Target: $0 + 0.9 \times 10 = 9$
Error: $9 - 5 = 4$
New estimate: $5 + 0.5 \times 4 = 7$

Repeat this over many episodes and the estimates settle on the true values.

DQN (DeepMind, 2015) replaced the table of Q values with a neural network that reads the screen pixels, and learned to play dozens of Atari games from the score alone.

In language models

The states are every possible start of an answer (a prefix), far too many for a table. PPO trains a critic network that predicts V for every prefix of an answer. If V drops sharply after one token, that token probably caused the bad outcome. The critic is usually about as large as the model itself, which is why GRPO drops it.

example · a critic reading an answer

Prompt: "What is 17 × 6?". After each part of the answer, the critic predicts the chance it ends up correct:

Answer so far	V (predicted score)	Change
(nothing)	0.60
`17 × 6 = 17 × 5 + 17`	0.75	+0.15
`… = 85 + 17`	0.85	+0.10
`… = 112`	0.05	−0.80

The answer is wrong (17 × 6 = 102), and the reward of 0 arrives only at the end. But the critic's drop points at the exact step that went wrong: 112 gets almost all the blame, and the correct setup steps are not punished. This is the corridor example again, with prefixes of text as the rooms.

Switch between credit from the critic and no critic. Without one, every step of the wrong answer is blamed equally, including the correct setup.

Prompt: “What is 17 × 6?” The critic’s prediction after each step

Credit per step = change in V

17 × 6 = 17 × 5 + 17+0.15

= 85 + 17+0.10

= 112-0.80

The critic’s drop pins the blame on “= 112” (-0.80). The correct setup steps get small positive credit.

V is the critic’s predicted chance that the answer ends up correct. Credit is what each step gets told: positive means do more of this, negative means less.

going deeper

Bellman equations

V(s) = \max_a \sum_{s'} P(s' \mid s, a)\,\big[\, r(s, a, s') + \gamma\, V(s') \,\big]

Value iteration applies this as an update until it stops changing. "Slip" in the gridworld is $P(s' \mid s, a)$ : the chance a move lands somewhere other than intended.

Q-learning

Q(s, a) \leftarrow Q(s, a) + \alpha \Big[\, r + \gamma \max_{a'} Q(s', a') - Q(s, a) \,\Big]

The bracket is the temporal-difference (TD) error. In PPO the critic $V_\phi$ is trained by regression on returns, and advantages come from GAE: $\hat A_t = \sum_k (\gamma\lambda)^k \delta_{t+k}$ , with $\delta_t = r_t + \gamma V(s_{t+1}) - V(s_t)$ .

The idea

Value iteration

Try it: a 6 × 5 gridworld

Learning values from experience

In language models

Bellman equations

Q-learning

Related