Exploration vs Exploitation

ε-greedy, UCB, curiosity (ICM), count-based, Thompson sampling, high-dimensional exploration

Consider a news recommendation system. For each user request you can recommend the user's known-favorite category (exploitation) or try a different category to learn their preferences (exploration). With 100% exploitation the user sees only what they have liked before — you never learn whether they would enjoy something new, and you are stuck with increasingly stale preferences. With 100% exploration recommendations are random and user satisfaction drops. The dilemma: exploration costs short-term performance but enables long-term improvement.

ε-greedy handles this with a simple switch: with probability ε take a random action, otherwise take the best known one. Simple, but fundamentally broken in large action spaces. With 10M news articles and ε = 0.1, ε-greedy explores uniformly across all 10M items — allocating just as much exploration to articles you are certain are terrible as to those with genuine uncertainty. It wastes exploration budget on obviously inferior options.

UCB (Upper Confidence Bound) directs exploration at uncertainty instead. Score each action as μ_a + c√(log t / N_a) where μ_a is the estimated reward, N_a is visit count, and t is total time steps. The second term is an exploration bonus that shrinks as N_a grows. Actions you have barely tried have large bonuses — the algorithm prefers them until it has reduced its uncertainty. This implements "optimism in the face of uncertainty": act as if uncertain actions are as good as their highest plausible value.

Thompson Sampling is the Bayesian version. Model each action's reward as a distribution — Beta(α, β) for click/no-click outcomes. Sample one reward estimate from each action's current posterior. Take the best. Actions with high uncertainty have wide distributions and are more likely to sample a high value — which means they are more likely to be selected and explored. As evidence accumulates, posteriors tighten and exploration naturally decreases. No explicit exploration rate to tune.

NOT this: exploration is just about trying random actions. Structured exploration — UCB, Thompson Sampling — outperforms random exploration by directing effort toward uncertain actions, not arbitrary ones. In a recommendation system with 10M items, ε-greedy wastes exploration uniformly. UCB concentrates exploration where information value is highest. The difference in regret is asymptotically O(ε T) versus O(log T).

Key points

• Use Thompson Sampling as your default for bandit problems — it adapts exploration to uncertainty automatically and outperforms ε-greedy empirically in most non-stationary settings. Thompson Sampling requires no explicit exploration rate tuning. As evidence accumulates, posterior distributions tighten and exploration naturally decreases. For contextual bandits where per-user context matters, use contextual Thompson Sampling or LinUCB.
• Never use a fixed ε in ε-greedy in production — constant exploration overhead wastes resources even after the policy has converged. Use a decaying schedule (ε_t = 1/√t) or switch to UCB/Thompson which naturally reduce exploration as uncertainty decreases. A fixed ε = 0.1 means 10% of all recommendations forever are random, even after millions of interactions.
• If exploration rate per time step drops to near zero, the system has converged and will not adapt to preference changes — maintain a minimum exploration floor. In non-stationary environments (user preferences shift, product catalog changes, seasonality), a fully converged policy becomes stale. Set a minimum exploration floor of 1–5% and monitor whether the floor is actively being used, which signals that preferences may have shifted.

Recap

• The dilemma: exploitation costs nothing short-term but goes stale; exploration costs performance but enables improvement.
• ε-greedy is broken at scale: with 10M items it explores obviously-terrible options uniformly.
• UCB directs exploration at uncertainty: $\mu_a + c\sqrt{\log t / N_a}$ — optimism in the face of uncertainty.
• Thompson Sampling (Bayesian): sample from each action's posterior, take the best; exploration decays as posteriors tighten, no rate to tune.
• Regret: ε-greedy $O(\epsilon T)$ vs UCB/TS $O(\log T)$.
• Never use fixed ε in production; decay it or switch to UCB/TS. Keep a 1–5% exploration floor for non-stationary settings.
• Hard-exploration (Montezuma): random discovery is ~$10^{-218}$ — need ICM/RND novelty rewards; beware the noisy-TV problem.

Check your understanding