acceptodds
Under review as a conference paper at ICLR 2027

Does LinUCB Need Valid Confidence Sets?

Abstract

We show that replacing LinUCB's usual confidence width by any fixed preserves sublinear regret when the action set is -smooth and -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 , our -round regret bound in dimensions is , up to iterated-logarithmic factors, improving the horizon dependence of the classical LinUCB guarantee by a factor of .

Primary area:
learning theory
Keywords:
Linear bandits, optimisim, confidence sets, spectral analysis, regret bounds

Reviews

Among:
Shape:
1234this paper, Top 30%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.67 over 3 reviews, above 70% of the others.
Reviewer_DyVWOpenReview ↗
Rating
3
Confidence
4
Informativeness
3
Presentation
3
Soundness
2
Read review
Paper summary

This paper investigates whether valid confidence sets are necessary for LinUCB to achieve sublinear regret. The authors show that a variant of LinUCB with a fixed confidence width achieves sublinear regret under smoothness and strong convexity assumptions on the action set. They establish a high-probability regret bound using a novel spectral potential analysis, improving the horizon dependence of classical LinUCB guarantees.

Critical strengths

Given the central role of valid confidence sets in linear bandit algorithms, this paper raises a novel and compelling research question.

Critical weaknesses

See Questions.

Questions for authors
  1. Could the authors clarify how the assumptions in Section 3 compare with those in standard linear bandits? In particular, does the analysis rely on stronger structural assumptions to compensate for the lack of valid confidence sets?

  2. The improvement over the lower bound of Banerjee et al. appears to require assumptions on the minimum eigenvalue, particularly in the unit-ball setting. How does this lower bound extend to more general action sets?

  3. Recent work on sketch-based linear bandits [1] has also explored spectral properties to improve regret guarantees. Could the authors discuss potential connections between α-LinUCB and these approaches?

[1] Revisiting Matrix Sketching in Linear Bandits: Achieving Sublinear Regret via Dyadic Block Sketching. ICLR 2026.

2 comments

We thank the reviewer for the positive assessment and the precise questions, which we answer in order.


  1. Assumptions compared with standard linear bandits. (A1) and the boundedness conditions (∥θ⋆∥2≤S⋆\Vert\theta^\star\Vert_2\le S^\star, X⊆B2d(1)\mathcal X\subseteq B_2^d(1)) are those of Abbasi-Yadkori et al. (2011). The only additional assumption is (A2), and the answer to the reviewer’s question is yes: it is the structural assumption that replaces validity. The classical analysis allows arbitrary, even time-varying, action sets because optimism does all the work. Once θ⋆∉Ct(α)\theta^\star\notin\mathcal C_t(\alpha), optimism is lost and some geometric condition is unavoidable: on a polytope, α\alpha-LinUCB has linear regret for all small α\alpha (Proposition 6.1). (A2) is the condition under which Abeille et al. (2025) analyse Thompson sampling without inflation. It covers balls, ellipsoids and C2C^2 bodies with curvature bounded above and below, and excludes polytopes and finite arm sets. Two remarks:

    • The algorithm uses none of the quantities in (A2).
    • Only the strong-convexity half is needed for exploration, i.e. for polynomial spectral growth; smoothness is used for the sharp rates (see our answer to Reviewer 8pio).  
  2. Spectral lower bound and general action sets. We make no assumption on the minimum eigenvalue: its growth is the conclusion of Theorem 4.3, derived from (A1)–(A2) alone. The result is not specific to the unit ball; we state the comparison there only because ωt=1/λmin⁡(Vt)\omega_t=1/\lambda_{\min}(V_t) in that case. Theorem 4.3 holds for every action set satisfying (A2) and yields, with high probability and after burn-in, λmin⁡(Vt)≳t\lambda_{\min}(V_t)\gtrsim\sqrt t, with a constant that depends on the geometry only through mm, MM, J⋆J_\star and the distance from the origin to the boundary of X\mathcal X. Unlike the bound of Banerjee et al., which concerns the expected design and presupposes O(T)O(\sqrt T) regret, ours holds along the trajectory.

 

  1. Connection with sketch-based linear bandits. We thank the reviewer for this pointer; the connection is real and we will discuss it. Both works modify the ellipsoid of LinUCB and both hinge on the spectrum of the design, in complementary ways.

    • What is modified. Wen et al. replace VtV_t by a sketch and enlarge the radius to account for the sketching error, so that the ellipsoid remains a valid confidence set and optimism is preserved. We keep VtV_t exact and shrink the radius: validity is lost, and exploration must come from the geometry.
    • Role of the spectrum. For sketching, a slowly decaying spectrum is the obstacle: their Observation 1 uses Banerjee et al. to argue that, on curved arm sets, the growth of the smallest eigenvalue makes the bound of a fixed-size sketch vacuous. For us, the same growth is the resource that replaces validity.
    • What our result adds. For α\alpha-LinUCB, Theorem 4.3 proves this growth along the trajectory. On the unit ball, with high probability, the top eigenvalue of VtV_t is of order tt and all others are of order t\sqrt t, up to logarithmic factors (Theorem 4.3 and Lemma D.12). The actions played by α\alpha-LinUCB thus form a rank-one component plus a full-rank bulk, and any sketch of size l<dl<d of this stream has error at least of order T\sqrt T, above the o(T1/3)o(T^{1/3}) level that fixed-size sketches require.

    The two settings are therefore complementary: curvature makes exploration cheap but forces a full-rank design, whereas sketching pays off when the design is close to low rank. Whether the robustness to a miscalibrated radius shown here extends to a miscalibrated shape, as produced by sketching, is a natural question for future work.


We hope these answers address the reviewer’s concerns, and we would be grateful if the reviewer would consider them in the final assessment. We are happy to discuss further.

Thank you for your reply; my issue has essentially been resolved. I will continue to maintain my positive score.

Reviewer_8pioOpenReview ↗
Rating
3
Confidence
4
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

he paper studies whether LinUCB can achieve sublinear regret when its confidence sets are not statistically valid. The authors introduce α\alpha-LinUCB, which treats the confidence width as a free exploration parameter rather than requiring it to ensure that the true parameter lies inside the confidence set. They prove that, when the action set satisfies a smoothness and strong-convexity condition, α\alpha-LinUCB achieves sublinear regret for any fixed α>0\alpha>0. The key technical contribution is a logarithmically capped spectral potential, which establishes growth of the design matrix in every direction and allows the authors to derive regret guarantees without relying on the usual optimism argument or elliptical-potential analysis. For the standard confidence width, their analysis improves the classical LinUCB regret bound by a factor of log⁡T\sqrt{\log T}, up to iterated-logarithmic factors. The authors also provide a counterexample showing that, for polygonal action sets and sufficiently small exploration widths, the algorithm can incur linear regret with constant probability. Numerical simulations on the unit ball support the theoretical findings

Critical strengths
  1. Challenges a fundamental assumption in LinUCB analysis. The paper questions whether statistically valid confidence sets and the associated optimism guarantee are necessary for sublinear regret. By establishing guarantees for arbitrary fixed exploration widths under suitable geometric conditions, it provides a useful alternative perspective on the mechanism underlying LinUCB's performance.

  2. Identifies a geometric mechanism for exploration. The paper shows how smoothness and strong convexity of the action set can ensure exploration across all directions, even when the confidence sets fail to contain the true parameter. This provides a concrete explanation for how the algorithm can succeed without the usual optimism argument.

  3. Introduces a novel analytical tool. The logarithmically capped spectral potential controls the growth of the design matrix while limiting the contribution of well-explored directions. This enables the authors to establish minimum-eigenvalue growth and derive regret bounds without relying on the standard elliptical-potential argument.

  4. Provides stronger regret guarantees for standard LinUCB. At the conventional confidence width, the analysis improves the classical regret upper bound by a factor of log⁡T\sqrt{\log T}, up to iterated-logarithmic factors. This is a meaningful theoretical improvement, even though a gap to the minimax lower bound remains.

  5. Characterizes a concrete failure regime. The polygonal-action-set counterexample demonstrates that curvature is not merely a technical convenience: without the required geometry, α\alpha-LinUCB can repeatedly select suboptimal actions and incur linear regret with constant probability for sufficiently small exploration widths.

  6. Supports the theoretical analysis with targeted experiments. The simulations examine regret, minimum-eigenvalue growth, and confidence-set failure frequency, providing empirical evidence consistent with the proposed exploration mechanism.

Critical weaknesses

Restrictive geometric assumptions. The theoretical guarantees rely on the action set being smooth and strongly convex, excluding common action sets such as polytopes.

  1. Limited improvement over existing regret bounds. Although the analysis improves the classical LinUCB regret bound by a factor of log⁡T\sqrt{\log T}, up to iterated-logarithmic factors, it does not close the gap to the minimax lower bound of Ω(dT)\Omega(d\sqrt{T}). The authors acknowledge that a remaining log⁡T\sqrt{\log T} factor arises from the concentration inequality used in their analysis.

  2. Limited empirical validation. The experiments focus on a single synthetic setting—the Euclidean unit ball with d=10d=10—and use 48 independent replications. While the results support the theoretical predictions, the evaluation does not investigate a broader range of dimensions, action-set geometries, or problem parameters to assess the practical scope of the findings.

  3. The role of curvature could be characterized more precisely. The paper establishes that the assumed curvature condition is sufficient for sublinear regret and provides a polygonal counterexample where the algorithm fails for sufficiently small exploration widths. However, it explicitly does not establish that this condition is necessary. A sharper characterization of the action-set geometries under which α\alpha-LinUCB succeeds or fails would strengthen the results

  4. The only major weakness I see in this paper is in terms of applicability.. Given that LinUCB is not practical to implement and that we have better formulations (say TS), I am not sure what extra this method brings to the table. I agree that the result is neat and the implications are nice, however in terms of practical usability I have serious doubts. Perhaps the authors can extend a TS version where the regret version is undisturbed by the noise scale.

Questions for authors

While the results in Banerjee et al show the growth of the minimum eigen value in expectation (albeit an assumption which enables a high probability bound), the authors result seem to bring out the high probability spectral growth naturally. Could the authors provide a brief clarification on this result. A small proof sketch is more than enough.

Does the result still hold for general convex sets, say an ℓp\ell_p ball with p>2p>2? The spectral result of Banerjee et al still seem to hold with a polynomial growth for the minimum eigen value of general convex bodies.

What seems a bit unclear is how despite paying for an exploration penalty you are yet not paying anything in terms of regret. I guess this is because of the geometry, where even if you play an imperfect arm you will still be improving your collected reward. Is my intuition correct?

2 comments

We thank the reviewer for the careful and constructive review. We answer the questions first, then the remaining weaknesses.


  1. High-probability spectral growth, and Banerjee et al. (2023). Their Theorem 2.2 is a change-of-measure argument: an algorithm with O(T)O(\sqrt T) expected regret at θ\theta, and at a perturbation of θ\theta along the least eigenvector of the expected design, must distinguish the two instances, which forces λmin⁡(E[VT])≳T\lambda_{\min}(\mathbb E[V_T])\gtrsim\sqrt T. The argument is algorithm-independent but intrinsically in expectation; for trajectories, their applications assume the high-probability bound (Assumption 5.1), and their appendix derives it under an additional stability condition on the algorithm. We argue in the opposite direction, from the dynamics of the algorithm to the spectrum, with no regret bound presupposed. This matters here: to our knowledge, no regret bound was available for LinUCB with invalid confidence sets, so their theorem, which takes such a bound as input, could not be applied to α\alpha-LinUCB. The only probabilistic input of our proof is the self-normalised concentration event E\mathcal E (Proposition 4.1); on E\mathcal E every step is deterministic:

    • Engine (Lemma D.7): we establish that, at every round, the total energy of the played arm satisfies ∥xt∥Vt−12≳α2ωt2\Vert x_t\Vert_{V_t^{-1}}^2\gtrsim\alpha^2\omega_t^2.
    • Budget (Lemmas D.11–D.13): most of this energy lands on the small eigenvalues, and each such round raises the capped potential, a tool introduced in our paper.
    • Doubling (Lemma D.14): since the capacity of the capped potential is bounded independently of the horizon, the smallest eigenvalue must double within a number of rounds quadratic in its current value, which yields the t\sqrt t rate.

    The bound thus holds directly at all rounds after burn-in, with probability 1−δ1-\delta. In particular, Theorem 4.3 at α=β\alpha=\beta proves, for LinUCB on sets satisfying (A2), the bound that Banerjee et al. assume in their applications. To our knowledge, this is the first trajectory-wise characterisation of the spectral dynamics of a UCB-type algorithm.

 

  1. General convex sets, ℓp\ell_p balls, and the role of curvature. Beyond locally ellipsoidal sets, Banerjee et al. (Theorem 3.3) obtain Ω(Ts)\Omega(T^s) for a geometry-dependent s∈(0,12]s\in(0,\tfrac12], again in expectation and assuming O(T)O(\sqrt T) regret; their result also requires a positive-definite Hessian at the optimal arm, which fails on an ℓp\ell_p ball, p>2p>2, whenever θ⋆\theta^\star has a zero coordinate. For α\alpha-LinUCB, our proof gives a high-probability statement with an explicit rate, because the two halves of (A2) play separate roles in the spectral analysis.

    • Strong convexity of JX2J_{\mathcal X}^2 (no corners) drives exploration. The proofs of Lemma D.7, Proposition D.8(i) and Lemma D.9 use only the lower inequality in (1). They give, after a polylogarithmic burn-in, ωt−1≥c1t/log⁡t\omega_t^{-1}\ge c_1\sqrt{t/\log t} with c1∝mα/(J⋆d)c_1\propto m\alpha/(J_\star\sqrt d).
    • Smoothness (no flat points) is used to sharpen this to t\sqrt t (Theorem 4.3).

    For the (rescaled) ℓp\ell_p ball with p>2p>2, JX2∝∥⋅∥q2J_{\mathcal X}^2\propto\Vert\cdot\Vert_q^2 with q=p/(p−1)<2q=p/(p-1)<2 is strongly convex, with m≍1/(p−1)m\asymp 1/(p-1), but not smooth, since the curvature of the boundary vanishes wherever a coordinate is zero. The first regime applies: with high probability, for every α>0\alpha>0 and every θ⋆≠0\theta^\star\neq0, the design grows at least as t/log⁡t\sqrt{t/\log t} in every direction. The constant degrades as p→∞p\to\infty, consistently with the polytope limit, where m=0m=0 and the design need not grow at all (Proposition 6.1). We will add this remark; a full characterisation remains open.

  1. Intuition on the cost of exploration. Yes, in essence. On a curved set the first-order term vanishes at the optimal arm, so the regret is quadratic in the parameter error: after burn-in, rt≤M2J⋆∥θ⋆−θt∥∗2r_t\le\frac{M}{2J_\star}\Vert\theta^\star-\theta_t\Vert_*^2 (Lemma E.1 and (1)). By Theorem 4.3, this error is of order t−1/4t^{-1/4}, and so is the displacement of the played arm from x⋆x^\star. The squared displacement, of order t−1/2t^{-1/2}, is both what the round adds to the least-explored eigenvalues of VtV_t and what it costs in regret. Regret and information are thus paid in the same currency: summing over rounds gives t\sqrt t spectral growth and T\sqrt T regret. Exploration is therefore not free, but it enters only at second order: it is the α2\alpha^2 term in (α2+β2)/α(\alpha^2+\beta^2)/\alpha, while β2/α\beta^2/\alpha is the price of under-exploration. On a polytope this coupling breaks: the arm does not move with the parameter, and no information is gained (Proposition 6.1).

 

  1. Applicability. LinUCB has been run with a tuned α\alpha since Li et al. (2010), who note that the theoretical width may be conservatively large. Our results give this practice a first theoretical footing on curved action sets, and Proposition 6.1 shows where it can fail. Moreover, α\alpha-LinUCB requires neither the noise scale, nor ∥θ⋆∥\Vert\theta^\star\Vert, nor TT; these enter only β\beta, which is used in the analysis alone. On balls and ellipsoids, the decision rule maximises a quadratic over an ellipsoid, a trust-region problem that is solved exactly.

 

  1. Remaining gap. The last log⁡T\sqrt{\log T} comes from the self-normalised bound, which cannot be improved for general adaptive designs (Lattimore, 2023). Our analysis removes the factor due to the elliptical potential. Removing the other within this family of algorithms is not straightforward, but we believe that the fine-grained understanding of the spectral dynamics developed in this paper is a useful step towards it: sharper concentration bounds are known when the design has additional structure (e.g. the stability condition of Lai & Wei, 1982), and our results describe precisely how each direction of the design grows.

We hope these answers clarify the points raised, and we would be grateful if the reviewer would consider them in the final assessment. We are happy to discuss further.

Reviewer_wt3yOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

This paper studies stochastic bandits where the action set is uniformly curved (formally, the squared support function of the action set is MM-strongly-convex and mm-smooth; so unit ball is good but polytope isn't). In addition to Thompson Sampling considered by Abeille'25, this paper proves that α\alpha-LinUCB, which replaces the standard LinUCB confidence width β=dlog⁡T\beta=\sqrt{d\log T} with an arbitrary constant α>0\alpha>0 that doesn't change with TT, also attains sublinear regret:

RT=O(Mmα2+dlog⁡TαdT).R_T=\mathcal O\left (\frac{M}{m} \frac{\alpha^2 + d\log T}{\alpha} \sqrt{dT}\right ).

As a corollary, picking α=dlog⁡T\alpha=\sqrt{d\log T} (recovering standard LinUCB) gives O(dTlog⁡T)\mathcal O(d\sqrt{T\log T}) regret for the unit bal. This beats the standard LinUCB bound by a factor of log⁡T\sqrt{\log T}. Note that this bound become vacuous when α→0+\alpha\to 0^+, hence direct greedy doesn't work well (and there's indeed a counterexample for greedy over the unit ball).

Critical strengths

This paper is good to have. Compared to Abeille'25, this paper gives more explicit characterization of the smallest eigenvalues of the design matrices, and consequently a more precise regret bound that interpolates with α\alpha. This paper also sharpens the LinUCB regret by a factor of log⁡T\sqrt{\log T} for those good action sets.

Critical weaknesses

With the Strength being said, I won't be excited about this result, also given Abeille'25. From that paper, the community can already infer that for these good action sets, a smaller amount of exploration already suffices (because TS no longer needs inflation). So the main contribution of this paper is going to LinUCB and gives a more precise bound on the smallest eigenvalues & regret bounds. These are not direct corollaries or straightforward enough from Abeille'25, but in my view they are relatively incremental.

It would also be great if the authors can better justify whether these assumptions are really minimal. Authors indeed claim "we construct a counterexample confirming that assumptions on the action set are necessary". Nevertheless: (1) Yes, a counterexample indeed shows that some assumptions are necessary. (2) But it by no means justifies strongly convex + smooth assumptions are necessary. So I don't feel these assumptions are really well-justified after this paper, and don't feel there's substantial contribution to the lower bound side either.

Questions for authors

Please consider justifying why the results in this paper is much more ground-breaking than that of Abeille'25, given that the community is already aware that "with good action sets, exploration can be smaller."

3 comments

We thank the reviewer for the time dedicated to this careful review, and for noting that the paper is good to have. We address the concerns in turn.


  1. Relation to Abeille et al. (2025). Our result is of interest in itself: it changes how LinUCB, a foundational algorithm, is analysed. Its analyses in the literature rest on valid confidence sets and the optimism they imply. On curved action sets, we show that neither is needed: the regret is controlled through the spectral growth of the design, with neither the optimism inequality nor the elliptical potential lemma. At the standard radius, this improves the classical LinUCB bound by a factor of log⁡T\sqrt{\log T}.

    Abeille et al. showed that, for smooth action sets, structured randomised exploration (un-inflated TS) achieves the appropriate exploration rate in every direction and near-optimal regret (and as a side effect, without optimism). We ask whether randomness is the key to non-optimistic exploration, or whether a deterministic exploration scheme (UCB-based) can similarly dispense with optimism, and answer the latter in the affirmative. We do so for a key algorithm whose classical, optimism-based proof is widely accepted and not regarded as flawed. That proof offers nothing to build on once the confidence sets are invalid, so a completely new strategy was needed: our analysis requires fundamentally different tools (detailed below), and cannot be deduced from the TS results either. TS explores more uniformly, potentially leading to over-exploration. Consistent with this intuition, optimally tuned α\alpha-LinUCB improves on the TS regret bound by a factor of log⁡T\sqrt{\log T}.

    Together, these results justify using exploration sets smaller than confidence sets, a widely shared practice that had long lacked theoretical support. Moreover, we believe that our contribution offers an unexpected view of UCB, whose reliance on valid confidence sets had not been challenged in theory. Finally, while an expert reader could draw some intuition from the TS analysis of Abeille et al., this does not diminish the contribution of this work, which establishes the result formally; to the best of our knowledge, both the finding and its derivation are novel.

 

  1. New proof techniques. Their argument is intrinsically randomised: its key step (Lemma 5.1) lower-bounds Et−1[XtXt⊤]\mathbb E_{t-1}[X_tX_t^\top] through the variance of the perturbations, which are required to be rotationally invariant so as to cover all plausible directions. For a deterministic rule this matrix is the rank-one xtxt⊤x_tx_t^\top, and the argument yields nothing. We prove instead a pathwise statement: at every round, the optimistic argmax itself injects energy into the least-explored direction, and a capped potential converts this energy into spectral growth. This rests on three new tools.

    • A deterministic exploration engine (Lemma D.7). At every round, with neither randomness nor optimism, strong convexity of JX2J_{\mathcal X}^2 forces the argmax over Ct(α)\mathcal C_t(\alpha) to satisfy ∥xt∥Vt−1≳αωt\Vert x_t\Vert_{V_t^{-1}}\gtrsim\alpha\omega_t.
    • A logarithmically capped potential (Definition 5.1). It is a difference of two regularised log-determinants whose capacity is bounded independently of the horizon. Unlike the log-determinant potential, it stops crediting well-explored directions.
    • A leakage decomposition and doubling argument (Lemmas D.12–D.14). Most of the engine’s energy lands on the small eigenvalues, so the smallest eigenvalue doubles within a number of rounds quadratic in its current value, which gives t\sqrt t growth.

    To our knowledge, our spectral lower bound and regret guarantee for α\alpha-LinUCB with invalid confidence sets are the first of their kind for a UCB-type algorithm. We believe they complete the picture of confidence-set tuning beyond standard theoretical prescriptions, while introducing technical tools of independent interest.

  1. Necessity of the assumptions. We agree that our wording around the counterexample is ambiguous. We will make clear, from the introduction on, that we only claim sufficiency of our assumptions, not necessity. We nevertheless believe the example is of interest. Theorem 4.2 raises a question a reader will naturally have: should all analyses of LinUCB then be rethought? Proposition 6.1 answers in the negative: on a polytope, α\alpha-LinUCB has linear regret with constant probability for all small α\alpha, so the guarantee cannot hold on arbitrary action sets. We do not claim that strong convexity and smoothness are minimal. Their roles are distinct: strong convexity (mm) drives exploration (Lemma D.7, c0∝mc_0\propto m), and smoothness (MM) sharpens the spectral rate to t\sqrt t and converts parameter error into regret (Section E). Characterising the exact class of action sets is open, as it is for Thompson sampling (Abeille et al., Section 6).

We hope this clarifies the scope of the contribution and that the reviewer will reconsider the assessment in this light. We are happy to discuss further.

Thank you for the reply. I encourage the authors to incorporate them more explicitly in the revision. While I still don't quite feel the results are significant or the techniques are new enough to be of general interest, this paper is an interesting paper that could be accepted.

Comments on the paper

1 comment

Dear Reviewers wtyy and 8pio,

As we are approaching the end of the discussion period, could you read the authors' rebuttal and see if it has addressed your concerns and questions? Thanks again for your time!

AC

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.