Epsilon-Greedy

At each decision step, the algorithm generates a random number between 0 and 1. If this number is less than epsilon (ε), it selects a random arm for exploration. Otherwise, it selects the arm with the highest estimated value for exploitation. This simple logic ensures that no action is permanently ignored, maintaining a constant, non-zero probability of discovering a superior option even after the model has converged on a current best.

Epsilon (ε) is a value between 0 and 1 that defines the exploration rate. A common default is ε = 0.1, meaning 10% of decisions are random exploration. The choice of epsilon is critical:

• High ε (e.g., 0.2): Aggressive exploration, suitable for highly dynamic environments where user preferences shift rapidly.
• Low ε (e.g., 0.01): Conservative exploitation, maximizing immediate reward in stable environments.
• Decaying ε: A common enhancement where epsilon starts high and decreases over time, allowing the algorithm to explore heavily initially and then exploit more as it learns.

Epsilon-greedy explicitly manages the fundamental tension in reinforcement learning. Exploitation maximizes short-term reward by choosing the known best action, but risks settling on a local optimum. Exploration sacrifices immediate reward to gather information about potentially better actions, improving long-term performance. The algorithm's linear regret—meaning its cumulative opportunity cost grows linearly with time—is its primary theoretical weakness compared to more sophisticated methods like Upper Confidence Bound (UCB) or Thompson Sampling.

In a personalization context, epsilon-greedy transforms a static A/B test into a dynamic traffic allocation system. Instead of a fixed 50/50 split, the algorithm automatically routes a small fraction of users (ε) to exploratory variants and the majority to the current winner. This minimizes the opportunity cost of the experiment by reducing the number of users exposed to underperforming variants, while still gathering statistically valid data on alternatives.

Despite its simplicity, epsilon-greedy has notable drawbacks:

• Uniform Exploration: It explores all non-optimal actions with equal probability, wasting trials on clearly inferior options instead of focusing on the most promising alternatives.
• No Uncertainty Quantification: Unlike Bayesian methods, it does not account for the variance in its estimates. An arm with a single trial is explored with the same probability as one with thousands.
• Persistent Noise: Even after finding the optimal action, the algorithm continues to explore with probability ε, causing a constant, irreducible performance penalty.

The standard epsilon-greedy is a non-contextual bandit, meaning it treats all users identically and learns a single best action for the entire population. For personalized recommendations, this is extended to a Contextual Epsilon-Greedy approach. Here, the exploitation logic uses a predictive model (e.g., logistic regression) that takes user features as input to predict the best action for a specific individual, while exploration still selects a random action with probability ε. This allows for basic personalization while retaining the algorithm's core simplicity.

The parent framework for Epsilon-Greedy. A reinforcement learning approach that dynamically allocates traffic to better-performing variants in real-time, minimizing the opportunity cost of exploration compared to traditional fixed-horizon A/B tests.

• Goal: Maximize cumulative reward (e.g., clicks, conversions)
• Key Advantage: Stops sending traffic to losing variants early
• Trade-off: More complex statistical analysis than fixed-horizon tests

The central dilemma that Epsilon-Greedy addresses. Exploitation selects the best-known action to maximize immediate reward, while Exploration tries suboptimal actions to gather data that may improve future decisions.

• Pure Exploitation: Sticks to the known winner, risks missing a better option
• Pure Exploration: Tests randomly, incurs high opportunity cost
• Epsilon-Greedy Solution: Balances both with a single tunable parameter

The mathematical objective that Epsilon-Greedy optimizes. Regret is the difference between the reward achieved and the reward that would have been achieved by always selecting the optimal action.

• Cumulative Regret: Sum of lost rewards over the entire experiment
• Epsilon-Greedy Regret: Grows linearly with time due to constant random exploration
• Improvement: Annealing epsilon over time reduces asymptotic regret

An enhancement to standard Epsilon-Greedy that decays the exploration rate over time. As the algorithm gathers more data, it shifts from aggressive exploration to confident exploitation.

• Linear Decay: ε = ε₀ - (t × decay_rate)
• Exponential Decay: ε = ε₀ × e^(-λt)
• Benefit: Reduces long-term regret while maintaining early exploration

An alternative bandit algorithm that addresses Epsilon-Greedy's blind exploration. UCB selects arms based on an optimistic estimate of their potential reward, naturally balancing exploration and exploitation without a fixed epsilon parameter.

• Formula: Select arm with max (mean_reward + exploration_bonus)
• Exploration Bonus: Decreases as an arm is pulled more often
• Advantage: No uniform random exploration of clearly inferior arms

A Bayesian bandit algorithm that maintains a probability distribution over each arm's true reward rate. At each step, it samples from these distributions and selects the arm with the highest sampled value.

• Prior: Beta distribution for binary rewards
• Update Rule: Bayesian posterior after observing each outcome
• Advantage: Naturally balances exploration proportional to uncertainty