Bellman Equations: Value as Reward Plus What Comes Next
Published:
Break a long journey into one step and the remainder
Intuition first. To estimate the cost of a journey, combine the next segment with the estimated cost from its endpoint. RL uses the same recursive structure for expected reward.
With the reward convention from the MDP chapter, return satisfies \(G_t=R_{t+1}+\gamma G_{t+1}\). Taking the expectation under a policy gives the Bellman expectation equation:
Here \(V^\pi(s)\) means expected return starting in state \(s\) and then following \(\pi\). The equation averages both the policy’s action choices and the environment’s outcomes.
Evaluation and optimisation answer different questions
Policy evaluation asks how a specified policy performs. Optimal control instead asks which action gives the highest expected continuation:
The maximum is outside the expectation over next states: the agent chooses an action before learning which stochastic outcome occurs. Moving it inside would give the agent information it does not have. Dynamic programming lecture.
Worked example: propagate the goal reward backwards
Use the chain A to B to Goal, rewards 0 then 1, and \(\gamma=0.9\). Start with all values zero and update each state from the values in the previous iteration. Terminal Goal always has value zero.
| Synchronous iteration | A | B | Goal |
|---|---|---|---|
| Initial | 0 | 0 | 0 |
| First backup | 0 | 1 | 0 |
| Second backup | 0.9 | 1 | 0 |
The first backup finds B’s immediate reward. The second transfers that information to A. Updating A before or after B in place can change intermediate numbers, so specify the update convention when comparing traces.
Now add an action at A that terminates with reward 0.5. Optimal control chooses the route through B because \(0.9>0.5\). A policy that selects each action half the time has value \(0.5(0.9)+0.5(0.5)=0.7\) at A. Evaluating that policy does not turn it into the optimal one.
Why repeated backups can converge
For a finite discounted MDP with bounded rewards and \(\gamma<1\), the exact Bellman operators contract differences in the maximum norm by at most \(\gamma\). This gives unique fixed points and convergence of repeated exact backups under the standard assumptions.
That statement does not guarantee convergence for every neural-network training procedure. Function approximation, sampled data, and changing policies introduce additional issues. Keep the exact dynamic-programming result separate from the optimisation behaviour of a deep RL implementation.
The model is doing work here
Computing the full sum requires transition probabilities and expected rewards. If those are unknown, an agent can learn from sampled transitions instead. That is the bridge to temporal-difference learning.