Dynamic programming (value - policy iteration)

Overview

Dynamic programming (DP) methods solve Markov Decision Processes (MDPs) by breaking them into subproblems and caching solutions. They compute optimal value functions and optimal policies through iterative updates that leverage the Bellman optimality equations.

Why DP matters: DP is theoretical foundation for modernRL algorithms. Even though pure DP requires a perfect model (transition probabilities and rewards), understanding it unlocks model-free methods like Q-learning and actor-critic, which approximate DP without a model.

Figure — Dynamic programming (value - policy iteration)

Core Concepts

The Two Bellman Equations

Bellman Expectation Equation (for a given policy)

$V^\pi(s) = \sum_a \pi(a|s) \sum_{s',r} p(s',r|s,a)[r + \gamma V^\pi(s')]$

Derivation from first principles:

Start with the definition of value: $V^\pi(s) = \mathbb{E}_\pi[G_t | S_t = s]$

where $G_t = R_{t+1} + \gamma R_{t+2} + \gamma^2 R_{t+3} + \ldots$ is the return.

Separate the first reward from the rest: $V^\pi(s) = \mathbb{E}_\pi[R_{t+1} + \gamma(R_{t+2} + \gamma R_{t+3} + \ldots) | S_t = s]$

The term in parentheses is just $G_{t+1}$ , the return from the next state: $V^\pi(s) = \mathbb{E}_\pi[R_{t+1} + \gamma G_{t+1} | S_t = s]$

By the definition of value function, $\mathbb{E}[G_{t+1}|S_{t+1}=s'] = V^\pi(s')$ : $V^\pi(s) = \mathbb{E}_\pi[R_{t+1} + \gamma V^\pi(S_{t+1}) | S_t = s]$

Expand the expectation over actions (from policy $\pi$ ) and next states (from dynamics $p$ ): $V^\pi(s) = \sum_a \pi(a|s) \sum_{s',r} p(s',r|s,a)[r + \gamma V^\pi(s')]$

WHY each component:

$\pi(a|s)$ : Policy probability of taking action $a$ in state $s$
$p(s',r|s,a)$ : Environment dynamics (transition probability)
$r$ : Immediate reward we actually receive
$\gamma V^\pi(s')$ : Discounted value of where we end up

Bellman Optimality Equation

$V^*(s) = \max_asum_{s',r} p(s',r|s,a)[r + \gamma V^*(s')]$

Derivation:

The optimal value is the maximum over all possible policies: $V^*(s) = \max_\pi V^\pi(s)$

For the optimal policy $\pi^*$ , it must choose the action that maximizes expected return: $V^*(s) = \max_a Q^*(s,a)$

where $Q^*(s,a) = \mathbb{E}[R_{t+1} + \gamma V^*(S_{t+1}) | S_t=s, A_t=a]$

Expand the expectation: $V^*(s) = \max_a \sum_{s',r} p(s',r|s,a)[r + \gamma V^*(s')]$

WHY the max operator: The optimal policy always picks the best action, so we maximize over actions rather than averaging over a policy distribution.

Algorithm1: Policy Iteration

Policy iteration alternates between two steps: policy evaluation (compute $V^\pi$ for current policy) and policy improvement (make policy greedy).

Step 1: Policy Evaluation

Goal: Compute $V^\pi(s)$ for all states under current policy $\pi$ .

Algorithm:

Initialize $V(s)$ arbitrarily (e.g., 0 for all $s$ )
Repeat until convergence (change < $\theta$ $θ$ ):
- For each state $s$ : $V_{\text{new}}(s) \leftarrow \sum_a \pi(a|s) \sum_{s',r} p(s',r|s,a)[r + \gamma V(s')]$
- $V \leftarrow V_{\text{new}}$

WHY this works: Each iteration applies the Bellman expectation equation. Since it's a contraction mapping (due to $\gamma < 1$ ), repeated applications converge to the unique fixed point $V^\pi$ .

WHY this step: "The update shrinks the distance to the true value function by a factor of $\gamma$ with each sweep, so it must converge."

Step 2: Policy Improvement

Goal: Make policy better by acting greedily w.r.t. current value function.

Algorithm: For each state $s$ : $\pi_{\text{new}}(s) = \arg\max_a \sum_{s',r} p(s',r|s,a)[r + \gamma V(s')]$

WHY this improves the policy (Policy Improvement Theorem):

For the gredy action $a' = \arg\max_a Q^\pi(s,a)$ : $Q^\pi(s, a') \geq Q^\pi(s, \pi(s)) = V^\pi(s)$

If we follow $a'$ then continue with $\pi$ , we get at least as much value: $V^\pi(s) \leq Q^\pi(s, \pi'(s)) = V^{\pi'}(s)$

Since this holds for all states, $\pi'$ is at least as good as $\pi$ . If $\pi'$ is not strictly better, then $\pi$ is already optimal.

Full Policy Iteration Loop

1. Initialize π arbitrarily
2. Repeat:
   a. V ← PolicyEvaluate(π)  // converge to V^π
   b. π' ← Gredy(V)
   c. If π' = π, stop (optimal!)
   d. π ← π'

Convergence: Policy iteration converges in a finite number of steps (at most $|\mathcal{A}|^{|\mathcal{S}|}$ policies, but usually much faster). Each iteration strictly improves the policy until optimality.

Worked example Policy Iteration on Grid World

Setup: 4×4 grid, agent starts at (0,0), goal at (3,3). Actions: {up, down, left, right}. Reward: -1 per step,0 at goal (terminal). $\gamma = 0.9$ .

Initial policy: Random (0.25 probability for each action).

Iteration 1:

Policy Evaluation: Start with $V(s)=0$ $V (s) = 0$ everywhere.
- After sweep 1: States near goal get negative values (e.g., $V(3,2) \approx -1 + 0.9 \cdot 0 = -1$ )
- After sweep 2: Values propagate (e.g., $V(3,1) \approx -1 + 0.9(-1) = -1.9$ )
- Converge after ~10 sweeps: $V(0,0) \approx -20$ (far from goal)
Policy Improvement: At (0,0), gredy action is "right" or "down" (both move closer to goal). Update policy. Iteration 2:
Policy Evaluation: With improved policy, $V(0,0)$ increases (fewer steps to goal).
Policy Improvement: Policy becomes more direct toward goal.

Convergence: After 3-4 iterations, policy becomes optimal (shortest path to goal).

WHY this step: Each evaluation sweep updates values based on expected returns under current policy. Greedy improvement makes policy follow the "downhill" gradient of value.

Algorithm 2: Value Iteration

Value iteration combines policy evaluation and improvement into a single update step. Instead of fully evaluating a policy, we do one backup per state and immediately use it for the next iteration.

Algorithm:

Initialize $V(s)$ arbitrarily (e.g., 0 for all $s$ )
Repeat until convergence (change < $\theta$ $θ$ ):
- For each state $s$ : $V_{\text{new}}(s) \leftarrow \max_a \sum_{s',r} p(s',r|s,a)[r + \gamma V(s')]$
- $V \leftarrow V_{\text{new}}$
Extract optimal policy: $\pi^*(s) = \arg\max_a \sum_{s',r} p(s',r|s,a)[r + \gamma V(s')]$

WHY this works: Each update applies the Bellman optimality equation. We're directly computing $V^*$ without maintaining an explicit policy during iteration. The max operator implicitly improves the policy every step.

Key insight: Value iteration is policy iteration with truncated policy evaluation (just one sweep instead of converging fully). This is often more efficient because the policy might improve before $V^\pi$ fully converges.

Worked example Value Iteration on Grid World

Same setup: 4×4 grid, goal at (3,3), $\gamma=0.9$ . Iteration 1: All $V(s)=0$ .

$V(3,3) = 0$ (terminal, stays0)
$V(3,2) = \max\{\text{up}:-1+0, \text{down}:-1+0, \text{right}:-1+0, \text{left}:-1+0\} = -1$ $V (3, 2) = max {up : - 1 + 0, down : - 1 + 0, right : - 1 + 0, left : - 1 + 0} = - 1$
- WHY this step: Taking "right" reaches goal with $r=-1$ , next state value is 0.
$V(2,3) = -1$ similarly
$V(0,0) = -1$ (no info about goal yet)

Iteration 2:

$V(3,2) = \max\{\text{right}: -1 + 0.9(0)\} = -1$ (unchanged)
$V(3,1) = \max\{\text{right}: -1 + 0.9(-1), \ldots\} = -1.9$ $V (3, 1) = max {right : - 1 + 0.9 (- 1), \dots} = - 1.9$
- WHY this step: Moving right toward (3,2), which has value -1, gives $-1 + 0.9(-1)$ .
$V(2,2) = \max\{\text{right}: -1 + 0.9(-1), \text{down}: -1 + 0.9(-1)\} = -1.9$

Iteration 10: Values stabilize around $V(0,0) \approx -6$ (optimal path length7 steps).

Extract policy: At each state, take action that achieves the max in the final value update. Result: shortest-path policy to goal.

WHY this step: Each backup propagates optimal value information from goal backward through the state space. The max ensures we track the best action's value.

Policy vs Value Iteration: The Tradeoff

| Aspect | Policy Iteration | Value Iteration | |--------|------------------| | Update | Full policy evaluation + improvement | Single optimality backup | | Iterations | Fewer policy changes (3-5 typically) | More backups (10-100s) but cheaper | | Per-iteration cost | High (many sweps to converge $V^\pi$ ) | Low (one sweep) | | Total cost | Often similar or better for small $\gamma$ | Often better for large $\gamma$ | | Intermediate policy | Always have a well-defined policy | No explicit policy until end |

When to use which:

Policy iteration: When evaluating a policy is fast (small state space, high $\gamma$ ), or when you want intermediate policies during computation.
Value iteration: When policy evaluation is expensive, or when you only care about the final optimal policy.
Asynchronous DP: Update states in any order (focus on high-error states), converges faster in practice.

Common mistake Common Mistake: Forgetting the Max vs Expectation

Wrong idea: "Policy evaluation and value iteration are the same, just use the Bellman equation."

Why it feels right: Both iterate value functions using similar-looking formulas.

Why it's wrong: Policy evaluation uses the Bellman expectation equation (sum over policy distribution), while value iteration uses the Bellman optimality equation (max over actions).

The fix:

Policy evaluation: $V(s) \leftarrow \sum_a \pi(a|s) \ldots$ (follows current policy)
Value iteration: $V(s) \leftarrow \max_a \ldots$ (implicitly improves policy)

Steel-man: The confusion arises because both update values based on future values. But policy evaluation evaluates a fixed policy (passive), while value iteration searches for the optimal policy (active).

Common mistake Common Mistake: Updating Values In-Place vs Synchronously

Wrong idea: "I can update $V(s)$ immediately and use the new value for other states in the same sweep."

Why it feels right: Seems more efficient to use the latest information.

Why it's not wrong, but changes convergence: In-place updates (Gauss-Seidel style) actually converge faster than synchronous updates (Jacobi style)! But the order matters.

The fix: Both work, but understand what you're doing:

Synchronous: $V_{\text{new}}(s) = \ldots$ using old $V(s')$ for all successors, then $V \leftarrow V_{\text{new}}$
In-place: $V(s) = \ldots$ using current $V(s')$ , some already updated this sweep

In-place is standard in practice and often 2× faster. The theoretical convergence proof works for both.

Computational Complexity

Per iteration:

Policy evaluation: $O(|\mathcal{S}|^2 |\mathcal{A}|)$ per sweep (for each state, sum over actions and next states)
Value iteration backup: $O(|\mathcal{S}|^2 |\mathcal{A}|)$ per sweep

Total iterations:

Policy iteration: $O(|\mathcal{A}|^{|\mathcal{S}|})$ worst case (every policy), but typically3-10 in practice
Value iteration: $O\left(\frac{\log(1/\theta)}{\log(1/\gamma)}\right)$ to reach error threshold $\theta$

WHY $\gamma$ affects convergence: The contraction factor is $\gamma$ . Each iteration reduces error by at least factor $\gamma$ , so smaller $\gamma$ (less far-sighted) converges faster.

Space complexity: $O(|\mathcal{S}|)$ to store $V$ and $\pi$ .

Formula Error Bound for Value Iteration

After $k$ iterations, the error in value function is bounded: $||V_k - V^*||_\infty \leq \gamma^k ||V_0 - V^*||_\infty$

Derivation: Bellman optimality operator $T$ is a $\gamma$ -contraction in $\ell^\infty$ norm: $||TV - TU||_\infty \leq \gamma ||V - U||_\infty$

Apply repeatedly: $V_k = T^k V_0$ , so $||V_k - V^*|| = ||T^k V_0 - T^k V^*|| \leq \gamma^k ||V_0 - V^*||$ .

Stopping criterion: If $||V_{k+1} - V_k||_\infty < \theta$ , then $||V_k - V^*||_\infty < \frac{2\theta\gamma}{1-\gamma}$ .

Connections to Other RL Methods

Relationship to temporal-difference learning:

DP: Model-based (needs $p(s',r|s,a)$ ), sweps all states
TD learning: Model-free (learns from samples), updates one state at a time
TD is essentially DP with sampled backups instead of full expectation

Generalized Policy Iteration (GPI): All RL methods can be viewed as GPI: interleaving policy evaluation (making value function consistent with policy) and policy improvement (making policy greedy w.r.t. value). DP does this with exact computation; TD/Q-learning approximate it with samples.

Monte Carlo methods:

DP: Bootstrap (use estimated $V(s')$ in updates)
Monte Carlo: No bootstrap (wait for actual return $G_t$ )
Tradeoff: DP has lower variance but needs a model

Modern deep RL:

AlphaZero: Policy iteration with neural networks for $V$ and $\pi$ , Monte Carlo tree search for evaluation
Actor-critic: Policy gradient (improvement) + TD learning (evaluation)

Connections

5.108-Markov-Decision-Process-(MDP) —DP solves MDPs
5.1.10-Temporal-difference-learning — Model-free version of DP
5.1.11-Q-learning — Value iteration without a model
5.1.12-SARSA — Policy iteration without a model
5.1.15-Policy-gradient-methods — Direct policy search (no value function)
Bellman-equations — Foundation of DP
Contraction-mapping-theorem — Why DP converges

Recall Explain to a 12-year-old

Imagine you're playing a board game where you want to reach the finish as fast as possible. You don't know the best strategy yet, so you try this: Plan 1 (Policy Iteration):

Start with a random strategy: "I'll just roll the dice and move however I feel."
Now pretend you follow that strategy for many games and calculate "How many turns does it take on average from each square?"
Look at your strategy again: "Wait, if I'm on square 10, my strategy says go left, but if I go right instead, I reach the finish faster!"
Update your strategy to always pick the move that gets to lower-turn squares.
Repeat steps 2-4 until your strategy stops changing.

Plan 2 (Value Iteration):

Start by guessing "0 turns from every square."
Update each square: "If I'm here, what's the fastest I could finish?" Look at all possible moves and pick the best.
Repeat step 2 until the numbers stop changing.
Your final strategy: always move to the square with the lowest number.

Both plans find the perfect strategy! The first one is like trying a strategy, testing it, then fixing it. The second is like calculating the best possible score for each square and following that.

Flashcards

What are the two main DP algorithms for solving MDPs? :: Policy iteration and value iteration.

What is the key difference between policy evaluation and value iteration updates?

Policy evaluation uses expectation over policy:

\sum_a \pi(a|s)

. Value iteration uses max over actions:

\max_a

What is the Bellman expectation equation?

V^\pi(s) = \sum_a \pi(a|s) \sum_{s',r} p(s',r|s,a)[r + \gamma V^\pi(s')]

What is the Bellman optimality equation?

V^*(s) = \max_a \sum_{s',r} p(s',r|s,a)[r + \gamma V^*(s')]

Why does policy improvement theorem guarantee that gredy policy is better?

Because

Q^\pi(s, \pi'(s)) \geq Q^\pi(s, \pi(s)) = V^\pi(s)

for all states, so

V^{\pi'} \geq V^\pi

What is the contraction factor inDP convergence?

\gamma

(discount factor). Error shrinks by factor

\gamma

each iteration.

What is the stopping criterion for value iteration given tolerance

\theta

||V_{k+1} - V_k||_\infty < \theta

implies

||V_k - V^*||_\infty < \frac{2\theta\gamma}{1-\gamma}

What is generalized policy iteration (GPI)?

The framework of interleaving policy evaluation and policy improvement, which underlies all RL algorithms.

Why does value iteration often converge faster than policy iteration per wall-clock time?

Each iteration is cheaper (one backup vs full convergence), and truncated evaluation is often sufficient for policy improvement.

What is the key requirement that makes DP infeasible for large real-world RL problems?

DP requires the full MDP model: transition probabilities

p(s',r|s,a)

for all states and actions.

When should you prefer policy iteration over value iteration?

When the state space is small and policy evaluation is fast, or when

\gamma

is high (closer to 1).

What is in-place/asynchronous DP and why use it?

Updating states in any order (even focusing on high-error states) using latest values. Converges faster than synchronous sweps in practice.

Concept Map

Hinglish (regional understanding)

Intuition Hinglish mein samjho

Hinglish (regional understanding)

Intuition Hinglish mein samjho

Chalo is topic ko simple tarike se samajhte hain. Dynamic Programming ka core idea yeh hai ki bade problem ko chote-chote subproblems mein tod do, aur unke solutions ko cache (save) kar lo taaki baar-baar calculate na karna pade. Socho ki tum ek maze mein shortest path dhundh rahe ho — instead of har route try karna, tum ulta soch ke chalte ho: "Agar main exit se ek step door hoon, to best move kya hai?" Phir "Do step door hoon to?" Is tarah tum chote answers build karte ho aur unhe reuse karte ho bade problems ke liye. Yahi kaam DP karta hai MDPs (Markov Decision Processes) ke saath, aur iska dil hai Bellman equation — jo kehti hai ki kisi state ka value equals immediate reward plus aage jahan pahunchoge uska discounted value.

Ab yahan do important equations aati hain. Pehli hai Bellman Expectation Equation, jo ek given policy ke liye value nikalti hai — yaani agar tum ek fixed strategy follow kar rahe ho to har state ka expected return kya hoga. Dusri hai Bellman Optimality Equation, jismein max operator lagta hai — yeh best possible action choose karti hai har state par, na ki average leti hai. Yeh max hi difference hai: expectation equation average nikalti hai policy ke according, jabki optimality equation hamesha best action pick karti hai. In dono ke saath humein V (state value), Q (action value), aur optimal policy π* milti hai, jo har state mein sabse acchi action batati hai.

Yeh cheez isliye important hai kyunki DP modern Reinforcement Learning ka theoretical foundation hai. Sach hai ki pure DP ko ek perfect model chahiye (transition probabilities aur rewards ka poora pata hona chahiye), jo real world mein aksar nahi milta. Lekin agar tum DP ache se samajh loge, to tumhe Q-learning aur actor-critic jaise model-free methods bhi easily samajh aayenge — yeh saare methods basically DP ko approximate karte hain bina model ke. To yeh topic ek building block hai jispe aage ki puri RL ki knowledge tiki hui hai, isliye ise strong karna zaroori hai.

Dynamic programming (value - policy iteration)

Overview

Core Concepts

The Two Bellman Equations

Bellman Expectation Equation (for a given policy)

Bellman Optimality Equation

Algorithm1: Policy Iteration

Step 1: Policy Evaluation

Step 2: Policy Improvement

Full Policy Iteration Loop

Algorithm 2: Value Iteration

Policy vs Value Iteration: The Tradeoff

Computational Complexity

Connections to Other RL Methods

Connections

Flashcards

Concept Map

Hinglish (regional understanding)

Hinglish (regional understanding)

Go deeper — visual, from zero

Test yourself — Reinforcement Learning Foundations

Connections