Epsilon-Greedy Exploration
Simplest exploration strategy, annealing schedules, failure modes, non-stationary rewards
You have 5 headlines for the same news article and no idea which gets the highest CTR. The traditional approach commits equal traffic to all 5 until you have 10K samples per variant, then picks the winner. While you're collecting that data, 80% of readers see a non-optimal headline — every one of those impressions is a missed opportunity. Epsilon-greedy attacks this directly: with probability ε, pick a random headline; otherwise show whichever has the highest estimated CTR so far. After 1,000 impressions you already have a leading candidate, and the exploit step sends most traffic there. Exploration keeps running in the background to correct initial estimates and catch changes.
The mechanism is straightforward but hides a critical flaw: it explores uniformly. Headline A with estimated CTR 3.1%, headline C with 4.2%, and headline D with 2.1% all get the same ε/K share of exploration traffic. Headline D is clearly worse — spending exploration budget there wastes capacity that could go toward distinguishing A from C. There is no mechanism to focus exploration where it matters.
The second flaw is deeper. With ε=0.1, every round has a 10% chance of random arm selection. In every such exploration round, the expected regret is Δ̄ — the average gap to the best arm — since exploration picks uniformly among all K arms; since a round is an exploration round with probability ε, the expected per-round regret averaged over all rounds is ε·Δ̄. Over T rounds, total exploration regret ≥ ε·T·Δ̄ — linear in T. No matter how small ε is, as long as it is fixed and positive, regret grows without bound. Annealing ε to zero is not optional — it is mathematically necessary for sub-linear regret.
NOT this. "Smaller ε is always better after initial exploration." If the arm rewards are non-stationary — headline CTR changes as the news cycle evolves — a decaying ε that goes to 0 stops adapting. The algorithm freezes on whatever was best when exploration stopped, even as the world changes. For non-stationary settings, maintain a minimum ε floor or switch to a method that tracks changing rewards explicitly.
Key points
- Fixed ε causes linear regret: exploration cost ε·T·Δ̄ grows without bound. In every exploration round, the expected regret is Δ̄, the average suboptimality gap — exploration picks uniformly among arms. Since a round is an exploration round with probability ε, the expected per-round regret averaged over all rounds is ε·Δ̄; over T rounds this totals ε·T·Δ̄ — linear regardless of how small ε is. Annealing ε_t = c/t reduces the total exploration cost to c·Δ̄·Σ_t 1/t = O(log T). The annealing is not a nice-to-have: fixed ε is guaranteed to produce linear regret in stationary settings.
- Uniform exploration is the core inefficiency: ε/K exploration budget goes to every arm regardless of how obviously inferior it is. With K=5 headlines and ε=0.1, headline D (CTR 2.1% vs headline C's 4.2%) receives the same 2% exploration share as headline B (CTR 2.8%, genuinely uncertain). UCB and Thompson Sampling avoid this by allocating exploration proportional to uncertainty — clearly inferior arms receive negligible exploration as their estimates converge.
- Cold start and stale means are the two production failure modes. Cold start: a new headline with K=50 and ε=0.1 gets 0.2% of traffic — at 10,000 daily impressions that is 20 impressions per day, far too few for rapid evaluation. Stale means: if CTR drops 30% due to creative fatigue, an arm with 90 days of data has 1 day's new signal barely moving its mean. Both require patches — forced exploration budgets for new arms, sliding window or discounted means for staleness — that UCB and Thompson Sampling handle more naturally.
Fixed ε causes linear regret because the exploration cost ε·T grows without bound — annealing ε_t → 0 is mathematically required, not optional. Uniform exploration is the core inefficiency: ε/K budget goes to every arm equally, wasting capacity on clearly inferior arms that UCB and Thompson Sampling would deprioritize automatically. The two critical production failure modes are cold start and stale means, both of which require patches that principled algorithms handle natively.
Recap
- Mechanism: with prob ε pick random arm, else exploit highest estimated CTR.
- Fixed ε → linear regret: exploration cost ε·T·Δ̄ grows without bound, however small ε is.
- Annealing is mandatory: ε_t = c/t drops exploration cost to O(log T).
- Uniform exploration = core flaw: ε/K goes to every arm, wasting budget on clearly inferior arms.
- Cold start: new arm with K=50, ε=0.1 gets 0.2% traffic — far too little.
- Stale means: old data barely moves the mean after a 30% CTR drop from creative fatigue.
- NOT this: decaying ε→0 freezes under non-stationarity — keep an ε floor or track changing rewards.
Check your understanding
Q1. You deploy ε=0.1 greedy for ad serving with K=50 ads. After 3 months, CTR on most ads has dropped 30% due to creative fatigue, but a new batch of ads was just added. Select the two problems actually occurring.
- A) Stale empirical means serve degraded ads whose historical CTR no longer reflects post-fatigue performance, since old samples dominate the average
- B) New ads get only ε/K ≈ 0.2% traffic each, far too little for rapid evaluation given their small share of the fixed exploration budget
- C) ε-greedy already handles this cleanly — the 10% exploration traffic continuously and evenly samples every ad, including the new batch, without patches
- D) Creative fatigue never affects ε-greedy at all, since the exploit step auto-adjusts to newer CTR levels the instant they change each round
Q2. Prove informally that ε-greedy with fixed ε has linear regret (O(T)) even with optimal ε.
- A) Fixed ε causes linear regret because the algorithm never converges numerically — it keeps oscillating between arms forever, regardless of T
- B) Linear regret follows because exploration rounds make the empirical mean oscillate wildly and it never settles on the truly best arm at all
- C) Fixed ε causes linear regret because exploration rounds make the reward-estimate variance grow steadily and unboundedly with T itself
- D) Each round's exploration contributes expected regret ε·Δ̄, so total regret ≥ ε·T·Δ̄ — linear in T unless ε_t → 0 over time
Q3. In a production system you compare two ε-greedy schedules over T=10,000 rounds with K=10 arms: (a) fixed ε=0.05, (b) annealed ε_t = c/t. Which achieves lower regret as T grows, and why?
- A) Annealed ε_t = c/t drops exploration cost to O(log T), while fixed ε=0.05 keeps paying exploration cost ε·T·Δ̄ that grows without bound — annealing wins as T grows
- B) Fixed ε=0.05 always achieves strictly lower regret than any annealed schedule, because decaying schedules are inherently numerically unstable
- C) The two achieve identical regret in every practical setting; the theoretical gap only becomes visible once T exceeds roughly 10 billion rounds
- D) Annealed ε_t only achieves lower regret once K exceeds 20 arms; for K=10 the fixed schedule is provably superior in this exact regime
Try it interactively
ML Systems Lab is a free interview-prep platform for ML engineers — work through the full interactive module, quizzes, and drills.
Open ML Systems Lab →