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.

Meaning of each term in UCB1? Why is $\sqrt{2\ln t / n_a}$ the optimal exploration bonus (Hoeffding)?

Numerical: at $t=100$, 3 arms with $(n_a, \hat{\mu}_a)$: arm1 (60, 0.6), arm2 (30, 0.5), arm3 (10, 0.4) — compute each UCB value and pick the arm.

Sketch the $O(\ln T)$ regret proof: why is each bad arm's play count bounded by $O(\ln T)$?

How does UCB's exploration fundamentally differ from Thompson sampling and ε-greedy?

Limitations and extensions of UCB1: non-stationary environments, reward assumptions, UCB1-tuned / sliding-window UCB?