Upper Confidence Bound (UCB) is an exploration strategy for bandit problems that selects actions by choosing the option with the highest upper confidence bound on its estimated reward. This "optimism in the face of uncertainty" principle ensures that uncertain actions are explored while known-good actions are exploited.

The UCB Formula (UCB1)

• $\hat{\mu}_a$: Estimated mean reward for action $a$ (exploitation term).
• $c \sqrt{\frac{\ln t}{n_a}}$: Confidence bonus (exploration term). $t$ = total time steps, $n_a$ = times action $a$ was selected.
• $c$: Exploration parameter controlling the confidence width.

How UCB Works

• Initially: All actions have been tried few times ($n_a$ is small), so the exploration bonus is large for all actions — encouraging broad exploration.
• Over Time: Frequently selected actions have large $n_a$, reducing their exploration bonus. Under-explored actions maintain large bonuses.
• Convergence: Eventually, the best action's mean reward dominates, and the algorithm predominantly exploits it.

Key Properties

• Deterministic: Unlike Thompson Sampling (which is stochastic), UCB is deterministic given the same history. Easier to analyze and debug.
• Logarithmic Regret: UCB1 achieves regret growing as $O(\ln T)$, which is theoretically optimal for multi-armed bandits.
• No Hyperparameter Sensitivity: With appropriate theory-based $c$, UCB works well without extensive tuning.

UCB Variants

• UCB1: The basic algorithm described above. Simple and effective.
• UCB-V: Incorporates variance estimates for tighter bounds.
• KL-UCB: Uses Kullback-Leibler divergence for tighter bounds on binary rewards.
• LinUCB: Extends UCB to contextual bandits with linear reward models — widely used in recommendation systems.
• Neural UCB: Uses neural networks for the reward estimate with UCB-style exploration.

Applications

• A/B/N Testing: Automatically allocate traffic to the best performing variant.
• Recommendation: Balance showing popular content (exploitation) with discovering new content (exploration).
• Hyperparameter Optimization: Explore hyperparameter configurations optimistically.
• Monte Carlo Tree Search (MCTS): UCT (UCB applied to trees) is the foundation of AlphaGo's search algorithm.

UCB is one of the foundational algorithms in decision-making under uncertainty — its "optimism in the face of uncertainty" principle has influenced algorithms across ML, optimization, and AI planning.