Thompson Sampling for Non-Monotone Convex Ridge Bandits: Monotonicity Is Not Needed for Polynomial Regret
cs.LG
Quick verdict
Answers a COLT 2025 open question: TS gets Õ(d^{9/2}√n) Bayesian regret on non-monotone convex ridge bandits; rigorous; d² gap to monotone case remains.
Summary
This paper resolves an open question of Bakhtiari, Lattimore and Szepesvári (COLT 2025), who proved that Thompson sampling attains Õ(d^{5/2}√n) Bayesian regret for bandit convex optimisation with convex monotone ridge losses and asked whether monotonicity of the link is necessary. The author answers qualitatively in the negative: for every prior on [0,1]-valued, 1-Lipschitz convex ridge losses with an arbitrary convex, possibly non-monotone link, and any fixed measurable tie-breaking of minimisers, exact-posterior Thompson sampling achieves Bayesian regret O((d+1)⁴√(dn) log(e+nd·max{1,diam K})) = Õ(d^{9/2}√n). The monotone proof rested on a single-removal John-ellipsoid dichotomy; a twelve-point configuration in d=3 (Proposition 3.6) shows that dichotomy fails for non-monotone links. In its place, a Boolean rounding lemma (a 0-1 matrix within 1/(4r) in max-norm of a rank-r matrix has rank at most 2r−1) yields an O(d²) cardinality bound for uninformative configurations (Theorem 3.3), tight up to constants via a d(d+1)-loss truncated-simplex construction in the large diameter-to-gap regime. Limitations: the exponent gap versus the monotone case remains open, explicit constants are enormous, history-dependent tie-breaking is excluded, and no lower bound exists for the non-monotone class.
Review complete
Assessment at a glance
4
risk flags identified
● high 0
● medium 1
● low 3
5 strengths · 5 weaknesses · 5 author questions
AI text signal = Binoculars zero-shot detector score over 20 sampled passages (Fast-DetectGPT co-reported) — absence does not prove human authorship, and a flag does not imply misconduct.
Levels reflect verification complexity — not a quality score. Evolve never rates your paper.
Key claims under review
- Exact-posterior Thompson sampling attains Bayesian regret Õ(d^{9/2}√n) on every class of [0,1]-valued 1-Lipschitz convex ridge losses with arbitrary convex, possibly non-monotone link, for any fixed measurable tie-breaking (Theorem 3.1).
- Every uninformative configuration has at most 3(d+1)²−(d+1)−1 elements, and d(d+1) is achievable, so the bound is tight up to constants in the large diameter-to-gap regime (Theorem 3.3, Proposition 3.5).
- The single-removal John-ellipsoid dichotomy underlying the monotone proof of Bakhtiari et al. fails for non-monotone links — a twelve-point configuration in d=3 refutes it for every shrink factor γ<1 (Proposition 3.6).
- A 0-1 matrix within 1/(4r) in max-norm of a rank-r matrix has rank at most 2r−1, and no uniform tolerance of order 1/√r exists for arbitrary 0-1 matrices (Lemma 5.3, Proposition E.1).
Strengths
Resolves an explicit open question
Directly answers Bakhtiari-Lattimore-Szepesvári (COLT 2025), who wrote 'Our best guess is that it is not'; Theorem 3.1 confirms their conjecture qualitatively for exact-posterior TS with Õ(d^{9/2}√n) Bayesian regret on Fblr.
New proof technique replacing John ellipsoids
Proposition 3.6 gives a twelve-point truncated-tetrahedron configuration in d=3 showing the single-removal John-ellipsoid dichotomy (BLS Lemma 8) has no non-monotone analogue; Theorem 3.3 instead rests on Lemma 5.3 (0-1 matrix within 1/(4r) max-norm of rank r implies rank ≤ 2r−1), with Proposition E.1 (Sylvester-Hadamard) showing order-1/√r tolerances are impossible uniformly.
Two-sided tightness
Careful measure-theoretic hygiene
Honest cost and scope accounting
Weaknesses
Large quantitative gap
Tightness only in an extreme regime
Rounding tolerance pins the constants
Selection-rule restriction
Not yet peer-reviewed
Full Review Report
$1.99 · one-timeUnlock the complete preliminary analysis Evolve produced for this paper.
Report preview
Scope & Claims
The paper answers an explicit open question posed by Bakhtiari, Lattimore and Szepesvári (COLT 2025, quoted verbatim in Section 1): is monotonicity of the link needed for Thompson sampling (TS) to enjoy polynomial Bayesian regret on convex ridge bandits? The main result (Theorem 3.1) is that for every prior on Fblr — [0,1]-valued, 1-Lipschitz convex ridge functions on a convex body K ⊂ R^d with arbitrary convex, possibly non-monotone link — and every fixed measurable selection of minimisers, exact-posterior TS has Bayesian regret at most 7 + 73,728√3·(d+1)⁴·d^{1/2}·√n·log(e + nd·max{1, diam K}) = Õ(d^{9/2}√n). The claim is deliberately algorithm-specific: Lattimore's minimax O(d√n log(nD)) for adversarial ridge bandits does not certify TS itself, which BLS showed can fail on general convex losses. The paper is precise about what it does not claim: the 9/2-vs-5/2 exponent gap, computation, and history-dependent tie-breaking are all explicitly out of scope (Section 9, three scope remarks).
The remaining sections cover Methodology Assessment, Statistical Evidence, Results & Reproducibility, Limitations & Risks, and Verdict & Recommendations.
- All 5 strengths & 5 weaknesses, analyzed in detail
- 4 risk flags with severity, section & reviewer questions
- Methods & statistical evidence assessment
- 5 questions a peer reviewer would ask
- Full six-dimension evaluation report & recommendations
One-time purchase · this paper only
One-time purchase, this paper only. AI-generated preliminary analysis — not peer review.
Frequently asked questions
Is monotonicity necessary for Thompson sampling to work on convex ridge bandits?
No. This paper proves that exact-posterior Thompson sampling achieves polynomial Bayesian regret — specifically Õ(d^{9/2}√n) — for all convex 1-Lipschitz ridge losses on a convex body in R^d, even when the outer link is convex but non-monotone (e.g., V-shaped losses like ℓ(s)=|s−s₀|), answering an open question from Bakhtiari, Lattimore and Szepesvári (COLT 2025).
What is the cost of dropping monotonicity?
The regret exponent degrades from d^{5/2} (monotone case) to d^{9/2}, because the monotone proof's John-ellipsoid dichotomy fails (explicit twelve-point counterexample in d=3) and is replaced by an O(d²) cardinality bound proved via a matrix rounding lemma. Whether d^{5/2} can be recovered is open, and no lower bound specific to non-monotone links is known.
Does the paper include code or experiments?
No. It is a purely theoretical contribution: all results are mathematical theorems with full proofs across five appendices (A-E); no code, simulations, or datasets are involved.
What tie-breaking does Thompson sampling need when minimisers are not unique?
Any measurable selection rule fixed in advance works — the regret bound holds uniformly over all such rules. However, rules that change with the observed history are not covered by the analysis.
About this review
This is an AI-generated preliminary review by Evolve.Pub, produced from the openly available text of the paper. It is not peer review and does not represent the authors' views. The canonical record of the paper is at the publisher link above.
- PDF extraction flattened display mathematics (fraction bars lost in a few inequalities, e.g., the balanced-row bound in Section 5.2 reads as 4h²(h+1)/(7h)−1 but reconstructs to the correct 4h²(h+1)/(7h−1)−1); I verified the reconstructed versions hold, and no text is missing.
- The extraction is complete through Appendix E (ends with the full statement and proof of Proposition E.1 and page number 19); no truncation was detected at the far end of the text.
Go deeper on this paper
Wrote a paper? Stress-test it before reviewers do.
Upload your manuscript for the same structured scrutiny — reasoning, statistics, evidence, figures, and reproducibility.