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

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

    Oct 5, 2026Yujie Liu, Vincent Y. F. Tan, Yunbei XuAdaptive InferenceContextual Bandits

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

    Sep 26, 2026Arda Güçlü, Subhonmesh Bose, John R. BirgeMulti-Armed BanditsUCB Algorithms

  3. Accelerating Linear Bandits with Persistent Candidate Sets

    Oct 9, 2026Bingkui Tong, Daria Korovaitceva, Marina Sheshukova +2Multi-Armed BanditsLinear Contextual Bandits