Upper Confidence Bound (UCB)

UCB operates on the principle of optimism in the face of uncertainty. For each action, it constructs a confidence interval around the estimated mean reward and selects the action with the highest upper bound. This systematically gives underexplored actions a chance, as their wide confidence intervals produce high upper bounds.

• Deterministic selection: Unlike Thompson Sampling, UCB uses a fixed formula with no randomness
• Confidence-driven: Actions with fewer trials get a larger exploration bonus
• Asymptotic optimality: Regret grows logarithmically with time, matching the theoretical lower bound

The classic UCB1 algorithm selects the action a that maximizes:

UCB1(a) = μ̂ₐ + √(2 ln(t) / Nₐ)

Where:

• μ̂ₐ: Empirical mean reward of action a
• t: Total number of rounds played so far
• Nₐ: Number of times action a has been selected

The exploration bonus √(2 ln(t) / Nₐ) decreases as an action is tried more often, naturally shifting the algorithm from exploration to exploitation over time.

UCB provides strong theoretical guarantees on regret minimization. The cumulative regret of UCB1 is bounded by:

O(K log T) where K is the number of arms and T is the time horizon.

• Logarithmic regret: The penalty for suboptimal choices grows very slowly
• No prior needed: Unlike Bayesian methods, UCB requires no prior distribution over rewards
• Distribution-free: The bound holds for any bounded reward distribution
• Problem-independent: Guarantees apply regardless of the gap between optimal and suboptimal arms

LinUCB extends the UCB principle to contextual bandits by modeling the expected reward as a linear function of context features:

E[r|x,a] = θₐᵀ x

The upper confidence bound becomes: UCB(a) = θ̂ₐᵀ x + α √(xᵀ Aₐ⁻¹ x)

Where Aₐ⁻¹ is the covariance matrix of the feature vectors observed for action a. The exploration bonus is now context-dependent, shrinking more for familiar contexts and expanding for novel ones. This enables personalized recommendations that adapt to user features.

While theoretically elegant, UCB requires careful implementation in production:

• Reward scaling: The exploration bonus assumes rewards in [0,1]; rescaling is essential for real-world metrics like revenue
• Non-stationarity: Standard UCB assumes stationary rewards; sliding windows or discount factors are needed for changing user behavior
• Cold-start: Initial rounds require forced exploration since all confidence bounds are wide
• Computational cost: LinUCB requires matrix inversion per action, which can be expensive with high-dimensional features
• Hyperparameter α: Controls the exploration-exploitation balance; typically tuned via offline evaluation

UCB occupies a distinct position in the bandit algorithm landscape:

• vs. Epsilon-Greedy: UCB explores more intelligently by targeting uncertain actions rather than random exploration, leading to lower regret
• vs. Thompson Sampling: UCB is deterministic and easier to debug, but Thompson Sampling often performs better empirically with non-uniform reward distributions
• vs. Softmax: UCB's exploration is uncertainty-based rather than proportional to estimated value, making it more aggressive in reducing uncertainty
• Best for: Applications requiring strong theoretical guarantees, deterministic reproducibility, and where reward distributions are well-behaved

A Bayesian probabilistic alternative to UCB that selects actions by sampling from the posterior distribution of each arm's reward. Unlike UCB's deterministic optimism, Thompson Sampling introduces natural randomness that often achieves lower regret in practice, especially in non-stationary environments. It excels when prior knowledge about reward distributions is available and interpretable uncertainty estimates are required.

The simplest bandit baseline that selects the best-known action with probability 1-ε and explores randomly with probability ε. While computationally trivial, its undirected exploration wastes budget on clearly suboptimal arms. UCB improves upon this by directing exploration toward high-uncertainty, high-potential actions, making it far more sample-efficient in large action spaces.

The contextual extension of UCB that models expected reward as a linear function of context features. LinUCB computes an upper confidence bound using the ridge regression coefficient estimates and their covariance matrix. This closed-form solution makes it computationally attractive for real-time personalization where latency budgets are measured in milliseconds and interpretability is valued.

The theoretical framework for evaluating bandit algorithms. Regret measures the cumulative difference between the reward of always choosing the optimal arm and the algorithm's actual performance. UCB achieves logarithmic regret bounds under stationary assumptions, meaning the per-round penalty decays to zero as the algorithm learns. This provides formal guarantees that epsilon-greedy cannot match.

The critical safety framework for validating UCB policies before production deployment. Techniques like Inverse Propensity Scoring (IPS) and Doubly Robust estimation use logged data from a different policy to estimate UCB's expected performance. This allows data scientists to answer 'What if we had used UCB?' without risking revenue on untested exploration strategies.

A deep learning variant that replaces UCB's linear or tabular assumptions with a neural network reward model. NeuralUCB uses the network's gradient information to approximate uncertainty, enabling UCB-style exploration in high-dimensional, non-linear feature spaces like image or text embeddings. Essential when linear assumptions break down in complex personalization tasks.