Value functions & Bellman equations

Chapter 01 gave you the object \(\mathcal{M}=(S,A,P,R,\gamma)\) and the goal \(\max_\pi \mathbb{E}_\pi[G_0]\). To optimize that goal you need a measuring stick: for each situation, how much return should you expect?

That measuring stick is a value function. Once values exist, a remarkable algebraic fact appears: they satisfy a self-consistency equation — Bellman’s equation — relating the value at \(s\) to values at successors \(s'\). Dynamic programming (next chapter) iterates that equation. Temporal-difference learning estimates it from samples. Q-learning replaces expectation over \(\pi\) by a \(\max\). Policy gradients still use values (or advantages) as critics. The entire stack hangs on this chapter.

There is nothing mystical in the recursion. It is simply \(G_t = r_{t+1} + \gamma G_{t+1}\) after taking expectations. Memorize that one-line unrolling; every formula below is bookkeeping around it.

Both are functions of the policy: change \(\pi\), change the values. We write \(V^*\) and \(Q^*\) for values of an optimal policy \(\pi^*\). Because an optimal deterministic policy exists in finite discounted MDPs (Chapter 01, Theorem 7.1), these are well-defined and attained.

Intuition check: \(V^{\pi}(s)\) answers “how good is it to be here if I behave like \(\pi\)?” while \(Q^{\pi}(s,a)\) answers “how good is it to try \(a\) right now, then behave like \(\pi\)?” The second question is what you need to improve a policy: compare actions without resimulating whole futures by hand.

Averaging the Q-function under the policy’s action distribution recovers \(V\):

Conversely, one-step expansion of \(Q\) yields

where \(\mathcal{R}(s,a)=\sum_{s'}P(s'\mid s,a)R(s,a,s')\) as in Chapter 01. Equations (1)–(2) together say: values of states and state–actions are two views of the same expected return, linked by one application of \(\pi\) or \(P\).

Substitute (2) into (1), or expand \(G_t\) directly (Section 5). The Bellman expectation equation for \(V^{\pi}\) is

Read left to right:

1. Average over the action the policy would take.
2. Average over the environment’s response.
3. Each branch contributes immediate reward plus discounted value of the landing state.

The companion equation for \(Q^{\pi}\) is

Equation (3) is a linear system in the unknowns \(\{V^{\pi}(s)\}_{s\in S}\): \(|S|\) equations, \(|S|\) unknowns. For finite MDPs it has a unique solution. Policy evaluation algorithms solve that system — by matrix inversion for tiny MDPs, or by iterative backups for larger ones.

Start from the definition and the return recursion \(G_t = r_{t+1} + \gamma G_{t+1}\):

where the last step uses the law of total expectation and the fact that, given \(s_{t+1}\), the expected remaining return under \(\pi\) is exactly \(V^{\pi}(s_{t+1})\). Expand the outer expectation by enumerating \(a\) and \(s'\):

which is (3). The same argument with a fixed first action produces (4).

Optimal values satisfy a different recursion: instead of averaging over \(\pi\), take the best action. The Bellman optimality equation is

Once \(Q^*\) is known, an optimal policy is a one-liner — no further planning:

Equation (9) is the seed of greedy policy improvement, Q-learning’s target, and the “actor reads argmax of critic” design in discrete-action deep RL.

This is why “evaluate, then act greedy, repeat” is an escalator that never goes down. Chapter 03 turns the theorem into Policy Iteration. The same greedy step appears inside Value Iteration and in the target of Q-learning — only the source of \(Q\) (exact vs sampled) changes.

Define the Bellman expectation operator \(\mathcal{T}^{\pi}\) on value vectors by

Then \(V^{\pi}\) is exactly the fixed point \(V = \mathcal{T}^{\pi} V\). In the infinity norm, \(\|\mathcal{T}^{\pi} V - \mathcal{T}^{\pi} U\|_\infty \le \gamma \|V-U\|_\infty\): \(\mathcal{T}^{\pi}\) is a \(\gamma\)-contraction. By the Banach fixed-point theorem there is a unique fixed point, and iterated application converges exponentially fast with rate \(\gamma\).

The optimality operator \(\mathcal{T}^*\) (max instead of \(\pi\)-average) is likewise a \(\gamma\)-contraction; its unique fixed point is \(V^*\). This is the heavy-math guarantee behind Value Iteration. You do not need the full proof to use the algorithms — but it explains why they do not oscillate forever.

If you know \(P\), knowing \(V^*\) is enough: choose \(a\) maximizing the one-step lookahead in (7). If you do not know \(P\) (robotics, Atari, the usual RL setting), you cannot evaluate that lookahead. But if you know \(Q^*\), equation (9) needs no model — just compare numbers \(Q^*(s,\cdot)\). That is why model-free control learns \(Q\) (or a policy directly), not bare \(V\).

Actor–critic methods reintroduce \(V\) (or \(A\)) as a baseline / critic for training a separate policy network — values assist gradients; they do not replace the policy when actions are continuous.

Fix a simple policy on a 4×4 grid (no walls): always try to move toward the bottom-right goal with a little randomness. Each click applies one synchronous Bellman expectation backup \(V \leftarrow \mathcal{T}^{\pi} V\) for all states. Watch values flow backward from the goal — the contraction in Section 8 made visible.

Tiny two-state illustration. States \(\{s_0,s_G\}\) with \(s_G\) terminal, \(V(s_G)=0\). From \(s_0\), action \(g\) reaches the goal with probability \(1\) and reward \(+1\). Policy takes \(g\) always. Then

If instead the goal is reached with probability \(0.5\) and otherwise we self-loop with reward \(0\),

Solve: \(V(s_0)(1 - 0.5\gamma) = 0.5\), hence \(V(s_0) = 0.5 / (1 - 0.5\gamma)\). For \(\gamma=0.9\), \(V(s_0)\approx 0.909\). Iterative policy evaluation discovers the same number by repeating the backup without algebraically solving the linear system — that is what the laboratory is doing on a larger grid.

Dynamic Programming turns Bellman into algorithms you can run when \(P\) and \(R\) are known: Policy Iteration (evaluate → greedy improve → repeat) and Value Iteration (apply \(\mathcal{T}^*\) until convergence). Then TD learning removes the need for \(P\) itself — same backup structure, sampled successors.