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

Bakhtiari, Lattimore and Szepesv'ari (COLT 2025) proved that Thompson sampling (TS) has Bayesian regret tilde O(d5/2√ n) for bandit convex optimisation with convex monotone ridge losses f(x)=ℓ(ipxθ), 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 Obig((d+1)4√dn,log(e+ndmax1,diam K)big)=tilde O(d9/2√ 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(d2) 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 d5/2 dependence of the monotone case can be retained remains open.