Upper confidence bound (UCB): Definition and Examples

Upper confidence bound (UCB) algorithms pick, at each step, the action whose value could plausibly be highest: its estimated mean plus a bonus that grows with uncertainty. This "optimism in the face of uncertainty" explores under-sampled actions automatically and stops exploring them once the data shows they are worse.

The UCB1 rule

For rewards in $[0, 1]$ , UCB1 plays each arm once and then chooses

A_{t} = ar g a max [μ^_{a} + \frac{2 ln t}{N _{a}}],

where $μ^_{a}$ is arm $a$ 's average reward so far, $N_{a}$ the number of times it has been pulled and $t$ the total number of pulls. The bonus comes from a Hoeffding concentration bound: it is the width of an interval that contains the true mean with high probability. Rarely pulled arms have wide intervals; as $t$ grows the $ln t$ term slowly reopens the question for arms that have been neglected.

Worked example

After 100 pulls, arm A has mean 0.6 from 80 pulls and arm B has mean 0.5 from 20 pulls. With $ln 100 \approx 4.61$ , A's score is $0.6 + 9.21/80 \approx 0.6 + 0.34 = 0.94$ and B's is $0.5 + 9.21/20 \approx 0.5 + 0.68 = 1.18$ . UCB pulls B: its lower average is not yet convincing evidence that it is worse.

Guarantee

Auer, Cesa-Bianchi and Fischer showed that UCB1's expected regret after $T$ rounds is bounded by a sum over suboptimal arms of terms of order $ln T / Δ_{a}$ , where $Δ_{a}$ is the arm's gap to the best. Logarithmic regret matches the known lower bound up to constants, so UCB1 is near optimal in this setting, without any random exploration.

Variants and uses

KL-UCB and UCB-V use tighter confidence intervals.
LinUCB extends the idea to contextual bandits with linear rewards.
UCT applies UCB at every node of a search tree, which is the selection rule behind Monte Carlo tree search in game-playing systems.
In full RL, count-based exploration bonuses $β / N (s, a)$ carry the same intuition to MDPs.

Why it matters

UCB is the clearest example of directed exploration: it explores because of uncertainty, not randomness, and its behaviour is deterministic and auditable. Compared with epsilon-greedy it wastes far fewer pulls on clearly bad options. Compared with Thompson sampling it needs no prior but is usually a little less efficient in practice, and it can over-explore when many arms are nearly tied.

Sources

Peter Auer, Nicolò Cesa-Bianchi, Paul Fischer. Finite-time Analysis of the Multiarmed Bandit Problem, 2002. doi.org
Tor Lattimore, Csaba Szepesvári. Bandit Algorithms, 2020. tor-lattimore.com