UCB and Optimism Under Uncertainty

Optimism in the face of uncertainty is a design principle with a precise justification: act as though the world is as good as it plausibly could be, and either you were right, in which case you got a good outcome, or you were wrong, in which case you learned something. Either way the round was not wasted, and that is the whole argument.

The algorithm

For each arm, maintain an empirical mean \(\hat{\mu}_i\) and a count \(n_i\), and choose the arm maximising

The first term is exploitation and the second is an exploration bonus that shrinks as an arm is pulled more and grows slowly with total time. UCB1 achieves \(O(\log T)\) regret, matching the lower bound's order (Auer, Cesa-Bianchi and Fischer, 2002, Machine Learning 47:235-256).

The balance is automatic rather than tuned. An arm pulled rarely has a large bonus and gets selected even with a mediocre mean; an arm pulled often has a small bonus and must earn selection on its estimate. The \(\ln t\) in the numerator ensures that as time passes, arms that have been neglected become attractive again, which is what prevents premature commitment.

Why the bonus has that form

The bonus is a high-probability confidence radius from Hoeffding's inequality: with \(n_i\) samples of a bounded random variable, the empirical mean is within \(\sqrt{2\ln t / n_i}\) of the truth with probability at least \(1 - t^{-4}\). Choosing the arm with the highest upper bound therefore means choosing the arm that could plausibly be best.

The failure probability must shrink with \(t\), which is where the logarithm comes from, because the algorithm makes \(T\) decisions and a fixed failure probability per decision would fail eventually.

Tighter bounds give better constants. KL-UCB uses a divergence-based bound instead of Hoeffding's and is asymptotically optimal rather than merely order-optimal, which matters in practice on problems with skewed reward distributions.

When it breaks

The bound assumes bounded rewards. Hoeffding requires rewards in a known range. Unbounded or heavy-tailed rewards need a different concentration inequality, and applying the standard bonus to them produces an algorithm with no guarantee and, usually, insufficient exploration.

Deterministic selection is a problem in parallel settings. UCB always picks the same arm given the same statistics, so a system issuing many simultaneous decisions before any feedback arrives sends them all to one arm. Thompson sampling's randomisation handles this naturally, which is a substantial practical advantage in production.

The constant matters more than the order. The theoretical \(\sqrt{2\ln t}\) is frequently too aggressive in practice, and implementations tune a multiplier on the bonus. That tuning is doing real work and removes the parameter-free property that is often cited as UCB's advantage.

Non-stationarity breaks it badly. Because the bonus shrinks with the total pull count, an arm that was good and became bad retains a small bonus and a stale mean, so the algorithm is slow to abandon it. Discounted or sliding-window variants are required, and the window length becomes a parameter encoding an assumption about how fast the world changes.