alphaFeedback

WorksComputer Science

Does LinUCB Need Valid Confidence Sets?

AI contributions
  • generative AI tools
View details

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}.

Introduction

A learner interacting with a bandit environment chooses actions sequentially to earn rewards while gathering the information needed to improve future decisions. We consider this exploration–exploitation trade-off in the stochastic linear bandit setting. Fix an unknown parameter θ⋆∈Rd\theta^\star\in\mathbb{R}^d, a closed action set X\mathcal{X} contained in the unit ball of Rd\mathbb{R}^d, and an integer horizon T≥1T \ge1. At each round t∈{1,…,T}t \in\{1,\ldots,T\}, the learner selects an action xt∈Xx_t \in\mathcal{X} and receives a reward yt=⟨θ⋆,xt⟩+ηty_t = \langle\theta^\star,x_t\rangle+ \eta_t, where the noise ηt\eta_t is conditionally centred and sub-Gaussian. We consider the TT-round (pseudo-)regret,

RT:=∑t=1T⟨θ⋆,x⋆−xt⟩,x⋆∈arg⁡max⁡x∈X⟨θ⋆,x⟩.R_T := \sum_{t=1}^{T}\langle\theta^\star,x^\star-x_t\rangle,\qquad x^\star\in\arg\max_{x\in\mathcal{X}}\langle\theta^\star,x\rangle.

LinUCB addresses this trade-off using upper confidence bounds on rewards [9, 21, 1]. We study α\alpha-LinUCB (Algorithm 1), a generalisation that treats the confidence width as a free parameter. Given fixed α,λ0>0\alpha,\lambda_0 > 0, at each round tt, the algorithm selects xtx_t through

(xt,θt)∈arg⁡max⁡(x,θ)∈X×Ct(α)⟨θ,x⟩,Ct(α):={θ∈Rd:∥θ−θ^t∥Vt≤α}.(x_t,\theta_t) \in\arg\max_{(x,\theta)\in\mathcal{X}\times\mathcal{C}_t(\alpha)}\langle\theta,x\rangle,\qquad\mathcal{C}_t(\alpha):=\left\{\theta\in\mathbb{R}^d:\|\theta-\hat{\theta}_t\|_{V_t}\le\alpha\right\}.

where θ^t=Vt−1∑s=1t−1xsys\hat{\theta}_t=V_t^{-1}\sum_{s=1}^{t-1}x_sy_s is the ridge estimate of θ⋆\theta^\star with design Vt:=λ0I+∑s=1t−1xsxs⊤V_t:=\lambda_0I+\sum_{s=1}^{t-1}x_sx_s^\top. Equivalently, the action satisfies

xt∈arg⁡max⁡x∈X{⟨θ^t,x⟩+α∥x∥Vt−1}.x_t\in\arg\max_{x\in\mathcal{X}}\left\{\langle\hat{\theta}_t,x\rangle+\alpha\|x\|_{V_t^{-1}}\right\}.

Thus, actions are selected through a combination of the mean and an α\alpha-weighted exploration bonus, with ∥x∥Vt−1\|x\|_{V_t^{-1}} being large for xx aligned with directions poorly represented by previous actions.

Standard LinUCB chooses a confidence width β≍dlog⁡T\beta\asymp\sqrt{d\log T} so that θ⋆∈⋂t=1TCt(β)\theta^\star\in\bigcap_{t=1}^{T}\mathcal{C}_t(\beta) with high probability. On this event, the selected pair (xt,θt)(x_t,\theta_t) satisfies the optimism inequality $\langle\theta_t,x_t\rangle\ge ⟨θ⋆,x⋆⟩\langle\theta^\star,x^\star\rangle, which underlies its usual regret guarantee [1]. For arbitrary α>0\alpha>0, α\alpha-LinUCB retains an exploration bonus, but its ellipsoids need not be valid confidence sets. The optimism inequality is then no longer guaranteed, so the usual regret argument does not extend to arbitrary choices of α\alpha. This raises the question: Does LinUCB Need Valid Confidence Sets?

Under an additional curvature condition on the action set, we answer this question in the negative:

  • Regret without valid confidence sets. When the squared support function of the action set is MM-smooth and mm-strongly convex, we prove a high-probability regret bound of2

RT=O(MmMα2+β2αdT),R_T=\mathcal{O}\left(\frac{M}{m}\frac{M\alpha^2+\beta^2}{\alpha}\sqrt{dT}\right),

up to iterated-logarithmic factors (Theorem 4.2). The bound is sublinear for every fixed α>0\alpha>0, including widths for which the exploration ellipsoids are not valid confidence sets. The geometric condition, stated in Assumption (A2), includes Euclidean balls, ellipsoids, and convex bodies with uniformly positive and bounded curvature.

  • A geometric exploration mechanism. We identify the mechanism through which α\alpha-LinUCB works without optimism: action-set curvature drives α\alpha-LinUCB to explore every direction, even when optimism is not guaranteed. Our spectral theorem makes this precise by controlling the growth of the design matrix (Theorem 4.3). On the unit ball, it gives a lower bound proportional to t\sqrt{t} on λmin⁡(Vt)\lambda_{\min}(V_t), holding with high probability at every round after a burn-in period; the general result controls the corresponding width in the action set geometry.

  • A logarithmically capped potential. To analyse this exploration mechanism, we introduce a logarithmically capped spectral potential that, unlike the standard log-determinant potential, caps contributions from well-explored directions. The resulting spectral bounds yield regret control without the usual elliptical-potential argument. At the standard width α=β\alpha=\beta, this gives O(MmdTlog⁡T)\mathcal{O}\left(\frac{M}{m}d\sqrt{T\log T}\right) regret, improving the horizon dependence of the classical O(dTlog⁡T)\mathcal{O}(d\sqrt{T}\log T) guarantee by a factor of log⁡T\sqrt{\log T}, up to iterated-logarithmic factors.

Moreover, we construct a counterexample confirming that assumptions on the action set are necessary: on a two-dimensional polygon, α\alpha-LinUCB incurs linear regret with constant probability, for every sufficiently small α>0\alpha>0 (Proposition 6.1). We support our theoretical findings with experiments: on the unit ball, the observed regret and smallest-eigenvalue growth are consistent with the predicted t\sqrt{t} rates, even when the ellipsoids exclude the true parameter in most rounds.

Notation. We write [T]:={1,…,T}[T]:=\{1,\ldots,T\}, I\mathbf{I} for the identity matrix in Rd×d\mathbb{R}^{d\times d}, and λmin⁡(V)\lambda_{\min}(V) for the smallest eigenvalue of a symmetric matrix VV. For u,v∈Rdu,v\in\mathbb{R}^d, let ⟨u,v⟩\langle u,v\rangle denote their inner product, and define ∥u∥2:=⟨u,u⟩\|u\|_2:=\sqrt{\langle u,u\rangle} and ∥u∥V:=⟨u,Vu⟩\|u\|_V:=\sqrt{\langle u,Vu\rangle} for V≻0V\succ0. We write B2d(r)\mathbb{B}_2^d(r) for the dd-dimensional closed Euclidean ball of radius rr centred at the origin.

Related work

Our work is closest to that of Abeille et al. [3], who use the same geometric condition to analyse Thompson sampling without forced optimism or posterior inflation. Banerjee et al. [6] also connect curvature with exploration, deriving growth of the smallest eigenvalue of the expected design matrix from an assumed O(T)\mathcal{O}(\sqrt{T}) regret guarantee. We discuss these and further connections below.

Optimism and confidence sets in linear bandits. The classical O(dTlog⁡(T))\mathcal{O}(d\sqrt{T}\log(T)) regret analysis of LinUCB/OFUL combines self-normalised concentration with the elliptical-potential lemma [21, 1]. Each contributes a log⁡(T)\sqrt{\log(T)} factor, leaving a logarithmic gap to the Ω(dT)\Omega(d\sqrt{T}) minimax lower bound [9, 26, 20]. Lattimore [18] proves that the continuous-time counterpart of the self-normalised concentration bound cannot be improved for general adaptive covariates. Flynn et al. [12] construct tighter confidence sequences using adaptive martingale mixtures, improving empirical performance while retaining O(dTlog⁡(T))O(d\sqrt{T}\log(T)) worst-case regret. Our analysis uses the standard confidence bound but with a logarithmically capped potential.

Classical frequentist analyses of linear Thompson sampling also rely on optimism: posterior inflation ensures a constant probability of an optimistic draw, at the cost of an additional d\sqrt{d} factor in the regret bound [4, 2]. For finite-armed linear bandits, Lattimore & Szepesvári [19] show that standard optimism-based algorithms can be suboptimal. Subsequent asymptotically optimal algorithms explicitly optimise exploration allocations to account for the information provided by suboptimal actions [13, 28].

Action-set curvature and exploration. When the action set is smooth and strongly convex, the played arm xt=∇JX(θt)x_t = \nabla J_{\mathcal{X}}(\theta_t) moves continuously with the parameter, and perturbations of the estimate translate into exploration. The benefit of curvature is classical in online learning, where follow-the-leader enjoys fast rates on strongly convex constraint sets for much the same reason [14]. In stochastic bandits, Banerjee et al. [6] quantify this: for action sets with bounded curvature around the optimal arm, any algorithm with O(T)O(\sqrt{T}) expected regret has a design matrix whose minimum eigenvalue grows as Ω(T)\Omega(\sqrt{T}) in expectation; in contrast well-separated arms [19] force eventual logarithmic growth. Abeille et al. [3] exploit the same geometry, under the assumption we adopt here, to analyse randomised exploration without forced optimism or posterior inflation, and show that Thompson sampling attains O(dTlog⁡(T))O(d\sqrt{T}\log(T)) regret.

Taking α=0\alpha= 0 in our decision rule gives the greedy policy. Greedy methods are studied in contextual bandits, but only known to succeed under diversity of contexts, either assumed [7] or induced by smoothing [15, 24]. On a fixed action set no such diversity is available and, accordingly, our bound degrades as α→0\alpha\to0.

Inference under adaptive sampling. Conditions on the growth of the design matrix play a central role in inference from adaptively collected data, beginning with Lai & Wei [17]. Ordinary least squares can have non-Gaussian asymptotic distributions and inflated estimation error under adaptive designs [16, 22], motivating debiasing procedures that recover asymptotic normality under conditions on the data-collection process [10, 16, 30, 22]. A complementary approach establishes stability of the design after deterministic normalisation; Praharaj & Khamaru [23] use this to obtain asymptotically valid Wald intervals for a regularised EXP4 algorithm in linear contextual bandits.

Assumptions

We use the following two assumptions, placed on the noise and the action set, respectively.

Stochasticity. Let Ft\mathcal{F}_t be the σ\sigma-field generated by the history up to round tt together with the next action, so that xt+1x_{t+1} is Ft\mathcal{F}_t-measurable; namely, Ft:=σ(x1,y1,…,xt,yt,xt+1)\mathcal{F}_t := \sigma(x_1,y_1,\ldots,x_t,y_t,x_{t+1}).

(A1) (Sub-Gaussian Noise). The noise variables are conditionally μ\mu-sub-Gaussian: for every t∈[T]t \in[T],

E[ηt∣Ft−1]=0andE[exp⁡(νηt)∣Ft−1]≤exp⁡(μ2ν22)for all ν∈R.\mathbb{E}[\eta_t \mid\mathcal{F}_{t-1}] = 0 \quad\text{and} \quad\mathbb{E}[\exp(\nu\eta_t) \mid\mathcal{F}_{t-1}] \leq\exp\left(\frac{\mu^2\nu^2}{2}\right) \quad\text{for all } \nu\in\mathbb{R}.

The sub-Gaussian property ensures the concentration of self-normalized martingales, which we shall leverage to control the cumulative effect of noise under adaptive design.

The geometry of the action set. We consider a generic action set X\mathcal{X} and impose the same assumptions as in Abeille et al. [3], which are expressed in terms of the support function of X\mathcal{X},

JX(θ):=max⁡x∈X⟨θ,x⟩.J_{\mathcal{X}}(\theta) := \max_{x \in\mathcal{X}} \langle\theta, x \rangle.

The optimal expected reward is denoted by J∗:=JX(θ∗)J_* := J_{\mathcal{X}}(\theta^*). The support function plays a central role in the analysis: whenever it is differentiable at θt\theta_t, the action selected by the algorithm is $x_t = ∇JX(θt)\nabla J_{\mathcal{X}}(\theta_t), so the instantaneous regret can be written entirely in terms of JXJ_{\mathcal{X}},

References

  1. [1]Yasin Abbasi-Yadkori, Dávid Pál, and Csaba Szepesvári. Improved algorithms for linear stochastic bandits. In Advances in Neural Information Processing Systems, 2011.
  2. [2]Marc Abeille and Alessandro Lazaric. Linear Thompson sampling revisited. In Proceedings of the 20th International Conference on Artificial Intelligence and Statistics, 2017.DOI
  3. [3]Marc Abeille, David Janz, and Ciara Pike-Burke. When and why randomised exploration works (in linear bandits). In Proceedings of the 36th International Conference on Algorithmic Learning Theory, 2025.arxiv.org/abs/2502.08870
  4. [4]Shipra Agrawal and Navin Goyal. Thompson sampling for contextual bandits with linear payoffs. In Proceedings of the 30th International Conference on Machine Learning, 2013.arxiv.org/abs/1209.3352
  5. [5]A. D. Alexandrov. Almost everywhere existence of the second differential of a convex function and some properties of convex surfaces connected with it. Leningrad State University Annals [Uchenye Zapiski], Mathematical Series, 6:3–35, 1939. In Russian.
  6. [6]Debangshu Banerjee, Avishek Ghosh, Sayak Ray Chowdhury, and Aditya Gopalan. Exploration in linear bandits with rich action sets and its implications for inference. In Proceedings of the 26th International Conference on Artificial Intelligence and Statistics, 2023.arxiv.org/abs/2207.11597
  7. [7]Hamsa Bastani, Mohsen Bayati, and Khashayar Khosravi. Mostly exploration-free algorithms for contextual bandits. Management Science, 67(3):1329–1349, 2021.arxiv.org/abs/1704.09011
  8. [8]Amir Beck. First-Order Methods in Optimization. Society for Industrial and Applied Mathematics, 2017.DOI
  9. [9]Varsha Dani, Thomas P. Hayes, and Sham M. Kakade. Stochastic linear optimization under bandit feedback. In Proceedings of the 21st Annual Conference on Learning Theory, 2008.
  10. [10]Yash Deshpande, Lester Mackey, Vasilis Syrgkanis, and Matt Taddy. Accurate inference for adaptive linear models. In Proceedings of the 35th International Conference on Machine Learning, 2018.arxiv.org/abs/1712.06695
  11. [12]Hamish Flynn, David Reeb, Melih Kandemir, and Jan R. Peters. Improved algorithms for stochastic linear bandits using tail bounds for martingale mixtures. In Advances in Neural Information Processing Systems, 2023.arxiv.org/abs/2309.14298
  12. [13]Botao Hao, Tor Lattimore, and Csaba Szepesvári. Adaptive exploration in linear contextual bandit. In Proceedings of the 23rd International Conference on Artificial Intelligence and Statistics, 2020.arxiv.org/abs/1910.06996
  13. [14]Ruitong Huang, Tor Lattimore, András György, and Csaba Szepesvári. Following the leader and fast rates in linear prediction: Curved constraint sets and other regularities. In Advances in Neural Information Processing Systems, 2016.
  14. [15]Sampath Kannan, Jamie Morgenstern, Aaron Roth, Bo Waggoner, and Zhiwei Steven Wu. A smoothed analysis of the greedy algorithm for the linear contextual bandit problem. In Advances in Neural Information Processing Systems, 2018.arxiv.org/abs/1801.03423
  15. [16]Koulik Khamaru, Yash Deshpande, Tor Lattimore, Lester Mackey, and Martin J. Wainwright. Near-optimal inference in adaptive linear regression. The Annals of Statistics, 53(6):2329–2355, 2025.arxiv.org/abs/2107.02266
  16. [17]Tze Leung Lai and Ching Zong Wei. Least squares estimates in stochastic regression models with applications to identification and control of dynamic systems. The Annals of Statistics, 10(1): 154–166, 1982.DOI
  17. [18]Tor Lattimore. A lower bound for linear and kernel regression with adaptive covariates. In Proceedings of the 36th Conference on Learning Theory, 2023.
  18. [19]Tor Lattimore and Csaba Szepesvári. The end of optimism? an asymptotic analysis of finite-armed linear bandits. In Proceedings of the 20th International Conference on Artificial Intelligence and Statistics, 2017.arxiv.org/abs/1610.04491
  19. [20]Tor Lattimore and Csaba Szepesvári. Bandit Algorithms. Cambridge University Press, 2020.
  20. [21]Lihong Li, Wei Chu, John Langford, and Robert E. Schapire. A contextual-bandit approach to personalized news article recommendation. In Proceedings of the 19th International Conference on World Wide Web, 2010.DOI
  21. [22]Licong Lin, Mufang Ying, Suyrojit Ghosh, Koulik Khamaru, and Cun-Hui Zhang. Statistical limits of adaptive linear models: Low-dimensional estimation and inference. In Advances in Neural Information Processing Systems, 2023.arxiv.org/abs/2310.00532
  22. [23]Samya Praharaj and Koulik Khamaru. Avoiding the price of adaptivity: Inference in linear contextual bandits via stability. arXiv:2512.20368v2, 2026.arxiv.org/abs/2512.20368
  23. [24]Manish Raghavan, Aleksandrs Slivkins, Jennifer Wortman Vaughan, and Zhiwei Steven Wu. Greedy algorithm almost dominates in smoothed contextual bandits. SIAM Journal on Computing, 52(2): 487–524, 2023.arxiv.org/abs/2005.10624
  24. [25]R. Tyrrell Rockafellar and Roger J.-B. Wets. Variational Analysis. Springer, 1998.DOI
  25. [26]Paat Rusmevichientong and John N. Tsitsiklis. Linearly parameterized bandits. Mathematics of Operations Research, 35(2):395–411, 2010.
  26. [28]Andrea Tirinzoni, Matteo Pirotta, Marcello Restelli, and Alessandro Lazaric. An asymptotically optimal primal-dual incremental algorithm for contextual linear bandits. In Advances in Neural Information Processing Systems, 2020.arxiv.org/abs/2010.12247
  27. [29]Jean Ville. Étude critique de la notion de collectif. PhD thesis, Université de Paris, 1939.
  28. [30]Mufang Ying, Koulik Khamaru, and Cun-Hui Zhang. Adaptive linear estimating equations. In Advances in Neural Information Processing Systems, 2023.arxiv.org/abs/2307.07320

Paper details

vlnc:W_5233a9ft
v1 · latestHistory (1)

published · Fresh — added to the Hub within the last 30 days

added ·

Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

CC BY 4.0

Original source

  • Computer Science

generative AI tools · View statement →

Looking for related papers…
Contents