UCB Algorithms

UCB: Upper Confidence Bound

Overview

UCB algorithms choose actions by combining estimated rewards with confidence bonuses, balancing exploration of uncertain options against exploiting promising ones. The approach spans multi-armed and linear or contextual bandits, as well as Gaussian-process optimization, with variants for nonstationary rewards, constraints, delayed feedback, and multiple objectives. Analyses typically establish regret guarantees, while benchmarks test performance in settings such as pricing, ranking, resource allocation, and adaptive model selection. A central challenge is adapting confidence bounds to realistic noise and structure without making decisions too costly or compromising safety, fairness, or valid statistical inference.

Latest papers

62 papers5 papers in the last four weeks, down 50% on the four weeks before. 0.0% of all new papers.

Feb 11, 2025

Linear Bandits beyond Inner Product Spaces, the case of Bandit Optimal Transport

Linear bandits have long been a central topic in online learning, with applications ranging from recommendation systems to adaptive clinical trials. Their general learnability has been established when the objective is to minimise the inner product between a cost parameter and the decision variable. While this is highly general, this reliance on an inner product structure belies the name of linear bandits, and fails to account for problems such as Optimal Transport. Using the Kantorovich formulation of Optimal Transport as an example, we show that an inner product structure is not necessary to achieve efficient learning in linear bandits. We propose a refinement of the classical OFUL algorithm that operates by embedding the action set into a Hilbertian subspace, where confidence sets can be built via least-squares estimation. Actions are then constrained to this subspace by penalising optimism. The analysis is completed by leveraging convergence results from penalised (entropic) transport to the Kantorovich problem. Up to this approximation term, the resulting algorithm achieves the same trajectorial regret upper bounds as the OFUL algorithm, which we turn into worst-case regret using functional regression techniques. Its regret interpolates between O~(T)\tilde{\mathcal O}(\sqrt{T}) and O(T){\mathcal O}(T), depending on the regularity of the cost function, and recovers the parametric rate O~(dT)\tilde{\mathcal O}(\sqrt{dT}) in finite-dimensional settings.
Dec 12, 2024

Allocation Stability and Wald Inference under Variance-Aware UCB

Allocation stability is often used to justify Gaussian inference from bandit data, but when is it necessary? In this paper, we address this question for a two-armed, fixed-horizon variance-aware UCB policy with bounded reward distributions that may vary with the horizon. We find a sharp criterion in terms of the reward gap and variances that determines whether the optimal-arm count admits a deterministic approximation with vanishing relative error, while the suboptimal-arm count is always stable. Despite the possible instability of the optimal-arm count, we show that the ordinary Wald statistic for a linear combination of the arm means has a standard normal limit for every fixed nonzero coefficient vector, provided the product of the pull count and reward variance diverges in probability for each arm. Under the same condition, however, this Gaussian approximation holds uniformly over deterministic nonzero coefficient vectors if and only if the optimal-arm count is stable. The analysis relies on two main ingredients: (i) a pathwise comparison with an auxiliary policy whose final optimal-arm count is asymptotically equivalent to the original count and independent of the optimal-arm reward sequence; and (ii) joint limits for the rescaled optimal-arm count and the two studentized sample-mean errors under the original policy, which yield nonstandard Wald limits for certain linear combinations of the arm means with coefficients that vary with the horizon.