SARSA algorithm

5.1.12 · AI-ML › Reinforcement Learning Foundations

SARSA kya hai?

Core property: SARSA optimal Q-values mein converge karta hai us behavior policy ke liye jo follow ki ja rahi hai (jaise $ϵ$-greedy), zaroori nahi ki optimal greedy policy ke liye.

First Principles se Derivation

Step 1: Action-Values ke liye Bellman Equation

Policy $\pi$ ke under action-value function $Q^{\pi }(s,a)$ satisfy karta hai:

$Q^{\pi }(s,a)={\mathbb{E}}_{\pi }[R_{t+1}+\gamma Q^{\pi }(S_{t+1},A_{t+1})\mid S_t=s,A_t=a]$

Yeh form kyun? $(s,a)$ se expected return equals hai immediate reward plus us jagah ki discounted value jahaan policy tumhe actually next le jaati hai.

Step 2: Q-values ke liye TD Error

TD error measure karta hai ki hamara current estimate kitna galat hai:

${\delta }_t=R_{t+1}+\gamma Q(S_{t+1},A_{t+1})-Q(S_t,A_t)$

Yeh kyun important hai?

• Agar ${\delta }_t>0$: Humne $Q(S_t,A_t)$ ko underestimate kiya — outcome expected se better tha.
• Agar ${\delta }_t<0$: Humne overestimate kiya — outcome worse tha.

Key insight: Hum $A_{t+1}$ use karte hain ($S_{t+1}$ par current policy dwara actually chuna gaya action), na ki ${\max }_{a}Q(S_{t+1},a)$.

Step 3: SARSA Update Rule

Jahaan:

• $\alpha \in (0,1]$ learning rate hai
• $\gamma \in [0,1)$ discount factor hai
• $(S_t,A_t,R_{t+1},S_{t+1},A_{t+1})$ experience tuple hai

Derivation: $(Q^{\pi }(s,a)-Q(s,a){)}^2$ minimize karne ke liye stochastic gradient descent apply karo. Target hai $R_{t+1}+\gamma Q(S_{t+1},A_{t+1})$, aur hum apna estimate $\alpha \cdot {\delta }_t$ se us taraf move karte hain.

Complete SARSA Algorithm

Initialize Q(s,a) arbitrarily (often 0) for all s∈ S, a ∈ A
Set Q(terminal, ·) = 0

For each episode:
    Initialize S
    Choose A from S using policy derived from Q (e.g., ε-greedy)
    For each step of episode:
        Take action A, observe R, S'
        Choose A' from S' using policy derived from Q (ε-greedy)
        Q(S, A) ← Q(S, A) + α[R + γQ(S', A') - Q(S, A)]
        S ← S'
        A ← A'
    Until S is terminal

Algorithm is tarah kyun kaam karta hai:

1. Initialize S: Episode ek valid state mein shuru karo
2. Loop se pehle A choose karo: Pehla step lene ke liye ek action chahiye
3. Loop ke andar A' choose karo: SARSA ko update ke liye next action chahiye, isliye hum use update se pehle select karte hain
4. A' se update karo: Yeh on-policy hai — hum woh action use karte hain jo hum actually lenge
5. S ← S', A ← A': Us action ke saath aage badho jo hum pehle se chuk chuke hain

Worked Examples

Setup:

• Grid world: 4×12, start (3,0) par, goal (3,11) par
• Actions: up, down, left, right
• Reward: har step par -1, cliff ke liye -100 (row 3, columns 1-10)
• Policy: $ϵ$-greedy with $ϵ=0.1$
• $\alpha =0.5$, $\gamma =1.0$

Episode trace:

Step	$S_t$	$A_t$	$R_{t+1}$	$S_{t+1}$	$A_{t+1}$	Update
1	(3,0)	up	-1	(2,0)	right	$Q((3,0),\text{up})\leftarrow 0+0.5[-1+1.0\cdot 0-0]=-0.5$
2	(2,0)	right	-1	(2,1)	right	$Q((2,0),\text{right})\leftarrow 0+0.5[-1+0-0]=-0.5$

Yeh steps kyun?

• Step 1: Hum cliff bachane ke liye upar jaate hain. TD target hai $-1+0=-1$ (next Q-value 0 hai kyunki hum ek naye state mein hain). Hamara estimate 0 se -0.5 ho jaata hai.
• Step 2: Safe path par right chalte rehte hain. Same logic apply hoti hai.

Key observation: SARSA safer path seekhta hai (upar jaana phir right) kyunki yeh $ϵ$-greedy exploration ko account karta hai jo accidentally cliff mein step kar sakti hai. Q-learning cliff edge ke bilkul paas optimal path seekh leta, jo exploration ke dauran dangerous hai.

Setup:

• State $S_t=(2,3)$, action $A_t=\text{right}$, $Q(S_t,A_t)=-15.3$
• Wind 1 cell upar push karta hai → $S_{t+1}=(1,4)$
• Reward $R_{t+1}=-1$
• Policy $S_{t+1}$ par $A_{t+1}=\text{right}$ choose karti hai, $Q(S_{t+1},A_{t+1})=-12.1$
• $\alpha =0.1$, $\gamma =0.9$

Step-by-step update:

1. TD target compute karo: $\text{Target}=R_{t+1}+\gamma Q(S_{t+1},A_{t+1})=-1+0.9\times (-12.1)=-1+(-10.89)=-11.89$

   Yeh value kyun? Humein -1 ka reward mila, aur next state-action pair ki value -12.1 hai, 0.9 se discount ki gayi.

2. TD error compute karo: ${\delta }_t=-11.89-(-15.3)=3.41$

   Positive kyun? Hamara current estimate (-15.3) bahut zyada pessimistic tha. Actual outcome better tha.

3. Q-value update karo: $Q(S_t,A_t)\leftarrow -15.3+0.1\times 3.41=-15.3+0.341=-14.959$

   Itna chhota change kyun? 0.1 ka learning rate matlab hai ki hum new estimate ki taraf sirf 10% move karte hain, stability maintain karte hue.

Setup:

• Action "forward" 80% time succeed karta hai, 10% each left/right slip karta hai
• $S_t=s_1$, $A_t=\text{forward}$, $Q(s_1,\text{forward})=5.0$
• Agent right slip karta hai → $S_{t+1}=s_2$ (intended $s_3$ ki jagah)
• $R_{t+1}=-2$ (slipping ka penalty), $\alpha =0.2$, $\gamma =0.95$
• $s_2$ par, policy $A_{t+1}=\text{left}$ choose karti hai, $Q(s_2,\text{left})=3.5$

Update: $\text{Target}=-2+0.95\times 3.5=-2+3.325=1.325$ ${\delta }_t=1.325-5.0=-3.675$ $Q(s_1,\text{forward})\leftarrow 5.0+0.2\times (-3.675)=5.0-0.735=4.265$

Yeh safety kyun sikhata hai: Chahe "forward" usually acha ho, SARSA seekhta hai ki kabhi kabhi yeh bure outcomes lead karta hai. Kaafi episodes ke baad, $Q(s_1,\text{forward})$ slip probabilities samete average outcome reflect karega, jo policy ko zyada cautious banata hai.

On-Policy vs Off-Policy: Key Distinction

Property	SARSA (On-Policy)	Q-Learning (Off-Policy)
Update uses	$Q(S_{t+1},A_{t+1})$ — action actually liya gaya	${\max }_{a}Q(S_{t+1},a)$ — best possible action
Seekhta hai	Behavior policy ki value (jaise $ϵ$-greedy)	Optimal policy ki value
Convergence	$Q^{ϵ\text{-greedy}}$ ki taraf	$Q^{\ast }$ ki taraf
Safety	Exploration ke dauran conservative	Optimistic, riskier

Practice mein yeh kyun important hai:

• Robot navigation: SARSA cliffs ke paas drive karna nahi seekhega kyunki yeh jaanta hai ki yeh randomly explore kar sakta hai. Q-learning perfect future actions assume karta hai.
• Medical treatment: SARSA account karta hai "kya hoga agar next action perfect nahi hai?" — experimentation ke liye safer.

Common Mistakes

Galat update: $Q(S_t,A_t)\leftarrow Q(S_t,A_t)+\alpha [R_{t+1}+\gamma {\max }_{a}Q(S_{t+1},a)-Q(S_t,A_t)]$

Yeh sahi kyun lagta hai: "Kya humein hamesha best action aim nahi karna chahiye?"

Steel-man defense: Yeh logical lagta hai kyunki hum eventually optimal behavior seekhna chahte hain, aur max best possible outcome represent karta hai.

Galat kyun hai: Yeh Q-learning hai, SARSA nahi! SARSA ko policy dwara chosen actual next action $A_{t+1}$ use karna hi padega. Max use karna ise off-policy bana deta hai aur convergence properties change kar deta hai. Tum algorithm se jhooth bol rahe ho ki woh actually kya karega.

Fix: Hamesha $A_{t+1}$ apni policy se update se pehle select karo, aur update mein usi specific action ki Q-value use karo.

Galat algorithm:

Take action A, observe R, S'
Q(S, A) ← Q(S, A) + α[R + γQ(S', A') - Q(S, A)]  // A' not chosen yet!
Choose A' from S' using ε-greedy

Yeh sahi kyun lagta hai: "Pehle update karna chahiye, phir decide karo kya karna hai."

Steel-man defense: Lagta hai ki decisions lene se pehle humein apna knowledge update karna chahiye, jaise experience se seekhna phir act karna.

Galat kyun hai: Update formula ko $Q(S_{t+1},A_{t+1})$ chahiye, lekin $A_{t+1}$ abhi exist hi nahi karta! Ya toh tum ek undefined variable use karoge ya accidentally $A$ ki purani value use karoge, jo algorithm tod deta hai.

Fix: $A^{\prime }$ update se pehle choose karo. Action ko $S^{\prime }$ se select karna hi padega pehle $Q(S^{\prime },A^{\prime })$ query karne se.

Galat expectation: "SARSA $Q^{\ast }$, optimal action-values, mein converge karega."

Yeh sahi kyun lagta hai: "Saare RL algorithms best possible policy seekhna chahiye."

Steel-man defense: Hum reinforcement learning optimal behavior dhundhne ke liye karte hain, isliye har algorithm optimality mein converge karna chahiye.

Galat kyun hai: SARSA $Q^{\pi }$ seekhta hai us policy ke liye jo tum use kar rahe ho. Agar tum $ϵ=0.1$ ke saath $ϵ$-greedy use karte ho, SARSA seekhta hai "har action ki value kya hai agar main $ϵ$-greedy rehta hun?" Na ki "value kya hai agar main optimally act karun?"

Fix:

• $Q^{\ast }$ seekhne ke liye: Q-learning (off-policy) use karo, ya SARSA use karo jahan $ϵ$ 0 tak decay kare.
• Exploration ke under safe behavior seekhne ke liye: Fixed $ϵ$ wala SARSA exactly wahi hai jo tum chahte ho.

Intuitive Mental Model

Recall Ek 12-saal ke bacche ko explain karo

Socho tum ek maze navigate karna seekh rahe ho aankhein band karke, aur kabhi kabhi move karne se pehle randomly ghumte ho.

Q-learning ek aisa dost hai jo tumhe dekh ke kehta hai "Theek hai, lekin agar tum perfect hote aur kabhi randomly nahi ghumte, toh har move ki itni value hoti."

SARSA ek aisa dost hai jo kehta hai "Yeh dhyan mein rakhte hue ki tum KABHI KABHI randomly ghoomte HO, har move ki actually itni value hai jab tum aise todte-todte chal rahe ho."

Agar koi khadda ho, Q-learning kehta hai "optimal path khadde ke bilkul paas hai!" kyunki yeh assume karta hai ki tum kabhi randomly us mein nahi ghumoge. SARSA kehta hai "woh path dangerous hai kyunki tum randomly khadde mein ghoom sakte ho, isliye main ise lower rate karunga."

Tum Q-learning tab chahte ho jab sirf simulation mein seekh rahe ho aur reset kar sakte ho. Tum SARSA tab chahte ho jab actually maze mein ho aur mar nahi sakte.

SARSA kab use karein

SARSA choose karo jab:

1. Safety important ho: Real-world systems (robots, medical, finance) jahaan exploration mistakes ke consequences hain
2. Online learning: Agent actual environment ke saath interact karte hue seekhta hai
3. Stochastic policy: Tum puri exploration maintain karna chahte ho ($ϵ$ ko 0 decay nahi karna)
4. Policy evaluation: Tum jaanna chahte ho "meri current policy kitni acchi hai?" na ki "main kitna acha ho sakta hun?"

Q-learning choose karo jab:

1. Tum eventually optimal policy chahte ho
2. Resets ke saath simulation mein seekh rahe ho
3. Tum safely explore kar sakte ho phir greedy execution par switch kar sakte ho

Parameter Guidelines

Concept Map