RL — LECTURE 03 · PREREQUISITE: LECTURE 02 (MDP) · NEXT: TEMPORAL DIFFERENCE (SARSA & Q-LEARNING)
Value Functions & Bellman Equations
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.
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.
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)
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:
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 π:
Because the action is already chosen, an agent can act greedily (argmax_a Q) with ZERO transition model — enabling Model-Free RL!
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!
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.
THE COMPLETE BELLMAN EXPECTATION EQUATION FOR STATE VALUE
v_π(s) = Σ_{a} π(a|s) · Σ_{s'} P(s'|s,a) · [ R(s,a,s') + γ · v_π(s') ]
| Step Component | Mathematical Term | Intuitive Meaning | Example 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.
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') ]
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!
THE MATRIX EQUATION & CLOSED-FORM INVERSE
v_π = R^π + γ · P^π · v_π ⟹ (I - γ · P^π) · v_π = R^π ⟹ v_π = (I - γ · P^π)⁻¹ · R^π
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 ||_∞
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?
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') ]
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!
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.
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!”