Upper Confidence Bound Algorithms

In a multi-armed bandit problem, you must repeatedly choose among options (arms) with unknown reward rates, balancing trying new options (exploration) against sticking with what's worked so far (exploitation). The Upper Confidence Bound (UCB) algorithm resolves this with one simple rule: always pick the arm whose optimistic upper estimate — its observed average reward plus a bonus for how little it's been tried — is currently the highest.

Why the bonus shrinks

The bonus term typically scales like $\sqrt{2 \ln t / n_i}$, where $t$ is the total number of rounds so far and $n_i$ is how many times arm $i$ has been tried. As $n_i$ grows, the bonus shrinks toward zero, so a heavily-tried arm's score converges to its true observed average; an arm tried only once or twice keeps a large bonus, keeping it in contention until the data itself demotes it.

Worked example

Two ad variants are tested online. Variant A has been shown 100 times with an 8% average click rate; variant B has been shown only 5 times with a (noisy) 10% average click rate. Variant A's UCB score is roughly $0.08 + \sqrt{2\ln(105)/100} \approx 0.08 + 0.32 = 0.40$. Variant B's is roughly $0.10 + \sqrt{2\ln(105)/5} \approx 0.10 + 1.42 = 1.52$. Despite A's higher and more reliable average, B's larger uncertainty bonus wins out, so the algorithm shows B again next — exactly the exploration a naive "always pick the current best average" rule would have skipped.