Exploration vs exploitation tradeoff — Hinglish notes

5.1.7 · AI-ML › Reinforcement Learning Foundations

What Is This Tradeoff?

Yeh matter kyun karta hai? RL mein, ek agent ko interaction ke through seekhna hota hai. Supervised learning ke unlike jahan saara training data pehle se diya hota hai, ek RL agent ko khud apna training data gather karna padta hai actions lekar. Actions ka sequence decide karta hai ki agent kya seekhta hai.

First Principles Derivation

Chaliye mathematically derive karte hain ki yeh tradeoff exist kyun karta hai.

Setup: Multi-Armed Bandit

$K$ actions (arms), har ek ka unknown reward distribution hai
Action $a$ reward deta hai $r \sim p (r ∣ a)$ unknown mean $μ_{a}$ ke saath
Goal: $T$ steps mein cumulative reward maximize karna

The Tradeoff Emerges:

Agar hum sirf exploit karte hain (hamesha current best estimate pick karo):

Early estimates thode data pe based hain → galat hone ki sambhavana zyada
Hum hamesha ke liye ek suboptimal action pe stuck ho jaate hain
Regret linearly badhta hai: $Regret (T) = O$

Agar hum sirf explore karte hain (random actions):

Hum saare $μ_{a}$ ke accurate estimates seekhte hain
Lekin hum yeh knowledge kabhi use nahi karte!
Regret phir bhi linearly badhta hai: $Regret (T) = O (T)$

Optimal strategy dono ko balance karta hai:

Itna explore karo ki high confidence ke saath $a^{*}$ identify ho sake
Zyaadatar time best action exploit karo
Achievable regret: $Regret (T) = O (lo g T)$ (sublinear!)

Strategies for Managing the Tradeoff

1. Epsilon-Greedy

Kaise use karein: $ϵ = 0.1$ se shuru karo (10% exploration). Time ke saath decay karo: $ϵ_{t} = ϵ_{0} / t$ ya $ϵ_{t} = ϵ_{0} \cdot 0.9 9^{t}$ .

Figure — Exploration vs exploitation tradeoff

2. Upper Confidence Bound (UCB)

Formula UCB Action Selection

$a_{t} = ar g max_{a} [Q_{t} (a) + c \frac{l n t}{N _{t} ( a )}]$ Derivation:

Goal: Woh actions pick karo jo ya toh high-reward hain YA uncertain hain
Current estimate: $Q_{t} (a) = \frac{1}{N _{t} ( a )} \sum_{i : a_{i} = a} r_{i}$ (sample mean)
Uncertainty: $σ_{a} \approx \frac{1}{N _{t} ( a )}$ (standard error samples ke saath shrink karta hai)
Optimism principle: Aise act karo jaise uncertain actions ka optimistic upper bound ho
Hoeffding bound: High probability ke saath, true mean $μ_{a}$ $Q_{t} (a) \pm c \frac{l n t}{N _{t} ( a )}$ ke andar hota hai
$ln t$ kyun? Jaise jaise time badhta hai, hume zyada confident hona chahiye (exploration ke liye higher bar) Intuition: $\frac{l n t}{N _{t} ( a )}$ term ek exploration bonus hai:

Bada hota hai agar action $a$ kam try hua ho ( $N_{t} (a)$ small)
Zyada data gather hone ke saath shrink karta hai
Under-sampled actions try karne ki encouragement deta hai

3. Thompson Sampling (Probability Matching)

Formula Thompson Sampling Algorithm

Har action ke reward ke liye probability distribution $P (μ_{a} ∣ data)$ maintain karo
Sample karo: $\tilde{μ}_{a} \sim P (μ_{a} ∣ data)$ sabhi $a$ ke liye
Pick karo: $a_{t} = ar g max_{a} \tilde{μ}_{a}$ Yeh kyun kaam karta hai:

Agar hum certain hain ki action $a$ best hai, toh $P (μ_{a} ∣ data)$ narrow hai → hum $a$ often pick karte hain
Agar hum uncertain hain, toh $P (μ_{a} ∣ data)$ wide hai → kabhi kabhi high sample → hum explore karte hain
$a$ pick karne ki probability ≈ probability ki $a$ optimal hai

Example with Beta distributions (binary rewards):

Prior: $μ_{a} \sim Beta (1, 1)$ (uniform)
$s_{a}$ successes, $f_{a}$ failures observe karne ke baad: $μ_{a} \sim Beta (1 + s_{a}, 1 + f_{a})$
High uncertainty (kam samples) → wide distribution → zyada exploration
High certainty → narrow distribution → mostly exploitation

Worked Examples

Worked example Example 1: Two-Armed Bandit

Setup: Do slot machines. Machine A: 60% win rate ( $μ_{A} = 0.6$ ). Machine B: 80% win rate ( $μ_{B} = 0.8$ ). Hum yeh values nahi jaante.

Scenario: Pehle 5 trials mein, hum A do baar try karte hain (1 win, 1 loss), B ek baar (1 loss).

$\overset{μ}{^}_{A} = 1/2 = 0.5$
$\overset{μ}{^}_{B} = 0/1 = 0$ Greedy approach: A ko hamesha pick karo (uski higher estimate hai)
Result: Hamesha 60% win rate milega, kabhi discover nahi hoga ki B better hai
Regret: $(0.8 - 0.6) \times T = 0.2 T$ (linear!)

Epsilon-greedy ( $ϵ = 0.1$ ):

90% time: A pick karo
10% time: randomly pick karo (5% each)
Explore karte karte, eventually $\overset{μ}{^}_{B} > \overset{μ}{^}_{A}$
Phir mostly B pick karo, occasional A
Regret: Bahut kam, mostly B pick karne pe converge ho jaata hai

Greedy approach kyun fail hua: B pe ek kharaab early sample ne permanent galti karwa di. Fix: Forced exploration galat estimates ko correct karta hai.

Worked example Example 2: UCB Calculation

100 steps ke baad:

Action 1: $Q_{t} (1) = 0.7$ , $N_{t} (1) = 80$ baar try kiya
Action 2: $Q_{t} (2) = 0.6$ , $N_{t} (2) = 10$ baar try kiya
Action 3: $Q_{t} (3) = 0.5$ , $N_{t} (3) = 10$ baar try kiya UCB scores ( $c = 2$ ke saath): $UCB_{1} = 0.7 + 2 \frac{l n 100}{80} = 0.7 + 2 \frac{4.605}{80} = 0.7 + 0.48 = 1.18$

Yeh calculation kyun?

$ln 100 = 4.605$ (total trials ka natural log)
$N_{t} (1) = 80$ denominator mein kyunki hum action 1 bahut baar try kar chuke hain
Chhota exploration bonus (0.48) kyunki hum action 1 ke baare mein confident hain $UCB_{2} = 0.6 + 2 \frac{l n 100}{10} = 0.6 + 2 0.4605 = 0.6 + 1.36 = 1.96$

Zyada bonus kyun?

Same $ln 100$ lekin $N_{t} (2) = 10$ (bahut kam try kiya)
$\frac{4.605}{10} = 0.68$ bada hai $\frac{4.605}{80} = 0.24$ se
High uncertainty → bada exploration bonus (1.36) $UCB_{3} = 0.5 + 2 \frac{l n 100}{10} = 0.5 + 1.36 = 1.86$

Decision: Action 2 pick karo (sabse high UCB score 1.96)

Chahe uski estimated value (0.6) sabse high nahi hai
Kyun? Uncertainty bonus dominate karta hai kyunki hum action 2 ko under-sample kar chuke hain
Yeh smart hai: Action 2 actually best ho sakta hai—hume zyada data chahiye!

Worked example Example 3: Exploration in Deep RL

Atari game (Montezuma's Revenge):

Sparse rewards: points tabhi milte hain jab complex sequence complete ho (key uthao → door unlock karo → treasure tak pahuncho)
Random exploration: success ki probability ≈ $\frac{1}{1 0 ^{20}}$ (bahut rare!) Standard $ϵ$ -greedy kyun fail hota hai:
Agent random actions try karta hai, 99.9999% time zero reward milta hai
Key kabhi discover nahi hoti → kuch nahi seekhta
Yahi hard environments mein exploration problem hai

Better strategies:

Curiosity-driven exploration: Novel states visit karne ke liye bonus reward
- $r_{t} = r_{t}^{ext} + β \cdot r_{t}^{intrinsic}$
- $r_{t}^{intrinsic}$ = state dynamics model ka prediction error
- Agent explore karta hai kyunki "surprising" states rewarding hain
Count-based exploration: Rarely visited states ke liye bonus
- $Bonus (s) = \frac{β}{N ( s )}$ jahan $N (s)$ = visit count
- Systematic state space coverage encourage karta hai

Yeh kyun kaam karte hain: Yeh exploration ke liye hi shaped rewards dete hain, sirf game score ke liye nahi. Agent curious hona seekhta hai.

Common Mistakes

Common mistake Mistake 2: "High epsilon = zyada learning"

Kyun sahi lagta hai: Zyada exploration → zyada data → better learning?

Kyun galat hai:

High $ϵ$ (jaise 0.5) matlab random actions 50% time
Training mein late stage pe, hum already jaante hain kaun se actions good hain
Is point pe random actions kharab actions pe experience waste karte hain
Slow convergence: Agent bad actions try karta rehta hai chahe usse better pata ho

Fix: Epsilon ko time ke saath decay karo. High se shuru karo (unknown environment explore karo), jaise estimates improve hoti hain waise decrease karo (seekhi hui knowledge exploit karo). Common schedule: $ϵ_{t} = max (0.01, ϵ_{0} \cdot 0.99 5^{t})$ .

Graph intuition: Shuru mein, saare actions uncertain → explore karo. Baad mein, clear winner emerge hota hai → exploit karo.

Common mistake Mistake 3: "Thompson sampling hamesha UCB se better hai"

Kyun sahi lagta hai: Thompson sampling Bayesian hai (principled), optimal probability match karta hai, practice mein often jeet jaata hai.

Kyun incomplete hai:

UCB ke advantages: Deterministic, implement karna simple, proven regret bounds
Thompson sampling: Full distributions maintain karne ki zarurat hai (deep RL ke liye expensive), theoretically analyze karna mushkil
Context matters: Simple distributions (Beta, Gaussian) wale bandits ke liye, Thompson sampling often jeet jaata hai. Complex state spaces mein neural networks ke saath, epsilon-greedy zyada practical hai.

Fix: Apni problem ke basis pe choose karo. Simple bandits? Thompson sampling try karo. Deep RL with function approximation? Epsilon-greedy ya entropy bonuses se shuru karo.

The Information-Reward Tradeoff

Formula Expected Value of Information

Key insight: Exploration ki value hoti hai kyunki information better future decisions enable karti hai.

$V_{explore} = E [immediate reward] + E [value of information gained]$

Derivation:

Immediate cost: Action $a$ explore karna $μ_{a}$ deta hai (suboptimal ho sakta hai)
Information gain: Estimate $Q (a)$ update karo, uncertainty $σ_{a}^{2}$ reduce karo
Future benefit: Remaining $T - t$ steps ke liye better decisions
Breakeven: Explore karo agar $E [future gain] > immediate loss$

Example calculation:

Current best action: $μ_{1} = 10$
Uncertain action: $Q_{2} = 8 \pm 5$ (3 se 13 tak ho sakta hai)
Agar hum action 2 ek baar try karein (cost: $10 - 8 = 2$ )
Aur discover karein ki actually $μ_{2} = 12$ hai (uncertainty ke basis pe 10% chance)
Toh hum remaining 99 steps mein $(12 - 10) \times 99 = 198$ gain karte hain
Expected gain: $0.1 \times 198 - 2 = 19.8 - 2 = 17.8$ (worth it!)

Isi liye UCB aur Thompson sampling kaam karte hain—yeh implicitly is tradeoff ko compute karte hain.

Recall 12 saal ke bachche ko samjhao

Socho tumhare paas $10 hain e k f ai r m e inbah u t s aa r e g am e b oo t h s k es aa t hk h e l n e k e l i y e . T u m p e h l a g am e k h e l k e$ 3 jeette ho—kaafi accha! Ab tumhare paas ek choice hai:

Exploitation: Wahi game khelते raho. Tum jaante ho yeh $3 deta hai, toh zaroor paise banoge. Safe aur steady.
Exploration: Koi aur game try karo. Ho sakta hai yeh $5 d e (a w eso m e!), y a s i r f$ 1 (oops). Risky hai, lekin ho sakta hai kuch better mile.

Agar tum SIRF pehle game pe tike raho (exploit), toh har baar $3 mi l e g a ... l e k ink y ah o g aa g a r p aa s m e inhi e k g am e h o j o$ 5 deta hai? Tumhe kabhi pata nahi chalega!

Agar tum HАR game randomly try karo (explore), toh best wala dhoondh loge... lekin dhundte dhundte bahut saara paisa kharaab games pe waste hoga.

Smart strategy: Kuch alag games try karo pata lagane ke liye ki kaun se acche hain. Jab best game mil jaaye, zyaadatar time wahi khelo, lekin kabhi kabhi doosre bhi try karo bas yeh check karne ke liye ki kuch change toh nahi hua ya kuch miss toh nahi kiya.

Yahi computers karte hain jab woh video games khelna seekhte hain! Woh alag alag moves try karte hain (explore) yeh seekhne ke liye ki kya kaam karta hai, phir mostly best moves use karte hain jo unhe mile (exploit), lekin kabhi kabhi kuch naya try karte hain bas yeh check karne ke liye.

Connections

5.1.01-Markov-Decision-Process: RL framework jahan exploration-exploitation aata hai
5.1.06-Temporal-Difference-Learning: TD learning ko state-action pairs visit karne ke liye exploration chahiye
5.1.08-Q-Learning: Q-learning ka convergence sufficient exploration pe depend karta hai
5.1.11-Policy-Gradient-Methods: Stochastic policies naturally explore karti hain; entropy bonuses encourage karte hain
5.2.03-Multi-Armed-Bandits: Sabse simple setting jahan exploration-exploitation hi SIRF challenge hai
5.3.05-Curiosity-Driven-Exploration: Intrinsic motivation use karke advanced exploration
4.5.07-Overfitting-and-Regularization: Analogous tradeoff—exploitation = training data pe overfit karna, exploration = alag hypotheses try karna

Summary

Exploration-exploitation tradeoff reinforcement learning ka fundamental challenge hai: current knowledge use karna (exploitation) aur nayi information gather karna (exploration) balance karna. Pure exploitation suboptimal actions pe stuck kar deta hai; pure exploration bad actions pe reward waste karta hai. Optimal strategies jaise epsilon-greedy, UCB, aur Thompson sampling dono ko balance karte hain is tarah:

Jab uncertain ho toh zyada explore karo (early mein ya under-sampled actions ke liye)
Jab confident ho toh zyada exploit karo (sufficient data ke baad)
Exploration ko time ke saath decay karo (jaise estimates improve hoti hain)

Yeh tradeoff regret analysis mein rigorous mathematical foundations rakhta hai, jahan optimal algorithms $O (lo g T)$ regret achieve karte hain vs. naive approaches ke $O (T)$ .

#flashcards/ai-ml

RL mein exploitation kya hai? :: Current knowledge/estimates ke basis pe reward maximize karne wale actions choose karna

RL mein exploration kya hai? :: Environment ke baare mein nayi information gain karne ke liye uncertain outcomes wale actions try karna

Agar ek RL agent sirf exploit kare toh kya hota hai?

Suboptimal actions pe stuck ho jaata hai kyunki early estimates galat ho sakti hain; regret linearly badhta hai O(T)

Agar ek RL agent sirf explore kare toh kya hota hai?

Accurate value estimates seekhta hai lekin knowledge kabhi use nahi karta; regret phir bhi linearly badhta hai O(T)

Multi-armed bandit problem mein regret kya hai?

Optimal action ke reward aur agent ke actual reward ke beech ka cumulative difference: Regret(T) = T·μ* - Σ E[r_t]

Epsilon-greedy policy kya hai?

Probability ε se, ek random action choose karo (explore); probability 1-ε se, greedy action choose karo (exploit)

Epsilon-greedy mein epsilon ko time ke saath decay kyun karte hain?

Learning ke shuru mein, high exploration acche actions discover karne mein help karta hai; baad mein, lower exploration known-bad actions pe experience waste karne se bachata hai

UCB (Upper Confidence Bound) formula kya hai?

a_t = argmax_a [Q_t(a) + c·sqrt(ln(t)/N_t(a))], woh actions select karta hai jinka estimated value high ho YA uncertainty high ho

UCB exploration bonus mein sqrt(ln(t)/N_t(a)) kyun hai?

Bonus under-sampled actions ke liye bada hota hai (chhota N_t(a)) aur zyada data ke saath shrink karta hai; ln(t) time ke saath confidence threshold badhata hai

Thompson Sampling kya hai?

Har action ke reward ke upar ek probability distribution maintain karo, har distribution se sample karo, highest sample wala action pick karo

Thompson Sampling ki key insight kya hai?

Ek action pick karne ki probability us action ke optimal hone ki probability ke barabar hoti hai, naturally exploration aur exploitation balance karta hai

RL mein greedy action selection kyun fail hota hai?

Ek chicken-egg problem create karta hai: accurate estimates ke liye actions explore karne chahiye, lekin greedy un actions ko try karna band kar deta hai jo thoda worse lagte hain early mein

Exploration mein information ki value kya hai?

Exploration se gain ki gayi information better future decisions enable karti hai, isliye explore karo jab expected future gain immediate reward loss se zyada ho

Curiosity-driven exploration kya hai?

Agents ko novel ya surprising states visit karne ke liye intrinsic reward bonuses dena, sparse-reward environments mein help karta hai

Optimal exploration strategies kaun sa regret bound achieve kar sakti hain?

O(log T) regret, jo sublinear hai—naive strategies ke linear O(T) regret se bahut dheere badhta hai