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**
| Algorithm | Exploration Type | Regret Bound | Complexity |
|-----------|-----------------|-------------|------------|
| **ε-Greedy** | Uniform random | O(T^{2/3}) | Trivial |
| **UCB** | Optimism-based | O(log T) | Low |
| **Thompson Sampling** | Posterior sampling | O(log T) | Medium |
| **Softmax** | Quality-weighted | O(T^{2/3}) | Low |
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.