UCB1

Imagine choosing among several slot machines when you do not know which one pays best. UCB1 is a strategy for making that choice: it favors machines with high observed rewards, while deliberately giving uncertain machines a chance to prove themselves.

How UCB1 chooses
UCB1 means Upper Confidence Bound 1. For each action (or “arm”), it keeps an empirical average reward, then adds an optimism bonus:

• Estimated value: the arm’s average reward so far.
• Uncertainty bonus: a larger bonus for arms tried fewer times.

At time t, UCB1 selects the arm i with the largest score: average reward_i + √(2 ln(t) / n_i), where n_i is the number of times that arm has been selected. Each arm is tried once first, so no arm has a zero count. The first term exploits what looks rewarding; the second explores what remains uncertain. As an arm is sampled repeatedly, its bonus shrinks.

Why the “upper bound” matters
The score is an optimistic plausible estimate of an arm’s reward. An under-tested arm could be better than its current average suggests, so UCB1 temporarily treats it as such. In an A/B test, for example, a new recommendation might receive traffic even after a few mediocre clicks, because the evidence is still weak. But a well-tested mediocre recommendation loses its uncertainty bonus and stops consuming many impressions.

Guarantees and limits
For stationary, independent reward distributions bounded in [0, 1], UCB1 achieves logarithmic regret: its extra loss relative to always choosing the true best arm grows slowly with time. This is a major result because it supplies a principled exploration rule rather than a fixed random-exploration rate. Its assumptions also matter: if rewards drift, depend on user context, or have long delayed consequences, plain UCB1 can confidently pursue outdated estimates. Contextual bandits and full RL methods address those richer interaction settings.