Thompson sampling achieves polynomial regret without monotone link assumptions
Thompson Sampling for Non-Monotone Convex Ridge Bandits: Monotonicity Is Not Needed for Polynomial Regret
Machine Learning
Summary
This paper studies how well a method called Thompson sampling works in learning to make good decisions when outcomes depend on unknown convex relationships. Previously, good performance guarantees required the relationship to be monotone (always increasing or decreasing). The authors show that this monotone assumption is not needed, extending the method's effectiveness to more general convex relationships. They prove that Thompson sampling still learns efficiently with polynomial regret, meaning it doesn't lose too much potential reward over time, even when monotonicity is not present.
What this means in practice
- •For online advertising teams: Improve adaptive ad placement algorithms when user response models are convex but not necessarily monotone, ensuring learning remains efficient over time.
- •For automated pricing engineers: Design pricing strategies using convex customer demand models without assumptions of monotone demand changes, while maintaining performance guarantees.
A theory result. No direct application yet.
Authors
Xuan Li
Abstract
Bakhtiari, Lattimore and Szepesvári (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}θ)$, 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.