Markov Decision Processes (MDP) — Hinglish notes

5.1.2 · AI-ML › Reinforcement Learning Foundations

MDP kya hai?

Yeh components kyun?

States: Agent kahan ho sakta hai? (positions, configurations, observations)
Actions: Agent ke paas kya choices hain? (moves, controls, decisions)
Transitions: Jab main act karta hoon toh kya hota hai? (physics, rules, uncertainty)
Rewards: Kya achha/bura hai? (goals jo numbers ke roop mein encode hain)
Discount: Future rewards ki value kam hoti hai (impatience, uncertainty, mathematical convenience)

Value Function ko First Principles se Derive Karna

Goal: Ek policy $π : S \to A$ dhundho (ek strategy jo states ko actions se map karti hai) jo total reward maximize kare.

Step 1: Total Return

State $s_{0}$ se shuru karke, agar hum policy $π$ follow karte hain, toh hume ek sequence milta hai: $s_{0} a_{0} s_{1} a_{1} s_{2} a_{2} \dots$

Time $t$ se return $G_{t}$ saare future rewards ka sum hai: $G_{t} = R_{t + 1} + R_{t + 2} + R_{t + 3} + \dots$

Problem: Yeh sum infinite ho sakta hai aur near vs. far rewards mein distinguish nahi karta.

Step 2: Discounted Return

Discount kyun? Teen reasons:

Uncertainty: Future kam certain hai, isliye worth less hai
Impatience: Baad mein milne se pehle reward prefer karo (economic time-preference)
Mathematical convergence: Infinite horizons ke liye finite sums ensure karta hai

Discounted return: $G_{t} = R_{t + 1} + γ R_{t + 2} + γ^{2} R_{t + 3} + \dots = \sum_{k = 0}^{\infty} γ^{k} R_{t + k + 1}$

Yeh kyun kaam karta hai: Agar $∣ γ ∣ < 1$ aur rewards $R_{m a x}$ se bounded hain, toh: $G_{t} \leq \sum_{k = 0}^{\infty} γ^{k} R_{m a x} = \frac{R _{m a x}}{1 - γ}$ Geometric series converge ho jaati hai!

Step 3: State-Value Function

State-value function $V^{π} (s)$ woh expected return hai jo state $s$ se shuru karke aur policy $π$ follow karke milta hai:

$V^{π} (s) = E_{π} [G_{t} ∣ S_{t} = s]$

Expectation kyun? Transitions stochastic hain ( $P (s^{'} ∣ s, a)$ ), isliye hum saare possible futures ka average lete hain.

Expand karte hain: $V^{π} (s) = E_{π} [R_{t + 1} + γ G_{t + 1} ∣ S_{t} = s]$

Key insight: $G_{t + 1}$ khud $S_{t + 1}$ se ek return hai, isliye $E [G_{t + 1} ∣ S_{t + 1} = s^{'}] = V^{π} (s^{'})$ .

Step 4: Bellman Equation Derivation

$V^{π} (s) = E_{π} [R_{t + 1} + γ V^{π} (S_{t + 1}) ∣ S_{t} = s]$

Policy $π$ ke under, hum deterministically action $a = π (s)$ lete hain (ya stochastic policies ke liye $π (a ∣ s)$ se sample karte hain). Deterministic $π$ ke liye:

$V^{π} (s) = \sum_{s^{'}} P (s^{'} ∣ s, π (s)) [R (s, π (s), s^{'}) + γ V^{π} (s^{'})]$

Ise tod ke samjhte hain:

Hum state $s$ mein hain, policy kehti hai action $π (s)$ lo
Environment randomly next state $s^{'}$ choose karta hai probability $P (s^{'} ∣ s, π (s))$ ke saath
Hume immediate reward $R (s, π (s), s^{'})$ milta hai
Phir naye state se hume discounted future value $γ V^{π} (s^{'})$ milti hai

Step 5: Action-Value Function (Q-function)

Kabhi kabhi hum jaanna chahte hain: "State $s$ mein action $a$ lena kitna achha hai (aur phir $π$ follow karna)?"

Action-value function: $Q^{π} (s, a) = E_{π} [G_{t} ∣ S_{t} = s, A_{t} = a]$

Derivation: $Q^{π} (s, a) = \sum_{s^{'}} P (s^{'} ∣ s, a) [R (s, a, s^{'}) + γ V^{π} (s^{'})]$

$V$ se relationship: $V^{π} (s) = Q^{π} (s, π (s))$

Optimal Policy aur Bellman Optimality

Goal: Optimal policy $π^{*}$ dhundho jo saare states ke liye value maximize kare: $π^{*} = ar g max_{π} V^{π} (s), \forall s \in S$

Optimal value functions define karo: $V^{*} (s) = max_{π} V^{π} (s)$ $Q^{*} (s, a) = max_{π} Q^{π} (s, a)$

Bellman Optimality Equation Derive Karna

Agar $V^{*} (s)$ best possible value hai, toh: $V^{*} (s) = max_{a \in A} Q^{*} (s, a)$

Kyun? Optimal policy ko woh action choose karna chahiye jiska Q-value sabse zyada ho.

Q-function expansion substitute karte hain: $V^{*} (s) = max_{a \in A} \sum_{s^{'}} P (s^{'} ∣ s, a) [R (s, a, s^{'}) + γ V^{*} (s^{'})]$

Q-function ke liye: $Q^{*} (s, a) = \sum_{s^{'}} P (s^{'} ∣ s, a) [R (s, a, s^{'}) + γ max_{a^{'}} Q^{*} (s^{'}, a^{'})]$

Optimal policy extraction: Jab ek baar humein $V^{*}$ ya $Q^{*}$ mil jaaye: $π^{*} (s) = ar g max_{a} Q^{*} (s, a)$

Worked Examples

Worked example Example 1: Simple Grid World

Setup:

$S = {s_{1}, s_{2}, s_{3}}$ (ek line mein 3 states)
$A = {left, right}$
Deterministic transitions: left, left move karta hai (boundary pe nahi), right, right move karta hai
$R (s_{3}, any, s_{3}) = + 10$ (goal state), baaki saare rewards = 0
$γ = 0.9$
Policy $π$ : hamesha right jao

$V^{π} (s_{1})$ compute karo: Step 1: Har state ke liye Bellman equations likho.

$s_{1}$ : Right lena → probability 1 ke saath $s_{2}$ mein land karta hai $V^{π} (s_{1}) = 0 + 0.9 \cdot V^{π} (s_{2})$

$s_{2}$ : Right lena → probability 1 ke saath $s_{3}$ mein land karta hai $V^{π} (s_{2}) = 0 + 0.9 \cdot V^{π} (s_{3})$ $s_{3}$ : Terminal state (self-loop with reward +10) $V^{π} (s_{3}) = 10 + 0.9 \cdot V^{π} (s_{3})$

Step 2: $V^{π} (s_{3})$ solve karo: $V^{π} (s_{3}) = 10 + 0.9 V^{π} (s_{3})$ $0.1 V^{π} (s_{3}) = 10$ $V^{π} (s_{3}) = 100$

Yeh step kyun? $V^{π} (s_{3})$ ko ek side isolate karne ke liye rearrange karna. $1/ (1 - γ)$ term goal pe rewards ki infinite geometric series se aata hai.

Step 3: Back-substitute karo: $V^{π} (s_{2}) = 0.9 \times 100 = 90$ $V^{π} (s_{1}) = 0.9 \times 90 = 81$

Intuition: $s_{1}$ se, hum goal se 2 steps door hain, isliye value do baar discount hoti hai: $γ^{2} \times V^{π} (s_{3}) = 0.81 \times 100 = 81$ .

Common Mistakes aur Fixes

Memory Aids

Recall Feynman Explain-to-a-12-Year-Old

Socho tum ek board game khel rahe ho. Har turn pe, tum kisi square pe ho (woh state hai). Tum ek move choose karte ho (woh tumhara action hai). Game mein kuch randomness hai—shayad tum dice roll karte ho dekhne ke liye ki tum kahan land karoge (woh transition probability hai). Jab tum land karte ho, tumhe points milte hain ya lose hote hain (woh reward hai).

Ab, Markov property kehti hai: sirf tumhara current square matter karta hai tumhara next move decide karne aur tum kahan land karoge yeh decide karne ke liye. Tumhe har square yaad rakhne ki zaroorat nahi jo tumne pehle visit kiya—bas dekho tum abhi kahan ho.

Tumhari policy tumhari strategy hai: "Jab main square X pe hoon, main move Y choose karunga." Ek square ki value hai: "Agar main yahan se shuru karun aur smartly kheluun, toh total mujhe kitne points milenge?" Discount factor aise kehna hai ki "Mujhe woh points zyada care karta hai jo mujhe jald milenge rather than dur future ke points."

Bellman equation sirf iske liye math hai: "Mere current square ki value = abhi mujhe milne wale points + jahan main next land karunga uski (discounted) value."

Best strategy dhundna matlab hai: har square ke liye, woh move choose karo jo sabse zyada total points tak le jaata hai. Wahi optimal policy hai!

Connections

5.1.01-Reinforcement-Learning-Problem-Formulation - MDPs RL problem ko formalize karte hain
5.1.03-Policy-and-Value-Functions - Policies aur values ka deep dive
5.1.04-Bellman-Equations - Bellman equations ka detailed treatment
5.2.01-Dynamic-Programming-inRL - MDPs ko DP methods se solve karna
5.3.01-Monte-Carlo-Methods - $V$ aur $Q$ ka model-free estimation
5.3.02-Temporal-Difference-Learning - TD learning online updates ke liye Bellman equation use karta hai
5.4.01-Q-Learning - Q-values ke liye Bellman optimality equation use karta hai
Markov-Chains - MDPs, Markov chains ko actions aur rewards add karke extend karte hain
Dynamic-Programming - MDP solution methods DP algorithms hain

#flashcards/ai-ml

MDP mein Markov Property kya hai? :: Next state ki probability sirf current state aur action pe depend karti hai, history pe nahi: $P (s_{t + 1} ∣ s_{t}, a_{t}, s_{t - 1}, ...) = P (s_{t + 1} ∣ s_{t}, a_{t})$

MDP ke paanch components kya hain?

States (S), Actions (A), transition Probability (P), Rewards (R), aur discount factor (gamma)

Discount factor

γ

kya hai aur yeh kyun zaroori hai?

[0,1) mein ek value jo future rewards ko immediate rewards se kam valuable banati hai. Mathematical convergence ke liye zaroori hai (finite sums ensure karta hai), future ke baare mein uncertainty model karta hai, aur control karta hai ki agent kitna farsighted hai.

State-value function

V^{π} (s)

kya hai?

State

s

se shuru hokar aur policy

π

follow karke milne wala expected return (cumulative discounted reward):

V^{π} (s) = E_{π} [G_{t} ∣ S_{t} = s]

Action-value function

Q^{π} (s, a)

kya hai?

State

s

se shuru hokar, action

a

lekar, phir policy

π

follow karke milne wala expected return:

Q^{π} (s, a) = E_{π} [G_{t} ∣ S_{t} = s, A_{t} = a]

V^{π}

ke liye Bellman Expectation Equation batao

V^{π} (s) = \sum_{s^{'}} P (s^{'} ∣ s, π (s)) [R (s, π (s), s^{'}) + γ V^{π} (s^{'})]

— value equals immediate reward plus discounted future value

V^{*}

ke liye Bellman Optimality Equation batao

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

— optimal value equals actions ke maximum of expected reward + discounted optimal future

Q^{*} (s, a)

se optimal policy kaise extract karte hain?

π^{*} (s) = ar g max_{a} Q^{*} (s, a)

— har state mein sabse zyada Q-value wala action choose karo

V^{π} (s)

aur

Q^{π} (s, a)

mein kya relationship hai?

V^{π} (s) = Q^{π} (s, π (s))

— state ki value equals us action ki Q-value jo policy us state mein leti hai

MDP mein policy kya hai?

States se actions ka ek mapping

π : S \to A

(deterministic) ya ek probability distribution

π (a ∣ s)

(stochastic) jo agent ka behavior define karta hai

Agar

γ = 0.9

aur tum terminal reward 100 se 3 steps door ek state mein ho, toh undiscounted contribution kya hai?

γ^{3} \times 100 = 0. 9^{3} \times 100 = 0.729 \times 100 = 72.9

Continuing tasks mein

γ = 1

kyun use nahi kar sakte?

Kyunki rewards ka infinite sum diverge ho jaata (infinite value), jisse problem mathematically intractable ho jaati hai jab tak saare rewards zero na hon

γ = 0.95

ke liye effective planning horizon kya hai?

Approximately

1/ (1 - γ) = 1/0.05 = 20

steps — itni door future mein agent effectively consider karta hai

Sach ya Jhooth: Markov property ka matlab hai policy historical information use nahi kar sakti :: Jhooth. Policy history use kar sakti hai agar state mein encode ki gayi ho. Markov property environment dynamics pe apply hoti hai, policy design pe nahi.

MDP ke context mein model-based aur model-free RL mein kya fark hai?

Model-based ko

P (s^{'} ∣ s, a)

aur

R (s, a, s^{'})

(MDP model) pata hota hai aur woh planning use kar sakta hai. Model-free ko yeh nahi pata aur use experience se seekhna padta hai.