Dynamic programming (value - policy iteration)

5.1.9 · AI-ML › Reinforcement Learning Foundations

Overview

Dynamic programming (DP) methods Markov Decision Processes (MDPs) ko subproblems mein todkar aur solutions cache karke solve karte hain. Ye optimal value functions aur optimal policies ko iterative updates ke zariye compute karte hain jo Bellman optimality equations ka use karte hain.

DP kyun important hai: DP modern RL algorithms ki theoretical foundation hai. Bhaleki pure DP ke liye ek perfect model chahiye (transition probabilities aur rewards), ise samajhna model-free methods jaise Q-learning aur actor-critic ko unlock karta hai, jo model ke bina DP ko approximate karte hain.

Figure — Dynamic programming (value - policy iteration)

Core Concepts

The Two Bellman Equations

Bellman Expectation Equation (ek given policy ke liye)

$V^{π} (s) = \sum_{a} π (a ∣ s) \sum_{s^{'}, r} p (s^{'}, r ∣ s, a) [r + γ V^{π} (s^{'})]$

First principles se derivation:

Value ki definition se shuru karo: $V^{π} (s) = E_{π} [G_{t} ∣ S_{t} = s]$

jahan $G_{t} = R_{t + 1} + γ R_{t + 2} + γ^{2} R_{t + 3} + \dots$ return hai.

Pehle reward ko baaki se alag karo: $V^{π} (s) = E_{π} [R_{t + 1} + γ (R_{t + 2} + γ R_{t + 3} + \dots) ∣ S_{t} = s]$

Parentheses wala term bas $G_{t + 1}$ hai, yaani next state se return: $V^{π} (s) = E_{π} [R_{t + 1} + γ G_{t + 1} ∣ S_{t} = s]$

Value function ki definition se, $E [G_{t + 1} ∣ S_{t + 1} = s^{'}] = V^{π} (s^{'})$ : $V^{π} (s) = E_{π} [R_{t + 1} + γ V^{π} (S_{t + 1}) ∣ S_{t} = s]$

Actions (policy $π$ se) aur next states (dynamics $p$ se) par expectation expand karo: $V^{π} (s) = \sum_{a} π (a ∣ s) \sum_{s^{'}, r} p (s^{'}, r ∣ s, a) [r + γ V^{π} (s^{'})]$

WHY har component:

$π (a ∣ s)$ : State $s$ mein action $a$ lene ki policy probability
$p (s^{'}, r ∣ s, a)$ : Environment dynamics (transition probability)
$r$ : Immediate reward jo hum actually receive karte hain
$γ V^{π} (s^{'})$ : Jahan hum pahunchte hain uska discounted value

Bellman Optimality Equation

$V^{*} (s) = max_{a} \sum_{s^{'}, r} p (s^{'}, r ∣ s, a) [r + γ V^{*} (s^{'})]$

Derivation:

Optimal value sabhi possible policies par maximum hai: $V^{*} (s) = max_{π} V^{π} (s)$

Optimal policy $π^{*}$ ke liye, use wo action choose karna chahiye jo expected return maximize kare: $V^{*} (s) = max_{a} Q^{*} (s, a)$

jahan $Q^{*} (s, a) = E [R_{t + 1} + γ V^{*} (S_{t + 1}) ∣ S_{t} = s, A_{t} = a]$

Expectation expand karo: $V^{*} (s) = max_{a} \sum_{s^{'}, r} p (s^{'}, r ∣ s, a) [r + γ V^{*} (s^{'})]$

WHY max operator: Optimal policy hamesha best action pick karti hai, isliye hum policy distribution par average lene ki jagah actions par maximize karte hain.

Algorithm 1: Policy Iteration

Policy iteration do steps ke beech alternate karta hai: policy evaluation (current policy ke liye $V^{π}$ compute karo) aur policy improvement (policy ko greedy banao).

Step 1: Policy Evaluation

Goal: Current policy $π$ ke under sabhi states ke liye $V^{π} (s)$ compute karo.

Algorithm:

$V (s)$ ko arbitrarily initialize karo (e.g., sabhi $s$ ke liye 0)
Convergence tak repeat karo (change < $θ$ ):
- Har state $s$ ke liye: $V_{new} (s) \leftarrow \sum_{a} π (a ∣ s) \sum_{s^{'}, r} p (s^{'}, r ∣ s, a) [r + γ V (s^{'})]$
- $V \leftarrow V_{new}$

WHY this works: Har iteration Bellman expectation equation apply karta hai. Kyunki yeh ek contraction mapping hai ( $γ < 1$ ki wajah se), repeated applications unique fixed point $V^{π}$ par converge hoti hain.

WHY this step: "Yeh update true value function se distance ko har sweep mein $γ$ factor se shrink karta hai, isliye yeh zaroor converge hoga."

Step 2: Policy Improvement

Goal: Current value function ke w.r.t. greedily act karke policy ko better banao.

Algorithm: Har state $s$ ke liye: $π_{new} (s) = ar g max_{a} \sum_{s^{'}, r} p (s^{'}, r ∣ s, a) [r + γ V (s^{'})]$

WHY this policy improve karta hai (Policy Improvement Theorem):

Greedy action $a^{'} = ar g max_{a} Q^{π} (s, a)$ ke liye: $Q^{π} (s, a^{'}) \geq Q^{π} (s, π (s)) = V^{π} (s)$

Agar hum $a^{'}$ follow karein phir $π$ ke saath continue karein, toh hume kam se kam utni hi value milegi: $V^{π} (s) \leq Q^{π} (s, π^{'} (s)) = V^{π^{'}} (s)$

Kyunki yeh sabhi states ke liye hold karta hai, $π^{'}$ kam se kam $π$ jitni acchi hai. Agar $π^{'}$ strictly better nahi hai, toh $π$ already optimal hai.

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 finite number of steps mein converge hoti hai (zyada se zyada $∣ A ∣^{∣ S ∣}$ policies, lekin usually bahut faster). Har iteration policy ko strictly improve karti hai jab tak optimality na aa jaaye.

Worked example Policy Iteration on Grid World

Setup: 4×4 grid, agent (0,0) se start karta hai, goal (3,3) par. Actions: {up, down, left, right}. Reward: har step par -1, goal par 0 (terminal). $γ = 0.9$ .

Initial policy: Random (har action ke liye 0.25 probability).

Iteration 1:

Policy Evaluation: $V (s) = 0$ har jagah se shuru karo.
- Sweep 1 ke baad: Goal ke paas ke states negative values lete hain (e.g., $V (3, 2) \approx - 1 + 0.9 \cdot 0 = - 1$ )
- Sweep 2 ke baad: Values propagate hoti hain (e.g., $V (3, 1) \approx - 1 + 0.9 (- 1) = - 1.9$ )
- ~10 sweeps ke baad converge: $V (0, 0) \approx - 20$ (goal se door)
Policy Improvement: (0,0) par, greedy action "right" ya "down" hai (dono goal ke karib jaate hain). Policy update karo.

Iteration 2:

Policy Evaluation: Improved policy ke saath, $V (0, 0)$ increase hota hai (goal tak kam steps).
Policy Improvement: Policy goal ki taraf aur direct ho jaati hai.

Convergence: 3-4 iterations ke baad, policy optimal ho jaati hai (goal tak shortest path).

WHY this step: Har evaluation sweep current policy ke under expected returns ke basis par values update karta hai. Greedy improvement policy ko value ke "downhill" gradient follow karaata hai.

Algorithm 2: Value Iteration

Value iteration policy evaluation aur improvement ko ek single update step mein combine karta hai. Kisi policy ko fully evaluate karne ki jagah, hum ek backup per state karte hain aur use immediately next iteration ke liye use karte hain.

Algorithm:

$V (s)$ ko arbitrarily initialize karo (e.g., sabhi $s$ ke liye 0)
Convergence tak repeat karo (change < $θ$ ):
- Har state $s$ ke liye: $V_{new} (s) \leftarrow max_{a} \sum_{s^{'}, r} p (s^{'}, r ∣ s, a) [r + γ V (s^{'})]$
- $V \leftarrow V_{new}$
Optimal policy extract karo: $π^{*} (s) = ar g max_{a} \sum_{s^{'}, r} p (s^{'}, r ∣ s, a) [r + γ V (s^{'})]$

WHY this works: Har update Bellman optimality equation apply karta hai. Hum directly $V^{*}$ compute kar rahe hain bina iteration ke dauran explicit policy maintain kiye. Max operator implicitly har step policy improve karta hai.

Key insight: Value iteration, policy iteration hai jisme truncated policy evaluation hai (fully converge karne ki jagah bas ek sweep). Yeh aksar zyada efficient hota hai kyunki policy $V^{π}$ fully converge hone se pehle improve ho sakti hai.

Worked example Value Iteration on Grid World

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

$V (3, 3) = 0$ (terminal, 0 rehta hai)
$V (3, 2) = max {up : - 1 + 0, down : - 1 + 0, right : - 1 + 0, left : - 1 + 0} = - 1$
- WHY this step: "right" lena goal reach karta hai $r = - 1$ ke saath, next state value 0 hai.
$V (2, 3) = - 1$ similarly
$V (0, 0) = - 1$ (goal ke baare mein abhi koi info nahi)

Iteration 2:

$V (3, 2) = max {right : - 1 + 0.9 (0)} = - 1$ (unchanged)
$V (3, 1) = max {right : - 1 + 0.9 (- 1), \dots} = - 1.9$
- WHY this step: (3,2) ki taraf right move karna, jiska value -1 hai, $- 1 + 0.9 (- 1)$ deta hai.
$V (2, 2) = max {right : - 1 + 0.9 (- 1), down : - 1 + 0.9 (- 1)} = - 1.9$

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

Policy extract karo: Har state par wo action lo jo final value update mein max achieve kare. Result: goal tak shortest-path policy.

WHY this step: Har backup optimal value information ko goal se backward state space mein propagate karta hai. Max ensure karta hai ki hum best action ki value track karein.

Policy vs Value Iteration: The Tradeoff

Aspect	Policy Iteration	Value Iteration
Update	Full policy evaluation + improvement	Single optimality backup
Iterations	Kam policy changes (typically 3-5)	Zyada backups (10-100s) lekin sasta
Per-iteration cost	High (many sweeps to converge $V^{π}$ )	Low (ek sweep)
Total cost	Chhote $γ$ ke liye aksar similar ya better	Bade $γ$ ke liye aksar better
Intermediate policy	Hamesha well-defined policy hoti hai	End tak koi explicit policy nahi

Kab kya use karein:

Policy iteration: Jab policy evaluate karna fast ho (chhota state space, high $γ$ ), ya jab computation ke dauran intermediate policies chahiye hon.
Value iteration: Jab policy evaluation expensive ho, ya jab sirf final optimal policy chahiye.
Asynchronous DP: States ko kisi bhi order mein update karo (high-error states par focus karo), practice mein faster converge hoti hai.

Common mistake Common Mistake: Max vs Expectation Bhool Jaana

Galat idea: "Policy evaluation aur value iteration same hain, bas Bellman equation use karo."

Kyun sahi lagta hai: Dono similar-dikhne wale formulas use karke value functions iterate karte hain.

Kyun galat hai: Policy evaluation Bellman expectation equation use karta hai (policy distribution par sum), jabki value iteration Bellman optimality equation use karta hai (actions par max).

Fix:

Policy evaluation: $V (s) \leftarrow \sum_{a} π (a ∣ s) \dots$ (current policy follow karta hai)
Value iteration: $V (s) \leftarrow max_{a} \dots$ (implicitly policy improve karta hai)

Steel-man: Confusion isliye hoti hai kyunki dono future values ke basis par values update karte hain. Lekin policy evaluation ek fixed policy ko evaluate karta hai (passive), jabki value iteration optimal policy ko search karta hai (active).

Common mistake Common Mistake: In-Place vs Synchronously Values Update Karna

Galat idea: "Main $V (s)$ immediately update kar sakta hun aur same sweep mein doosre states ke liye nayi value use kar sakta hun."

Kyun sahi lagta hai: Latest information use karna zyada efficient lagta hai.

Kyun galat nahi hai, lekin convergence change karta hai: In-place updates (Gauss-Seidel style) actually synchronous updates (Jacobi style) se faster converge hote hain! Lekin order matter karta hai.

Fix: Dono kaam karte hain, lekin samjho tum kya kar rahe ho:

Synchronous: $V_{new} (s) = \dots$ sabhi successors ke liye old $V (s^{'})$ use karke, phir $V \leftarrow V_{new}$
In-place: $V (s) = \dots$ current $V (s^{'})$ use karke, kuch is sweep mein already updated hain

In-place practice mein standard hai aur aksar 2× faster hota hai. Theoretical convergence proof dono ke liye kaam karta hai.

Computational Complexity

Per iteration:

Policy evaluation: $O (∣ S ∣^{2} ∣ A ∣)$ per sweep (har state ke liye, actions aur next states par sum)
Value iteration backup: $O (∣ S ∣^{2} ∣ A ∣)$ per sweep

Total iterations:

Policy iteration: $O (∣ A ∣^{∣ S ∣})$ worst case (har policy), lekin typically 3-10 in practice
Value iteration: $O (\frac{l o g ( 1/ θ )}{l o g ( 1/ γ )})$ error threshold $θ$ tak pahunchne ke liye

WHY $γ$ convergence affect karta hai: Contraction factor $γ$ hai. Har iteration error ko kam se kam $γ$ factor se reduce karta hai, isliye chhota $γ$ (kam far-sighted) faster converge karta hai.

Space complexity: $V$ aur $π$ store karne ke liye $O (∣ S ∣)$ .

Connections to Other RL Methods

Temporal-difference learning se relationship:

DP: Model-based (needs $p (s^{'}, r ∣ s, a)$ ), sabhi states ko sweep karta hai
TD learning: Model-free (samples se seekhta hai), ek state at a time update karta hai
TD essentially DP hai jisme full expectation ki jagah sampled backups hain

Generalized Policy Iteration (GPI): Sabhi RL methods ko GPI ke roop mein dekha ja sakta hai: policy evaluation (value function ko policy ke consistent banana) aur policy improvement (policy ko value ke w.r.t. greedy banana) ko interleave karna. DP yeh exact computation se karta hai; TD/Q-learning ise samples se approximate karte hain.

Monte Carlo methods:

DP: Bootstrap karta hai (updates mein estimated $V (s^{'})$ use karta hai)
Monte Carlo: Bootstrap nahi (actual return $G_{t}$ ka wait karta hai)
Tradeoff: DP ki variance lower hai lekin model chahiye

Modern deep RL:

AlphaZero: $V$ aur $π$ ke liye neural networks ke saath policy iteration, evaluation ke liye Monte Carlo tree search
Actor-critic: Policy gradient (improvement) + TD learning (evaluation)

Connections

5.108-Markov-Decision-Process-(MDP) — DP MDPs solve karta hai
5.1.10-Temporal-difference-learning — DP ka model-free version
5.1.11-Q-learning — Model ke bina value iteration
5.1.12-SARSA — Model ke bina policy iteration
5.1.15-Policy-gradient-methods — Direct policy search (bina value function ke)
Bellman-equations — DP ki foundation
Contraction-mapping-theorem — DP kyun converge karta hai

Recall Ek 12-saal ke bachche ko samjhao

Socho tum ek board game khel rahe ho jahan finish tak jitni jaldi ho sake pahunchna chahte ho. Abhi best strategy pata nahi hai, toh tum yeh try karte ho:

Plan 1 (Policy Iteration):

Random strategy se shuru karo: "Main bas dice roll karunga aur jo mann kare move karunga."
Ab pretend karo ki tum us strategy ko kai games ke liye follow karte ho aur calculate karo "Har square se average mein kitne turns lagte hain?"
Apni strategy dobara dekho: "Ruko, agar main square 10 par hun, meri strategy kehti hai left jao, lekin agar main right jaaun, toh finish zyada jaldi pahunchunga!"
Apni strategy update karo ki hamesha wo move choose karo jo kam-turns wale squares par le jaaye.
Steps 2-4 repeat karo jab tak strategy change karna band na ho jaaye.

Plan 2 (Value Iteration):

Guess karke shuru karo "Har square se 0 turns."
Har square update karo: "Agar main yahan hun, toh main kitni jaldi finish kar sakta hun?" Sabhi possible moves dekho aur best pick karo.
Step 2 repeat karo jab tak numbers change karna band na ho jaayein.
Teri final strategy: hamesha sabse kam number wale square ki taraf move karo.

Dono plans perfect strategy dhundh lete hain! Pehla wala ek strategy try karne, use test karne, phir fix karne jaisa hai. Doosra wala har square ke liye best possible score calculate karne aur use follow karne jaisa hai.

Flashcards

MDPs solve karne ke liye do main DP algorithms kaun se hain? :: Policy iteration aur value iteration.

Policy evaluation aur value iteration updates mein key difference kya hai?

Policy evaluation policy par expectation use karta hai:

\sum_{a} π (a ∣ s)

. Value iteration actions par max use karta hai:

max_{a}

Bellman expectation equation kya hai?

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

Bellman optimality equation kya hai?

V^{*} (s) = max_{a} \sum_{s^{'}, r} p (s^{'}, r ∣ s, a) [r + γ V^{*} (s^{'})]

Policy improvement theorem kyun guarantee karta hai ki greedy policy better hai?

Kyunki sabhi states ke liye

Q^{π} (s, π^{'} (s)) \geq Q^{π} (s, π (s)) = V^{π} (s)

hai, isliye

V^{π^{'}} \geq V^{π}

DP convergence mein contraction factor kya hai?

γ

(discount factor). Har iteration mein error

γ

factor se shrink hoti hai.

Value iteration ke liye tolerance

θ

diye stopping criterion kya hai?

∣∣ V_{k + 1} - V_{k} ∣ ∣_{\infty} < θ

implies

∣∣ V_{k} - V^{*} ∣ ∣_{\infty} < \frac{2 θ γ}{1 - γ}

Generalized policy iteration (GPI) kya hai?

Policy evaluation aur policy improvement ko interleave karne ka framework, jo sabhi RL algorithms ke underlying hai.

Value iteration policy iteration se wall-clock time mein aksar faster kyun converge karta hai?

Har iteration sasti hai (full convergence ki jagah ek backup), aur truncated evaluation aksar policy improvement ke liye sufficient hoti hai.

Wo key requirement kya hai jo DP ko large real-world RL problems ke liye infeasible banati hai?

DP ko full MDP model chahiye: sabhi states aur actions ke liye transition probabilities

p (s^{'}, r ∣ s, a)

Policy iteration ko value iteration par kab prefer karna chahiye?

Jab state space chhota ho aur policy evaluation fast ho, ya jab

γ

high ho (1 ke karib).

In-place/asynchronous DP kya hai aur ise kyun use karein?

States ko kisi bhi order mein update karna (high-error states par bhi focus karna) latest values use karke. Synchronous sweeps se practice mein faster converge hota hai.