Monte Carlo methods — Hinglish notes

5.1.10 · AI-ML › Reinforcement Learning Foundations

Monte Carlo Alag Kaise Hai?

Model-free kyun matter karta hai: Real-world problems mein (robotics, game playing, resource allocation), hame rarely accurate models milte hain ki environment actions pe kaise respond karta hai. MC methods hume directly interaction se seekhne deti hain.

Return: Hum Kya Average Kar Rahe Hain

Recursive form ki derivation: Definition se shuru karte hain: $G_{t} = R_{t + 1} + γ R_{t + 2} + γ^{2} R_{t + 3} + γ^{3} R_{t + 4} + \dots$

Pehle term ke alawa baaki sab se $γ$ factor out karo: $G_{t} = R_{t + 1} + γ (R_{t + 2} + γ R_{t + 3} + γ^{2} R_{t + 4} + \dots)$

Parentheses mein jo expression hai woh exactly $G_{t + 1}$ hai: $G_{t} = R_{t + 1} + γ G_{t + 1}$

First-Visit vs Every-Visit MC

Distinction kyun? Kuch episodes mein tum same state ko kai baar visit kar sakte ho (e.g., ek maze mein tum same room mein wapas aa sakte ho). Kya hume har visit alag count karni chahiye ya sirf pehli?

Monte Carlo Policy Evaluation

Incremental update kyun? Saare returns store karne aur mean recompute karne ki jagah: $NewMean = \frac{1}{n} \sum_{i = 1}^{n} x_{i} = \frac{1}{n} [(n - 1) \cdot OldMean + x_{n}] = OldMean + \frac{1}{n} (x_{n} - OldMean)$

Yeh memory-efficient hai aur mathematically equivalent hai.

Worked example MC Policy Evaluation: Blackjack

Problem: Simplified blackjack mein "20 ya 21 par stick karo" policy ki value estimate karo.

States: (player sum, dealer showing, usable ace?)
Episode example: Start (12, 2, no) → hit → (19, 2, no) → stick → dealer 21 tak draw karta hai → lose $R = - 1$ State (12, 2, no) ki pehli visit:
$G = - 1$ (final reward, $γ = 1$ )
Agar $N$ (12, 2, no) $= 5$ , toh yeh 6th visit hai: $V (12, 2, no) \leftarrow V (12, 2, no) + \frac{1}{6} [- 1 - V (12, 2, no)]$ Yeh step kyun? Humne is state se ek naya sample return observe kiya. Hum apna running average update kar rahe hain is naye evidence ko incorporate karne ke liye. $1/6$ weight (sixth visit) ensure karta hai ki saare samples mean mein equally contribute karein.

10,000 episodes ke baad, (12, 2, no) shayad 200 baar visit hua hoga alag alag returns ke saath, aur $V (12, 2, no)$ true value ki taraf converge hoga (exact rules ke hisaab se roughly -0.3 se -0.5 tak).

Monte Carlo Control: Optimal Policy Seekhna

Policy evaluation bataata hai ki ek policy kitni achi hai. Monte Carlo control optimal policy dhundta hai generalized policy iteration ke through: evaluation aur improvement ke beech alternate karo.

Formula ε-Greedy Exploration ke saath MC Control

Goal: Bina model ke optimal policy $π_{*}$ seekhna.

Challenge: Better actions dhundne ke liye exploration maintain karni padegi. Solution: ε-greedy policies.

Algorithm (On-Policy First-Visit MC Control):

Initialize: $Q (s, a) = 0$ , $N (s, a) = 0$ , $π$ = $Q$ ke w.r.t. ε-greedy
Repeat:

$π$ use karke episode generate karo: $S_{0}, A_{0}, R_{1}, \dots, S_{T}$
Visit kiye gaye har $(s, a)$ pair ke liye (first-visit):
- $G \leftarrow$ $(s, a)$ ki pehli occurrence ke baad ki return
- $N (s, a) \leftarrow N (s, a) + 1$
- $Q (s, a) \leftarrow Q (s, a) + \frac{1}{N ( s , a )} [G - Q (s, a)]$
Policy Improvement: Episode mein har $s$ ke liye: $π (s) = {ar g max_{a} Q (s, a) random action w.p. 1 - ε w.p. ε$ ε-greedy kyun? Pure greedy ( $ε = 0$ ) shayad kabhi woh actions try na kare jo optimal path tak le jaate hain. $ε > 0$ ke saath, hum explore karte hain (random actions try karte hain) chhoti probability se, ensuring ki saare $(s, a)$ pairs infinitely often visit hon → optimal policy ki taraf convergence.

$V (s)$ ki jagah $Q (s, a)$ kyun seekhte hain? Policy improvement ke liye hume chahiye: $π^{'} (s) = ar g max_{a} [r (s, a) + γ \sum_{s^{'}} P (s^{'} ∣ s, a) V (s^{'})]$

Lekin hume $P$ ya $r$ nahi pata (model-free)! $Q (s, a)$ ke saath, improvement simple hai: $π^{'} (s) = ar g max_{a} Q (s, a)$ Koi model nahi chahiye— $Q$ already expected future ko encapsulate karta hai.

Worked example MC Control: Grid World

Environment: 4×4 grid, goal (3,3) par, har step par -1 reward.

Random policy ke under episode: $(0, 0) right (0, 1) down (1, 1) down (2, 1) right (2, 2) right (2, 3) down (3, 3)$

Total steps: 6, toh start se $G = - 6$ Q-value updates (first-visit, $γ = 1$ ):
$Q ((0, 0), right) \leftarrow Q ((0, 0), right) + α [- 6 - Q ((0, 0), right)]$
$Q ((0, 1), down) \leftarrow Q ((0, 1), down) + α [- 5 - Q ((0, 1), down)]$
... (har state-action ko aage se return milti hai)

Yeh step kyun? Har $(s, a)$ pair ko us return ka credit milta hai jab se woh liya gaya. Bahut saare episodes ke baad, $((0, 0), right)$ un saare episodes ke returns average karta hai jahan start se right liya gaya. Eventually, optimal actions (jaise shortest paths) ke Q-values better ho jaate hain.

Policy improvement: 100 episodes ke baad, agar $Q ((0, 0), right) = - 5.2$ aur $Q ((0, 0), down) = - 6.8$ , toh ε-greedy right action prefer karta hai (agar 4 actions hain toh $1 - ε + ε /4$ probability se liya jaata hai).

Off-Policy Learning ke liye Importance Sampling

Importance sampling correction ki derivation: Hume chahiye: $v_{π} (s) = E_{π} [G_{t} ∣ S_{t} = s]$

Lekin hum $b$ se sample kar rahe hain, jo deta hai: $E_{b} [G_{t} ∣ S_{t} = s]$

Trick: $P_{b} (τ)$ se multiply aur divide karo, yaani factor $1 = \frac{P _{b} ( τ ∣ s )}{P _{b} ( τ ∣ s )}$ insert karo aur numerator ko $P_{π} (τ ∣ s)$ likhte hain, jahaan $τ$ woh trajectory hai jo $s$ ke baad aati hai: $E_{π} [G ∣ S_{0} = s] = \sum_{τ} P_{π} (τ ∣ s) G (τ) = \sum_{τ} P_{b} (τ ∣ s) \frac{P _{π} ( τ ∣ s )}{P _{b} ( τ ∣ s )} G (τ) = E_{b} [\frac{P _{π} ( τ ∣ s )}{P _{b} ( τ ∣ s )} G S_{0} = s]$

Ratio $\frac{P _{π} ( τ )}{P _{b} ( τ )} = \prod_{t = 0}^{T - 1} \frac{π ( A _{t} ∣ S _{t} )}{b ( A _{t} ∣ S _{t} )}$ isliye kyunki state-transition probabilities $P (S_{t + 1} ∣ S_{t}, A_{t})$ numerator aur denominator dono mein identically appear hoti hain (same environment) aur cancel ho jaati hain.

Worked example Importance Sampling in Action

Scenario: Target policy $π$ hamesha right jaati hai. Behavior policy $b$ 50% right, 50% left jaati hai.

$b$ se episode: Start $S_{0}$ → right → $S_{1}$ → right → $S_{2}$ (terminal), $G_{0} = 10$ Importance ratio: $ρ_{0 : 1} = \frac{π ( right ∣ S _{0} )}{b ( right ∣ S _{0} )} \times \frac{π ( right ∣ S _{1} )}{b ( right ∣ S _{1} )} = \frac{1.0}{0.5} \times \frac{1.0}{0.5} = 4.0$

Yeh step kyun? Trajectory (right, right) $π$ ke under $b$ se 4 guna zyada likely hai. Toh hum is episode ki return ko 4 se weight karte hain jab target policy $π$ ke liye $V (S_{0})$ update karte hain.

Weighted update: Agar yeh hamara ek hi episode hai, toh ordinary importance sampling deta hai $V (S_{0}) = \frac{4.0 \times 10}{1} = 40$ , jabki weighted importance sampling deta hai $V (S_{0}) = \frac{4.0 \times 10}{4.0} = 10$ . Weighted estimate yahan zyada stable hai kyunki ratios ke sum se divide karne par value observed return ke same scale par rehti hai.

Problem: Agar $b$ ne left-left liya hota (probability 0 under $π$ ), toh us episode ka $ρ = 0$ hota aur kuch contribute nahi karta. Hum sirf un episodes se seekh sakte hain jo $π$ ne generate kiye ho sakte the. Agar $π$ deterministic hai aur $b$ stochastic, toh bahut saare episodes ko zero weight milta hai → inefficient.

Common mistake Common Pitfalls

Mistake 1: "MC toh sirf averaging hai—main partial episodes use kar sakta hoon" Kyun sahi lagta hai: Hum returns average kar rahe hain, toh episode khatam hone ka wait kyun karein? Kyun galat hai: Return $G_{t}$ episode termination tak sum ke roop mein defined hai. Episode beech mein kaatne se biased estimate milta hai (jaise agar tum reward se pehle rok do, $G_{t} = 0$ hamesha). MC ko episodic tasks chahiye. Fix: Continuing tasks ya bahut lambe episodes wale environments ke liye TD methods (temporal difference) use karo.

Mistake 2: "Pure greedy kaam karta hai—explore kyun karein?" Kyun sahi lagta hai: Agar $Q (s, a_{1}) > Q (s, a_{2})$ , toh return maximize karne ke liye hamesha $a_{1}$ lo. Kyun galat hai: Initial $Q$ estimates limited samples par based hain. $a_{2}$ actually better ho sakta hai lekin abhi tak itna try nahi kiya gaya. Greedy un local optima mein lock ho jaata hai jo pehle discover hue. Fix: ε-greedy exploration guarantee karta hai. Bade $ε$ se shuru karo (jaise 0.1), time ke saath decay karo. Ensure karta hai ki saare actions infinitely often try hon → eventually global optimum milta hai.

Mistake 3: "Importance sampling off-policy ke liye hamesha kaam karta hai" Kyun sahi lagta hai: Math dikhata hai $E_{b} [ρG] = E_{π} [G]$ , toh bas samples weight karo. Kyun galat hai: Agar $π$ aur $b$ bahut alag hain, toh $ρ$ mein huge variance hoti hai. Zyaatar episodes ko near-zero weight milta hai, kuch ko enormous weight → estimates explode hoti hain ya slowly converge hoti hain. Agar $π$ deterministic hai aur trajectory mein koi ek action bhi $π (a ∣ s) = 0$ wala ho, toh woh poori trajectory kuch contribute nahi karti. Fix: $b$ ko $π$ ke paas rakho (jaise $b$ = greedy $π$ ki ε-greedy version). Off-policy ke liye design kiye gaye methods use karo (jaise Q-learning with TD, alag cover kiya gaya hai).

MC vs Temporal Difference (TD)

MC ke Advantages:

Unbiased estimates (true value ki taraf converge hote hain)
No bootstrapping → incorrect value estimates se koi error propagation nahi
Implement karna aur samajhna simple hai
Incomplete knowledge se bhi seekh sakte hain environment ki (jab tak episodes terminate hote hain)

MC ke Disadvantages:

High variance: Ek episode ki return stochasticity ki wajah se wildly vary kar sakti hai
Episodic tasks zaroori hain (terminal state tak pahunchna padta hai)
Slow convergence: Estimates stabilize hone se pehle bahut saare episodes chahiye
Delayed learning: Episode complete hone tak update nahi kar sakte (lambe episodes ke liye bura)

Recall Ek 12-Saal Ke Bacche Ko Explain Karo

Socho tum ek video game khelna seekh rahe ho aur har level kitna acha hai yeh figure out karne ki koshish kar rahe ho. Monte Carlo way: Tum level 3 se game ke end tak poora game khelte ho, apna final score dekhte ho, aur bolte ho "Okay, level 3 se start karke, mujhe average 50 points mile." Tum yeh baar baar karte ho—complete games khelna, jo hua woh likhna, aur results average karna. Yeh aisa hai jaise ek science experiment karo jahan tum har baar poora test run karo aur final result record karo. Super accurate, lekin bahut time lagta hai kyunki har game finish karni padti hai!

Kyun cool hai: Tumhe game ke rules jaanne ki zaroorat nahi! Tum bas khelo aur dekho kya hota hai. Chahe game random bhi ho (kabhi enemies aate hain, kabhi nahi), agar tum enough baar khelo, tumhara average sach ke bahut karib hoga.

Tricky part: Agar game bahut lamba hai ya kabhi khatam hi nahi hoti (jaise Minecraft), toh tum yeh method use nahi kar sakte kyunki tumhe kabhi "final score" nahi milta!

Connections

5.1-Markov-Decision-Processes: MC un values estimate karta hai jo Bellman equations satisfy karti hain
5.1.2-Dynamic-Programming