Bellman Equations and Dynamic Programming

Definition

The Bellman equations break the value of a state into two parts: the immediate reward, plus the discounted value of the next state. They express the value of being somewhere in terms of the value of where you go next. Nearly all of reinforcement learning is built on them.

In simple words

How good is your position in Ludo? It's whatever you get on your next move, plus how good the place you land in is. You don't need to imagine the whole game: just one step and an estimate of the rest. Apply that everywhere, and all the values become consistent.

Why it matters

This turns an endless sum of future rewards into a simple step-by-step update. Value iteration, Q-learning, SARSA and deep Q-networks all come directly from these equations.

How it works

Function	Question it answers
Vπ(s)	How good is state s, if I follow policy π?
Qπ(s, a)	How good is taking action a in state s, then following π?
V*(s)	The value of s under the best possible policy

The expectation equation describes a given policy, averaging over its actions. The optimality equation describes the best policy, taking the maximum over actions. That max is the only real difference.

The maths

Bellman expectation equation

V^{π} (s) = a \sum π (a ∣ s) s^{'} \sum P (s^{'} ∣ s, a) [r + γ V^{π} (s^{'})]

$π (a ∣ s)$: The chance the policy picks action a in state s
$P (s^{'} ∣ s, a)$: The chance of landing in s′
$r$: The reward for that step
$γ$: The discount factor

Bellman optimality equation

V^{*} (s) = a max s^{'} \sum P (s^{'} ∣ s, a) [r + γ V^{*} (s^{'})]

Optimality for action values

Q^{*} (s, a) = s^{'} \sum P (s^{'} ∣ s, a) [r + γ a^{'} max Q^{*} (s^{'}, a^{'})]

A corridor: A → B → Goal. Moving into Goal gives a reward of 10, and other moves give 0. γ = 0.9. Goal's value is 0, as nothing follows it.

V(B) = 10 + 0.9 × V(Goal) = 10 + 0 = 10
V(A) = 0 + 0.9 × V(B) = 0.9 × 10 = 9

In code

Value iteration applies the optimality equation repeatedly, until the values stop changing.

value_iteration.py

gamma = 0.9
states = ["A", "B", "C", "Goal"]
moves = {"A": ["B"], "B": ["A", "C"], "C": ["B", "Goal"], "Goal": []}
reward = lambda to: 10 if to == "Goal" else 0

V = {s: 0.0 for s in states}
for sweep in range(1, 100):
    change = 0.0
    for s in states:
        if not moves[s]:
            continue
        best = max(reward(next_s) + gamma * V[next_s] for next_s in moves[s])
        change = max(change, abs(best - V[s]))
        V[s] = best
    if change < 1e-6:
        print("Converged after", sweep, "sweeps")
        break

print({s: round(v, 2) for s, v in V.items()})

Output

Converged after 4 sweeps
{'A': 8.1, 'B': 9.0, 'C': 10.0, 'Goal': 0.0}

Common mistakes

Giving the terminal state a future value. Nothing follows it, so it adds no future reward.
Setting γ = 1 in a task that never ends. The total can grow without limit.

Check yourself

1. What separates the optimality equation from the expectation one?

2. V(next) = 20, reward = 5 and γ = 0.5. What's the value of this state?

Summary

Value = reward now + discounted value of what's next.
Expectation for a given policy, and optimality with a max for the best one.
Value iteration and Q-learning come directly from them.

Finished reading?

Sources: Sutton & Barto, Reinforcement Learning: An Introduction