Thompson Sampling for Non-Monotone Convex Ridge Bandits: Monotonicity Is Not Needed for Polynomial Regret — Paper

Abstract

Bakhtiari, Lattimore and Szepesv\'ari (COLT 2025) proved that Thompson sampling (TS) has Bayesian regret $\tilde O(d^{5/2}\sqrt n)$ for bandit convex optimisation with convex \emph{monotone} ridge losses $f(x)=\ell(\ip{x}{\theta})$, and asked whether monotonicity of the link is necessary. We give a qualitative negative answer. For every prior on $[0,1]$-valued, $1$-Lipschitz convex ridge losses with an arbitrary convex, possibly non-monotone, link, and for any fixed measurable selection of minimisers, exact-posterior TS has Bayesian regret $O\big((d+1)^4\sqrt{dn}\,\log(e+nd\max\{1,\diam K\})\big)=\tilde O(d^{9/2}\sqrt n)$. The monotone proof relies on a single-removal John-ellipsoid dichotomy; we show by an explicit twelve-point configuration that this dichotomy fails for non-monotone links, and replace it by an $O(d^2)$ cardinality bound for ``uninformative'' configurations. The bound uses a Boolean rounding argument: a $0$-$1$ matrix within $1/(4r)$ in max-norm of a rank-$r$ matrix has rank at most $2r-1$. We construct $d(d+1)$ uninformative losses, showing that the cardinality bound is tight up to constants in the large-diameter-to-gap regime, and give a self-contained information-ratio-to-regret transfer that is uniform over fixed measurable selections. Whether the $d^{5/2}$ dependence of the monotone case can be retained remains open.

Authors 1

Xuan Li

Specification

Official page: arxiv.org/abs/2609.10981
Source:arXiv (Atom API + RSS)T1observed 46 min agohigh
Arxiv announce type: new
Source:arXiv (Atom API + RSS)T1observed 46 min agohigh
arXiv id: 2609.10981
Source:arXiv (Atom API + RSS)T1observed 46 min agohigh
Categories: cs.LG
Source:arXiv (Atom API + RSS)T1observed 46 min agohigh
PDF: arxiv.org/pdf/2609.10981
Source:arXiv (Atom API + RSS)T1observed 46 min agohigh
Primary category: cs.LG
Source:arXiv (Atom API + RSS)T1observed 46 min agohigh
Published: 11 Sept 2026
Source:arXiv (Atom API + RSS)T1observed 46 min agohigh

Each value shows its source, tier and observation time. Conflicting claims are kept side by side and flagged — never averaged. How AI Atlas records facts →

Provenance

Attributed facts

9

Source tiers

T19

Freshest observation

46 min ago

Conflicts

None

No models linked to this paper yet.

Authors: Xuan Li

As of

Rewind the record: see this entity's attributes exactly as AI Atlas knew them on a given day.

Claim history · Primary category

1 claims · 1 propertiesShow all properties

Primary categoryprimary_category1

Claim history for Primary category
Value	Valid from → to	Status	Source	Confidence	Extractor
cs.LG	11 Sept 2026 21:02 UTC → current	current	arXiv (Atom API + RSS)T1	high	deterministic

Claims are temporal and append-only: a new observation closes the previous claim (valid_to) instead of overwriting it. Conflicting claims from different sources are kept side by side and flagged — never averaged. Methodology →

11 Sept 2026
New paperPaperThompson Sampling for Non-Monotone Convex Ridge Bandits: Monotonicity Is Not Needed for Polynomial Regret
New paper: Thompson Sampling for Non-Monotone Convex Ridge Bandits: Monotonicity Is Not Needed for Polynomial Regret
arxiv
rss.arxiv.org

Full timeline →

Source documents
Source	Document	Type	Tier	Last observed	Snapshots
arXiv (Atom API + RSS)	rss.arxiv.org/rss/cs.LG	feed	T1· Official	46 min ago	1

Tier 1 = official/primary, 2 = quality secondary, 3 = community, 4 = unverified. Every snapshot is archived; see all sources and the methodology.