Optimism in the Face of Uncertainty: the UCB1 Algorithm

Abstraction: Mathematical derivation and implementation of the UCB1 bandit algorithm

Key points:

• UCB1 selects the action maximizing x̄_j + √(2 log t / n_j); the upper confidence bound shrinks as arm j is pulled more often
• Uses Chernoff-Hoeffding inequality to set confidence bound so P(true mean > UCB) ≤ t^{-4}
• Worst-case expected cumulative regret is O(√KT log T); lower bound for any algorithm is Ω(√KT)
• Specific regret bound: Σ_i [8 log T / Δ_i² + 1 + π²/3] where Δ_i = μ* − μ_i (uses Basel's problem result)
• "Optimism in the face of uncertainty": unpulled arms get growing confidence bounds, ensuring no arm is permanently ignored
• Empirical regret on synthetic data (10 arms, 1M rounds) is substantially below the theoretical worst-case bound

Connections: Multi Armed Bandit · Upper Confidence Bound · Exploration Exploitation · Regret Minimization

Source: https://jeremykun.com/2013/10/28/optimism-in-the-face-of-uncertainty-the-ucb1-algorithm/