5.1.8 · AI-ML › Reinforcement Learning Foundations

Yeh Kaunsi Problem Solve Karta Hai?

Reinforcement learning mein, ek agent ko balance karna hota hai:

Exploitation: Woh actions choose karo jo pehle high rewards dete the
Exploration: Nayi actions try karo taaki potentially better rewards discover ho sakein

Pure exploitation tab fail hota hai jab tumhare initial estimates galat hote hain. Pure exploration obviously bure actions par time waste karta hai. Epsilon-greedy ek principled randomization provide karta hai jo ensure karta hai ki value estimates converge hon true action values ki taraf, aur yeh computationally bilkul trivial bhi rehta hai. (Note: fixed $ε$ ke saath policy khud kabhi purely greedy nahi banti—woh hamesha ke liye explore karti rehti hai.)

Epsilon-greedy policy time $t$ par action select karti hai:

a_{t} = {ar g max_{a \in A} Q (a) random action from A with probability 1 - ε (exploit) with probability ε (explore)

Yeh kaam kyun karta hai: $ε$ term guarantee karta hai ki har action infinitely often try hoga (jab $t \to \infty$ ), isliye $Q (a)$ estimates true values $q_{*} (a)$ par converge ho jaate hain. Lekin policy pure greedy par converge nahi karti—woh hamesha $ε$ rate se explore karti rehti hai.

First Principles Se Derivation

Starting point: Multi-armed bandit problem. Har action $a$ ka unknown true reward $q_{*} (a)$ hai. Hum estimates $Q_{t} (a)$ maintain karte hain observed rewards ke basis par.

Step 1: Pure greedy fail hota hai Greedy policy: hamesha $ar g max_{a} Q_{t} (a)$ pick karo

Problem: Agar action $a_{1}$ pehli try par reward 5 deta hai, aur hum kabhi $a_{2}$ explore nahi karte, toh hum kabhi discover nahi kar paate ki $q_{*} (a_{2}) = 10$ hai. Humara estimate $Q (a_{1})$ ek lucky sample par based ho sakta hai, true mean par nahi.

Step 2: Exploration add karo $ε$ probability se, current estimates ignore karo aur uniformly at random pick karo. Yeh ensure karta hai:

Pr [action a chosen at time t] \geq \frac{ε}{k}

jahan $k = ∣ A ∣$ . Infinite time mein, har action infinitely often try hota hai.

Step 3: Actually kya converge hota hai Jaise jaise har action $a$ ko $n_{a}$ baar try kiya jaata hai, law of large numbers se:

Q (a) = \frac{1}{n _{a}} i = 1 \sum n_{a} r_{i} n_{a} \to \infty q_{*} (a)

Kyunki $ε > 0$ ensure karta hai ki sabhi $a$ ke liye $n_{a} \to \infty$ , value estimates converge ho jaate hain: eventually $ar g max_{a} Q (a) = ar g max_{a} q_{*} (a)$ (high probability ke saath). Lekin policy hamesha optimal action pick karne par converge nahi karti. Limit mein, optimal action select karne ki probability hai:

t \to \infty lim Pr [a_{t} = a^{*}] = (1 - ε) + \frac{ε}{k}

na $1 - ε$ aur na $1$ . Ek aisi policy paane ke liye jo sach mein pure greedy par converge kare, tumhe decay karna hoga $ε \to 0$ over time (neeche dekho).

Pr [a_{t} = a^{*}] = (1 - ε) \cdot 1 [a^{*} = ar g a max Q_{t} (a)] + \frac{ε}{k}

Kisi bhi suboptimal action $a_{i}$ ke liye jahan $q_{*} (a_{i}) < q_{*} (a^{*})$ :

Pr [a_{t} = a_{i}] = (1 - ε) \cdot 1 [a_{i} = ar g a max Q_{t} (a)] + \frac{ε}{k}

Yeh formulas kyun hain: Probability do mutually exclusive cases mein split hoti hai:

Hum exploit karte hain (prob $1 - ε$ ) AUR yeh action abhi best estimated hai (indicator function)
Hum explore karte hain (prob $ε$ ) AUR randomly yeh action pick hoti hai (uniform $1/ k$ )

Jab estimates accurate ho jaate hain, optimal action hi estimated-best hota hai, isliye $Pr [a_{t} = a^{*}] = (1 - ε) + ε / k$ (strictly less than 1 fixed $ε > 0$ ke liye).

Hum $ε = 0.1$ use karte hain (10% time explore karo).

Initial state (t=0): $Q_{0} (a_{1}) = Q_{0} (a_{2}) = Q_{0} (a_{3}) = 0$ (koi knowledge nahi)

Step 1: Random exploration $a_{1}$ choose karta hai, observe karo $r_{1} = 1.2$

Update: $Q_{1} (a_{1}) = 1.2$ , baaki 0 rehte hain
Current best: $a_{1}$

Step 2: 0.9 prob se, exploit karo → $a_{1}$ choose karo. Maano hume milta hai $r_{2} = 0.8$

$Q_{2} (a_{1}) = (1.2 + 0.8) /2 = 1.0$

Yeh step kyun? Hum current knowledge exploit kar rahe hain, lekin humara estimate sirf 2 samples par based hai.

Step 10: Kuch explores ke baad, maano $Q_{10} (a_{1}) = 1.1$ , $Q_{10} (a_{2}) = 4.8$ , $Q_{10} (a_{3}) = 2.9$

Current best: $a_{2}$
Next action: 0.9 prob se → $a_{2}$ choose karo (exploit), 0.1 prob se → uniform random

Epsilon kyun matter karta hai: Bhale hi $a_{2}$ best lagta hai, hum phir bhi kabhi kabhi $a_{1}$ aur $a_{3}$ try karte hain agar hamare estimates galat hain. 1000 steps mein, exploration ke dauran har action $\approx (0.1/3) \times 1000 = 33$ baar try hota hai, plus current best ke liye extra. Note: estimates perfect hone ke baad bhi, hum $a_{2}$ sirf $90% + 3.3% = 93.3%$ time choose karte hain—kabhi 100% nahi.

Regret per step: Jab hum suboptimal action $a_{i}$ choose karte hain, hum $Δ_{i} = q_{*} (a^{*}) - q_{*} (a_{i})$ reward kho dete hain.

Estimates converge hone ke baad (woh accurate hain, lekin policy abhi bhi explore karti hai), expected regret per step hai:

L = a \neq = a^{*} \sum Pr [a_{t} = a] \cdot Δ_{a}

Hamare bandit ke liye $ε = 0.1$ ke saath:

Pr [a_{t} = a_{2}] Pr [a_{t} = a_{1}] Pr [a_{t} = a_{3}] = 0.9 + \frac{0.1}{3} = 0.933 = \frac{0.1}{3} = 0.033 (Δ_{1} = 5.0 - 1.0 = 4.0) = \frac{0.1}{3} = 0.033 (Δ_{3} = 5.0 - 3.0 = 2.0)

Expected regret per step:

L = 0.033 \times 4.0 + 0.033 \times 2.0 = 0.132 + 0.066 = 0.198

Yeh kyun important hai: Exploration ki wajah se hum average mein har step ~0.2 reward lose karte hain. 1000 steps mein, cumulative regret $\approx 198$ . Fixed $ε > 0$ ke liye yeh kabhi zero nahi jaata—yeh exploration ka permanent cost hai. Yahi reason hai ki policy optimal par converge nahi karti: constant $ε$ -exploration hamesha ke liye bure actions ko sample karta rehta hai.

Trade-off: Chhota $ε$ → convergence ke baad kam regret, lekin estimate convergence slow. Bada $ε$ → faster discovery, lekin zyaada long-term regret.

Epsilon Kaise Choose Karein

Fixed epsilon:

$ε = 0.1$ (10% exploration): Standard default, general-purpose ke liye achha
$ε = 0.01$ (1% exploration): Jab environment stable ho aur convergence important ho
$ε = 0.3$ (30% exploration): Learning ke shuruaat mein ya non-stationary environments mein

Decaying epsilon (zyaada sophisticated):

ε_{t} = max (ε_{m i n}, ε_{0} \cdot γ^{t})

jahan $ε_{0} = 1.0$ (initially pure exploration), $γ \in (0.995, 0.999)$ , $ε_{m i n} = 0.01$ .

Decay kyun? Shuruaat mein aggressively explore karo taaki achhe estimates ban sakein. Baad mein zyaada exploit karo kyunki estimates reliable ho chuke hain. Importantly, sirf agar $ε_{t} \to 0$ ho tabhi policy khud purely optimal (greedy) policy par converge karti hai. Fixed $ε_{m i n} > 0$ ke saath tum permanent exploration rakhte ho non-stationary environments handle karne ke liye (is cost par ki tum kabhi fully optimal nahi ban paate).

Kyun sahi lagta hai: Tum 99.9% time exploit kar rahe ho, toh zyaadatar actions high-reward hain.

Problem yeh hai: 10-armed bandit mein, har non-greedy action $0.001/10 = 0.0001$ probability per step se try hota hai. Har action ko 10 baar try karne ke liye (decent estimates ke liye bare minimum), tumhe $10/0.0001 = 100, 000$ steps chahiye. Agar true optimal action pehle lucky try kiya hua nahi hai, toh tum reasonable time mein shayad kabhi discover nahi kar paoge.

Fix: Pehle kuch thousand steps ke liye $ε \geq 0.1$ se start karo. 2-3 samples par bane estimates unreliable hote hain.

Common mistake Common Mistake 2: Q-values Update Karna Bhool Jaana

Galat implementation:

if random() < epsilon:
    action = random_choice(actions)  # explore
else:
    action = argmax(Q_values)  # exploit

Forgot to update Q_values[action] with observed reward!


**Kyun sahi lagta hai**: Epsilon-greedy logic complete lagta hai.

**Problem yeh hai**: Har action ke baad $Q(a)$ update kiye bina, tumhare estimates kabhi improve nahi hote. Tum hamesha *initial random guesses* ke basis par explore aur exploit karte rehte ho.

**Fix**: Hamesha update rule shamil karo (sample-average ya incremental):

$$
Q_{n+1}(a) = Q_n(a) + \frac{1}{n} \left[r_n - Q_n(a)\right]
$$

har action ke baad. Yahi reinforcement learning ka *learning* part hai.

> [!mistake] Common Mistake 3: "Policy Optimal Par Converge Hoti Hai"
> **Galat idea**: "Fixed $\varepsilon$ ke saath, epsilon-greedy hamesha best action pick karne par converge hoti hai ($1-\varepsilon$ probability se)."

**Kyun sahi lagta hai**: Value estimates $Q(a)$ *sach mein* $q_*(a)$ par converge ho jaate hain, toh yeh sochna tempting hai ki behavior bhi optimal par converge ho jaata hai.

**Problem yeh hai**: Sirf *estimates* converge karte hain. *Policy* hamesha ke liye $\varepsilon$ rate se explore karti rehti hai. Limit mein, $\Pr[a_t = a^*] = (1-\varepsilon) + \varepsilon/k$, jo **strictly less than 1** hai (aur simply $1-\varepsilon$ nahi—tumhe exploration ke dauran randomly $a^*$ par stumble karne se chhota $\varepsilon/k$ gain bhi milta hai). Expected regret positive rehta hai.

**Fix**: "Estimate convergence" (guaranteed) aur "policy convergence to optimal" (jo $\varepsilon_t \to 0$ require karta hai) mein fark samjho. Agar tumhe limit mein sach mein optimal policy chahiye, toh decay schedule use karo.

> [!mistake] Common Mistake 4: Explore = Second-Best Pick Karna
> **Galat idea**: "Exploration ka matlab hai second-best action try karna dekhne ke liye ki estimates galat hain ya nahi."

**Steel-man**: Yeh pure random se smarter lagta hai—obviously terrible actions par time kyun waste karein?

**Problem yeh hai**: Yeh ek alag scheme hai, epsilon-greedy nahi. Agar true ranking $a_3 > a_2 > a_1$ hai lekin tumhare estimates $Q(a_1) > Q(a_2) > Q(a_3)$ hain (shuruaat mein unlucky the), toh tum kabhi $a_3$ try nahi karoge aur kabhi discover nahi karoge ki woh best hai.

**Math yeh hai**: Is galat scheme ke under true optimal action $a_3$ try karne ki probability 0 hai agar woh top 2 estimates mein nahi hai. True epsilon-greedy ke under, $\Pr[a_3 \text{ chosen}] \geq \varepsilon/k > 0$ hamesha.

**Fix**: Exploration phase ke dauran, sabhi actions mein se *uniformly at random* pick karo, kisi subset se nahi.

## Algorithm Pseudocode

```python
# Initialize
Q = {a: 0 for a in actions}  # Value estimates
N = {a: 0 for a in actions}  # Action counts

for t in range(num_steps):
    # Epsilon-greedy action selection
    if random() < epsilon:
        action = random_choice(actions)  # Explore
    else:
        action = argmax(Q)  # Exploit
    
    # Take action, observe reward
    reward = environment.step(action)
    
    # Incremental update (why: efficient, online learning)
    N[action] += 1
    Q[action] += (reward - Q[action]) / N[action]
    # This is equivalent to Q[a] = mean of all rewards for action a

Incremental update kyun? Saare past rewards store karke mean compute karne (memory intensive) ki jagah, hum estimate online update karte hain:

Q_{n + 1} = \frac{1}{n + 1} i = 1 \sum n + 1 r_{i} = \frac{1}{n + 1} (r_{n + 1} + i = 1 \sum n r_{i}) = \frac{1}{n + 1} (r_{n + 1} + n \cdot Q_{n}) = Q_{n} + \frac{1}{n + 1} (r_{n + 1} - Q_{n})

Yeh ek moving average hai jo sample mean par converge hoti hai.

Recall Kisi 12 Saal ke Bacche ko Explain Karo

Socho tum ek naye shop par best ice cream flavor dhundh rahe ho jahan 10 flavors hain. Pehle chocolate taste ki aur woh yummy thi (8/10). Ab tumhare paas choice hai:

Hamesha chocolate lo (greedy): Tum har baar chocolate khaoge. Lekin kya hoga agar mint chocolate chip actually 10/10 ho aur tum kabhi pata nahi lagaoge?

Random flavors try karo (pure exploration): Tum bakwaas bubblegum flavor baar baar taste karne mein paise waste karoge.

Epsilon-greedy smarter hai: Zyaadatar time (jaise 10 visits mein se 9 baar), abhi tak joa sabse achha flavor mila hai woh khao. Lekin 10 mein se 1 baar, kuch random try karo—shayad tumhe koi aur bhi achha flavor mil jaaye!

" $ε$ " (epsilon) bas ek fancy naam hai "main kitni baar kuch random try karunga?" ke liye. Agar $ε = 0.1$ hai, toh 10 mein se 1 baar. Yahan ek twist hai: pata lagane ke baad bhi ki truly best flavor kaunsa hai, tum PHIR BHI 1-in-10 baar random try karte ho. Isliye tum best flavor har baar nahi khaate—kuch visits explore karne mein "waste" hoti rehti hain. Yahi koi better flavor miss na karne ki kimat hai. Agar tum ek baar sure ho jaane ke baad visits waste karna band karna chahte ho, toh dhire dhire $ε$ ko zero ki taraf le jaao.

Connections

5.1.01-Multi-armed-Bandits: Epsilon-greedy sabse simple effective solution hai
5.1.09-Upper-Confidence-Bound: Uncertainty ke basis par smarter exploration
5.1.10-Thompson-Sampling: Epsilon-greedy ka probabilistic alternative
5.2.04-Exploration-vs-Exploitation: Fundamental RL tradeoff jise yeh address karta hai
6.3.02-Q-Learning: MDPs mein action selection ke liye epsilon-greedy use karta hai
7.1.05-Experience-Replay: Deep RL bhi neural Q-networks ke saath epsilon-greedy use karta hai
3.4.07-Stochastic-Gradient-Descent: $Q (a)$ ke liye similar incremental update rule

#flashcards/ai-ml

Epsilon-greedy policy kya hoti hai?

1 - ε

probability se, highest estimated value wali action choose karo (exploit).

ε

probability se, uniformly ek random action choose karo (explore).

Fixed-ε epsilon-greedy ke under exactly kya converge hota hai—policy ya value estimates?

Sirf value estimates

Q (a)

true

q_{*} (a)

par converge hote hain. Policy purely optimal par converge NAHI karti; woh hamesha ke liye

ε

rate se explore karti rehti hai.

Limit mein, fixed ε ke under optimal action select karne ki probability kya hai?

(1 - ε) + \frac{ε}{k}

, jo strictly less than 1 hai (aur sirf

1 - ε

nahi, kyunki exploration randomly

a^{*}

ε / k

probability se pick karta hai).

Epsilon-greedy policy ko optimal par converge kaise karaate hain?

ε_{t} \to 0

over time decay karo (jaise

ε_{t} = max (ε_{m i n}, ε_{0} γ^{t})

jahan

ε_{m i n} = 0

). Tabhi policy limit mein purely greedy ban jaati hai.

Har action ke liye estimate

Q (a)

kyun converge hota hai?

Kyunki

ε > 0

guarantee karta hai ki har action infinitely often try hota hai (

n_{a} \to \infty

), isliye law of large numbers se sample-average estimate true mean

q_{*} (a)

par converge ho jaata hai.

Epsilon-greedy ke under ek non-greedy action

a_{i}

choose kiye jaane ki probability kya hai?

Pr [a_{t} = a_{i}] = (1 - ε) \cdot 1 [currently estimated best] + \frac{ε}{k}

jahan

k

actions ki number hai.

10-armed bandit mein epsilon bahut chhota hone (jaise 0.001) par kya hota hai?

Har action

\approx 0.001

probability per step se explore hoti hai. Reliable estimates banane mein thousands ya millions steps lagte hain, isliye estimate convergence extremely slow ho jaati hai.

Epsilon-greedy mein action values ka incremental update rule kya hai?

Q_{n + 1} (a) = Q_{n} (a) + \frac{1}{n + 1} [r_{n + 1} - Q_{n} (a)]

jo sample average ka efficient online computation hai.

Estimates converge hone ke baad fixed-ε epsilon-greedy ke under expected per-step regret kya hota hai?

L = \frac{ε}{k} \sum_{a \neq = a^{*}} (q_{*} (a^{*}) - q_{*} (a))

, jo strictly positive rehta hai—fixed

ε > 0

ke liye kabhi zero nahi jaata.

Epsilon-greedy strategy