PaperlayerView exact revision on arXiv

Source-linked AI summary

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

Xuan Li

arXiv:2609.10981v1cs.LG

TL;DR

The paper asks whether monotonicity is necessary for polynomial Bayesian regret of exact-posterior Thompson sampling on convex ridge losses. It replaces the failed monotone geometric dichotomy with cardinality and rounding arguments plus a selection-uniform transfer, obtaining ˜O(d9/2√n) regret for arbitrary convex links. Matching the monotone d5/2 dependence remains open.

  • Problem

    Whether exact-posterior Thompson sampling retains polynomial Bayesian regret for convex ridge losses when the link is convex but not monotone was unresolved.

  • Method

    The paper bounds uninformative configurations using Boolean rounding and develops a self-contained information-ratio-to-regret transfer uniform over fixed measurable minimiser selections.

  • Results

    ˜O(d9/2√n) Bayesian regret holds for every prior on the non-monotone convex ridge class and every fixed measurable minimiser selection.

  • Takeaways & Limitations

    Monotonicity is not necessary for polynomial-in-d Bayesian regret of exact-posterior TS on convex ridge losses.

  • Takeaways & Limitations

    The result is Bayesian rather than frequentist, concerns exact-posterior TS without addressing computation, and excludes history-dependent selection rules.

Abstract

from arXiv · show

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.

1 Introduction

The paper shows that convex ridge structure suffices for polynomial Bayesian regret of exact-posterior Thompson sampling even with arbitrary convex, non-monotone links. It replaces the monotone analysis with cardinality, rounding, and selection-uniformity arguments.

  • Related work: Existing work established monotone-ridge TS guarantees and other ridge-bandit results, but did not provide this Bayesian exact-TS guarantee for arbitrary convex non-monotone links.The paper distinguishes its algorithm-specific result from minimax guarantees for different algorithms.
  • Motivation: Dropping monotonicity permits links such as |s − s0|, whose minimisers can form a hyperplane section, making tie-breaking consequential.The ordering of minimisers that supports the monotone analysis is lost.
  • Main result: Exact-posterior TS achieves Bayesian regret ˜O(d9/2√n) for arbitrary convex, possibly non-monotone ridge links and fixed measurable minimiser selections.The result is qualitative: monotonicity is not necessary for polynomial-in-d regret.
  • Contributions: The monotone single-removal John-ellipsoid dichotomy fails for non-monotone links, so the paper proves an O(d^2)-scale cardinality bound for uninformative configurations instead.The new bound is at most 3(d+1)^2−(d+1)−1 elements.
  • Contributions: A Boolean rounding lemma drives the argument: a 0-1 matrix within 1/(4r) in max-norm of rank r has rank at most 2r−1.The construction also gives uninformative configurations of size d(d+1), making the bound tight up to constants.
  • Contributions: A self-contained information-ratio-to-regret transfer applies uniformly to every fixed measurable selection rule, while history-dependent tie-breaking remains outside the result.This addresses non-unique minimisers without assuming a consistent selection supplied by the prior analysis.

2 Setting and notation

The setting uses Bayesian bandit convex optimisation over convex ridge losses with Bernoulli feedback and exact-posterior Thompson sampling. A fixed measurable minimiser selection is part of the model, and the analysis uses pointwise prior means plus an information-ratio decomposition.

  • Function classes: The loss class consists of convex, [0,1]-valued, 1-Lipschitz ridge functions f(x)=ℓ(⟨x,θ⟩), with the non-monotone class extending the non-decreasing-link subclass.The domain K is a convex body in R^d with 0 in K and diameter D.
  • Measurability and tie-breaking: A measurable selection f↦x_f∈arg min_K f is fixed in advance, so all statements are uniform over fixed selections but exclude history-dependent tie-breaking.This convention is needed because convex ridge minimisers may be non-unique.
  • Prior means: The analysis permits arbitrary priors and uses the pointwise prior mean f̄=Eξ[f], which need not be a finite convex combination of class members.The measurable structure ensures point evaluations and selected minimisers are measurable.
  • Thompson sampling: A prior on losses is sampled once, and TS samples from the posterior each round before playing the selected minimiser of the sampled function.Observations are Bernoulli with conditional mean f(X_t).
  • Information-ratio machinery: The decomposition lemma converts within-piece information bounds for finite partitions into an information-ratio guarantee for the full class.Its proof averages over independent draws and applies Cauchy–Schwarz across pieces.

3 Main results

The paper proves polynomial Bayesian regret for exact-posterior Thompson sampling on non-monotone convex ridge losses, replacing the failed monotone geometric argument with a cardinality bound for uninformative configurations.

  • Exact-posterior TS has Bayesian regret O((d+1)^4√(dn) log(e + nd max{1, D})) for arbitrary convex 1-Lipschitz ridge links and fixed measurable minimiser selections.
  • Uninformative configurations contain at most 3(d+1)^2 − (d+1) − 1 < 4(d+1)^2 functions, yielding the core dimension-dependent bound.
  • The cardinality bound is tight up to constants because configurations of size d(d+1) exist, including for larger diameter-to-gap ratios by rescaling.
  • The monotone single-removal John-ellipsoid dichotomy fails for non-monotone links: twelve functions can preserve the same ellipsoid after any single removal.
  • The proof combines thin-band geometry, balanced and unbalanced row analyses, counting, and an information-ratio-to-regret transfer whose dimension exponent is tracked through five steps.

4 Structure of uninformative rows

Each uninformative ridge row forces the other selected minimisers into two narrow extreme projection bands, one on either side of its own minimiser.

  • A convex 1-Lipschitz ridge loss admits a global convex link representation whose minimum is attained at the projections of all selected minimisers.
  • Uninformativeness confines every other minimiser’s projection to a thin band near the minimum or maximum projection along the row’s ridge direction.
  • The two-band conclusion follows by comparing the loss to the convex comparison function and interpolating the link between its minimum and an extreme projection.

5 The cardinality bound

The cardinality proof separates balanced rows, controlled by quadratic low-rank evaluations, from unbalanced rows, controlled by Boolean rounding of an approximately low-rank band mask.

  • Hadamard-product rank control and trace–rank inequalities combine the affine evaluations with the band mask to complete the count.
  • Rounding lemma: The Boolean rounding lemma converts max-norm approximation by a rank-r matrix into an exact 0-1 rank bound when the tolerance is at most 1/(4r).
  • Balanced rows: For balanced rows, a quadratic evaluation matrix has rank at most h(h+1)/2 and small off-diagonal entries, limiting their number.
  • Unbalanced rows: For unbalanced rows, a near-band Boolean mask lies within 1/(8h) of an affine rank-h matrix, so integer rounding gives rank at most 2h − 1.

6 From the cardinality bound to the information ratio

The cardinality bound supplies the energy lower bounds needed by the blocking argument, which yields an information-ratio guarantee uniform over measurable minimiser selections.

  • Deleting informative-pair endpoints shows that configurations exceeding the cardinality threshold contain many informative ordered pairs and therefore substantial total energy.
  • The proof partitions functions by dyadic gap levels, blocks ordered tuples, and applies the cardinality bound to many low-spread blocks.
  • The resulting information ratio contains a pair with β ≤ 113,246,208(d+1)^8 m_α, and the argument is independent of the fixed measurable selection.
  • This replaces the monotone proof’s John-ellipsoid iteration because the non-monotone class lacks the corresponding dichotomy.

7 From the information ratio to regret under a fixed selection rule

The section develops a self-contained transfer from information-ratio bounds to Bayesian regret for exact Thompson sampling under any fixed measurable minimiser selection. It combines finite covers, continuity under function and action perturbations, and uniformity over randomised minimisers.

  • Uniformity over measurable selections extends the information-ratio result to randomised minimisers by representing kernels as mixtures of measurable selections.Both regret and information ratio are linear in the induced policy, enabling the mixture argument.
  • Continuity lemmas control information and regret under uniform function perturbations and coupled action perturbations, and flattening converts near-minimisers into exact minimisers.The same conditional-centring operator gives the required L2 contraction bounds.
  • A finite cover approximates each selected minimiser by a nearby exact minimiser of a ridge proxy, while preserving measurability, convexity, Lipschitzness, and near-minimality.The cover uses nets over K and the sphere, with at most (1 + 2D/ρ)^d(1 + 8D/ρ)^d labels.
  • Theorem 7.5 transfers a uniform information-ratio bound to exact Thompson sampling regret for every measurable selection, prior, horizon, and approximation scale.The transfer handles non-unique minimisers without requiring a consistent tie-breaking rule.
  • Choosing α = ρ = 1/n and combining the transfer with the information-ratio and covering bounds yields Bayesian regret of order (d + 1)^4√(dn) log(e + nd max{1, D}).The cover contributes log N_1/n ≤ 8dL, where L = log(e + nd max{1, D}).

8 The lower-bound family and the failure of the John dichotomy

The paper constructs large uninformative configurations and shows why the monotone John-ellipsoid removal argument fails for non-monotone links. The constructions motivate replacing geometric shrinkage with a cardinality argument.

  • The lower-bound family contains d(d + 1) uninformative losses on a truncated simplex, showing the cardinality bound is tight up to constants.The points x_ij are indexed by ordered pairs of distinct simplex vertices.
  • A twelve-point truncated tetrahedron demonstrates that removing any one point need not shrink the maximum-volume inscribed ellipsoid by a fixed factor.Both the original and one-point-removed bodies share the tetrahedron’s inscribed ball as their maximum-volume ellipsoid.
  • Non-monotone links can place other minimisers in two bands with arbitrarily imbalanced distances, so the single-removal, fixed-shrink-factor John dichotomy has no analogue.The mask argument avoids controlling this imbalance ratio.

9 Discussion

The discussion establishes the qualitative result that monotonicity is unnecessary for polynomial Bayesian regret, while identifying the dimension dependence and scope limitations that remain unresolved.

  • Theorem 3.1 resolves the qualitative question: exact-posterior Thompson sampling has polynomial Bayesian regret without monotonicity for arbitrary priors in the stated ridge class.
  • The resulting dimension exponent is 9/2 rather than the monotone case’s 5/2, and the paper does not claim that 9/2 is optimal.The information-ratio certificate is larger than the monotone analysis, while no non-monotone-specific lower bound is known.
  • The Θ(d^2) cardinality bound is tight, and the rounding threshold 1/(4r) forces η ≲ 1/d^2 in the present construction.Improving the exponent through a larger tolerance would require exploiting additional structure of the band-membership matrices.
  • The guarantee concerns Bayesian regret with an arbitrary prior and exact-posterior TS, not a frequentist guarantee for every fixed environment or computationally tractable implementation.
  • The selection rule must be fixed in advance, while history-dependent selection rules are outside the stated scope.

C Proofs for Section 7

The proofs implement the transfer theorem through measurable ridge representations, finite infimal-convolution covers, continuity estimates, and mutual-information accounting. The construction carefully avoids applying the ridge information-ratio hypothesis to a non-ridge conditional average.

  • A measurable direction map and jointly continuous profile representation provide a Borel ridge representation for every function in the class.The direction is selected by the Kuratowski–Ryll-Nardzewski theorem, and the profile uses an infimal-convolution construction.
  • The finite cover preserves ridge structure by averaging only functions sharing a common direction, while nearby selected minimisers become exact minimisers of proxy functions.The proxies remain convex, 1-Lipschitz, and valued in [0, 1].
  • The proof separates the finitely valued ridge proxy Gκ from the conditional average Hκ, applying the information-ratio hypothesis only to a flattened proxy and using continuity for Hκ.Hκ need not be a ridge function when it averages nearby functions with different directions.
  • Pinsker’s inequality bounds the Bernoulli information term by mutual information involving the finite label κ, whose cumulative contribution is controlled by the chain rule and Cauchy–Schwarz.
  • Substituting α = ρ = 1/n into the transfer calculation and bounding the cover size produces the stated regret rate.

D Proofs for Section 8

The construction gives d(d+1) uninformative convex ridge losses whose single-vertex removals leave the John ellipsoid unchanged, demonstrating the non-monotone obstruction and its tight cardinality scale.

  • d(d+1) uninformative losses are constructed from truncated-simplex vertices, with each loss uniquely minimized at its associated point.The functions are convex ridge functions, pairwise distinct, and their values remain within a controlled gap around the constant comparison function.
  • The losses exhibit two bands: d−1 nearby points at distance τ^2 and the remaining d^2 points at distance about one along each ridge direction.This near/far separation is the geometric feature underlying the uninformative configuration.
  • The construction remains uninformative after shrinking the gaps, while the diameter-to-gap ratio can be made arbitrarily large within the stated regime.Rescaling preserves the selected points and ridge directions, does not increase Lipschitz constants, and attains every larger ratio D/ε′.
  • Every single-vertex removal leaves the maximum-volume inscribed ellipsoid unchanged, so the John-ellipsoid shrinkage argument cannot separate these configurations.Both the full and vertex-removed bodies contain the same inscribed ball and have that ball as their maximum-volume ellipsoid.

E A limit of max-norm rounding

The paper proves that the 1/(4r) max-norm tolerance in its Boolean rounding lemma has the correct order for arbitrary 0-1 matrices, while structured band matrices may still permit improvement.

  • No uniform 1/√r rounding tolerance can guarantee rank at most 2r−1 for arbitrary 0-1 matrices.The distance 2/(r+1) is eventually at most a/√r for every fixed a>0, contradicting such an implication for infinitely many r.
  • The result limits arbitrary 0-1 matrices only; the paper leaves open whether the two-band structure of its membership matrices allows a larger tolerance.The relevant band matrices include additional structure, including an extremely thin band.
Loading 2609.10981v1…