- 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
-
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?
-
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?
-
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
Thank you for your reply; my issue has essentially been resolved. I will continue to maintain my positive score.
We thank the reviewer for the positive assessment and the precise questions, which we answer in order.
Assumptions compared with standard linear bandits. (A1) and the boundedness conditions (∥θ⋆∥2≤S⋆, X⊆B2d(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(α), optimism is lost and some geometric condition is unavoidable: on a polytope, α-LinUCB has linear regret for all small α (Proposition 6.1). (A2) is the condition under which Abeille et al. (2025) analyse Thompson sampling without inflation. It covers balls, ellipsoids and C2 bodies with curvature bounded above and below, and excludes polytopes and finite arm sets. Two remarks:
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) 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, with a constant that depends on the geometry only through m, M, J⋆ and the distance from the origin to the boundary of X. Unlike the bound of Banerjee et al., which concerns the expected design and presupposes O(T) regret, ours holds along the trajectory.
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.
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.