Beyond Monotonicity: Thompson Sampling for Convex Ridge Bandits with Polynomial Bayesian Regret

Thompson sampling (TS) is a canonical algorithm for Bayesian bandit optimization, yet its theoretical guarantees in nonlinear bandits remain confined to strongly structured settings. In particular, recent work established polynomial Bayesian regret for convex ridge bandits under a monotonicity assumption on the unknown convex link function and posed the open question of whether monotonicity is necessary. We answer this question negatively. We study Bayesian bandit convex optimization with convex ridge losses of the form \(f(x)=\ell(\langle x,\theta\rangle)\), where the link \(\ell\) is convex but not necessarily monotone. For arbitrary priors over bounded, Lipschitz convex ridge losses, any fixed measurable selection of minimizers, and exact-posterior Thompson sampling, we prove a polynomial-in-dimension Bayesian regret bound of \(O(d^9/2n)\). The single-removal John-ellipsoid argument underlying the monotone analysis does not extend to the non-monotone setting. To overcome this obstacle, we develop a cardinality-based analysis of uninformative configurations that combines two-band geometry with a Boolean matrix-rounding argument, yielding an \(O(d^2)\) cardinality bound that is tight up to constants in the large-diameter-to-gap regime. Beyond resolving the open question, our results show that convex ridge structure alone is sufficient for exact-posterior Thompson sampling to achieve polynomial Bayesian regret without link monotonicity. This extends the class of nonlinear bandit problems for which Thompson sampling admits a provable Bayesian regret guarantee, while leaving the optimal dependence on dimension open.