M4-T3 — Value Functions and the Bellman Equations

Learning objectives

After this lesson, you should be able to:

• Define V^π(s) and Q^π(s, a) and the optimal functions V* and Q*.
• Write and apply the Bellman expectation and optimality equations, including for a stochastic transition.
• Perform policy evaluation and greedy improvement on a small MDP by hand.
• Use the Bellman residual to check a value function, and explain why Q is useful when the model is unknown.

The intuition

Stand in a cell of the ward and ask: if Scout follows its current policy from here, how much discounted reward will it collect on average? That average is the value of the cell. Cells close to the pharmacy door, with no hazard in between, have high value; cells next to the stairwell edge have lower value because of the chance of falling.

The value of a cell is not mysterious. One step of reward, plus the discounted value of wherever the step lands, averaged over the possible landings. Compute that in every cell at once and you have a system of equations, one per state, which is the Bellman equation. If the values are right, the equations balance; if they are wrong, they do not, and the mismatch (the residual) tells you how wrong. Sweeping the equations over and over is how the values are found (lesson M4-T4).

A second quantity, Q, attaches the number to a state and a first action: “the value of taking this action here, then following the policy”. Compare the Q numbers of the four actions in a cell and the best one is the action to take. The figure shows a tiny chain where we can do all of this with a pencil.

The mathematics

State and action values

For a policy π, the state-value function is the expected return from s when following π, and the action-value function is the expected return from s when taking a first and following π afterwards:

The optimal values are the best that any policy can do: V*(s) = max_π V^π(s), and Q*(s, a) = max_π Q^π(s, a). For terminal states V = 0.

Bellman expectation equation

Split the return into the first reward and the rest, G_t = r_t + γ G_t+1, and take expectations:

π(a | s)

Probability the policy picks a in s (1 for the chosen action if deterministic)

P(s′ | s, a)

Transition probability of lesson M4-T1

R(s, a, s′)

Reward of that transition; for a terminal s′, the term γ V(s′) is 0

[ … ]

One-step backup: immediate reward plus discounted value of the next state

For a fixed π this is a linear system with one unknown per state, solved exactly by a matrix inverse or approximately by sweeping.

Bellman optimality equation

The optimal values choose the best action instead of averaging over the policy:

The max makes this system non-linear, so it is solved by iteration rather than by one matrix inverse. Once V* or Q* is known, an optimal policy is greedy: π*(s) = argmax_a Q*(s, a). With V* alone you need the model to compute the Q* inside the argmax.

Policy evaluation and improvement

1. Evaluate. For the current policy π, solve the expectation equation for V^π and Q^π.
2. Improve. Make the new policy greedy with respect to Q^π: π′(s) = argmax_a Q^π(s, a).
3. Repeat until the policy stops changing. Each improvement is at least as good as the one before it, and in a finite MDP the process ends at an optimal policy (the policy improvement theorem; Sutton and Barto, Chapter 4).

The Bellman residual

Given any candidate V, compute the right-hand side of the optimality equation, (TV)(s), and compare:

A residual of 0 means V satisfies the equation, so V = V*. A small residual means V is close: for γ < 1 the distance to V* is at most residual / (1 − γ) (a standard consequence of T being a γ-contraction; Puterman, 1994). This is the stopping rule used in practice, and a handy test for a buggy implementation.

Why Q when the model is unknown

To act greedily from V you need Σ_s′ P(s′ | s, a) [R + γ V(s′)], which requires P. To act greedily from Q you only need to compare |A| numbers stored for the current state. And Q can be updated from sampled transitions (s, a, r, s′) alone, because the expectation over s′ is replaced by one sample (lessons M4-T5 and M4-T6). So Q is what a model-free learner stores. The price is |S| × |A| numbers rather than |S|.

A worked example

A three-state chain, by hand. States s1 and s2 and a terminal goal. γ = 0.9. Two actions in each non-terminal state. Careful is deterministic: it advances to the next state and pays −2 (so arriving at the goal pays −2 + 10 = 8). Fast advances with probability 0.8 and stays with probability 0.2, paying −1 each step (arriving pays −1 + 10 = 9). This is a tiny model of a robot that can rush at some risk of a delay or go slowly and surely.

Step 1: evaluate the “always careful” policy. Using the expectation equation from the end: V(s2) = 8, V(s1) = −2 + 0.9 × 8 = 5.2.

Step 2: improve. Compute Q for the other action using these values. Q(s2, fast) = 0.8 × 9 + 0.2 × (−1 + 0.9 × 8) = 7.2 + 0.2 × 6.2 = 8.44, which beats 8. Q(s1, fast) = 0.8 × (−1 + 0.9 × 8) + 0.2 × (−1 + 0.9 × 5.2) = 0.8 × 6.2 + 0.2 × 3.68 = 4.96 + 0.736 = 5.696, which beats 5.2. The greedy policy is “fast” in both states.

Step 3: re-evaluate. For “always fast”, the equation for s2 contains V(s2) itself because of the 0.2 chance of staying: V(s2) = 0.8 × 9 + 0.2 × (−1 + 0.9 V(s2)). Collect terms: V(s2) × (1 − 0.18) = 7.2 − 0.2 = 7.0, so V(s2) = 7.0 / 0.82 = 8.5366. Then V(s1) × 0.82 = 0.8 × (−1 + 0.9 × 8.5366) − 0.2 = 0.8 × 6.6829 − 0.2 = 5.1463, so V(s1) = 6.2760.

Step 4: check optimality. Now Q for the alternative: Q(s2, careful) = 8 < 8.5366, and Q(s1, careful) = −2 + 0.9 × 8.5366 = 5.6829 < 6.2760. No state wants to switch, so “always fast” is optimal and V* = (6.276, 8.537). A policy iteration loop reached it in two improvements.

Residual check on the chain. Start from V = (0, 0). The optimality backup gives (−1, 8), so the residual is 8. After the exact V* = (6.276, 8.537), backing up gives back (6.276, 8.537): residual 0.

Scout’s ward. With slip 0.2, the standard rewards and γ = 0.95 (lesson M4-T1), value iteration from V = 0 takes 35 sweeps to a maximum change below 10⁻⁹, and gives V*(start) = 3.3137. The maximum change per sweep shrinks as the contraction predicts: 7.90 (sweep 1), 5.99 (sweep 2), 2.15 (sweep 5), 1.11 (sweep 10), 0.060 (sweep 20), 2.2 × 10⁻⁶ (sweep 35). The Bellman residual of V = 0 is 7.90 (the largest one-step backup, in a cell next to the door, is 7.9); the residual of the converged V is 2.6 × 10⁻¹⁰.

The Bellman equation, checked at one cell. The optimal action at the start is “right” (lesson M4-T1, transition row 0.8 / 0.1 / 0.1). With V*(1,2) = 3.7043, V*(2,1) = 2.9857 and V*(1,1) = 3.3137:

which equals V*(start): the equation balances. The four action values at the start are up 3.085, right 3.314, down 2.836 and left 3.017. Notice that “left” (into the wall) is not far behind “up”: both mostly bump and wait. A policy that picks uniformly among the four actions has V(start) = −2.071, which is the expected return of a random walk, discouragingly far from 3.314.

What the simulation simplifies. These are exact, small, tabular computations in a known model. In a real task the transition model is unknown, the state space is far too large to tabulate, and V has to be approximated (module 6). The equations still hold; what fails is the ability to evaluate them exactly.

Engineering implications and limitations

Use the residual as a unit test

If your value iteration returns V, compute the optimality backup of V once and print the largest difference. Anything above your tolerance is a bug: a terminal state not held at 0, a missed done flag, a probability row that does not sum to 1. Lab M4-L1 grades the solver this way and lab M4-L4 shows the same bugs inside Q-learning.

Inspect Q gaps, not only the greedy action

Print the four Q values of a few cells. Near-ties explain why a policy flips with small changes and why the greedy action sometimes looks odd (waiting in front of a hazard in lesson M4-T2).

Choose V or Q on purpose

Planning with a known model can use V. Learning from experience uses Q, or V together with a model. Remember the memory cost: a Q table for a 100 × 100 grid with 4 actions is 40,000 numbers.

Watch the stopping rule

Stop on a small residual, not on a fixed number of sweeps: the ward needs 35 sweeps at γ = 0.95 and about 190 at γ = 0.99 for a tight tolerance, and a hard-coded 5 would return values that are not even close.

Common misconceptions

Engineering takeaways

1. V^π(s) is the expected return from s under π; Q^π(s, a) adds a free first action; V* and Q* are the best over all policies.
2. The Bellman expectation equation says V^π(s) is the policy-averaged one-step reward plus γ times the value of the next state; the optimality equation replaces the average over actions by a max.
3. Policy iteration alternates evaluation and greedy improvement; on the chain it reached V* = (6.276, 8.537) in two steps.
4. The Bellman residual measures how far a value function is from satisfying the optimality equation; the ward’s converged V*(start) = 3.314 has residual 2.6 × 10⁻¹⁰ after 35 sweeps.
5. Q stores one number per state-action pair, so a greedy action needs no model: that is why model-free methods learn Q.

References and further reading

Chapter 3 of the textbook defines value functions and the Bellman equations, and Chapter 4 covers policy evaluation, improvement and iteration (I am sure of these chapter titles; section numbers are not cited). The monograph proves the contraction property.

• R. S. Sutton and A. G. Barto, Reinforcement Learning: An Introduction, 2nd ed., MIT Press, 2018, Chapters 3 and 4.
• M. L. Puterman, Markov Decision Processes: Discrete Stochastic Dynamic Programming, Wiley, 1994.

Knowledge check

Three conceptual questions. Write an answer, then reveal the explanation. Your answers stay in your browser.

What’s next

Next: dynamic programming, which turns the Bellman optimality equation into value iteration and shows why it converges.

Related content

Nothing below is required to finish this lesson.

• Before
  M4-T2: Returns and Discounting

  Compute discounted returns, choose a discount factor for a task horizon, and explain what it does to behaviour.

• Lab
  M4-L1: Solve an MDP by Value Iteration

  Plan Scout's route through a hospital grid with slippery floors by computing optimal values and the greedy policy.