cs.LGNov 3, 2026

Does LinUCB Need Valid Confidence Sets?

Authors: Ahmed Ben Yahmed, Marc Abeille, David Janz, Clément Calauzènes

Organizations: Criteo AI Lab, Paris, France · CREST, ENSAE, Institut Polytechnique de Paris, France · FairPlay joint team, Inria, France · University of Oxford

Abstract

We show that replacing LinUCB's usual confidence width ββ by any fixed α>0α>0 preserves sublinear regret when the action set is MM-smooth and mm-strongly convex. Our high-probability regret bound for this generalisation, αα-LinUCB, establishes that valid confidence sets are not necessary for the success of LinUCB. We identify the mechanism behind this result: action-set curvature drives αα-LinUCB to explore every direction, even when optimism is not guaranteed. To analyse this mechanism, we introduce a logarithmically capped spectral potential that, unlike the standard log-determinant potential, caps contributions from well-explored directions. This yields lower bounds on the smallest eigenvalue of the design matrix. At the standard confidence width α=β≍dlog⁡Tα=β\asymp\sqrt{d\log T}, our TT-round regret bound in dd dimensions is O(MmdTlog⁡T)O\bigl(\frac{M}{m}d\sqrt{T\log T}\bigr), up to iterated-logarithmic factors, improving the horizon dependence of the classical LinUCB guarantee by a factor of log⁡T\sqrt{\log T}.

Figures & tables

Appendix figures & tables2 assets

Supplementary material from the paper’s appendix.

Appendix

Explore similar work

Oct 5, 2026

Sampling Allocation of LinUCB: Optimal Design Limits in the Small-Gap Regime

We study the sampling allocation of LinUCB in the small-gap regime, where the reward gaps are of order at most n−1/2n^{-1/2} over the decision horizon nn. This scaling captures the hard instances underlying worst-case regret lower bounds, for which LinUCB is known to be near optimal up to logarithmic factors in nn. Using a mean-field perspective, we characterize this allocation through the empirical sampling distribution, a macroscopic object that averages the effect of adaptive decisions over the horizon, and identify its limit as n→∞n\to\infty. We establish that in this regime, the empirical sampling distribution induced by LinUCB converges to the set of D-optimal designs. This central result reveals that, in the small-gap regime, LinUCB not only achieves near optimal minimax regret but also allocates samples in a way that is asymptotically efficient for learning the reward parameter, thereby connecting regret-driven online learning with information-efficient experimental design. Building on the optimal design limit, we obtain two useful consequences. First, we refine the asymptotic regret analysis of LinUCB in the small-gap regime by characterizing its leading-order constant in the limit. Second, we show that, despite LinUCB's adaptive sampling strategy, the regularized least-squares estimator satisfies a central-limit-type theorem in the small-gap regime, thereby enabling valid statistical inference for the reward parameter.
Sep 26, 2026

A Unified Optimism-Agnostic Framework for Linear Bandits over Spherical Action Sets

Linear bandits model sequential decision-making problems with noisy rewards that are linear in the decision variable, where an agent must simultaneously learn about an unknown parameter that governs the mean rewards, while maximizing (expected) rewards over time. Two prominent algorithmic families--upper confidence bound (UCB) and Thompson sampling (TS)--achieve a balance of exploration (to estimate said parameter) and exploitation (utilization of knowledge about it) across time. The quality of estimation of that parameter depends on the eigenvalues of a design matrix. In this paper, we begin by showing that if the inference quality obtained from exploration, encoded in the minimum eigenvalue of the design matrix, grows ≳t\gtrsim \sqrt{t} with time tt, while actions remain sufficiently concentrated for exploitation, then an algorithm produces optimal high-probability O(Tlog⁡T)\mathcal{O}(\sqrt{T}\log T)-regret rate over a time-horizon TT for spherical action sets. This analysis is algorithm-agnostic and follows an alternative route to the classical optimism-based elliptical-potential argument for regret analysis. Then, we illustrate that variants of UCB and TS satisfy the inference and concentration properties and in turn, enjoy optimal regret rate. In effect, our results provide a modular framework that can be used to analyze linear bandit algorithms and explicitly connect quality of parameter estimation to optimal regret accumulation.
Oct 9, 2026

Accelerating Linear Bandits with Persistent Candidate Sets

Exhaustive optimistic scoring can make action selection costly in linear bandits with a large fixed set of KK actions, requiring O(K)\mathcal{O}(K) score evaluations per round. We introduce Persistent Candidate LinUCB (PC-LinUCB), which maintains kk active actions and samples qq challengers uniformly from the remaining K−kK-k actions at each round. By scoring only these k+qk+q candidates, PC-LinUCB reduces the number of score evaluations per round to O(k+q)\mathcal{O}(k+q). We establish problem-independent and problem-dependent high-probability regret bounds consisting of a standard linear-bandit learning term and an additive discovery cost of order O((K−k)log⁡(K−k)/q)\mathcal{O}\left((K-k)\log(K-k)/q\right) at fixed confidence. Notably, this additional cost does not grow with the horizon. For fixed gaps and sufficiently long horizons, we establish an Ω((K−k)/q)Ω\left((K-k)/q\right) regret lower bound under uniform challenger sampling, showing that partial candidate access itself imposes an unavoidable regret cost. Experiments show that PC-LinUCB substantially accelerates LinUCB while maintaining comparable regret, and that the persistent candidate mechanism can extend beyond LinUCB.