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

arXiv: https://arxiv.org/abs/2609.10981 · HTML: https://mlsanity.com/paper/2609.10981/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 7 of its 17 references that are in the map.
- First posted on arXiv 10 Sep 2026.

## Builds on (most cited first, 7 of 7)

- [An Information-Theoretic Analysis of Thompson Sampling](https://mlsanity.com/paper/1403.5341/) (2014)
- [Improved Regret for Zeroth-Order Adversarial Bandit Convex Optimisation](https://mlsanity.com/paper/2006.00475/) (2020)
- [Statistical Complexity and Optimal Algorithms for Non-linear Ridge Bandits](https://mlsanity.com/paper/2302.06025/) (2023)
- [Single Index Bandits: Generalized Linear Contextual Bandits with Unknown Reward Functions](https://mlsanity.com/paper/2506.12751/) (2025)
- [Minimax Regret for Bandit Convex Optimisation of Ridge Functions](https://mlsanity.com/paper/2106.00444/) (2021)
- [Interactive Learning of Single-Index Models via Stochastic Gradient Descent](https://mlsanity.com/paper/2602.17876/) (2026)
- [The Price of Hidden Curvature: Improved Lower Bounds for Bandit Convex Optimization](https://mlsanity.com/paper/2607.18652/) (2026)

## Abstract (arXiv)

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.