Upper Confidence Bound (UCB)

Rank every action by its best plausible payoff, not its average, so under-tested options get their trial and proven losers fade on their own.

Three arms score 1.439, 1.576 and 1.917 after bonuses of 0.619, 0.876 and 1.517, so the least-tried arm wins despite the lowest average

Why Does This Exist?

In a multi-armed bandit, acting greedily on observed averages strands you: one unlucky pull can bury the best arm forever. Epsilon-greedy fixes the freeze by exploring at random, but it explores blindly, handing equal trials to a proven loser and a total unknown.

UCB explores with direction. Each arm gets a score of its empirical mean plus an uncertainty bonus that shrinks as the arm is pulled. You always play the highest score, which means an arm gets retried exactly while it could plausibly be the best. Auer and colleagues (2002) proved this rule keeps total regret growing only logarithmically, the best rate any method achieves on stationary bandits.

The one idea you need first

The exploration versus exploitation tradeoff is the tension itself: pull the current winner or gather information. UCB is one principled answer to it, sitting between blind epsilon-greedy and full Bayesian sampling. Know the tradeoff first; this page is the formula.

Think of It Like This

A newcomer picking lunch stalls at a food court

You just moved near a food court with three stalls. Stall A fed you six times and averaged a solid 8 out of 10. Stall B fed you three times at a 7. Stall C served you once, a 4, on a day the cook looked new.

Greedy eating says A forever. Random exploring says roll dice and sometimes queue at a stall you already know is bad. UCB says: rank each stall by its best plausible rating. A is reliably around 8. B could be a 9 on a good day. C, with one data point, could be anything from a 2 to a 10, so its ceiling beats both and you try C next. If C flops again, its ceiling crashes and you stop going without needing any schedule or coin flip.

Where the analogy stops: your taste drifts and stalls change cooks, while UCB1 assumes each arm pays from a fixed distribution in $[0, 1]$ . On drifting rewards the old averages lie and the bonus math stops meaning what it says.

How It Actually Works

Track pulls $N_t(a)$ and sample mean $Q_t(a)$ per arm. At round $t$ , UCB1 plays:

A_t = \arg\max_a \left[ Q_t(a) + c \sqrt{\frac{\ln t}{N_t(a)}} \right]

Here $Q_t(a)$ exploits and the bonus explores. Pulling an arm grows its denominator and shrinks its bonus, while $\ln t$ in the numerator slowly re-inflates neglected arms so none is abandoned. The constant $c$ sets curiosity; the classic derivation gives $c = \sqrt{2}$ .

Where the square root comes from

Hoeffding's inequality bounds how far a sample mean of $[0, 1]$ rewards can undershoot the true mean $\mu_a$ :

P(\mu_a > Q_t(a) + U) \le \exp(-2 N_t(a) U^2)

Demanding failure probability $t^{-4}$ and solving for $U$ gives $U = \sqrt{2 \ln t / N_t(a)}$ , which is the bonus with $c = \sqrt{2}$ . So each score is a high-probability ceiling on the true value, and picking the top ceiling is optimism made literal. The full regret analysis, and the matching lower bound this rate meets, are in regret bounds.

Worked example

Three arms, $c = 1.0$ . Nine pulls are done ( $6 + 3 + 1$ ), so the next decision is round $t = 10$ with $\ln 10 \approx 2.3026$ . Averages: $Q = 0.82$ (6 pulls), $0.70$ (3 pulls), $0.40$ (1 pull).

Bonuses $U = \sqrt{\ln 10 / N}$ : arm 1 $\sqrt{2.3026/6} \approx 0.619$ , arm 2 $\sqrt{2.3026/3} \approx 0.876$ , arm 3 $\sqrt{2.3026/1} \approx 1.517$ .

Scores: arm 1 $0.82 + 0.619 = 1.439$ , arm 2 $0.70 + 0.876 = 1.576$ , arm 3 $0.40 + 1.517 = 1.917$ . Arm 3 wins despite the worst average, purely on uncertainty.

Suppose arm 3 then pays 0. Its average falls to $(0.40 + 0.0)/2 = 0.20$ over 2 pulls. At $t = 11$ , $\ln 11 \approx 2.3979$ , bonus $\sqrt{2.3979/2} \approx 1.095$ , score $0.20 + 1.095 = 1.295$ , now last. One bad trial extinguished the exploration by itself.

Code

This snippet scores the worked position and the follow-up round. It uses only the standard library.

1import math2
3
4def ucb_scores(means: list[float], counts: list[int], t: int, c: float = 1.0) -> list[float]:5    """Return Q(a) + c * sqrt(ln t / N(a)) for each arm."""6    return [m + c * math.sqrt(math.log(t) / n) for m, n in zip(means, counts)]7
8
9print([round(s, 3) for s in ucb_scores([0.82, 0.70, 0.40], [6, 3, 1], 10)])  # -> [1.439, 1.576, 1.917]10print(round(0.20 + math.sqrt(math.log(11) / 2), 3))  # -> 1.295

The least-pulled arm leads at 1.917, and after one zero reward it drops to 1.295, exactly the hand computation above.

Watch Out For

Scoring an arm that was never pulled

With $N_t(a) = 0$ the bonus divides by zero and the code crashes or yields infinity in the argmax. This bites whenever arms appear mid-run, like new ads entering rotation. Symptom: a ZeroDivisionError on day two of a working system, or silent infinity comparisons picking garbage.

Play every arm once before the formula starts. Guard the scorer too: if any count is zero, return that arm immediately instead of computing.

Feeding raw unscaled rewards into a unit-scale bonus

The $c = \sqrt{2}$ bonus lives at magnitude 1 to 3, tuned for rewards in $[0, 1]$ . On raw payoffs like $0 to $1000, averages sit in the hundreds and the bonus becomes rounding noise, so UCB degrades into greedy and unexplores. Symptom: one arm takes nearly every pull after a lucky start.

Normalize rewards into $[0, 1]$ before updating, or scale $c$ to the reward range. Whichever you choose, check the bonus is at least a few percent of the mean gaps, or exploration is decorative.

The Quick Version

UCB ranks each arm by sample mean plus bonus $c\sqrt{\ln t / N(a)}$ and plays the max, which is optimism in the face of uncertainty.
Untried arms carry huge bonuses, so exploration happens exactly where uncertainty is highest, with no random coin flips.
The bonus comes from Hoeffding's inequality, making each score a high-probability ceiling on the true mean.
Regret grows only logarithmically, matching the theoretical floor for stationary bandits.
Play each arm once first, and keep rewards in $[0, 1]$ or scale $c$ , or the formula misfires.