What Problem Does This Solve?

In reinforcement learning, an agent must balance:

• Exploitation: Choose actions that gave high rewards in the past
• Exploration: Try new actions to discover potentially better rewards

Pure exploitation fails when your initial estimates are wrong. Pure exploration wastes time on obviously bad actions. Epsilon-greedy provides a principled randomization that ensures the value estimates converge to the true action values, while remaining computationally trivial. (Note: with a fixed $\varepsilon$ the policy itself never becomes purely greedy—it keeps exploring forever.)

The epsilon-gredy policy selects action at time $t$ as:

Why this works: The $\varepsilon$ term guarantees that every action gets tried infinitely often (as $t \to \infty$), so the $Q(a)$ estimates converge to true values $q_*(a)$. The policy, however, does NOT converge to pure greedy—it always explores with rate $\varepsilon$.

Derivation From First Principles

Starting point: Multi-armed bandit problem. Each action $a$ has unknown true reward $q_*(a)$. We maintain estimates $Q_t(a)$ based on observed rewards.

Step 1: Pure gredy fails Gredy policy: always pick $\arg\max_a Q_t(a)$

Problem: If action $a_1$ gives reward5 on first try, and we never explore $a_2$, we never discover that $q_*(a_2) = 10$. Our estimate $Q(a_1)$ might be based on a lucky sample, not the true mean.

Step 2: Add exploration With probability $\varepsilon$, ignore current estimates and pick uniformly at random. This ensures:

where $k = |\mathcal{A}|$. Over infinite time, each action is tried infinitely often.

Step 3: What actually converges As each action $a$ is tried $n_a$ times, by law of large numbers:

Since $\varepsilon > 0$ ensures $n_a \to \infty$ for all $a$, the value estimates converge: eventually $\arg\max_a Q(a) = \arg\max_a q_*(a)$ (with high probability). But the policy does NOT converge to always picking the optimal action. In the limit, the probability of selecting the optimal action is:

not $1-\varepsilon$ and not $1$. To get a policy that does converge to pure greedy, you must decay $\varepsilon \to 0$ over time (see below).

For any suboptimal action $a_i$ where $q_*(a_i) < q_*(a^*)$:

Why these formulas: The probability splits into two mutually exclusive cases:

1. We exploit (prob $1-\varepsilon$) AND this action is currently estimated best (indicator function)
2. We explore (prob $\varepsilon$) AND randomly pick this action (uniform $1/k$)

Once estimates are accurate, the optimal action is the estimated-best, so $\Pr[a_t = a^*] = (1-\varepsilon) + \varepsilon/k$ (strictly less than1 for fixed $\varepsilon>0$).

We use $\varepsilon = 0.1$ (explore 10% of the time).

Initial state (t=0): $Q_0(a_1) = Q_0(a_2) = Q_0(a_3) = 0$ (no knowledge)

Step 1: Random exploration choses $a_1$, observe $r_1 = 1.2$

• Update: $Q_1(a_1) = 1.2$, others stay 0
• Current best: $a_1$

Step 2: With prob 0.9, exploit → choose $a_1$. Suppose we get $r_2 = 0.8$

• $Q_2(a_1) = (1.2 + 0.8)/2 = 1.0$

Why this step? We're exploiting current knowledge, but our estimate is based on only 2 samples.

Step 10: After several explores, suppose $Q_{10}(a_1)=1.1$, $Q_{10}(a_2)=4.8$, $Q_{10}(a_3)=2.9$

• Current best: $a_2$
• Next action: With prob 0.9→ choose $a_2$ (exploit), with prob 0.1 → uniform random

Why epsilon matters: Even though $a_2$ looks best, we still occasionally try $a_1$ and $a_3$ in case our estimates are wrong. Over1000 steps, each action gets tried $\approx (0.1/3) \times 1000 = 33$ times during exploration, plus extra for the current best. Note: even after estimates are perfect, we choose $a_2$ only $90\% + 3.3\% = 93.3\%$ of the time—never 100%.

Regret per step: When we choose suboptimal action $a_i$, we lose $\Delta_i = q_*(a^*) - q_*(a_i)$ reward.

After the estimates converge (they are accurate, but the policy still explores), the expected regret per step is:

For our bandit with $\varepsilon = 0.1$:

Expected regret per step:

Why this matters: We lose ~0.2 reward per step on average due to exploration. Over 1000 steps, cumulative regret $\approx 198$. This never goes to zero for fixed $\varepsilon>0$—it's the permanent cost of exploration. This is precisely why the policy does not converge to optimal: the constant $\varepsilon$-exploration keeps sampling bad actions forever.

Trade-off: Smaller $\varepsilon$ → less regret after convergence, but slower estimate convergence. Larger $\varepsilon$ → faster discovery, but more long-term regret.

Choosing Epsilon

Fixed epsilon:

• $\varepsilon = 0.1$ (10% exploration): Standard default, good general-purpose
• $\varepsilon = 0.01$ (1% exploration): When environment is stable and convergence matters
• $\varepsilon = 0.3$ (30% exploration): Early in learning or non-stationary environments

Decaying epsilon (more sophisticated):

where $\varepsilon_0 = 1.0$ (pure exploration initially), $\gamma \in (0.995, 0.999)$, $\varepsilon_{\min} = 0.01$.

Why decay? Early on, explore agressively to build good estimates. Later, exploit more since estimates are reliable. Crucially, only if $\varepsilon_t \to 0$ does the policy itself converge to the purely optimal (greedy) policy. With a fixed $\varepsilon_{\min} > 0$ you retain permanent exploration to handle non-stationary environments (at the cost of never being fully optimal).

Why it feels right: You're exploiting 99.9% of the time, so most actions are high-reward.

The problem: In a10-armed bandit, each non-gredy action is tried with probability $0.001/10 = 0.0001$ per step. To try each action 10 times (bare minimum for decent estimates), you need $10 / 0.0001 = 100{,}000$ steps. If the true optimal action isn't the one you tried first by luck, you might never discover it in reasonable time.

Fix: Start with $\varepsilon \geq 0.1$ for first few thousand steps. Estimates built on 2-3 samples are unreliable.

Forgot to update Q_values[action] with observed reward!

**Why it feels right**: The epsilon-greedy logic looks complete.

**The problem**: Without updating $Q(a)$ after each action, your estimates never improve. You're exploring and exploiting based on *initial random guesses* forever.

**Fix**: Always include the update rule (sample-average or incremental):

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

after every action. This is the *learning* part of reinforcement learning.

> [!mistake] Common Mistake 3: "The policy converges to optimal"
> **Wrong idea**: "With fixed $\varepsilon$, epsilon-greedy converges to always picking the best action (with probability $1-\varepsilon$)."

**Why it feels right**: The value estimates $Q(a)$ *do* converge to $q_*(a)$, so it's tempting to think the behavior converges to optimal too.

**The problem**: Only the *estimates* converge. The *policy* keeps exploring at rate $\varepsilon$ forever. In the limit, $\Pr[a_t = a^*] = (1-\varepsilon) + \varepsilon/k$, which is **strictly less than 1** (and not simply $1-\varepsilon$—you gain a small $\varepsilon/k$ from randomly stumbling onto $a^*$ during exploration). Expected regret stays positive.

**Fix**: Distinguish "estimate convergence" (guaranteed) from "policy convergence to optimal" (requires $\varepsilon_t \to 0$). If you truly need an optimal policy in the limit, use a decay schedule.

> [!mistake] Common Mistake 4: Explore = Pick Second-Best
> **Wrong idea**: "Exploration means trying the second-best action to see if estimates are wrong."

**Steel-man**: This seems smarter than pure random—why waste time on obviously terrible actions?

**The problem**: This is a different scheme, not epsilon-greedy. If the true ranking is $a_3 > a_2 > a_1$ but your estimates are $Q(a_1) > Q(a_2) > Q(a_3)$ (you got unlucky early), you'll never try $a_3$ and never discover it's best.

**The math**: Probability of trying the true optimal action $a_3$ under this wrong scheme is0 if it's not in the top 2 estimates. Under true epsilon-greedy, $\Pr[a_3 \text{ chosen}] \geq \varepsilon/k > 0$ always.

**Fix**: During exploration phase, pick *uniformly at random* from all actions, not from some subset.

## 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

Why incremental update? Instead of storing all past rewards andcomputing the mean (memory intensive), we update the estimate online:

This is a moving average that converges to the sample mean.

Always pick chocolate (gredy): You'll eat chocolate every time. But what if mint chocolate chip is actually10/10 and you never find out?

Try random flavors (pure exploration): You waste money tasting the gross bubblegum flavor over and over.

Epsilon-greedy is smarter: Most of the time (like 9 out of 10 visits), eat the best flavor you've found so far. But 1 out of 10 times, try something random—maybe you'll discover an even better flavor!

The "$\varepsilon$" (epsilon) is just a fancy name for "how often do I try something random?" If $\varepsilon = 0.1$, that's 1 out of 10 times. Here's the twist: even after you've figured out which flavor is truly best, you STILL try random ones 1-in-10 times. So you never eat the best flavor every single time—you keep "wasting" a few visits exploring. That's the price of never missing a better flavor. If you want to stop wasting visits once you're sure, you slowly lower $\varepsilon$ toward zero.

Connections

• 5.1.01-Multi-armed-Bandits: Epsilon-greedy is the simplest effective solution
• 5.1.09-Upper-Confidence-Bound: Smarter exploration based on uncertainty
• 5.1.10-Thompson-Sampling: Probabilistic alternative to epsilon-greedy
• 5.2.04-Exploration-vs-Exploitation: Fundamental RL tradeoff this addresses
• 6.3.02-Q-Learning: Uses epsilon-greedy for action selection in MDPs
• 7.1.05-Experience-Replay: Deep RL also uses epsilon-greedy with neural Q-networks
• 3.4.07-Stochastic-Gradient-Descent: Similar incremental update rule for $Q(a)$

#flashcards/ai-ml

Concept Map

Hinglish (regional understanding)

Hinglish (regional understanding)