UCB1 (Upper Confidence Bound)

UCB1 is a frequentist optimistic exploration algorithm: each round picks the arm with the largest confidence upper bound $a_t = \arg\max_a \left[ \hat{\mu}_a + \sqrt{\frac{2\ln t}{n_a}} \right]$, where $\hat{\mu}_a$ is the empirical mean of arm $a$, $n_a$ its play count, and $t$ the total rounds. The exploration bonus $\sqrt{2\ln t / n_a}$, derived from Hoeffding's inequality, shrinks with $n_a$ and grows with $t$: well-explored arms have bounds near their means (exploitation), neglected arms get high bounds (exploration), balancing exploration-exploitation automatically.

recsys/ads cold-start, multi-arm experiments, any online decision needing a parameter-free, simple, provably near-optimal algorithm; interviews love "compute which arm UCB picks" and the $O(\ln T)$ regret proof.

ε-greedy explores blindly at a fixed rate, wasting samples; UCB concentrates exploration on arms that might be optimal via confidence bounds, achieving the optimal $O(\ln T)$ regret (same order as Thompson sampling) with no Bayesian prior — fully frequentist and ready to deploy.

Test Your Knowledge: Practice Questions for "UCB1 (Upper Confidence Bound)"

Single choice pitfall questions with instant feedback and mistake tracking.