Epsilon-Greedy vs Thompson Sampling vs UCB1: Choosing the Right Algorithm

Three Algorithms, One Goal

Every multi-armed bandit algorithm tries to solve the same problem: maximize total reward by balancing exploration and exploitation. But they approach this trade-off with fundamentally different strategies.

Epsilon-Greedy uses randomness. UCB1 uses optimism. Thompson Sampling uses probability. Each philosophy leads to different behavior in practice, and the right choice depends on your specific situation.

Epsilon-Greedy: The Simple Baseline

Epsilon-Greedy is the most intuitive bandit algorithm. With probability 1 - epsilon, it picks the arm with the highest observed reward (exploit). With probability epsilon, it picks a random arm (explore).

How it works:

1. Generate a random number between 0 and 1
2. If the number is less than epsilon (default 0.1), pick a random arm
3. Otherwise, pick the arm with the highest average reward

Strengths:

• Dead simple to implement and explain
• Predictable exploration rate
• Works with any reward distribution

Weaknesses:

• Explores uniformly, wasting pulls on clearly bad arms
• The epsilon parameter needs tuning (too high = too much exploration, too low = gets stuck)
• Never stops exploring, even when the best arm is obvious

UCB1: Optimism Under Uncertainty

UCB1 (Upper Confidence Bound) takes a different approach. For each arm, it computes an upper confidence bound on the true reward and picks the arm with the highest bound. Arms with less data get wider bounds, so they get explored. Arms with lots of data have tight bounds that reflect their true performance.

The UCB1 formula:

For each arm, the score is: average_reward + sqrt(2 * ln(total_pulls) / arm_pulls)

The first term is exploitation (observed performance). The second term is an exploration bonus that shrinks as you gather more data for that arm.

Strengths:

• Zero tuning parameters
• Deterministic: same data always produces the same choice
• Strong theoretical regret guarantees (logarithmic regret)

Weaknesses:

• Deterministic behavior can be a liability in non-stationary environments
• Explores more aggressively than necessary in practice
• Confidence bounds assume sub-Gaussian rewards

Thompson Sampling: Bayesian Probability Matching

Thompson Sampling maintains a probability distribution over each arm's true reward rate. At each step, it samples from each distribution and picks the arm with the highest sample. Arms with more uncertainty produce more variable samples, so they get explored naturally.

How it works (binary outcomes):

1. For each arm, maintain a Beta distribution: Beta(successes + 1, failures + 1)
2. Sample a value from each arm's distribution
3. Pick the arm with the highest sampled value
4. Update the selected arm's distribution with the outcome

Strengths:

• No tuning parameters
• Naturally concentrates exploration on uncertain arms
• Lowest empirical regret across most scenarios
• Adapts well to non-stationary environments (due to stochastic selection)

Weaknesses:

• Requires choosing a prior distribution (Beta for binary, Normal for continuous)
• Slightly more complex to implement than Epsilon-Greedy
• Stochastic behavior makes exact reproducibility harder

Head-to-Head Comparison

Try It Yourself

The simulator below lets you run all three algorithms side by side against the same set of arms. Adjust the true conversion rates, set the number of rounds, and watch how each algorithm allocates traffic and accumulates regret.

Things to experiment with:

• Close conversion rates (e.g., 48% vs 52%): Thompson Sampling's advantage is most visible here
• One dominant arm (e.g., 80% vs 20% vs 15%). All algorithms converge quickly, but Epsilon-Greedy wastes the most traffic
• Many arms (5+), where UCB1's aggressive exploration becomes costly and Thompson Sampling scales better

Decision Framework

Choose Epsilon-Greedy when:

• You need the simplest possible implementation
• You want a predictable, fixed exploration rate
• The problem is easy (large separation between arms)
• You need to explain the algorithm to non-technical audiences

Choose UCB1 when:

• You want deterministic behavior (important for debugging and reproducibility)
• You prefer strong theoretical guarantees
• The environment is stationary (reward rates don't change)
• You don't want to tune any parameters

Choose Thompson Sampling when:

• You want the best empirical performance (lowest regret)
• The differences between variants are small
• The environment might be non-stationary
• You're working with binary outcomes (conversion, click, signup)
• You want exploration to diminish naturally as confidence grows

The Practical Answer

For most teams optimizing web experiences, Thompson Sampling is the best default. It requires no tuning, produces the lowest regret, and handles the messy realities of production environments (changing user behavior, seasonal effects, new variants) better than the alternatives.

Use UCB1 when you need determinism. Use Epsilon-Greedy when you need simplicity. Use Thompson Sampling when you need results.