Temporal Difference learning — Hinglish notes

5.1.11 · AI-ML › Reinforcement Learning Foundations

Temporal Difference Learning Kya Hai?

Fundamental TD Update

Chalte hain core TD(0) update ko first principles se derive karte hain.

Value function 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.

Key insight: Hum return ko recursively rewrite kar sakte hain: $G_{t} = R_{t + 1} + γ G_{t + 1}$

Yeh step kyun? Hum immediate reward ko saare future rewards se alag kar rahe hain, jo hamare future value ke estimate ko substitute karne deta hai.

Value function mein substitute karo: $V^{π} (s) = E_{π} [R_{t + 1} + γ G_{t + 1} ∣ S_{t} = s]$

Yeh step kyun? Expectation ki linearity se: $V^{π} (s) = E_{π} [R_{t + 1} ∣ S_{t} = s] + γ E_{π} [G_{t + 1} ∣ S_{t} = s]$

Bootstrapping ka magic: Doosra term sirf next state ki value hai: $V^{π} (s) = E_{π} [R_{t + 1} + γ V^{π} (S_{t + 1}) ∣ S_{t} = s]$

Yahi $V^{π}$ ke liye Bellman equation hai.

TD Target Derive Karna

Yeh diagram dikhata hai ki TD kyun kaam karta hai: har step par, hamen nayi information milti hai (actual reward $R_{t + 1}$ ) jo humara estimate pehle se zyada accurate banati hai.

Teen estimates jo play mein hain:

Purana estimate: $V (S_{t})$ — action lene se pehle hum kya sochte the
Actual sample: Hum $R_{t + 1}$ observe karte hain — real, experienced data
TD target: $R_{t + 1} + γ V (S_{t + 1})$ — real reward aur future ke baare mein hamare current best guess ko combine karta hai

Yeh Monte Carlo se smarter kyun hai:

MC episode end tak wait karta hai $G_{t} = R_{t + 1} + γ R_{t + 2} + γ^{2} R_{t + 3} + \dots$ dekhne ke liye
TD, infinite sum $R_{t + 2} + γ R_{t + 3} + \dots$ ki jagah $V (S_{t + 1})$ substitute karta hai
Yeh variance reduce karta hai kyunki hum kam estimate kar rahe hain (sirf ek step ki randomness)
Lekin bias introduce karta hai kyunki $V (S_{t + 1})$ abhi true value nahi hai

TD(0) Algorithm Policy Evaluation Ke Liye

Worked example TD(0) Step-by-Step

Goal: Ek given policy $π$ ke liye $V^{π} (s)$ estimate karna Algorithm:

Initialize V(s) arbitrarily for all s∈ S (except V(terminal) = 0)
For each episode:
    Initialize S_t
    For each step of episode:
        A_t ← action from π(S_t)
        Take action A_t, observe R_{t+1}, S_{t+1}
        V(S_t) ← V(S_t) + α[R_{t+1} + γV(S_{t+1}) - V(S_t)]
        
        S_t ← S_{t+1}
        If S_t is terminal, break

Har component kyun:

Hum arbitrarily initialize karte hain kyunki TD koi bhi starting values experience se correct kar dega
Hum turant update karte hain har transition ke baad (online learning)
Terminal states ki value 0 hoti hai by definition (koi future rewards nahi)

Worked Examples

Worked example Example 1: Grid World Navigation

Setup: 3×3 grid, start (0,0) par, goal (2,2) par, reward -1 per step, γ=0.9, α=0.1 Initial values: Saare $V (s) = 0$ except goal

Episode 1, Step 1:

State: (0,0), Action: Right, Reward: -1, Next State: (0,1)
TD error: $δ = - 1 + 0.9 \times 0 - 0 = - 1$
Update: $V (0, 0) \leftarrow 0 + 0.1 \times (- 1) = - 0.1$ Yeh step kyun? Humne abhi seekha ki (0,0) mein hona aur right jaana -1 reward deta hai aur ek aisi state par le jaata hai jise hum currently 0 value karte hain. Hamara estimate bahut optimistic tha (humne socha 0), toh hum ise kam karte hain.

Episode 1, Step 2:

State: (0,1), Action: Right, Reward: -1, Next State: (0,2)
TD error: $δ = - 1 + 0.9 \times 0 - 0 = - 1$
Update: $V (0, 1) \leftarrow 0 + 0.1 \times (- 1) = - 0.1$ Bahut saare episodes ke baad: Values goal se backward propagate hoti hain. Goal ke zyada paas wale states higher (kam negative) values develop karte hain. Agent bootstrapping ke through value landscape seekhta hai.

Common Mistakes aur Misconceptions

TD vs Monte Carlo vs Dynamic Programming

Property	TD	Monte Carlo	Dynamic Programming
Model chahiye?	Nahi	Nahi	Haan
Bootstrap karta hai?	Haan	Nahi	Haan
Online?	Haan	Nahi	N/A
Complete episodes?	Nahi	Haan	N/A
Bias	Biased	Unbiased	N/A
Variance	Low	High	N/A
Convergence	Guaranteed*	Guaranteed	Guaranteed

*appropriate learning rate schedule ke saath

Recall Feynman Explanation (Ek 12-saal ke bachche ko explain karo)

Socho tum school se ghar chal rahe ho, aur tum guess karna chahte ho kitna time lagega. Tum:

Monte Carlo way: Poora rasta ghar tak chalo, apni watch dekho, aur tab kaho "Oh, 20 minute lage." Sirf khatam hone ke baad apna guess update karo.
TD way: Har block ke baad apna guess update karo. "Mujhe laga tha 20 minute lagenge total, lekin maine abhi ek block 2 minute mein chala, aur mujhe lagta hai baaki 17 minute aur lagenge. Toh mera naya guess hai 2 + 17 = 19 minute."

TD smarter hai kyunki:

Tum chalte-chalte seekhte ho, sirf end mein nahi
Agar kuch unexpected hota hai (jaise traffic milna), tum apna guess turant update karte ho
Jab tak tum aadhe raste ho, tumhare paas already ek accha estimate hota hai

"Temporal difference" woh difference hai jo tumne socha tha hoga aur jo actually hua. Har baar jab reality tumhe surprise karti hai (accha ya bura), tum apna guess thoda adjust karte ho.

Fancy math kyun? $R_{t + 1} + γ V (S_{t + 1}) - V (S_{t})$ bas yeh hai:

$R_{t + 1}$ = abhi kya hua (jaise ek block chalna)
$V (S_{t + 1})$ = baaki journey ke liye tumhara guess
$V (S_{t})$ = poori journey ke liye tumhara purana guess
Difference batata hai ki tumhara purana guess bahut zyada tha ya bahut kam!

Doosre RL Concepts Se Connection

Key Takeaways

TD incomplete episodes se seekhta hai current value estimates se bootstrapping karke
TD error $δ_{t} = R_{t + 1} + γ V (S_{t + 1}) - V (S_{t})$ saare updates drive karta hai
TD strengths combine karta hai: sampling (MC ki tarah) + bootstrapping (DP ki tarah) = model-free online learning
Bias-variance tradeoff: TD ka variance MC se kam hai lekin bootstrapping se bias introduce hota hai
Faster propagation: Values, MC se zyada efficiently state space mein backward spread hoti hain

#flashcards/ai-ml

Temporal Difference learning ke peeche fundamental idea kya hai? :: TD learning, value estimates ko har step ke turant baad update karta hai, current prediction ko ek nayi prediction se compare karke jo actual reward received aur next state ki estimated value (bootstrapping) par based hoti hai. Yeh incomplete episodes se seekhta hai.

TD(0) update rule kya hai?

V (S_{t}) \leftarrow V (S_{t}) + α [R_{t + 1} + γ V (S_{t + 1}) - V (S_{t})]

, jahan bracketed term TD error hai jo measure karta hai ki hamari prediction kitni off thi.

TD error formula kya hai aur yeh kya represent karta hai?

δ_{t} = R_{t + 1} + γ V (S_{t + 1}) - V (S_{t})

. Yeh hamare improved estimate (TD target:

R_{t + 1} + γ V (S_{t + 1})

) aur hamare purane estimate

V (S_{t})

ke beech ka difference represent karta hai. Yeh batata hai ki hum kitne galat the.

TD target kya hai?

TD target

R_{t + 1} + γ V (S_{t + 1})

hai. Yeh hamara improved estimate hai jo actual observed reward

R_{t + 1}

aur future value ke baare mein hamare current best guess

γ V (S_{t + 1})

ko combine karta hai.

TD learning ke context mein bootstrapping kya hai?

Bootstrapping matlab hai ek estimate ko doosre estimates ke basis par update karna, actual final outcomes ka wait kiye bina. TD,

V (S_{t})

update karne ke liye

V (S_{t + 1})

(ek estimate) use karta hai, true return

G_{t}

ka wait karne ki jagah.

TD aur Monte Carlo ke beech teen key differences kya hain?

1) TD online update karta hai (har step) vs MC episode ke baad; 2) TD estimates se bootstrap karta hai vs MC actual returns use karta hai; 3) TD biased hai lekin lower variance vs MC unbiased hai lekin higher variance.

TD learning ka variance Monte Carlo se kam kyun hota hai?

TD sirf randomness ke ek step par depend karta hai (R_{t+1} aur S_{t+1}), phir ek estimate use karta hai. MC episode mein baaki saare steps ki randomness par depend karta hai. Kam random variables = lower variance.

TD learning mein bias hota hai jabki Monte Carlo mein nahi, kyun?

TD,

V (S_{t + 1})

use karta hai jo ek estimate hai (true value nahi) target compute karne ke liye. Yeh bias introduce karta hai. MC actual return

G_{t}

use karta hai, jo true value ka unbiased sample hai.

Kya TD learning model-free hai ya model-based aur kyun?

Model-free. TD, sampled experience (transitions) se seekhta hai bina transition dynamics

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

ya reward function

R (s, a)

jaane. Hum

(S_{t}, A_{t}, R_{t + 1}, S_{t + 1})

directly environment interaction se observe karte hain.

TD convergence ke liye learning rate α ko kaunsi properties satisfy karni chahiye?

Guaranteed convergence ke liye:

\sum_{t = 1}^{\infty} α_{t} = \infty

(sufficient learning) aur

\sum_{t = 1}^{\infty} α_{t}^{2} < \infty

(decreasing step sizes). Example:

α_{t} = 1/ t

α_{t} = 1/ n (s)

jahan n(s) state visit count hai.

TD learning, state space mein value information kaise propagate karta hai?

Backward propagation: rewards ke paas wale states pehle seekhte hain, phir unke predecessors unse seekhte hain, ek value gradient create karta hai. Har state, bootstrapping ke through apne predecessor ko "sikhata" hai, MC se faster propagation allow karta hai.

TD learning mein α=1 set karne par kya hota hai?

α=1 ke saath, tumhe milta hai

V (S_{t}) \leftarrow R_{t + 1} + γ V (S_{t + 1})

, purane estimate ko completely ek noisy sample se replace karta hai. Yeh wild oscillations cause karta hai aur convergence rokta hai—multiple experiences par koi smoothing nahi.

TD ka Dynamic Programming par kya advantage hai?

TD model-free hai (

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

R (s, a)

jaanne ki zaroorat nahi), actual experience se seekhta hai, aur naturally stochastic environments handle karta hai bina saare possible transitions par expectations compute kiye.

Perfect value estimates ke baath bhi TD error zero kyun nahi pahunchta?

Environment mein stochasticity ki wajah se. Correct values ke baad bhi, random rewards aur transitions TD error ko zero ke aas-paas fluctuate karate hain. Sirf expected TD error

E [δ_{t}]

zero par converge karta hai, individual samples nahi.

TD(0) aur Bellman equation ke beech kya relationship hai?

TD(0), Bellman equation ka ek stochastic approximation hai. TD target

R_{t + 1} + γ V (S_{t + 1})

, Bellman equation

E [R_{t + 1} + γ V (S_{t + 1}) ∣ S_{t}]

ke right side ka ek sampled estimate hai.