1. Courses
  2. Reinforcement Learning
  3. Lecture 4
Lecture 4 of 1419 min3D modelFree lecture

Value functions and the Bellman equation

How good is it to be here? A value function answers that for every state, and the Bellman equation links each state’s value to its neighbors’. Watch value iteration spread value outward from the goal, see it as a 3D landscape, and read a policy straight off it.

In this lecture you will

  • Define state values V(s) and action values Q(s, a)
  • Write the Bellman optimality equation in words and symbols
  • Run value iteration and explain why values spread outward from rewards
  • Extract the optimal policy from a value function

In the last lecture we compared policies by simulating them. That does not scale: a problem with thousands of states and dozens of actions has more policies than atoms in the universe. We need to reason about how good each state is directly. That quantity is the value function.

How good is it to be here?

The value of a state is the return the agent can expect from that state onward, if it acts as well as possible:

V∗(s)=max⁡π  E[ rt+1+γrt+2+γ2rt+3+⋯∣st=s]V^*(s) = \max_\pi \; \mathbb{E}\left[\, r_{t+1} + \gamma r_{t+2} + \gamma^2 r_{t+3} + \dots \mid s_t = s \right]

A closely related quantity scores each action as well:

State value V(s)
Expected return from state s when acting optimally. “How good is it to be here?”
Action value Q(s, a)
Expected return after taking action a in state s, then acting optimally. “How good is this move from here?”
Optimal policy π*
In every state, choose the action with the highest Q(s, a).
Backup
Updating a value using the values of the states that follow it — information flows backwards from the future.

The Bellman equation

Richard Bellman noticed in the 1950s that values have a recursive structure. The value of a state equals the best you can do with one action — the immediate reward plus the discounted value of wherever you land:

V∗(s)=max⁡a∑s′P(s′∣s,a) [ R(s,a,s′)+γ V∗(s′) ]V^*(s) = \max_a \sum_{s'} P(s' \mid s, a)\,\big[\, R(s, a, s') + \gamma\, V^*(s') \,\big]

In a deterministic world the sum disappears: value here = best of (reward + γ × value there).

AnimationOne Bellman backup
Loading animation…
  1. How valuable is this tile?We want the value of the tile in the middle of the grid, (2,2). The Bellman equation says: look one step ahead.
  2. List the actionsFrom (2,2) the robot can try up, right, down or left.
  3. See where each leadsEach move costs −1 and lands on a tile whose value we have already estimated. Moving left hits a wall, so the robot stays on (2,2).
  4. Score every actionAn action is worth its reward plus the discounted value of where it leads: −1 + 0.9 × V(next).
  5. Keep the bestThe value of (2,2) is the best score, 4.58. Up and right tie; both are optimal. Repeating this backup for every tile is value iteration.

Value iteration

Value iteration turns the Bellman equation into an algorithm: start with all values at zero, then sweep through every state applying the backup, again and again, until nothing changes.

InteractiveValue iteration on the grid worldSweep · click a tile
Loading visual…

Colors show value: teal is good, coral is bad. The arrow on each tile is the greedy action under the current values. Click a tile to see its backup.

Press One sweep a few times. After the first sweep every tile knows only that moves cost −1, except the tiles beside the goal, which jump to +10. With each sweep, value spreads one tile further from the goal, because a tile can only become valuable once one of its neighbors is. After about eight sweeps the values stop changing: they have converged.

Then experiment:

  • Lower γ to 0.5. Distant rewards barely count, so tiles far from the goal stay negative — the agent becomes short-sighted.
  • Add slip. Tiles next to the pits lose value, and the arrows change: the robot prefers routes that keep a safe distance from the pits, even if they are longer.

Seeing values as a landscape

A value function is easiest to understand as terrain. Step through the 3D view: each column’s height is the value of that tile.

3D modelThe value function in 3DDrag to rotate
Loading 3D model…
  1. All values start at zeroBefore any backups the agent knows nothing: every tile has value 0.
  2. After one sweepEvery move costs −1, so most tiles sink slightly below the floor. The two tiles next to the goal jump to +10.
  3. After three sweepsValue is spreading from the goal, one tile per sweep. Tiles further away are still waiting for the news.
  4. ConvergedEach column now shows the best achievable return from that tile. Values fall as you move away from the goal and around the pits.
  5. The policy climbs uphillThe optimal policy is simple: from any tile, step to the highest neighboring column. The ball follows it from the start to the goal.

Why this matters beyond grid worlds

The Bellman equation is one of the most widely used ideas in computing:

  • Route planning and logistics: shortest paths are value functions where each step costs time.
  • Inventory and pricing: dynamic programming decides how much stock to hold given future demand.
  • Game-playing AI: systems such as AlphaGo combine learned value estimates with search.
  • Finance: option pricing and optimal stopping problems use backward induction — Bellman backups over time.

Key takeaways

  • V(s) is the expected return from state s when acting optimally; Q(s, a) is the expected return after taking action a first.
  • The Bellman equation says a state’s value equals the best action’s reward plus the discounted value of where it leads.
  • Value iteration applies that equation to every state repeatedly until the values stop changing.
  • Once the values are known, the optimal policy is simply to move towards the highest-valued next state.

Check your understanding

4 questions · answers explained

Q1What does V(s) represent?

A value summarizes the whole future, not just the next reward. A tile next to the goal has high value even though standing there gives no reward.

Q2A tile’s neighbors have values 6.2 (up), 3.1 (down) and 4.6 (left), and every move costs −1 with γ = 0.9. What does one Bellman backup give?

The best action is up — −1 + 0.9 × 6.2 = 4.58. The backup takes the maximum over actions of reward plus discounted next value.

Q3Why do values spread outward from the goal one tile per sweep in value iteration?

A tile can only become valuable once a neighbor is valuable. Each sweep propagates the goal’s reward one more step, until the values stop changing.

Q4How do you get the optimal policy from the optimal values?

With V* known, acting greedily with respect to a one-step lookahead is optimal — the policy climbs the value landscape.