Policy Evaluation: Computing State Values
What You'll Learn
You'll learn how to systematically compute the value function V(s) for a given policy using iterative policy evaluation and the Bellman expectation equation.
The Core Idea
Policy evaluation answers the question: "How good is my current policy?" Given a fixed policy π (which tells us what actions to take in each state), we want to compute the value function V^π(s) for every state—that is, the expected cumulative reward we'll get starting from each state and following that policy.
We already know the Bellman expectation equation relates a state's value to its successor states:
V^π(s) = Σ_a π(a|s) Σ_{s'} P(s'|s,a) [R(s,a,s') + γ V^π(s')]
But this equation is defined in terms of itself! The solution: iterative policy evaluation.
The Algorithm
Start with arbitrary initial values V₀(s) for all states (often zeros). Then repeatedly apply the Bellman expectation equation as an update rule:
V_{k+1}(s) ← Σ_a π(a|s) Σ_{s'} P(s'|s,a) [R(s,a,s') + γ V_k(s')]
For each state, compute its new value based on the current estimates of its successor states' values. Repeat until the values converge (changes become negligibly small).
Analogy
Think of spreading heat through a metal grid. Each cell's temperature depends on its neighbors. You iteratively update each cell based on surrounding temperatures until the whole grid reaches thermal equilibrium—that's when you've found the steady-state distribution.
Why It Works
The Bellman equation is a contraction mapping, guaranteeing convergence to the true value function V^π as iterations increase. Each sweep brings you closer to the exact values.
Key Takeaway: Policy evaluation uses iterative application of the Bellman expectation equation to compute the value function for a given policy, providing the foundation for policy improvement algorithms.