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

arXiv:2609.10981v1 Announce Type: new Abstract: Bakhtiari, Lattimore and Szepesvari (COLT 2025) proved that Thompson sampling (TS) has Bayesian regret ilde O(d^{5/2}sqrt n) for bandit convex optimisation with convex monotone ridge losses f(x)=ell(ip{x}{heta}), 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 Oig((d+1)^4sqrt{dn},log(e+ndmax{1,iam K})ig)=ilde 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.

Related

• Prior Diffusiveness and Regret in the Linear-Gaussian Bandit
• Generalized Regret Analysis of Thompson Sampling using Fractional Posteriors
• The Price of Hidden Curvature: An widetilde{Omega} (d^{5/4} sqrt{T}) Lower Bound for Bandit Convex Optimization
• Variance-sensitive Thompson sampling for generalised linear bandits, revisited
• When and why randomised exploration works (in linear bandits)

Source: arXiv cs.LG | 2026-09-11