- Rating
- 2(+1)
- Confidence
- 2
- Informativeness
- 1
- Presentation
- 1
- Soundness
- 1
Read review
Paper summary
This paper analyses the Thompson sampling for a single-index bandit with convex but non-monotonic functions. Building on the open question raised by Bakhtiari et al. (2025) about whether monotonicity is necessary, this paper claims that monotonicity is not necessary and proves an optimal bound except for the order in terms .
Critical strengths
The contribution is significant in terms of answering an open question in the literature.
Critical weaknesses
This paper is very difficult to follow. Most of the results are listed only as lemmas, theorems, and propositions, without explaining the background, intuition, interpretations, or insights. I do not understand the implications of extremely large constants in lines 174, 192, and 197. I did not check the proof line by line; however, I do not intuitively understand how they explode so much.
This paper can benefit from a significant rewrite. The presentation could be better.
Many jargons and symbols are used before they are defined.
Questions for authors
Among the listed contributions, I can make sense of the first one, which I feel is the most important. The rest of the contributions seem like just analytical tools you use to establish the regret bound, right? If my understanding is correct, are these analytical tools novel contributions or already existing in the literature?
Is there any practical motivation to analyse non-monotonic bandits? Are there any other algorithms (e.g., UCB-type) that handle this non-monotonic condition?
I might reconsider my score based on the answers by the authors.
3 comments
Practical motivation for non-monotone links.
Target-tracking losses such as and penalise both undershooting and overshooting a target. If that target is inside the projection interval, these links are convex and non-monotone. On a compact action set they can be rescaled to meet our boundedness and Lipschitz assumptions. Monotone ridge losses admit a boundary minimiser, whereas these target losses can have an interior optimal index. Our contribution is a statistical foundation for exact posterior sampling in this setting; we make no computational or empirical-performance claim.
Other algorithms, including UCB-type methods.
Yes. Dey, Bhore and Ghosh (2026) [DBG26], Optimal Regret for Single Index Bandits, analyse ZoomSIB-UCB for unknown, possibly non-monotone links in a contextual model, with frequentist regret for fixed dimension under their assumptions. Kang et al. (2026) [Kang26] give Stein-estimator-based methods for contextual single-index models. Lattimore (2021) [Lattimore21] proves a nearly minimax bound in a related adversarial ridge model with normalised domain and observed loss values. These are different models or algorithms; they do not establish the guarantee for exact TS with Bernoulli observations that we study. Section 1 and Appendix F now make this distinction explicit.
References
[DBG26] Devdan Dey, Sujoy Bhore, and Avishek Ghosh. Optimal Regret for Single Index Bandits. arXiv preprint 2605.09454, version 3, 2026.
[Kang26] Yue Kang, Mingshuo Liu, Bongsoo Yi, Jing Lyu, Zhi Zhang, Doudou Zhou, and Yao Li. Single Index Bandits: Generalized Linear Contextual Bandits with Unknown Reward Functions. International Conference on Learning Representations, 2026.
[Lattimore21] Tor Lattimore. Minimax Regret for Bandit Convex Optimisation of Ridge Functions. arXiv preprint 2106.00444, version 2, 2021.
Thank you for the revisions. I raise my score by 1. However I am still leaning towards rejection.
We thank you for your careful reading and your suggestions on the presentation, contribution hierarchy, and practical motivation. Below, we clarify the role of each result and respond to your questions about the constants and related algorithms.
Main contribution and the role of the other results.
Your reading of the hierarchy is correct: the main result is the regret guarantee for exact TS without monotonicity. The geometric and linear-algebraic results are the tools that establish it. The revised introduction now distinguishes them explicitly:
The revised rate is O(d7/2n), improving the submitted O(d9/2n). The optimal dimension dependence remains open.
Why the proof and its constants grow.
The roadmap after the main results now gives the dependency chain and the source of each dimension factor: two-band geometry gives a configuration bound O(d2); blocking produces tuples of size O(d3); the decomposition lemma squares that size, giving a coefficient O(d6mα); taking the square root in the regret transfer and including the cover entropy gives d3d=d7/2.
The constants are explicit so that each step can be checked; their numerical values have not been optimised. The main text now keeps their parameter structure: the regret prefactor is 384cdωd, with 384=6⋅4⋅16, and the certificate lower bound uses α≤ε/4. The expanded constants for the alternative c=96(d+1) choice and the small-α threshold are retained in Appendices B and D. Proposition 3.5 now foregrounds the parameter regime used by the main theorem. This does not make the finite-horizon guarantee numerically sharp: it becomes smaller than the trivial regret bound only at horizons of order d7 times large constants and logarithmic factors. The paragraph after Theorem 3.1 states this limitation.
Changes that make the argument easier to follow.
The abstract now describes the ellipsoid obstruction and the matrix argument before using compressed technical labels. Section 1 introduces the decision problem, the link function and the motivation before listing contributions, and explains an uninformative configuration at its first use. Section 2 explains the information-ratio certificate, distinguishing posterior variance from the finite-label mutual information used in the transfer. Sections 3–5 explain what is being counted, why the two bands arise and what the mask removes before giving the formal statements. We also corrected a misleading simplification: an “uninformative” configuration has small off-diagonal deviations at the specified tolerance; it does not provide literally zero information.
References
[RVR16] Daniel Russo and Benjamin Van Roy. An Information-Theoretic Analysis of Thompson Sampling. Journal of Machine Learning Research, 17(68):1–30, 2016.
[BLS25] Alireza Bakhtiari, Tor Lattimore, and Csaba Szepesvári. Thompson Sampling for Bandit Convex Optimisation. In Proceedings of Thirty Eighth Conference on Learning Theory, Proceedings of Machine Learning Research, volume 291, pp. 231–263. PMLR, 2025.
[Alon09] Noga Alon. Perturbed Identity Matrices Have High Rank: Proof and Applications. Combinatorics, Probability and Computing, 18(1–2):3–15, 2009.