CAS logo CAS RL LABLecture 03 · Bellman Equations ← Series

RL — LECTURE 03 · PREREQUISITE: LECTURE 02 (MDP) · NEXT: TEMPORAL DIFFERENCE (SARSA & Q-LEARNING)

Value Functions & Bellman Equations

“How do we measure how good a state or action is without waiting until the end of time?”

In Lecture 02 you mapped the world's transition rules using Markov Decision Processes <S, A, P, R, γ>. Today we answer the fundamental question of Reinforcement Learning: How valuable is each position? We decompose infinite futures into one immediate step plus discounted tomorrow — unlocking the recursive equations discovered by Richard Bellman.

SIX RECURSIVE CHAPTERS

One-Look Blueprint Map of Bellman Equations

01 FROM MDP PHYSICS TO VALUATION

Why knowing the map is not enough — we need a compass of value

An agent standing in a labyrinth might know every transition probability P(s'|s,a), but without knowing which state leads to long-term fortune, it is blind.

G

THE RECURSIVE RETURN DECOMPOSITION · THE SPARK OF DYNAMIC PROGRAMMING

G(t) = R(t+1) + γ · R(t+2) + γ² · R(t+3) + ... = R(t+1) + γ · G(t+1)

G(t) = Total cumulative discounted return R(t+1) = Immediate one-step payout γ = Discount patience factor G(t+1) = Everything that happens tomorrow!
INTERACTIVE SIMULATOR · STEP THROUGH RECURSIVE RETURN DECOMPOSITION
Step t = 0 γ = 0.90

02 STATE VALUES VS ACTION VALUES

“Evaluating where you are vs evaluating what you choose”

Reinforcement Learning relies on two distinct value functions. Understanding the operational difference between V and Q is the secret to understanding modern RL algorithms.

State-Value Function V_π(s)

“SITUATION VALUE”

The expected return if the agent starts in state s and follows policy π thereafter:

v_π(s) = E_π [ G(t) | S(t) = s ]

To decide which action to take using V(s), an agent must look ahead through the environment's transition probabilities P(s'|s,a).

Action-Value Function Q_π(s, a)

“CHOICE VALUE”

The expected return of taking action a in state s, and then following policy π:

q_π(s, a) = E_π [ G(t) | S(t) = s, A(t) = a ]

Because the action is already chosen, an agent can act greedily (argmax_a Q) with ZERO transition model — enabling Model-Free RL!

INTERACTIVE LENS · V(s) PLANNING VS Q(s,a) MODEL-FREE ADVANTAGE

03 BACKUP DIAGRAM TREES

The visual secret to Sutton & Barto: Lookahead Trees

Bellman equations look like intimidating algebra until you draw them as trees. Open circles are states; solid dots are actions. The math simply walks down the tree!

BACKUP TREE SWITCHER · SEE HOW INFORMATION FLOWS BACKWARD

04 BELLMAN EXPECTATION EQUATION FOR V(s)

Decomposing state value: Immediate reward + discounted neighbors

No steps skipped: watch how the expected return of state s averages across candidate actions and environment transitions.

V_π

THE COMPLETE BELLMAN EXPECTATION EQUATION FOR STATE VALUE

v_π(s) = Σ_{a} π(a|s) · Σ_{s'} P(s'|s,a) · [ R(s,a,s') + γ · v_π(s') ]

Σ_{a} π(a|s) = Average over all policy moves Σ_{s'} P(s'|s,a) = Average over environment odds R = Immediate reward earned γ v_π(s') = Discounted value of destination
STEP-BY-STEP CALCULATION BREAKDOWN · CHECK IT BY HAND
Step ComponentMathematical TermIntuitive MeaningExample Numbers
1. Policy Selection π(a|s) Probability our policy chooses action a π(Right|s) = 0.60
2. Transition Odds P(s'|s,a) Probability environment lands on s' P(East|s,Right) = 0.80
3. One-Step Reward R(s,a,s') Points awarded right now for the move R = +2.00
4. Discounted Future γ · v_π(s') Discounted value already known for s' 0.9 × 10.0 = +9.00
5. Combined Total v_π(s) Weighted average of all branches 0.6 × 0.8 × (2 + 9) = 5.28 + ...

05 BELLMAN EXPECTATION EQUATION FOR Q(s,a)

Decomposing action value: Mutual conversion between V and Q

V and Q are two sides of the same coin: V is an expectation of Q values, and Q is an expectation of V values.

Q_π

THE COMPLETE BELLMAN EXPECTATION EQUATION FOR ACTION VALUE

q_π(s, a) = Σ_{s'} P(s'|s,a) · [ R(s,a,s') + γ · Σ_{a'} π(a'|s') · q_π(s', a') ]

Σ_{s'} P(s'|s,a) = Odds of next state R = Immediate reward Σ_{a'} π(a'|s') q_π(s',a') = Exactly v_π(s')!
THE MUTUAL CONVERSION BRIDGE
From Q to V: Average across actions using policy weights:
v_π(s) = Σ_{a} π(a|s) · q_π(s, a)
From V to Q: Look ahead one step with transition physics:
q_π(s, a) = Σ_{s'} P(s'|s,a) · [ R + γ · v_π(s') ]

06 MATRIX FORM & CLOSED-FORM SOLUTION

Solving Bellman Expectation as a linear system: (I - γP)⁻¹ R

Because Bellman Expectation is linear in v, we can write all |S| equations in one matrix equation and solve it analytically in closed form!

A⁻¹

THE MATRIX EQUATION & CLOSED-FORM INVERSE

v_π = R^π + γ · P^π · v_π ⟹ (I - γ · P^π) · v_π = R^π ⟹ v_π = (I - γ · P^π)⁻¹ · R^π

I = Identity Matrix P^π = State-to-state transition matrix R^π = Expected reward vector v_π = Exact value vector
LIVE 3-STATE DELIVERY ROBOT MATRIX SOLVER γ = 0.90

1. Matrix (I - γP^π)

2. Inverted Matrix (I - γP^π)⁻¹

3. Exact Value Vector v_π

07 THE BELLMAN CONTRACTION MAPPING THEOREM

Why iterative backups always converge to the exact truth

Even if you start with wildly wrong guesses (all zeros, or +1000 everywhere), the Bellman operator acts like a mathematical magnet pulling estimates toward the unique true value vector.

||·||

BANACH FIXED-POINT THEOREM · CONTRACTION FACTOR γ

|| T(u) - T(v) ||_∞ ≤ γ · || u - v ||_∞

T = Bellman backup operator ||·||_∞ = Maximum difference across all states γ < 1 = Distance strictly shrinks by at least γ Unique fixed point guaranteed! ✓
SIMULATE ERROR SHRINKAGE OVER ITERATIONS
Initial Error Δ₀ = +20.0
WHY CONTRACTION MATTERS FOR REINFORCEMENT LEARNING

1. Immunity to Bad Initialization: You don't need a lucky guess. Initialize V(s) = 0 everywhere, and convergence is mathematically guaranteed.

2. Predictable Convergence Rate: After k iterations, maximum error is bounded by γ^k · ||v₀ - v*||.

3. Foundation of Dynamic Programming: Both Policy Evaluation and Value Iteration rely on this exact contraction property to solve MDPs.

08 BELLMAN OPTIMALITY EQUATIONS

From evaluation to control: The non-linear MAX operator

To find the best possible behavior, policy averaging π(a|s) is replaced by the max operator: what is the best move I could possibly make?

V*

THE BELLMAN OPTIMALITY EQUATIONS FOR V* AND Q*

v*(s) = max_{a} Σ_{s'} P(s'|s,a) · [ R(s,a,s') + γ · v*(s') ]

q*(s, a) = Σ_{s'} P(s'|s,a) · [ R(s,a,s') + γ · max_{a'} q*(s', a') ]

No policy π in the formula! max_{a} chooses optimal action v*(s) = max_a q*(s,a) Optimal policy: π*(s) = argmax_a q*(s,a)
WHY CANNOT WE USE MATRIX INVERSION ON BELLMAN OPTIMALITY?

Notice the max_{a} operator! In linear algebra, you cannot factor out a matrix when a max function is present: max(x₁, x₂) + max(y₁, y₂) ≠ max(x₁+y₁, x₂+y₂).

The max operator makes the Bellman Optimality Equation non-linear. Therefore, no closed-form linear matrix inversion exists! Instead, we MUST use iterative algorithms: Value Iteration and Policy Iteration.

09 3x3 GRIDWORLD VALUE ITERATION & PYTHON

Watch Bellman values ripple backward from Goal (+10) across grid cells

Step through iterative backups on our 3x3 Gridworld: observe how optimal arrows emerge naturally as values propagate!

Iteration k = 0
Grid values initialized to 0.00. Click "Step Bellman Backup" to begin.
REPRODUCIBLE PYTHON / NUMPY IMPLEMENTATION

10 REVISION & MASTERY ASSESSMENT

10 diagnostic questions to test recursive valuation intuition

Test your understanding of the recursive return, V vs Q, backup diagrams, linear systems, contraction factors, and policy extraction.

DIAGNOSTIC SCORECARD

0 / 10

LECTURE 03 SUMMARY & NEXT STEP “Bellman equations give us the exact recursive truth: any long-term valuation is one step + discounted future. But what if we don't know the environment's transition probabilities P(s'|s,a)? Next in Lecture 04, we discover Temporal Difference learning: SARSA and Q-Learning!”