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

• URL: http://arxiv.org/abs/2609.10981v1
• Date: Thu, 10 Sep 2026 01:58:03 GMT
• Title: Thompson Sampling for Non-Monotone Convex Ridge Bandits: Monotonicity Is Not Needed for Polynomial Regret
• Abstract summary: We prove that Thompson sampling (TS) has Bayesian regret $tilde O(d5/2sqrt n)$ for bandit convex optimisation with convex emphmonotone ridge losses.
• Score: 6.657272312990604
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• 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.

Related papers

• Exact Recovery Thresholds for Weighted Data Selection in Vector-Valued Linear Regression [0.0]
  We prove that the minimal budget of weighted examples that recovers the full-data loss on every finite dataset is exactly $n*(d,m)=(m+1)d$.<n>As a we correct an erroneous claim circulating in a recent unrefereed preprint, exhibiting an explicit dataset with $m=2$ on which no weighted selection of $2d$ points recovers the optimal loss.
  arXiv  Detail & Related papers  (2026-08-31T05:04:49Z)
• Sharp Minimax Regret for Infinite-Memory Logistic Prediction [55.29259818039367]
  Lag $j$ can affect prediction by scale $r_j$ and enters only $n_T,j=T-j+1$ prediction rounds.<n>For every summable envelope, a localized mixture proves $cR_T(r)leq C_T(r)$.<n>For exponential and envelopes, under the stated finite-sample condition, a Toeplitz-design converse proves $cR_T(r)geq c_T(r)$.
  arXiv  Detail & Related papers  (2026-08-27T01:31:46Z)
• The sharp SAT/UNSAT phase transition in random ellipsoid fitting [5.7652356955571085]
  An emphellipsoid fit is a matrix $S succeq 0$ such that $x_itop S x_i =d$ for every $i$.<n>We prove Saunderson, Parrilo and Willsky's conjecture that, as $n,d to infty$, this semidefinite feasibility problem undergoes a sharp transition at $n sim d2/4$.
  arXiv  Detail & Related papers  (2026-08-10T19:55:11Z)
• The Condition-Number Barrier in Sparse Least Squares [77.64108812086542]
  In [AS21], Axiotis and Sviridenko conjectured that the linear dependence on the restricted condition number in convex optimization cannot be improved by a sparse-time algorithm.<n>We establish their conjectured lower bound for least-squares objectives, conditional on the randomized exact-volume Small-Set Expansion Hypothesis.
  arXiv  Detail & Related papers  (2026-08-03T17:57:01Z)
• The Price of Hidden Curvature: An $\widetildeΩ (d^{5/4} \sqrt{T})$ Lower Bound for Bandit Convex Optimization [4.774251262663345]
  We show that a $widetilde(d5/4sqrt T)$ lower bound on the minimax expected regret of bandit convex optimization of $1$-Lipschitz functions grows faster than $dsqrtT$.<n>This presents the first nontrivial regret lower bound that grows faster than $dsqrtT$ for this problem.
  arXiv  Detail & Related papers  (2026-07-21T02:44:33Z)
• On the Power of Adaptivity for $\varepsilon$-Best Arm Identification in Linear Bandits [8.86974002494041]
  We study the minimax sample complexity of $varepsilon$-best arm identification in linear bandits.<n>The goal is to output an arm $widehatxinmathcalX$ such that $langle ge max_xinmathcalX langle x,rangle ge max_xinmathcalX langle x,rangle ge max_xinmathcalX langle x
  arXiv  Detail & Related papers  (2026-05-15T06:35:31Z)
• Trade-off Functions for DP-SGD with Subsampling based on Random Shuffling: Tight Upper and Lower Bounds [7.787109481104569]
  We derive a tight analysis of the trade-off function for Differentially Private Gradient Descent (DP-SGD) with subsampling based on random shuffling.<n>Our concrete bounds, derived via the Berry-Esseen theorem, are tight up to constant factors within the proof framework.
  arXiv  Detail & Related papers  (2026-05-07T13:35:43Z)
• Variance-Dependent Regret Lower Bounds for Contextual Bandits [65.93854043353328]
  Variance-dependent regret bounds for linear contextual bandits, which improve upon the classical $tildeO(dsqrtK)$ regret bound to $tildeO(dsqrtsum_k=1Ksigma_k2)$.
  arXiv  Detail & Related papers  (2025-03-15T07:09:36Z)
• Low-rank Matrix Bandits with Heavy-tailed Rewards [55.03293214439741]
  We study the problem of underlinelow-rank matrix bandit with underlineheavy-underlinetailed underlinerewards (LowHTR) By utilizing the truncation on observed payoffs and the dynamic exploration, we propose a novel algorithm called LOTUS.
  arXiv  Detail & Related papers  (2024-04-26T21:54:31Z)
• Variance-Aware Sparse Linear Bandits [64.70681598741417]
  Worst-case minimax regret for sparse linear bandits is $widetildeThetaleft(sqrtdTright)$. In the benign setting where there is no noise and the action set is the unit sphere, one can use divide-and-conquer to achieve an $widetildemathcal O(1)$ regret. We develop a general framework that converts any variance-aware linear bandit algorithm to a variance-aware algorithm for sparse linear bandits.
  arXiv  Detail & Related papers  (2022-05-26T15:55:44Z)
• The planted matching problem: Sharp threshold and infinite-order phase transition [25.41713098167692]
  We study the problem of reconstructing a perfect matching $M*$ hidden in a randomly weighted $ntimes n$ bipartite graph. We show that if $sqrtd B(mathcalP,mathcalQ) ge 1+epsilon$ for an arbitrarily small constant $epsilon>0$, the reconstruction error for any estimator is shown to be bounded away from $0$.
  arXiv  Detail & Related papers  (2021-03-17T00:59:33Z)
• Linear Bandits on Uniformly Convex Sets [88.3673525964507]
  Linear bandit algorithms yield $tildemathcalO(nsqrtT)$ pseudo-regret bounds on compact convex action sets. Two types of structural assumptions lead to better pseudo-regret bounds.
  arXiv  Detail & Related papers  (2021-03-10T07:33:03Z)
• Variance-Aware Confidence Set: Variance-Dependent Bound for Linear Bandits and Horizon-Free Bound for Linear Mixture MDP [76.94328400919836]
  We show how to construct variance-aware confidence sets for linear bandits and linear mixture Decision Process (MDP) For linear bandits, we obtain an $widetildeO(mathrmpoly(d)sqrt1 + sum_i=1Ksigma_i2) regret bound, where $d is the feature dimension. For linear mixture MDP, we obtain an $widetildeO(mathrmpoly(d)sqrtK)$ regret bound, where
  arXiv  Detail & Related papers  (2021-01-29T18:57:52Z)
• Tight Regret Bounds for Noisy Optimization of a Brownian Motion [118.65407541895851]
  We consider the problem of Bayesian optimization of a one-dimensional Brownian motion in which the $T$ adaptively chosen observations are corrupted by Gaussian noise. We show that as the smallest possible expected cumulative regret and the smallest possible expected simple regret scale as $Omega(sigmasqrtT cdot log T)$.
  arXiv  Detail & Related papers  (2020-01-25T14:44:53Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.