Upper Confidence Bound Algorithms

UCB1, Lai-Robbins optimality, UCB variants, confidence bound construction

Epsilon-greedy's fundamental problem is that it allocates exploration uniformly — it has no mechanism for deciding which arms deserve more exploration. UCB solves this with a principled principle: always pull the arm whose true mean could plausibly be highest given what has been observed. The UCB index is μ̂_a + confidence_bonus, where the bonus shrinks as an arm accumulates data and grows as t increases.

An arm that is either genuinely high-reward or under-explored will win the argmax — and if it wins because it was over-estimated, the next observation corrects that, shrinking its UCB. Over-optimism is self-correcting. UCB1 achieves O(log T) regret matching the Lai-Robbins lower bound's order — though not its exact constant; only KL-UCB (below) matches the constant too. In production, UCB's determinism (fully reproducible, no random coin flips) makes it auditable — but naive UCB scales poorly to millions of arms because maintaining per-arm confidence intervals becomes expensive.

Key points

• **UCB1: $a_t = argmax_a [μ̂_a + √(2 ln t / N_a(t))].** The confidence bonus √(2 ln t / N_a) has two properties: it de$ cays as N_a grows (arm is better understood, exploration less urgent) and grows as t increases (global pressure to revisit under-pulled arms). An arm never pulled at all has infinite UCB by convention and gets pulled first — this is the natural cold-start solution.
• UCB1 regret bound: E[R_T] ≤ Σ_{a: Δ_a > 0} [8 ln T / Δ_a + (1 + π²/3)·Δ_a]. The 8/Δ_a factor means near-optimal arms (small Δ_a) get pulled more — which is correct, because they take many observations to identify as suboptimal. Arms with large gaps are eliminated quickly; arms close to optimal require persistent exploration until the confidence intervals separate.
• Optimism principle: UCB acts as if each arm's mean is at its most optimistic plausible value. If the true mean really is that high, pulling the arm is correct. If the true mean is lower, the next observation shrinks the confidence interval and the arm's UCB falls. Over-optimism generates the exploration needed to correct itself — this is why UCB never ignores an uncertain arm forever.
• UCB1-tuned replaces the fixed 1/4 variance bound with empirical variance: UCB = μ̂_a + √(min(1/4, V_a(t)) · ln t / N_a) where V_a accounts for both estimated variance and the uncertainty in that estimate. Arms with low variance get tighter confidence intervals, focusing exploration budget on arms where variance is genuinely high. Empirically outperforms UCB1 when reward variance differs substantially across arms.
• **KL-UCB uses the KL divergence between empirical and true mean as the confidence bound: $UCB_a = max{q : N_a · KL(μ̂_a, q) ≤ ln t + c ln ln t}.** This is t$ ighter than Hoeffding-based bounds (which UCB1 uses) and achieves the Lai-Robbins lower bound with matching constant. More computationally expensive — requires solving a one-dimensional optimisation per arm — but asymptotically optimal in a way UCB1 is not.
• **MOSS (Minimax Optimal Strategy in Stochastic case): UCB $index = μ̂_a + √(max(0, ln(T/(K·N_a))) / N_a).** Achieves minimax-optimal O(√(KT)) over worst-case instances. UCB1 is$ instance-optimal (low regret when gaps are large) but not minimax-optimal. Use UCB1 when you have reason to believe gaps are large; use MOSS when you need worst-case robustness.
• For continuous arm spaces, naive discretisation into K = T^{1/3} bins achieves O(T^{2/3}) regret. Kernel UCB or GP-UCB handle smooth reward functions by using a GP posterior as the confidence bound — O(T^{(d+1)/(d+2)}) regret in d dimensions. The GP's posterior variance is the uncertainty measure, and the acquisition function is the UCB index.
• At web scale with K=10M arms, naive argmax is O(K) per step — infeasible at thousands of QPS. Practical approaches: two-stage retrieval (ANN on embeddings to get top-100 candidates, then UCB over 100); pre-compute UCB scores in batch and store in Redis; hierarchical UCB (tree over arm categories, UCB at each level to select which subtree to descend).
• Heavy-tailed rewards (Cauchy, Pareto) break Hoeffding-based UCB confidence bounds, causing under-covering and insufficient exploration. The empirical mean itself has high variance for heavy-tailed distributions. Use robust mean estimators (trimmed mean, median of means) with correspondingly modified confidence intervals when reward distributions have heavy tails.

Recap

• UCB1 index: $a_t = argmax_a [μ̂_a + √(2 ln t / N_a(t))]$ — bonus decays with N_a, grows with t.
• Optimism principle: act as if each arm's mean is its most optimistic plausible value; over-optimism self-corrects on the next pull.
• Never-pulled arm has infinite UCB: natural cold-start solution.
• O(log T) regret with 8/Δ_a factor: near-optimal arms get pulled more — they take longest to eliminate.
• Variants: UCB1-tuned (empirical variance), KL-UCB (tighter, matches Lai-Robbins constant), MOSS (minimax O(√(KT))).
• Web scale K=10M: naive argmax O(K) infeasible — use two-stage ANN retrieval, batched Redis scores, or hierarchical UCB.
• Heavy tails break Hoeffding bounds: use robust mean estimators (trimmed mean, median of means).

Check your understanding