upper confidence bound (ucb)
**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)**
$$a_t = \arg\max_a \left[ \hat{\mu}_a + c \sqrt{\frac{\ln t}{n_a}} \right]$$
- $\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.