Q-learning algorithm

5.1.13 · AI-ML › Reinforcement Learning Foundations

Q-learning kya hai?

Properties ko tod ke samjhte hain:

• Model-free: Transition probabilities $P(s^{\prime }|s,a)$ ya reward function $R(s,a)$ ki knowledge ki zaroorat nahi
• Off-policy: Exploratory (jaise ε-greedy) policy follow karte hue bhi optimal policy seekh sakta hai
• Temporal-difference: Estimates ko doosri estimates ke basis par update karta hai (bootstrapping)

Q-learning ko First Principles se Derive Karna

Step 1: Bellman Optimality Equation se Shuru Karo

Optimal action-value function yeh satisfy karta hai:

$Q^{\ast }(s,a)={\mathbb{E}}_{s^{\prime }}\left[r+\gamma {\max }_{a^{\prime }}{Q}^{\ast }(s^{\prime },a^{\prime })\right]$

Yeh form kyun?

• $Q^{\ast }(s,a)$ = state $s$ se start karke, action $a$ lekar, phir optimal policy follow karne par expected total discounted return
• Immediate reward $r$ + next state se discounted optimal value
• Hum ${\max }_{a^{\prime }}$ lete hain kyunki optimal policy hamesha next state mein best action choose karti hai

Step 2: Expectation ko Sampling mein Badlo

Hume transition model pata nahi, isliye hum expectation compute nahi kar sakte. Iske bajaaye, hum experience se transitions $(s,a,r,s^{\prime })$ sample karte hain:

$Q^{\ast }(s,a)\approx r+\gamma {\max }_{a^{\prime }}{Q}^{\ast }(s^{\prime },a^{\prime })$

Yeh single sample humein ek target deta hai ki $Q(s,a)$ kya hona chahiye.

Step 3: Learning Rate ke Saath Iterative Update

Kyunki ek sample noisy hota hai, hum gradually update karte hain:

Jahan:

• $\alpha$ learning rate (0 < α ≤ 1)
• $\gamma$ = discount factor (0 ≤ γ ≤ 1)
• $r+\gamma {\max }_{a^{\prime }}Q(s^{\prime },a^{\prime })$ = TD target
• $r+\gamma {\max }_{a^{\prime }}Q(s^{\prime },a^{\prime })-Q(s,a)$ = TD error (δ)

Yeh kyun kaam karta hai:

• Hum Q(s,a) ko target ki taraf α fraction se move karte hain
• Agar α=1 hota, to hum Q(s,a) ko naye estimate se replace kar dete (high variance)
• Agar α chhota ho, to hum kaafi samples par average karte hain (lower variance, slower learning)
• $\max$ operation ensure karta hai ki hum optimal Q-values seekh rahe hain, chahe hum optimally act nahi kar rahe

Complete Q-learning Algorithm

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

For each episode:
    Initialize state s
    For each step of episode:
        Choose action a from s using policy derived from Q (e.g., ε-greedy)
        Take action a, observe reward r and next state s'
        
        Q(s,a) ← Q(s,a) + α[r + γ max_a' Q(s',a') - Q(s,a)]
        
        s ← s'
    Until s is terminal

Har component kyun hai:

• ε-greedy exploration: Exploitation (max Q choose karo) aur exploration (random action) ka balance
• Q ko arbitrarily initialize karo: Algorithm phir bhi converge karta hai (proof contraction mapping se)
• Terminal states Q=0: Episode khatam hone ke baad koi future value nahi
• Har step ke baad update: Online learning, episode complete hone ka wait nahi karna

Convergence Guarantees

Iska matlab:

• Condition 1: Exploration zaroori hai (ε-greedy yeh ensure karta hai)
• Condition 2: Learning rate kam hona chahiye lekin bahut jaldi nahi (jaise ${\alpha }_t=1/t$ kaam karta hai)
• Condition 3: Discounting ensure karta hai ki operator Q-functions ke beech distances "contract" kare

Yeh contraction kyun hai, iska derivation:

Do Q-functions $Q_1$ aur $Q_2$ ke liye, Bellman operator $\mathcal{T}$ apply karta hai:

$[\mathcal{T}Q](s,a)=\mathbb{E}[r+\gamma {\max }_{a^{\prime }}Q(s^{\prime },a^{\prime })]$

$\mathcal{T}$ apply karne ke baad distance:

$|\mathcal{T}{Q}_1-\mathcal{T}{Q}_2|{|}_{\infty }\le \gamma ||Q_1-Q_2|{|}_{\infty }$

Kyunki γ < 1 hai, har application maximum difference ko γ factor se reduce karta hai → unique fixed point $Q^{\ast }$ par convergence.

Worked Examples

Initial: Q(s,a) = 0 sabhi s,a ke liye

Episode 1, Step 1:

• State s = (0,0), action a = right choose karo (random exploration)
• Observe karo: r = -1, s' = (0,1)
• Current: Q((0,0), right) = 0
• Target: r + γ max Q((0,1), ·) = -1 + 0.9×0 = -1
• Update: Q((0,0), right)← 0 + 0.1×(-1 - 0) = -0.1

Yeh step kyun? Humne seekha ki start se right jaane ki value -0.1 hai (thodi negative kyunki humein -1 reward mila aur next state ki koi learned value nahi thi abhi tak).

Episode 1, Step 2:

• State s = (0,1), a = right choose karo
• Observe karo: r = -1, s' = (0,2)
• Update: Q((0,1), right) ← 0 + 0.1×(-1 - 0) = -0.1

Episode 5, Step 8 (kaafi updates ke baad):

• State s = (2,1), a = right choose karo
• Observe karo: r = -1, s' = (2,2) [goal]
• Current: Q((2,1), right) = -0.4 (pichle updates se)
• Target: -1 + 0.9×10 = 8.0 (goal state ki high value hai!)
• Update: Q((2,1), right) ← -0.4 + 0.1×(8.0 - (-0.4)) = -0.4 + 0.84 = 0.44

Yeh kyun important hai? +10 reward backward propagate hota hai! Ab goal tak jaane waale states valuable ho jaate hain.

1000 episodes ke baad: Q((0,0), right) ≈ 5.8 (goal tak accha path) Q((0,0), down) ≈ 4.2 (longer path) Agent ne optimal policy seekh li: goal tak shortest path.

Scenario:

• State s, optimal action a* ka Q(s, a*) = 5 hai
• Suboptimal action a₁ ka Q(s, a₁) = 2 hai
• Agent exploration ki wajah se a₁ choose karta hai, r=-1 milta hai, s' jahan max Q(s',·) = 6

Liye gaye suboptimal action ke liye update: Q(s, a₁) ← 2 + 0.1×[-1 + 0.9×6 - 2] = 2 + 0.1×2.4 = 2.24

Key insight: Chahe agent ne a₁ liya (optimal nahi), update $\max Q(s^{\prime },\cdot )$ use karta hai jo optimal future behavior represent karta hai. Algorithm suboptimally behave karte hue bhi Q* seekhta hai.

SARSA (on-policy) se comparison: SARSA Q(s', a') use karta jahan a' actual next action hota (jo ε-greedy ki wajah se suboptimal ho sakta tha). Q-learning ka max ka use ise off-policy banata hai.

Common Mistakes aur Steel-Manning

Steel-man: Yeh concern valid hai! Pure greedy selection local optima mein phans jaati hai.

Fix: Q-learning algorithm aur behavior policy alag hain. Exploration ensure karne ke liye action selection mein ε-greedy ya softmax use karo. Convergence theorem require karta hai ki sabhi (s,a) pairs infinite baar visit hon — tumhe explore karna hi hoga.

Practical tip: Uunche ε se shuru karo (jaise 0.3), time ke saath decay karo (jaise ε = 1/episode_number).

Steel-man: Yeh actually SACH hai! Ise maximization bias kehte hain. Stochastic environments mein, Q-estimates mein noise ki wajah se max Q(s',·) true value ko overestimate karta hai.

Fix: Double Q-learning use karo (Hasselt, 2010):

• Do Q-functions maintain karo: Q₁ aur Q₂
• Best action select karne ke liye Q₁ use karo: a* = argmax Q₁(s',a)
• Use usse evaluate karne ke liye Q₂: target = r + γ Q₂(s', a*)
• Q₁ update karo (aur vice versa, alternating)

Yeh kyun kaam karta hai: Independent estimates se selection aur evaluation bias cancel ho jaata hai.

Steel-man: Theoretical convergence to exact Q* ke liye mathematically correct.

Practical reality: Constant small α (jaise 0.01-0.1) practice mein better kaam karta hai kyunki:

• Environments non-stationary ho sakte hain (reward structure change hoti hai)
• Small constant α adapt karta rehta hai
• Tum "good enough" policy zyada jaldi reach karte ho

α kab decrease karo: Fixed, deterministic environments mein jahan tumhe exact convergence chahiye.

Active Recall Flashcards

#flashcards/ai-ml

Q-learning ki teen key properties kya hain? :: Model-free (koi environment model nahi chahiye), off-policy (suboptimally behave karte hue optimal seekhta hai), temporal-difference (estimates se bootstraps karta hai)

Q-learning update rule likho aur har term explain karo :: Q(s,a) ← Q(s,a) + α[r + γ max Q(s',a') - Q(s,a)]. α=learning rate, r=immediate reward, γ=discount, max Q(s',a')=optimal next state value, bracket wala term=TD error

Ek grid world mein, (1,1) par agent right action leta hai, reward=-1 milta hai, (1,2) pahuncha jahan max Q=3 hai. Current Q((1,1),right)=1. α=0.2, γ=0.9 ke saath naya Q-value kya hoga? :: Target = -1 + 0.9×3 = 1.7. TD error = 1.7 - 1 = 0.7. New Q = 1 + 0.2×0.7 = 1.14

Q-learning Q(s,a) ki arbitrary initialization kyun use kar sakta hai? :: Bellman optimality operator ek contraction mapping hai jab γ<1. Repeated application kisi bhi starting point se unique fixed point Q* par converge karta hai, haalaanki initialization convergence speed affect karti hai.

Q-learning ek notebook rakhne jaisa hai jisme tum apne har choice ke scores likhte ho. Har room mein, tum alag-alag doors try karte ho aur likhte ho: "Room A, left jao: score = 5" ya "Room A, right jao: score = -2".

Iska clever part yeh hai: jab tum naye room mein jaate ho, tum apni notebook dekhte ho ki us room ke kis door ka score sabse zyada hai jo tumne abhi tak likha hai. Tumne jis door se entry ki, uska score update karne ke liye tum usi ko use karte ho!

Chahe tum randomly explore kar rahe ho (kabhi kabhi coin flip karke doors choose karo), tumhari notebook best choices kya hain yeh seekhti hai. Kaafi exploring ke baad, tumhari notebook tumhe khazane tak perfect path bata deti hai, chahe seekhte waqt tumne kaafi galat turns liye hon.

"Q" bas tumhari notebook ke scores ka naam hai. Aur tum unhe dheere-dheere update karte ho (learning rate α) kyunki ek trip lucky ya unlucky ho sakti hai — tum kaafi tries ka average chahte ho.

Visual: Ek treasure map imagine karo jo khud draw hoti hai jab tum randomly explore karte ho — "max" operation hamesha abhi tak mili best path add karta hai.

Connections

• Foundational to: Deep Q-Networks (DQN), Double Q-learning, Prioritized Experience Replay
• Contrasts with: SARSA (on-policy alternative), Policy Gradient Methods (directly policy optimize karte hain), Monte Carlo RL (episode complete hone ka wait karta hai)
• Builds on: Bellman Equations, Temporal Difference Learning, Markov Decision Processes
• Requires: Exploration-Exploitation Trade-off, Function Approximation (bade state spaces ke liye)
• Applied in: Atari Game Playing, Robot Control, Resource Allocation
• Theoretical foundation: Dynamic Programming, Contraction Mapping Theorem, Stochastic Approximation

Last updated: 2026-07-01 | Review: Update rule scratch se derive karo, explain karo kyun max off-policy learning enable karta hai

Concept Map