Epsilon-Greedy

Epsilon-Greedy is a foundational exploration strategy in multi-armed bandit and reinforcement learning that selects the empirically best-known action with probability (1-ε) while choosing uniformly at random with probability ε — providing a simple, parameter-driven mechanism to balance exploitation of current knowledge with exploration of potentially superior alternatives, serving as the universal baseline against which all exploration algorithms are compared.

What Is Epsilon-Greedy?

• Definition: At each time step t, with probability ε select a uniformly random action; with probability (1-ε) select the action with the highest estimated mean reward (greedy action).
• Exploration Rate ε: The single hyperparameter controlling the exploration-exploitation tradeoff; ε = 0 is pure greedy (no exploration), ε = 1 is pure random (no exploitation), ε = 0.1 is a common production default.
• Implementation Simplicity: Requires only maintaining empirical reward estimates Q(a) = total reward / number of pulls for each action — O(K) memory, O(1) update per step.
• Universal Applicability: Works with any reward signal, action space type, and problem structure — requires no distributional assumptions about rewards.

Why Epsilon-Greedy Matters

• Universal Baseline: Any exploration algorithm claiming superiority must outperform ε-greedy — it establishes the performance floor for all bandit and RL exploration methods.
• Production Deployability: Its simplicity makes it the default choice in production systems where interpretability and debuggability outweigh theoretical optimality.
• DQN Foundation: Deep Q-Networks (DQN) use ε-greedy exploration with decaying ε — the technique that enabled superhuman Atari gameplay has ε-greedy at its core.
• A/B Test Analog: Fixed-ε-greedy is equivalent to always allocating ε fraction of traffic to exploration — interpretable in business terms as "explore X% of impressions."
• Tuning Simplicity: A single scalar hyperparameter ε is far easier to tune and audit than the distributional parameters required by Thompson Sampling or UCB confidence levels.

Variants and Extensions

Decaying ε (ε_t):
- Reduce ε over time: ε_t = ε_0 / t or ε_t = min(1, C / (d²·t)) for theoretical guarantees.
- Asymptotically converges to greedy as sufficient data accumulates — achieves O(log T) regret with proper schedule.
- Requires careful schedule design — too fast reduces exploration, too slow wastes samples.

ε-First (Explore-Then-Commit):
- Pure exploration for first ε·T rounds; pure exploitation for remaining (1-ε)·T rounds.
- Theoretically optimal for some stochastic bandit settings; requires T to be known in advance.
- Clean separation of phases simplifies analysis and implementation.

Boltzmann (Softmax) Exploration:
- Select action a with probability proportional to exp(Q(a)/τ) where τ is temperature.
- Explores actions in proportion to estimated quality rather than uniformly — superior to ε-greedy in theory.
- Requires temperature schedule τ; converges to greedy as τ → 0.

Comparison with Alternatives

Epsilon-Greedy is the indispensable workhorse of exploration strategies — its combination of simplicity, universality, and interpretability makes it the practical starting point for every sequential decision-making system, and its role as the exploration strategy in DQN demonstrates that simple exploration suffices even for state-of-the-art deep reinforcement learning systems.