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

# Thompson Sampling for Non-Monotone Convex Ridge Bandits:Monotonicity Is Not Needed for Polynomial Regret
Source: [https://arxiv.org/html/2609.10981](https://arxiv.org/html/2609.10981)
Xuan LiAffiliation:University of New South Wales, Sydney, Australia ·winny\.li@unsw\.edu\.auAffiliation:[ORCID: 0009\-0002\-0213\-6991](https://orcid.org/0009-0002-0213-6991)

September 10, 2026

###### Abstract

Bakhtiari, Lattimore and Szepesvári \(COLT 2025\) proved that Thompson sampling \(TS\) has Bayesian regretO~​\(d5/2​n\)\\tilde\{O\}\(d^\{5/2\}\\sqrt\{n\}\)for bandit convex optimisation with convex*monotone*ridge lossesf⁡\(x\)=ℓ⁡\(⟨x,θ⟩\)f\(x\)=\\ell\(\\langle x,\\theta\\rangle\), and asked whether monotonicity of the link is necessary\. We give a qualitative negative answer\. For every prior on\[0,1\]\[0,1\]\-valued,11\-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 regretO⁡\(\(d\+1\)4​d​n​log⁡\(e\+n​d​max⁡\{1,diam​K\}\)\)=O~​\(d9/2​n\)O\\big\(\(d\+1\)^\{4\}\\sqrt\{dn\}\\,\\log\(e\+nd\\max\\\{1,\\mathrm\{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 anO⁡\(d2\)O\(d^\{2\}\)cardinality bound for “uninformative” configurations\. The bound uses a Boolean rounding argument: a00\-11matrix within1/\(4​r\)1/\(4r\)in max\-norm of a rank\-rrmatrix has rank at most2​r−12r\-1\. We constructd⁡\(d\+1\)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 thed5/2d^\{5/2\}dependence of the monotone case can be retained remains open\.

## 1Introduction

Bayesian bandit convex optimisation is the following game\. A convex bodyK⊂ℝdK\\subset\\mathbb\{R\}^\{d\}and a classℱ\\mathcal\{F\}of convex functionsK→\[0,1\]K\\to\[0,1\]are known, together with a priorξ\\xionℱ\\mathcal\{F\}\. The environment samplesf∼ξf\\sim\\xionce\. In each roundt=1,…,nt=1,\\dots,nthe learner playsXt∈KX\_\{t\}\\in Kand observesYt∈\{0,1\}Y\_\{t\}\\in\\\{0,1\\\}with𝔼\[Yt∣X1,Y1,…,Xt,f\]=f\(Xt\)\\mathbb\{E\}\[Y\_\{t\}\\mid X\_\{1\},Y\_\{1\},\\dots,X\_\{t\},f\]=f\(X\_\{t\}\)\. The Bayesian regret of a learner𝒜\\mathcal\{A\}is

BRegn​\(𝒜,ξ\)=𝔼⁡\[supx∈K∑t=1n\(f⁡\(Xt\)−f⁡\(x\)\)\]\.\\mathrm\{BReg\}\_\{n\}\(\\mathcal\{A\},\\xi\)=\\mathbb\{E\}\\Big\[\\sup\_\{x\\in K\}\\sum\_\{t=1\}^\{n\}\\big\(f\(X\_\{t\}\)\-f\(x\)\\big\)\\Big\]\.Thompson sampling \(TS\) samplesftf\_\{t\}from the posterior in every round and plays a minimiserXt=xftX\_\{t\}=x\_\{f\_\{t\}\}of the sampled function\. Bakhtiari, Lattimore and Szepesvári\[[1](https://arxiv.org/html/2609.10981#bib.bib1)\]analysed TS in this setting via the information ratio\. Among their results, they showed that ifξ\\xiis supported on*monotone*convex ridge functions, i\.e\.f⁡\(x\)=ℓ⁡\(⟨x,θ⟩\)f\(x\)=\\ell\(\\langle x,\\theta\\rangle\)withℓ:ℝ→ℝ\\ell:\\mathbb\{R\}\\to\\mathbb\{R\}convex and non\-decreasing, thenBRegn​\(TS,ξ\)=O⁡\(d2\.5​n​log2⁡\(n​d​diam​K\)\)\\mathrm\{BReg\}\_\{n\}\(\\mathrm\{TS\},\\xi\)=O\(d^\{2\.5\}\\sqrt\{n\}\\log^\{2\}\(nd\\,\\mathrm\{diam\}K\)\); and they showed that TS can fail catastrophically on general convex losses\. In their discussion they write:

> “At present we are uncertain whether or not the monotonicity assumption is needed in the ridge setting\. Our best guess is that it is not\.”

The monotone ridge class is a Bayesian version of the generalised linear bandit with an unknown convex, increasing link\. Dropping monotonicity allows links such asℓ⁡\(s\)=\|s−s0\|\\ell\(s\)=\|s\-s\_\{0\}\|whose minimising set onKKis, whend≥2d\\geq 2ands0s\_\{0\}lies in the interior of the projection interval\{⟨x,θ⟩:x∈K\}\\\{\\langle x,\\theta\\rangle:x\\in K\\\}, a whole hyperplane section; minimisers of convex ridge losses can thus be non\-unique, so the tie\-breaking rule of TS matters, and the geometry that drives the monotone analysis \(an ordering of minimisers along the ridge direction\) is lost\.

Our goal is statistical rather than computational: we ask whether the canonical exact\-posterior TS rule itself is safe on this structured class\. The existence of low\-regret algorithms for convex ridge links does not settle this question\. Lattimore\[[3](https://arxiv.org/html/2609.10981#bib.bib3)\]obtainsO⁡\(d​n​log⁡\(n​D\)\)O\(d\\sqrt\{n\}\\log\(nD\)\)minimax regret for an adversarial ridge model with a different algorithm, but the question here is algorithm\-specific:\[[1](https://arxiv.org/html/2609.10981#bib.bib1)\]show that standard TS can fail catastrophically on general high\-dimensional convex losses, so structure is genuinely needed to certify TS itself, and the monotone ridge class was the one for which they could do so\. Our result identifies convex ridge structure as sufficient even when the link is non\-monotone: a qualitative robustness statement about the canonical Bayesian sampling rule, not a minimax\-optimality claim\.

#### Contributions\.

Letℱblr\\mathcal\{F\}\_\{\\mathrm\{blr\}\}be the class of convex ridge functionsK→\[0,1\]K\\to\[0,1\]that are11\-Lipschitz, with an arbitrary convex link \(Section[2](https://arxiv.org/html/2609.10981#S2)\)\.

1. 1\.Regret bound without monotonicity \(Theorem[3\.1](https://arxiv.org/html/2609.10981#S3.Thmtheorem1)\)\.For every prior onℱblr\\mathcal\{F\}\_\{\\mathrm\{blr\}\}and every fixed measurable selection of minimisers, TS satisfiesBRegn​\(TS,ξ\)=O~​\(d9/2​n\)\\mathrm\{BReg\}\_\{n\}\(\\mathrm\{TS\},\\xi\)=\\tilde\{O\}\(d^\{9/2\}\\sqrt\{n\}\); explicitly,BRegn​\(TS,ξ\)≤7\+73,728​3​\(d\+1\)4​d1/2​n​log⁡\(e\+n​d​max⁡\{1,diam​K\}\)\\mathrm\{BReg\}\_\{n\}\(\\mathrm\{TS\},\\xi\)\\leq 7\+73\{,\}728\\sqrt\{3\}\\,\(d\+1\)^\{4\}d^\{1/2\}\\sqrt\{n\}\\,\\log\(e\+nd\\max\\\{1,\\mathrm\{diam\}K\\\}\)\. This resolves the qualitative question of whether monotonicity is necessary for polynomial\-in\-ddBayesian regret of exact\-posterior TS; the quantitative question of matching thed5/2d^\{5/2\}dependence of the monotone case remains open, and is discussed in Section[9](https://arxiv.org/html/2609.10981#S9)\.
2. 2\.A cardinality bound for uninformative configurations \(Theorem[3\.3](https://arxiv.org/html/2609.10981#S3.Thmtheorem3)\)\.The information\-ratio machinery of\[[1](https://arxiv.org/html/2609.10981#bib.bib1)\]reduces to showing that a finite set of loss functions whose minimisers reveal nothing about one another is small\. In the monotone case this is proved by a John\-ellipsoid dichotomy\. We show that this single\-removal dichotomy has no non\-monotone analogue \(Proposition[3\.6](https://arxiv.org/html/2609.10981#S3.Thmtheorem6)\) and prove directly that every such configuration has at most3​\(d\+1\)2−\(d\+1\)−13\(d\+1\)^\{2\}\-\(d\+1\)\-1elements\. The key tool is an elementary rounding lemma \(Lemma[5\.3](https://arxiv.org/html/2609.10981#S5.Thmtheorem3)\): if a00\-11matrix is entrywise within1/\(4​r\)1/\(4r\)of a matrix of rankrrthen its rank is at most2​r−12r\-1\. The bound is tight up to a constant: Proposition[3\.5](https://arxiv.org/html/2609.10981#S3.Thmtheorem5)exhibits uninformative configurations of sized⁡\(d\+1\)d\(d\+1\)\.
3. 3\.Transfer from information ratio to regret under any fixed measurable selection rule \(Theorem[7\.5](https://arxiv.org/html/2609.10981#S7.Thmtheorem5)\)\.The covering argument of\[[1](https://arxiv.org/html/2609.10981#bib.bib1)\]uses that ties among minimisers are broken consistently\. Since minimisers of convex ridge losses can be non\-unique, we give a self\-contained transfer theorem for exact TS, valid for every fixed measurable selection rule, using a cover by infimal\-convolution approximations and an information\-ratio bound that is uniform over selection rules\. The rule is arbitrary but fixed in advance; history\-dependent tie\-breaking is not covered\.

#### Related work\.

Ridge \(single\-index\) bandits have been studied under different learning criteria and for different algorithms\. Lattimore\[[3](https://arxiv.org/html/2609.10981#bib.bib3)\]provesO⁡\(d​n​log⁡\(n​D\)\)O\(d\\sqrt\{n\}\\log\(nD\)\)minimax regret for an adversarial ridge model with a hidden fixed direction and convex links that may vary over time, by information\-theoretic arguments and minimax duality; as noted above, this establishes learnability of the ridge structure without bearing on standard TS under an arbitrary prior\. Bakhtiari et al\.\[[1](https://arxiv.org/html/2609.10981#bib.bib1)\]analyse exact TS directly and prove the monotone ridge bound; the present paper removes monotonicity within the ridge structure\. Rajaraman, Han, Jiao and Ramchandran\[[10](https://arxiv.org/html/2609.10981#bib.bib10)\], Rajaraman and Han\[[11](https://arxiv.org/html/2609.10981#bib.bib11)\]and Kang et al\.\[[13](https://arxiv.org/html/2609.10981#bib.bib13)\]study frequentist nonlinear ridge, single\-index and contextual single\-index bandits with algorithms other than TS, and Rajaraman and Han\[[12](https://arxiv.org/html/2609.10981#bib.bib12)\]give minimax lower bounds for general stochastic bandit convex optimisation, which quantify the difficulty of general convex losses but are not specific to non\-monotone ridge losses or to TS\. None of these results provides a Bayesian regret guarantee for exact\-posterior TS over arbitrary convex non\-monotone ridge links\. We do not address the*second*question of the same paragraph of\[[1](https://arxiv.org/html/2609.10981#bib.bib1)\]\(the information ratio with a*known*link\); see also the MSc thesis of Bakhtiari\[[2](https://arxiv.org/html/2609.10981#bib.bib2)\]\. Information\-ratio analyses of TS go back to\[[7](https://arxiv.org/html/2609.10981#bib.bib7)\]; the convex\-bandit machinery we build on is from\[[5](https://arxiv.org/html/2609.10981#bib.bib5),[6](https://arxiv.org/html/2609.10981#bib.bib6),[4](https://arxiv.org/html/2609.10981#bib.bib4),[1](https://arxiv.org/html/2609.10981#bib.bib1)\]\.

## 2Setting and notation

Throughout,K⊂ℝdK\\subset\\mathbb\{R\}^\{d\}is a convex body \(compact, convex, non\-empty interior\) with0∈K0\\in K, andD=diam⁡\(K\)D=\\mathrm\{diam\}\(K\)\. A functionf:K→ℝf:K\\to\\mathbb\{R\}is a*convex ridge function*iff⁡\(x\)=ℓ⁡\(⟨x,θ⟩\)f\(x\)=\\ell\(\\langle x,\\theta\\rangle\)for some convexℓ:ℝ→ℝ\\ell:\\mathbb\{R\}\\to\\mathbb\{R\}andθ∈ℝd\\theta\\in\\mathbb\{R\}^\{d\}\(θ=0\\theta=0is allowed\)\. We write

ℱbl=\{f:K→\[0,1\]convex,Lip\(f\)≤1\},ℱblr=\{f∈ℱbl:fis a convex ridge function\},\\mathcal\{F\}\_\{\\mathrm\{bl\}\}=\\\{f:K\\to\[0,1\]\\ \\text\{convex\},\\ \\mathrm\{Lip\}\(f\)\\leq 1\\\},\\qquad\\mathcal\{F\}\_\{\\mathrm\{blr\}\}=\\\{f\\in\\mathcal\{F\}\_\{\\mathrm\{bl\}\}:\\ f\\text\{ is a convex ridge function\}\\\},andℱblrm⊂ℱblr\\mathcal\{F\}\_\{\\mathrm\{blrm\}\}\\subset\\mathcal\{F\}\_\{\\mathrm\{blr\}\}for the subclass with non\-decreasing link\. The classesℱbl\\mathcal\{F\}\_\{\\mathrm\{bl\}\}andℱblrm\\mathcal\{F\}\_\{\\mathrm\{blrm\}\}are those of\[[1](https://arxiv.org/html/2609.10981#bib.bib1)\];ℱblr\\mathcal\{F\}\_\{\\mathrm\{blr\}\}is not treated there\.

#### Measurability and tie\-breaking \(standing convention\)\.

We equipℱblr\\mathcal\{F\}\_\{\\mathrm\{blr\}\}with aσ\\sigma\-algebra𝒜\\mathcal\{A\}for whichf↦f⁡\(x\)f\\mapsto f\(x\)is measurable for everyx∈Kx\\in Kand a measurable selectionf↦xf∈arg​minK​ff\\mapsto x\_\{f\}\\in\\mathrm\{arg\\,min\}\_\{K\}fhas been fixed once and for all \(such selections exist; see\[[1](https://arxiv.org/html/2609.10981#bib.bib1), Appendix B\]\)\. Pointwise measurability makes the identity\(ℱblr,𝒜\)→\(C⁡\(K\),ℬ\)\(\\mathcal\{F\}\_\{\\mathrm\{blr\}\},\\mathcal\{A\}\)\\to\(C\(K\),\\mathcal\{B\}\)measurable, whereℬ\\mathcal\{B\}is the Borelσ\\sigma\-algebra of the uniform norm;𝒜\\mathcal\{A\}may be strictly finer thanℬ\\mathcal\{B\}\. All approximating functions constructed in Section[7](https://arxiv.org/html/2609.10981#S7)are measurable as\(C⁡\(K\),ℬ\)\(C\(K\),\\mathcal\{B\}\)\-valued maps, and there the information\-ratio hypothesis is only applied to finitely\-valued random elements ofℱblr\\mathcal\{F\}\_\{\\mathrm\{blr\}\}, which are𝒜\\mathcal\{A\}\-measurable automatically; this is what allows arbitrary priors and arbitrary fixed selections\. All statements hold for*every*such selection rule, but the rule is fixed in advance: it may not depend on the history of the game\. We writef⋆=minK⁡f=f⁡\(xf\)f^\{\\star\}=\\min\_\{K\}f=f\(x\_\{f\}\)\. For a probability measureξ\\xionℱblr\\mathcal\{F\}\_\{\\mathrm\{blr\}\}we writef¯=𝔼ξ​\[f\]\\bar\{f\}=\\mathbb\{E\}\_\{\\xi\}\[f\]\(pointwise\), a convex functionK→\[0,1\]K\\to\[0,1\]which in general is*not*a finite convex combination of elements ofℱblr\\mathcal\{F\}\_\{\\mathrm\{blr\}\}\(for instance the average ofx↦max⁡\{⟨x,θ⟩,0\}x\\mapsto\\max\\\{\\langle x,\\theta\\rangle,0\\\}over uniformly random directions in the plane is a multiple of the Euclidean norm\); the arguments below only use pointwise values off¯\\bar\{f\}\.

#### Thompson sampling\.

TS with priorξ\\xiis Algorithm 1 of\[[1](https://arxiv.org/html/2609.10981#bib.bib1)\]: in roundttsampleftf\_\{t\}from the posteriorℙ\(f∈⋅∣X1,Y1,…,Xt−1,Yt−1\)\\mathbb\{P\}\(f\\in\\cdot\\mid X\_\{1\},Y\_\{1\},\\dots,X\_\{t\-1\},Y\_\{t\-1\}\)and playXt=xftX\_\{t\}=x\_\{f\_\{t\}\}\. The observation model is Bernoulli:Yt∈\{0,1\}Y\_\{t\}\\in\\\{0,1\\\}with𝔼\[Yt∣X1,Y1,…,Xt,f\]=f\(Xt\)\\mathbb\{E\}\[Y\_\{t\}\\mid X\_\{1\},Y\_\{1\},\\dots,X\_\{t\},f\]=f\(X\_\{t\}\)\.

#### Regret and information terms\.

Unless otherwise stated, a random functionh:K→\[0,1\]h:K\\to\[0,1\]is a Borel random element ofC⁡\(K\)C\(K\)\(so\(ω,x\)↦hω​\(x\)\(\\omega,x\)\\mapsto h\_\{\\omega\}\(x\)is jointly measurable andh⋆=minK⁡hh^\{\\star\}=\\min\_\{K\}his measurable\); laws onℱbl\\mathcal\{F\}\_\{\\mathrm\{bl\}\}, and laws on\(ℱblr,𝒜\)\(\\mathcal\{F\}\_\{\\mathrm\{blr\}\},\\mathcal\{A\}\)through the identity map, are included\. For the lawν\\nuof such a random function and a policyπ∈𝒫⁡\(K\)\\pi\\in\\mathcal\{P\}\(K\), let\(X,h\)∼π⊗ν\(X,h\)\\sim\\pi\\otimes\\nu,h¯=𝔼ν​\[h\]\\bar\{h\}=\\mathbb\{E\}\_\{\\nu\}\[h\], and

Δ⁡\(π,ν\)=𝔼⁡\[h¯​\(X\)−h⋆\],I⁡\(π,ν\)=𝔼⁡\[\(h⁡\(X\)−h¯​\(X\)\)2\]\.\\Delta\(\\pi,\\nu\)=\\mathbb\{E\}\[\\bar\{h\}\(X\)\-h^\{\\star\}\],\\qquad I\(\\pi,\\nu\)=\\mathbb\{E\}\\big\[\(h\(X\)\-\\bar\{h\}\(X\)\)^\{2\}\\big\]\.Forξ∈𝒫⁡\(ℱblr\)\\xi\\in\\mathcal\{P\}\(\\mathcal\{F\}\_\{\\mathrm\{blr\}\}\)letπTSξ\\pi^\{\\xi\}\_\{\\mathrm\{TS\}\}be the law ofxfx\_\{f\}underf∼ξf\\sim\\xi\. Following\[[1](https://arxiv.org/html/2609.10981#bib.bib1)\],

IR⁡\(ℱ\)=\{\(α,β\)∈ℝ\+2:supξ∈𝒫⁡\(ℱ\)\[Δ⁡\(πTSξ,ξ\)−α−β​I​\(πTSξ,ξ\)\]≤0\}\.\\mathrm\{IR\}\(\\mathcal\{F\}\)=\\Big\\\{\(\\alpha,\\beta\)\\in\\mathbb\{R\}\_\{\+\}^\{2\}:\\ \\sup\_\{\\xi\\in\\mathcal\{P\}\(\\mathcal\{F\}\)\}\\big\[\\Delta\(\\pi^\{\\xi\}\_\{\\mathrm\{TS\}\},\\xi\)\-\\alpha\-\\sqrt\{\\beta I\(\\pi^\{\\xi\}\_\{\\mathrm\{TS\}\},\\xi\)\}\\big\]\\leq 0\\Big\\\}\.SinceπTSξ\\pi^\{\\xi\}\_\{\\mathrm\{TS\}\}depends on the selection, so doesIR⁡\(ℱ\)\\mathrm\{IR\}\(\\mathcal\{F\}\); we say\(α,β\)∈IR⁡\(ℱ\)\(\\alpha,\\beta\)\\in\\mathrm\{IR\}\(\\mathcal\{F\}\)*uniformly*if it holds for every measurable selection\.

#### The decomposition lemma\.

The following is a restatement, for the prior meanf¯=𝔼ξ​f\\bar\{f\}=\\mathbb\{E\}\_\{\\xi\}f, of the decomposition device of\[[1](https://arxiv.org/html/2609.10981#bib.bib1), Lemma 3\], which is stated there forf¯∈conv⁡\(ℱ\)\\bar\{f\}\\in\\mathrm\{conv\}\(\\mathcal\{F\}\)\. Since𝔼ξ​f\\mathbb\{E\}\_\{\\xi\}fneed not be a finite convex combination, we include a proof in Appendix[A](https://arxiv.org/html/2609.10981#A1)\.

###### Lemma 2\.1\(Decomposition; after\[[1](https://arxiv.org/html/2609.10981#bib.bib1), Lemma 3\]\)\.

Letℱ⊆ℱblr\\mathcal\{F\}\\subseteq\\mathcal\{F\}\_\{\\mathrm\{blr\}\}andα,β0≥0\\alpha,\\beta\_\{0\}\\geq 0\. Suppose there are integersk≥2k\\geq 2andm≥1m\\geq 1such that for every priorξ∈𝒫⁡\(ℱ\)\\xi\\in\\mathcal\{P\}\(\\mathcal\{F\}\), withf¯=𝔼ξ​f\\bar\{f\}=\\mathbb\{E\}\_\{\\xi\}f, there is a measurable partitionℱ=⋃i=1mℱi\\mathcal\{F\}=\\bigcup\_\{i=1\}^\{m\}\\mathcal\{F\}\_\{i\}such that, with the maximum taken over the pieces of positiveξ\\xi\-measure,

maxi∈\[m\]⁡\[supf∈ℱi\(f¯​\(xf\)−f⋆\)−α−\(β0​inff1,…,fk∈ℱi∑\(j,l\)∈PAIR⁡\(k\)\(fj​\(xfl\)−f¯​\(xfl\)\)2\)1/2\]≤0,\\max\_\{i\\in\[m\]\}\\Big\[\\sup\_\{f\\in\\mathcal\{F\}\_\{i\}\}\(\\bar\{f\}\(x\_\{f\}\)\-f^\{\\star\}\)\-\\alpha\-\\Big\(\\beta\_\{0\}\\inf\_\{f\_\{1\},\\dots,f\_\{k\}\\in\\mathcal\{F\}\_\{i\}\}\\sum\_\{\(j,l\)\\in\\mathrm\{PAIR\}\(k\)\}\\big\(f\_\{j\}\(x\_\{f\_\{l\}\}\)\-\\bar\{f\}\(x\_\{f\_\{l\}\}\)\\big\)^\{2\}\\Big\)^\{1/2\}\\Big\]\\leq 0,wherePAIR⁡\(k\)\\mathrm\{PAIR\}\(k\)is the set of ordered pairs of distinct indices\. Then\(α,β0​k​\(k−1\)​m\)∈IR⁡\(ℱ\)\(\\alpha,\\beta\_\{0\}k\(k\-1\)m\)\\in\\mathrm\{IR\}\(\\mathcal\{F\}\)for the selection used to definexfx\_\{f\}\.

The proof averages the hypothesis overkkindependent draws from each piece and applies Cauchy–Schwarz over themmpieces, usingI⁡\(πTSξ,ξ\)≥∑iξ​\(ℱi\)2​JiI\(\\pi^\{\\xi\}\_\{\\mathrm\{TS\}\},\\xi\)\\geq\\sum\_\{i\}\\xi\(\\mathcal\{F\}\_\{i\}\)^\{2\}J\_\{i\}for the within\-piece informationsJiJ\_\{i\}; only pointwise values off¯\\bar\{f\}are used\.

#### Notation\.

h:=d\+1h:=d\+1\. For a unit vectorθ\\thetaand a finite setCCof functions with selected minimisers,tf​g=⟨xg,θf⟩t\_\{fg\}=\\langle x\_\{g\},\\theta\_\{f\}\\rangle\.PAIR⁡\(C\)\\mathrm\{PAIR\}\(C\)is the set of ordered pairs of distinct elements ofCC\. Logarithms are natural\.

## 3Main results

###### Theorem 3\.1\(Regret of TS on non\-monotone convex ridge losses\)\.

Letd≥1d\\geq 1, letK⊂ℝdK\\subset\\mathbb\{R\}^\{d\}be a convex body with0∈K0\\in Kand diameterDD, letξ\\xibe any prior onℱblr\\mathcal\{F\}\_\{\\mathrm\{blr\}\}\(with respect to anyσ\\sigma\-algebra under which point evaluations and the selection are measurable, as in Section[2](https://arxiv.org/html/2609.10981#S2)\), letf↦xff\\mapsto x\_\{f\}be any such fixed measurable selection of minimisers, and let observations be Bernoulli as above\. Then for everyn≥1n\\geq 1,

BRegn​\(TS,ξ\)≤7\+73,728​3​\(d\+1\)4​d1/2​n​log⁡\(e\+n​d​max⁡\{1,D\}\)\.\\mathrm\{BReg\}\_\{n\}\(\\mathrm\{TS\},\\xi\)\\ \\leq\\ 7\+73\{,\}728\\sqrt\{3\}\\,\(d\+1\)^\{4\}\\,d^\{1/2\}\\,\\sqrt\{n\}\\,\\log\\big\(e\+nd\\max\\\{1,D\\\}\\big\)\.

Theorem[3\.1](https://arxiv.org/html/2609.10981#S3.Thmtheorem1)combines an information\-ratio bound \(Theorem[3\.4](https://arxiv.org/html/2609.10981#S3.Thmtheorem4)\) with a transfer theorem \(Theorem[7\.5](https://arxiv.org/html/2609.10981#S7.Thmtheorem5)\); the former reduces, through the blocking argument of\[[1](https://arxiv.org/html/2609.10981#bib.bib1)\], to a cardinality bound for the following objects\.

###### Definition 3\.2\(Uninformative configurations\)\.

Fixc≥12c\\geq 12,ε\>0\\varepsilon\>0and setδ=ε/\(c⁡\(d\+1\)\)\\delta=\\varepsilon/\(c\(d\+1\)\)\. A*configuration*is a finite setC⊂ℱblrC\\subset\\mathcal\{F\}\_\{\\mathrm\{blr\}\}with pairwise distinct selected minimisers together with a convex functionf¯:K→\[0,1\]\\bar\{f\}:K\\to\[0,1\]\(the*comparison function*\) such that for allf,g∈Cf,g\\in C,

rf:=f¯​\(xf\)−f⋆∈\[ε/2,ε\],\|f¯​\(xf\)−f¯​\(xg\)\|≤δ\.r\_\{f\}:=\\bar\{f\}\(x\_\{f\}\)\-f^\{\\star\}\\in\[\\varepsilon/2,\\varepsilon\],\\qquad\|\\bar\{f\}\(x\_\{f\}\)\-\\bar\{f\}\(x\_\{g\}\)\|\\leq\\delta\.A rowf∈Cf\\in Cis*uninformative*if\|f⁡\(xg\)−f¯​\(xg\)\|<δ\|f\(x\_\{g\}\)\-\\bar\{f\}\(x\_\{g\}\)\|<\\deltafor allg∈C∖\{f\}g\\in C\\setminus\\\{f\\\}; the configuration is*uninformative*if every row is\. For fixedccandddwe writegc​\(d,z\)g\_\{c\}\(d,z\)for the supremum of\|C\|\|C\|over all uninformative configurations, over all convex bodiesK∋0K\\ni 0inℝd\\mathbb\{R\}^\{d\}, allε\>0\\varepsilon\>0withdiam⁡\(K\)/ε≤z\\mathrm\{diam\}\(K\)/\\varepsilon\\leq z, all comparison functions and all selections\.

###### Theorem 3\.3\(Cardinality bound\)\.

Letc=96​\(d\+1\)c=96\(d\+1\)\. Every uninformative configuration inℱblr\\mathcal\{F\}\_\{\\mathrm\{blr\}\}satisfies\|C\|≤3​\(d\+1\)2−\(d\+1\)−1<4​\(d\+1\)2\|C\|\\leq 3\(d\+1\)^\{2\}\-\(d\+1\)\-1<4\(d\+1\)^\{2\}; that is,gc​\(d,z\)≤3​\(d\+1\)2−\(d\+1\)−1g\_\{c\}\(d,z\)\\leq 3\(d\+1\)^\{2\}\-\(d\+1\)\-1for allz\>0z\>0\.

###### Theorem 3\.4\(Information ratio\)\.

Leth=d\+1h=d\+1,k=3072​h4k=3072\\,h^\{4\}and, forα∈\(0,1\)\\alpha\\in\(0,1\),mα=1\+⌈log2⁡\(1/α\)⌉m\_\{\\alpha\}=1\+\\lceil\\log\_\{2\}\(1/\\alpha\)\\rceil\. Then

\(α,12​k​\(k−1\)​mα\)∈IR⁡\(ℱblr\)uniformly over measurable selections;\\big\(\\alpha,\\ 12\\,k\(k\-1\)\\,m\_\{\\alpha\}\\big\)\\in\\mathrm\{IR\}\(\\mathcal\{F\}\_\{\\mathrm\{blr\}\}\)\\quad\\text\{uniformly over measurable selections;\}in particularIR⁡\(ℱblr\)\\mathrm\{IR\}\(\\mathcal\{F\}\_\{\\mathrm\{blr\}\}\)contains a pair\(α,β\)\(\\alpha,\\beta\)withβ≤113,246,208​\(d\+1\)8​mα\\beta\\leq 113\{,\}246\{,\}208\\,\(d\+1\)^\{8\}\\,m\_\{\\alpha\}\.

###### Proposition 3\.5\(Tightness of the cardinality bound\)\.

For everyd≥2d\\geq 2and everyc≥12c\\geq 12there is an uninformative configuration inℱblr\\mathcal\{F\}\_\{\\mathrm\{blr\}\}, on a truncated simplex of diameter at most2\\sqrt\{2\}in normalised coordinates, with\|C\|=d⁡\(d\+1\)\|C\|=d\(d\+1\)andD/ε≤64​2​c2​d​\(d\+1\)2D/\\varepsilon\\leq 64\\sqrt\{2\}\\,c^\{2\}d\(d\+1\)^\{2\}; rescaling the functions about the common comparison value shows that the same size is attained for every larger value ofD/εD/\\varepsilon\. In particular, forc=96​\(d\+1\)c=96\(d\+1\)andz≥589,824​2​d​\(d\+1\)4z\\geq 589\{,\}824\\sqrt\{2\}\\,d\(d\+1\)^\{4\},d⁡\(d\+1\)≤gc​\(d,z\)≤3​\(d\+1\)2−\(d\+1\)−1d\(d\+1\)\\leq g\_\{c\}\(d,z\)\\leq 3\(d\+1\)^\{2\}\-\(d\+1\)\-1\. Ford=1d=1,gc​\(1,z\)≤2g\_\{c\}\(1,z\)\\leq 2for everyz\>0z\>0andgc​\(1,z\)=2g\_\{c\}\(1,z\)=2forz≥4z\\geq 4\.

###### Proposition 3\.6\(The single\-removal John\-ellipsoid dichotomy has no non\-monotone analogue\)\.

Ford=3d=3and everyc≥12c\\geq 12there is an uninformative configurationCCof twelve functions inℱblr\\mathcal\{F\}\_\{\\mathrm\{blr\}\}such that, writingJζ​\(C\)=conv⁡\{xf:f∈C\}\+BζJ\_\{\\zeta\}\(C\)=\\mathrm\{conv\}\\\{x\_\{f\}:f\\in C\\\}\+B\_\{\\zeta\}andEζ​\(⋅\)E\_\{\\zeta\}\(\\cdot\)for the maximum\-volume inscribed ellipsoid,Eζ​\(C∖\{f\}\)=Eζ​\(C\)E\_\{\\zeta\}\(C\\setminus\\\{f\\\}\)=E\_\{\\zeta\}\(C\)for everyf∈Cf\\in Cand everyζ\>0\\zeta\>0\.

Proposition[3\.6](https://arxiv.org/html/2609.10981#S3.Thmtheorem6)concerns the proof strategy of\[[1](https://arxiv.org/html/2609.10981#bib.bib1)\], not their results: their Lemma 8 \(“some removal shrinks the John ellipsoid by a factor0\.850\.85, or some ordered pair is informative”\) is stated and proved for the monotone class only, and Proposition[3\.6](https://arxiv.org/html/2609.10981#S3.Thmtheorem6)shows that its literal analogue forℱblr\\mathcal\{F\}\_\{\\mathrm\{blr\}\}is false for every fixed shrink factorγ<1\\gamma<1in place of0\.850\.85\. It does not exclude other uses of John ellipsoids\.

### 3\.1Proof overview

The argument has five steps; we record for each its input, its output and its cost in the dimension, so that the exponent9/29/2can be traced\.

1. 1\.*Two thin bands \(Section[4](https://arxiv.org/html/2609.10981#S4)\)\.*Everyf∈ℱblrf\\in\\mathcal\{F\}\_\{\\mathrm\{blr\}\}has a representationℓ⁡\(⟨⋅,θ⟩\)\\ell\(\\langle\\cdot,\\theta\\rangle\)withℓ\\ellconvex,11\-Lipschitz and globally minimised at the projections of the minimisers \(Lemma[4\.1](https://arxiv.org/html/2609.10981#S4.Thmtheorem1)\)\. If a rowffof a configuration is uninformative, convexity ofℓ\\ellalongθf\\theta\_\{f\}forces the projections of all other minimisers into two thin bands at the extreme projections, on either side of⟨xf,θf⟩\\langle x\_\{f\},\\theta\_\{f\}\\rangle, each of relative widthη≈6/\(c⁡\(d\+1\)\)\\eta\\approx 6/\(c\(d\+1\)\)\(Lemma[4\.2](https://arxiv.org/html/2609.10981#S4.Thmtheorem2)\)\. For monotone links only one band can be non\-empty; the second band is the whole difficulty\.
2. 2\.*Balanced and unbalanced rows \(Section[5](https://arxiv.org/html/2609.10981#S5)\)\.*Rows whose two band distancesL,RL,Rare comparable are handled by a quadratic evaluation matrix of rank at mosth⁡\(h\+1\)/2h\(h\+1\)/2with small off\-diagonal entries, giving at mosth2−1h^\{2\}\-1such rows \(Lemma[5\.1](https://arxiv.org/html/2609.10981#S5.Thmtheorem1)\)\. For the remaining rows this quadratic estimate deteriorates when the two band distances are highly imbalanced, so we eliminate the far\-band entries with an exactly low\-rank Boolean mask instead: the near\-band membership matrixHH, a00\-11matrix, is within1/\(8​h\)1/\(8h\)of an affine evaluation matrix of rank at mosthh, and Lemma[5\.3](https://arxiv.org/html/2609.10981#S5.Thmtheorem3)givesrank​H≤2​h−1\\mathrm\{rank\}H\\leq 2h\-1\. Masking an affine matrix byHH\(Lemma[5\.2](https://arxiv.org/html/2609.10981#S5.Thmtheorem2)\) then yields a near\-identity matrix of rank at mosth⁡\(2​h−1\)h\(2h\-1\), hence at most2​h2−h2h^\{2\}\-hunbalanced rows\. Altogether\|C\|≤3​h2−h−1=O⁡\(d2\)\|C\|\\leq 3h^\{2\}\-h\-1=O\(d^\{2\}\)\(Theorem[3\.3](https://arxiv.org/html/2609.10981#S3.Thmtheorem3)\), which is tight up to constants \(Proposition[3\.5](https://arxiv.org/html/2609.10981#S3.Thmtheorem5)\)\. The rounding tolerance1/\(4​r\)1/\(4r\)withr=hr=his what forcesc=Θ⁡\(d\)c=\\Theta\(d\)\.
3. 3\.*Counting \(Section[6](https://arxiv.org/html/2609.10981#S6)\)\.*If a configuration hasG\+qG\+qelements, deleting first endpoints of informative pairsqqtimes shows that its ordered pairs carry energy at leastq​δ2q\\delta^\{2\}\(Lemma[6\.1](https://arxiv.org/html/2609.10981#S6.Thmtheorem1)\)\. Within one dyadic level of the gapf¯​\(xf\)−f⋆\\bar\{f\}\(x\_\{f\}\)\-f^\{\\star\}, akk\-tuple is cut intob=4​c​hb=4chblocks ofs=2​Gs=2Gfunctions; at least half the blocks are configurations, each contributingG​δ2G\\delta^\{2\}, so everykk\-tuple has energy at leastε2/12\\varepsilon^\{2\}/12withk=b​s=3072​h4k=bs=3072h^\{4\}\. Lemma[2\.1](https://arxiv.org/html/2609.10981#S2.Thmtheorem1)turns this into\(α,12​k​\(k−1\)​mα\)∈IR⁡\(ℱblr\)\(\\alpha,12k\(k\-1\)m\_\{\\alpha\}\)\\in\\mathrm\{IR\}\(\\mathcal\{F\}\_\{\\mathrm\{blr\}\}\), i\.e\.β=O⁡\(d8​log⁡\(1/α\)\)\\beta=O\(d^\{8\}\\log\(1/\\alpha\)\)\(Theorem[3\.4](https://arxiv.org/html/2609.10981#S3.Thmtheorem4)\)\. The exponent88is2×42\\times 4:kkis the number of blocksΘ⁡\(c​d\)=Θ⁡\(d2\)\\Theta\(cd\)=\\Theta\(d^\{2\}\)times the block sizeΘ⁡\(G\)=Θ⁡\(d2\)\\Theta\(G\)=\\Theta\(d^\{2\}\)\.
4. 4\.*Transfer \(Section[7](https://arxiv.org/html/2609.10981#S7)\)\.*A cover ofℱblr\\mathcal\{F\}\_\{\\mathrm\{blr\}\}byNρ≤\(1\+2​D/ρ\)d​\(1\+8​D/ρ\)dN\_\{\\rho\}\\leq\(1\+2D/\\rho\)^\{d\}\(1\+8D/\\rho\)^\{d\}value\-based pieces, built from infimal\-convolution approximations that keep the selected minimiser exact \(Lemma[7\.4](https://arxiv.org/html/2609.10981#S7.Thmtheorem4)\), together with the information\-ratio bound applied to finitely\-valued proxies, givesBRegn≤n​α\+n​ρ​\(6\+4​β\)\+β​n​log⁡Nρ/2\\mathrm\{BReg\}\_\{n\}\\leq n\\alpha\+n\\rho\(6\+4\\sqrt\{\\beta\}\)\+\\sqrt\{\\beta n\\log N\_\{\\rho\}/2\}for any fixed measurable selection \(Theorem[7\.5](https://arxiv.org/html/2609.10981#S7.Thmtheorem5)\);log⁡N1/n=O⁡\(d​log⁡\(e\+n​D\)\)\\log N\_\{1/n\}=O\(d\\log\(e\+nD\)\)costsd\\sqrt\{d\}\.
5. 5\.*Assembly\.*Withα=ρ=1/n\\alpha=\\rho=1/n,β=O⁡\(d4​log⁡n\)\\sqrt\{\\beta\}=O\(d^\{4\}\\sqrt\{\\log n\}\)andlog⁡N1/n=O⁡\(d​log⁡\(e\+n​D\)\)\\sqrt\{\\log N\_\{1/n\}\}=O\(\\sqrt\{d\\log\(e\+nD\)\}\)giveBRegn=O⁡\(d4​d​n​log⁡\(e\+n​d​max⁡\{1,D\}\)\)=O~​\(d9/2​n\)\\mathrm\{BReg\}\_\{n\}=O\(d^\{4\}\\sqrt\{dn\}\\log\(e\+nd\\max\\\{1,D\\\}\)\)=\\tilde\{O\}\(d^\{9/2\}\\sqrt\{n\}\)\(Theorem[3\.1](https://arxiv.org/html/2609.10981#S3.Thmtheorem1)\)\.

## 4Structure of uninformative rows

###### Lemma 4\.1\(Ridge representation with a global minimiser\)\.

For everyf∈ℱblrf\\in\\mathcal\{F\}\_\{\\mathrm\{blr\}\}there exist a unit vectorθ\\thetaand a convex,11\-Lipschitzℓ:ℝ→ℝ\\ell:\\mathbb\{R\}\\to\\mathbb\{R\}such thatf=ℓ⁡\(⟨⋅,θ⟩\)f=\\ell\(\\langle\\cdot,\\theta\\rangle\)onKK,ℓ≥f⋆≥0\\ell\\geq f^\{\\star\}\\geq 0on all ofℝ\\mathbb\{R\}, andℓ⁡\(⟨x,θ⟩\)=f⋆=minℝ⁡ℓ\\ell\(\\langle x,\\theta\\rangle\)=f^\{\\star\}=\\min\_\{\\mathbb\{R\}\}\\ellfor every minimiserxxofffonKK\. In particular\|f⁡\(x\)−f⁡\(y\)\|≤\|⟨θ,x−y⟩\|\|f\(x\)\-f\(y\)\|\\leq\|\\langle\\theta,x\-y\\rangle\|for allx,y∈Kx,y\\in K\.

The proof \(Appendix[A](https://arxiv.org/html/2609.10981#A1)\) shows that the link is11\-Lipschitz on the projection interval ofKKand extends it beyond that interval with slopes∓1\\mp 1; a constant extension would*not*be convex when the minimiser is interior\. The extension is defined on all ofℝ\\mathbb\{R\}and attains its global minimum at the projections of the minimisers offf; the part of it outside the projection interval is used in Section[7](https://arxiv.org/html/2609.10981#S7)\.

###### Lemma 4\.2\(Two thin extreme bands\)\.

Letc≥12c\\geq 12and letCCbe a configuration \(Definition[3\.2](https://arxiv.org/html/2609.10981#S3.Thmtheorem2)\)\. Fixf∈Cf\\in Cwith representation\(θf,ℓf\)\(\\theta\_\{f\},\\ell\_\{f\}\)from Lemma[4\.1](https://arxiv.org/html/2609.10981#S4.Thmtheorem1), and writes=⟨xf,θf⟩s=\\langle x\_\{f\},\\theta\_\{f\}\\rangle,tg=⟨xg,θf⟩t\_\{g\}=\\langle x\_\{g\},\\theta\_\{f\}\\rangle,a=ming∈C⁡tga=\\min\_\{g\\in C\}t\_\{g\},b=maxg∈C⁡tgb=\\max\_\{g\\in C\}t\_\{g\},L=s−aL=s\-a,R=b−sR=b\-s, and

η:=3​δε/2\+δ=3c⁡\(d\+1\)/2\+1\.\\eta:=\\frac\{3\\delta\}\{\\varepsilon/2\+\\delta\}=\\frac\{3\}\{c\(d\+1\)/2\+1\}\.If the rowffis uninformative then for everyg≠fg\\neq f:

1. \(i\)\|tg−s\|\>ε/2−2​δ≥5​ε/12\|t\_\{g\}\-s\|\>\\varepsilon/2\-2\\delta\\geq 5\\varepsilon/12;
2. \(ii\)tg∈\(b−ηR,b\]t\_\{g\}\\in\(b\-\\eta R,\\,b\]iftg\>st\_\{g\}\>s, andtg∈\[a,a\+ηL\)t\_\{g\}\\in\[a,\\,a\+\\eta L\)iftg<st\_\{g\}<s\.

The proof \(Appendix[A](https://arxiv.org/html/2609.10981#A1)\) is a two\-line convexity argument: uninformativeness pinsf⁡\(xg\)f\(x\_\{g\}\)to withinδ\\deltaoff¯​\(xg\)\\bar\{f\}\(x\_\{g\}\), which is at leastf⋆\+ε/2−2​δf^\{\\star\}\+\\varepsilon/2\-2\\delta, giving \(i\); and interpolatingℓf\\ell\_\{f\}between its minimum atssand its value at the extreme projectionbbshows that anytgt\_\{g\}strictly inside\(s,b\)\(s,b\)would makef⁡\(xg\)f\(x\_\{g\}\)smaller thanf¯​\(xg\)−δ\\bar\{f\}\(x\_\{g\}\)\-\\deltaunlesstgt\_\{g\}is within relative distanceη\\etaofbb, giving \(ii\)\. In particular, along its own direction each uninformative row sees the other minimisers at one of two projected distances,LLandRR, each determined up to a relative errorη\\eta\.

## 5The cardinality bound

### 5\.1Three linear\-algebra tools

###### Lemma 5\.1\(Trace–rank bound: the classical symmetric bound of\[[8](https://arxiv.org/html/2609.10981#bib.bib8), Lemma 2\.2\]and its non\-symmetric extension\)\.

For any realN×NN\\times NmatrixMM,\|tr​M\|2≤rank⁡\(M\)​∥M∥F2\|\\mathrm\{tr\}M\|^\{2\}\\leq\\mathrm\{rank\}\(M\)\\,\\lVert M\\rVert\_\{F\}^\{2\}\. Consequently, ifMi​i=1M\_\{ii\}=1for allii,\|Mi​j\|≤t\|M\_\{ij\}\|\\leq tfori≠ji\\neq j,rank​M≤Q\\mathrm\{rank\}M\\leq QandQ​t2<1Qt^\{2\}<1, then

N≤Q⁡\(1−t2\)1−Q​t2≤Q1−Q​t2;N\\leq\\frac\{Q\(1\-t^\{2\}\)\}\{1\-Qt^\{2\}\}\\leq\\frac\{Q\}\{1\-Qt^\{2\}\};and if moreoverQ≥1Q\\geq 1is an integer andt<1/Qt<1/Q, thenN≤QN\\leq Q\.

For symmetricMMthe second claim is\[[8](https://arxiv.org/html/2609.10981#bib.bib8), Lemma 2\.2\]; the trace–rank inequality for arbitrary real matrices also appears as\[[7](https://arxiv.org/html/2609.10981#bib.bib7), Fact 10\]\. The short proof \(via the orthogonal projection onto the column space ofMM\) is in Appendix[B](https://arxiv.org/html/2609.10981#A2)\.

###### Lemma 5\.2\(Hadamard products\)\.

For real matricesU,VU,Vof the same shape,rank⁡\(U∘V\)≤rank⁡\(U\)​rank​\(V\)\\mathrm\{rank\}\(U\\circ V\)\\leq\\mathrm\{rank\}\(U\)\\mathrm\{rank\}\(V\), where∘\\circis the entrywise product\.

###### Proof\.

WriteU=∑a≤pua​va⊤U=\\sum\_\{a\\leq p\}u\_\{a\}v\_\{a\}^\{\\top\}andV=∑b≤qyb​zb⊤V=\\sum\_\{b\\leq q\}y\_\{b\}z\_\{b\}^\{\\top\}withp=rank​Up=\\mathrm\{rank\}U,q=rank​Vq=\\mathrm\{rank\}V; thenU∘V=∑a,b\(ua∘yb\)​\(va∘zb\)⊤U\\circ V=\\sum\_\{a,b\}\(u\_\{a\}\\circ y\_\{b\}\)\(v\_\{a\}\\circ z\_\{b\}\)^\{\\top\}\. ∎

###### Lemma 5\.3\(Integer rounding preserves rank up to a factor two\)\.

Letr≥1r\\geq 1be an integer, letAAbe a real matrix withrank​A≤r\\mathrm\{rank\}A\\leq r, and letBBbe a00\-11matrix of the same shape with∥A−B∥max≤γ\\lVert A\-B\\rVert\_\{\\max\}\\leq\\gamma\. Ifγ≤1/\(4​r\)\\gamma\\leq 1/\(4r\)thenrank​B≤2​r−1\\mathrm\{rank\}B\\leq 2r\-1\.

#### Proof sketch\.

Ifrank​B≥2​r\\mathrm\{rank\}B\\geq 2r, take a non\-singular2​r×2​r2r\\times 2rsubmatrixB0B\_\{0\}ofBB, the correspondingA0A\_\{0\}, andE=B0−A0E=B\_\{0\}\-A\_\{0\}, sorank​A0≤r\\mathrm\{rank\}A\_\{0\}\\leq rand∥E∥F2≤4​r2​γ2\\lVert E\\rVert\_\{F\}^\{2\}\\leq 4r^\{2\}\\gamma^\{2\}\. On anrr\-dimensional subspace ofker⁡A0\\ker A\_\{0\}the matrixB0B\_\{0\}coincides withEE, so therrsmallest squared singular values ofB0B\_\{0\}sum to at most4​r2​γ24r^\{2\}\\gamma^\{2\}, while therrlargest sum to at most∥B0∥F2≤4​r2−1\\lVert B\_\{0\}\\rVert\_\{F\}^\{2\}\\leq 4r^\{2\}\-1\(a non\-singular00\-11matrix has a zero entry\)\. The arithmetic–geometric mean inequality on each group gives\|detB0\|≤\(4​r​γ\)r​\(1−1/\(4​r2\)\)r/2<1\|\\det B\_\{0\}\|\\leq\(4r\\gamma\)^\{r\}\(1\-1/\(4r^\{2\}\)\)^\{r/2\}<1forγ≤1/\(4​r\)\\gamma\\leq 1/\(4r\), contradicting\|detB0\|≥1\|\\det B\_\{0\}\|\\geq 1for a non\-singular integer matrix\. The details are in Appendix[B](https://arxiv.org/html/2609.10981#A2)\.

We have not found this elementary statement in the literature in this form, but we do not claim priority for it; the approximate\-rank literature \(e\.g\.\[[8](https://arxiv.org/html/2609.10981#bib.bib8),[9](https://arxiv.org/html/2609.10981#bib.bib9)\]\) studies both upper and lower bounds on theε\\varepsilon\-approximate rank of real matrices and their algorithmic applications, and we use the elementary rounding statement above only in its specific role, namely to turn a band\-membership matrix, which is only approximately low\-rank, into an*exactly*low\-rank00\-11mask; the integrality of the mask is what allows the two bands of Lemma[4\.2](https://arxiv.org/html/2609.10981#S4.Thmtheorem2)to be handled without any control on the ratio of their distances\. The tolerance1/\(4​r\)1/\(4r\)cannot be raised to order1/r1/\\sqrt\{r\}for arbitrary00\-11matrices \(Proposition[E\.1](https://arxiv.org/html/2609.10981#A5.Thmtheorem1)in Appendix[E](https://arxiv.org/html/2609.10981#A5)\)\.

### 5\.2Proof of Theorem[3\.3](https://arxiv.org/html/2609.10981#S3.Thmtheorem3)

Leth=d\+1h=d\+1,c=96​hc=96h, so that

η=348​h2\+1<116​h2,δ=ε96​h2\.\\eta=\\frac\{3\}\{48h^\{2\}\+1\}<\\frac\{1\}\{16h^\{2\}\},\\qquad\\delta=\\frac\{\\varepsilon\}\{96h^\{2\}\}\.\(1\)LetCCbe an uninformative configuration withN=\|C\|≥3N=\|C\|\\geq 3\(forN≤2N\\leq 2there is nothing to prove\)\. For each rowi∈Ci\\in Ctake the representation of Lemma[4\.1](https://arxiv.org/html/2609.10981#S4.Thmtheorem1)and the quantitiesti​j=⟨xj,θi⟩t\_\{ij\}=\\langle x\_\{j\},\\theta\_\{i\}\\rangle,sis\_\{i\},aia\_\{i\},bib\_\{i\},LiL\_\{i\},RiR\_\{i\}of Lemma[4\.2](https://arxiv.org/html/2609.10981#S4.Thmtheorem2)\. By Lemma[4\.2](https://arxiv.org/html/2609.10981#S4.Thmtheorem2)\(i\),Li\+Ri\>0L\_\{i\}\+R\_\{i\}\>0\. Replacing\(θi,ℓi\)\(\\theta\_\{i\},\\ell\_\{i\}\)by\(−θi,ℓi\(−⋅\)\)\(\-\\theta\_\{i\},\\ell\_\{i\}\(\-\\cdot\)\)if necessary \(this changes neither the function nor its selected minimiser\), we may assume

0≤Li≤Ri,Ri\>0,wi:=Li\+Ri,λi:=Li/wi∈\[0,1/2\]\.0\\leq L\_\{i\}\\leq R\_\{i\},\\qquad R\_\{i\}\>0,\\qquad w\_\{i\}:=L\_\{i\}\+R\_\{i\},\\qquad\\lambda\_\{i\}:=L\_\{i\}/w\_\{i\}\\in\[0,1/2\]\.By Lemma[4\.2](https://arxiv.org/html/2609.10981#S4.Thmtheorem2)\(ii\) everyj≠ij\\neq iis either in the*near band*ti​j∈\[ai,ai\+ηLi\)t\_\{ij\}\\in\[a\_\{i\},a\_\{i\}\+\\eta L\_\{i\}\)\(empty ifLi=0L\_\{i\}=0\) or in the*far band*ti​j∈\(bi−ηRi,bi\]t\_\{ij\}\\in\(b\_\{i\}\-\\eta R\_\{i\},b\_\{i\}\]\. Throughout,ai,bi,si,Li,Ria\_\{i\},b\_\{i\},s\_\{i\},L\_\{i\},R\_\{i\}refer to the whole configurationCCand are never recomputed for subsets\. Split

IB=\{i:λi\>1/\(8​h\)\},IU=\{i:λi≤1/\(8​h\)\}\.I\_\{B\}=\\\{i:\\lambda\_\{i\}\>1/\(8h\)\\\},\\qquad I\_\{U\}=\\\{i:\\lambda\_\{i\}\\leq 1/\(8h\)\\\}\.
#### Balanced rows\.

Fori∈IBi\\in I\_\{B\}we haveLi​Ri\>0L\_\{i\}R\_\{i\}\>0andRi/Li<8​h−1R\_\{i\}/L\_\{i\}<8h\-1\. Consider the quadratic polynomialpi​\(x\)=\(⟨x,θi⟩−ai\)​\(bi−⟨x,θi⟩\)/\(Li​Ri\)p\_\{i\}\(x\)=\(\\langle x,\\theta\_\{i\}\\rangle\-a\_\{i\}\)\(b\_\{i\}\-\\langle x,\\theta\_\{i\}\\rangle\)/\(L\_\{i\}R\_\{i\}\)and the matrixP=\(pi​\(xj\)\)i,j∈IBP=\(p\_\{i\}\(x\_\{j\}\)\)\_\{i,j\\in I\_\{B\}\}\. ThenPi​i=1P\_\{ii\}=1, and forj≠ij\\neq iin the near band0≤Pi​j<η⁡\(Li\+Ri\)/Ri≤2​η0\\leq P\_\{ij\}<\\eta\(L\_\{i\}\+R\_\{i\}\)/R\_\{i\}\\leq 2\\eta, in the far band0≤Pi​j<η⁡\(Li\+Ri\)/Li<8​h​η0\\leq P\_\{ij\}<\\eta\(L\_\{i\}\+R\_\{i\}\)/L\_\{i\}<8h\\eta; so all off\-diagonal entries are belowtB:=8​h​η<1/\(2​h\)t\_\{B\}:=8h\\eta<1/\(2h\)\. Each row ofPPis a polynomial of total degree at most two inxj∈ℝdx\_\{j\}\\in\\mathbb\{R\}^\{d\}, sorank​P≤QB:=1\+d\+d⁡\(d\+1\)/2=h⁡\(h\+1\)/2\\mathrm\{rank\}P\\leq Q\_\{B\}:=1\+d\+d\(d\+1\)/2=h\(h\+1\)/2\. SinceQB​tB2<\(h\+1\)/\(8​h\)≤3/16Q\_\{B\}t\_\{B\}^\{2\}<\(h\+1\)/\(8h\)\\leq 3/16, Lemma[5\.1](https://arxiv.org/html/2609.10981#S5.Thmtheorem1)gives

\|IB\|≤QB1−QB​tB2<4​h2​\(h\+1\)7​h−1<h2,i\.e\.​\|IB\|≤h2−1,\|I\_\{B\}\|\\leq\\frac\{Q\_\{B\}\}\{1\-Q\_\{B\}t\_\{B\}^\{2\}\}<\\frac\{4h^\{2\}\(h\+1\)\}\{7h\-1\}<h^\{2\},\\qquad\\text\{i\.e\. \}\|I\_\{B\}\|\\leq h^\{2\}\-1,\(2\)where the last strict inequality uses7​h−1−4​\(h\+1\)=3​h−5\>07h\-1\-4\(h\+1\)=3h\-5\>0forh≥2h\\geq 2\.

#### Unbalanced rows\.

All matrices below are indexed byIU×IUI\_\{U\}\\times I\_\{U\}\. Define the00\-11matrixHHbyHi​i=1H\_\{ii\}=1and, forj≠ij\\neq i,Hi​j=1H\_\{ij\}=1ifti​jt\_\{ij\}lies in the near band of rowiiandHi​j=0H\_\{ij\}=0if it lies in the far band\. Define the affine evaluation matrixAi​j=\(bi−ti​j\)/wiA\_\{ij\}=\(b\_\{i\}\-t\_\{ij\}\)/w\_\{i\}; each row is an affine function ofxjx\_\{j\}, sorank​A≤h\\mathrm\{rank\}A\\leq h\. Entrywise,\|Ai​i−1\|=λi≤1/\(8​h\)\|A\_\{ii\}\-1\|=\\lambda\_\{i\}\\leq 1/\(8h\); forjjin the near band\|Ai​j−1\|=\(ti​j−ai\)/wi<η​λi\|A\_\{ij\}\-1\|=\(t\_\{ij\}\-a\_\{i\}\)/w\_\{i\}<\\eta\\lambda\_\{i\}; forjjin the far band\|Ai​j\|=\(bi−ti​j\)/wi<η⁡\(1−λi\)\|A\_\{ij\}\|=\(b\_\{i\}\-t\_\{ij\}\)/w\_\{i\}<\\eta\(1\-\\lambda\_\{i\}\)\. By \([1](https://arxiv.org/html/2609.10981#S5.E1)\),∥A−H∥max≤1/\(8​h\)\\lVert A\-H\\rVert\_\{\\max\}\\leq 1/\(8h\), so Lemma[5\.3](https://arxiv.org/html/2609.10981#S5.Thmtheorem3)withr=hr=hgivesrank​H≤2​h−1\\mathrm\{rank\}H\\leq 2h\-1\.

Next defineUi​j=\(ti​j−ai\)/LiU\_\{ij\}=\(t\_\{ij\}\-a\_\{i\}\)/L\_\{i\}ifLi\>0L\_\{i\}\>0andUi​j=1U\_\{ij\}=1ifLi=0L\_\{i\}=0; again each row is affine inxjx\_\{j\}, sorank​U≤h\\mathrm\{rank\}U\\leq h\. LetM=U∘HM=U\\circ H\. ThenMi​i=1M\_\{ii\}=1; forjjin the far bandMi​j=0M\_\{ij\}=0exactly \(the mask removes the possibly huge valuesUi​jU\_\{ij\}there\); forjjin the near band0≤Mi​j<η0\\leq M\_\{ij\}<\\eta; and rows withLi=0L\_\{i\}=0have no near band, so their off\-diagonal entries vanish\. By Lemma[5\.2](https://arxiv.org/html/2609.10981#S5.Thmtheorem2),rank​M≤h⁡\(2​h−1\)=:QU\\mathrm\{rank\}M\\leq h\(2h\-1\)=:Q\_\{U\}, andQU​η<h⁡\(2​h−1\)/\(16​h2\)<1/8Q\_\{U\}\\eta<h\(2h\-1\)/\(16h^\{2\}\)<1/8, soη<1/QU\\eta<1/Q\_\{U\}and the integer form of Lemma[5\.1](https://arxiv.org/html/2609.10981#S5.Thmtheorem1)gives

\|IU\|≤QU=2​h2−h\.\|I\_\{U\}\|\\leq Q\_\{U\}=2h^\{2\}\-h\.\(3\)

#### Conclusion\.

By \([2](https://arxiv.org/html/2609.10981#S5.E2)\) and \([3](https://arxiv.org/html/2609.10981#S5.E3)\),\|C\|=\|IB\|\+\|IU\|≤3​h2−h−1<4​h2\|C\|=\|I\_\{B\}\|\+\|I\_\{U\}\|\\leq 3h^\{2\}\-h\-1<4h^\{2\}\. ∎

Only Lemmas[4\.1](https://arxiv.org/html/2609.10981#S4.Thmtheorem1)and[4\.2](https://arxiv.org/html/2609.10981#S4.Thmtheorem2)and finite\-dimensional linear algebra are used: no monotonicity, no John ellipsoid, no bound onD/εD/\\varepsilon, and only the fact thatxfx\_\{f\}is some minimiser, so the bound holds for every measurable selection\. On the family of Proposition[3\.5](https://arxiv.org/html/2609.10981#S3.Thmtheorem5)every row is unbalanced,HHis the “same base vertex” mask, andMMis the identity\.

## 6From the cardinality bound to the information ratio

###### Lemma 6\.1\(Counting informative pairs\)\.

Fixc≥12c\\geq 12and suppose every uninformative configuration \(Definition[3\.2](https://arxiv.org/html/2609.10981#S3.Thmtheorem2), with thiscc\) has at mostGGelements\. Letq≥1q\\geq 1be an integer\. IfCCsatisfies the hypotheses of Definition[3\.2](https://arxiv.org/html/2609.10981#S3.Thmtheorem2)and\|C\|≥G\+q\|C\|\\geq G\+q, then

∑\(f,g\)∈PAIR⁡\(C\)\(f⁡\(xg\)−f¯​\(xg\)\)2≥q​δ2\.\\sum\_\{\(f,g\)\\in\\mathrm\{PAIR\}\(C\)\}\\big\(f\(x\_\{g\}\)\-\\bar\{f\}\(x\_\{g\}\)\\big\)^\{2\}\\geq q\\delta^\{2\}\.

The proof \(Appendix[B](https://arxiv.org/html/2609.10981#A2)\) deletes,qqtimes, the first endpoint of an ordered pair with\|f⁡\(xg\)−f¯​\(xg\)\|≥δ\|f\(x\_\{g\}\)\-\\bar\{f\}\(x\_\{g\}\)\|\\geq\\delta; such a pair exists while more thanGGelements remain, the hypotheses of Definition[3\.2](https://arxiv.org/html/2609.10981#S3.Thmtheorem2)survive deletion, and theqqrecorded pairs have distinct first endpoints\.

###### Proof of Theorem[3\.4](https://arxiv.org/html/2609.10981#S3.Thmtheorem4)\.

Fix a measurable selection, a priorξ\\xionℱblr\\mathcal\{F\}\_\{\\mathrm\{blr\}\}, andf¯=𝔼ξ​f\\bar\{f\}=\\mathbb\{E\}\_\{\\xi\}f\. Leth=d\+1h=d\+1,c=96​hc=96handG=4​h2G=4h^\{2\}; by Theorem[3\.3](https://arxiv.org/html/2609.10981#S3.Thmtheorem3)every uninformative configuration for thiscchas at mostGGelements\. Withεi=α​2i\\varepsilon\_\{i\}=\\alpha 2^\{i\}partitionℱblr\\mathcal\{F\}\_\{\\mathrm\{blr\}\}intoℱ0=\{f:f¯​\(xf\)−f⋆≤α\}\\mathcal\{F\}\_\{0\}=\\\{f:\\bar\{f\}\(x\_\{f\}\)\-f^\{\\star\}\\leq\\alpha\\\}andℱi=\{f:f¯​\(xf\)−f⋆∈\(α​2i−1,α​2i\]\}\\mathcal\{F\}\_\{i\}=\\\{f:\\bar\{f\}\(x\_\{f\}\)\-f^\{\\star\}\\in\(\\alpha 2^\{i\-1\},\\alpha 2^\{i\}\]\\\}for1≤i≤⌈log2⁡\(1/α\)⌉1\\leq i\\leq\\lceil\\log\_\{2\}\(1/\\alpha\)\\rceil; these are measurable \(they only involvef↦f¯​\(xf\)f\\mapsto\\bar\{f\}\(x\_\{f\}\)andf↦f⋆f\\mapsto f^\{\\star\}\) and there aremαm\_\{\\alpha\}of them\. The condition of Lemma[2\.1](https://arxiv.org/html/2609.10981#S2.Thmtheorem1)holds trivially onℱ0\\mathcal\{F\}\_\{0\}\. Fixi≥1i\\geq 1,ε=εi\\varepsilon=\\varepsilon\_\{i\},δ=ε/\(c​h\)\\delta=\\varepsilon/\(ch\), and set

b=4​c​h,s=2​G,k=b​s=8​c​h​G=3072​h4b=4ch,\\qquad s=2G,\\qquad k=bs=8chG=3072\\,h^\{4\}\(overb=2​c​h\+ub=2ch\+u,s=G\+vs=G\+vthe argument below yields energyu​v​δ2uv\\delta^\{2\}, andk2/\(u​v\)k^\{2\}/\(uv\)is minimised atu=2​c​hu=2ch,v=Gv=G\)\. Letf1,…,fk∈ℱif\_\{1\},\\dots,f\_\{k\}\\in\\mathcal\{F\}\_\{i\}be akk\-tuple\. We show

S:=∑\(j,l\)∈PAIR⁡\(k\)\(fj​\(xfl\)−f¯​\(xfl\)\)2≥ε212,S:=\\sum\_\{\(j,l\)\\in\\mathrm\{PAIR\}\(k\)\}\\big\(f\_\{j\}\(x\_\{f\_\{l\}\}\)\-\\bar\{f\}\(x\_\{f\_\{l\}\}\)\\big\)^\{2\}\\geq\\frac\{\\varepsilon^\{2\}\}\{12\},\(4\)which withsupf∈ℱi\(f¯​\(xf\)−f⋆\)≤ε≤12​S\\sup\_\{f\\in\\mathcal\{F\}\_\{i\}\}\(\\bar\{f\}\(x\_\{f\}\)\-f^\{\\star\}\)\\leq\\varepsilon\\leq\\sqrt\{12S\}and Lemma[2\.1](https://arxiv.org/html/2609.10981#S2.Thmtheorem1)\(applied withβ0=12\\beta\_\{0\}=12\) proves the theorem\. If two functions of the tuple share the selected minimiser \(in particular if they coincide\), the pair contributes\(f¯​\(xf\)−f⋆\)2≥ε2/4\(\\bar\{f\}\(x\_\{f\}\)\-f^\{\\star\}\)^\{2\}\\geq\\varepsilon^\{2\}/4\. Otherwise order the tuple so thatvj=f¯​\(xfj\)v\_\{j\}=\\bar\{f\}\(x\_\{f\_\{j\}\}\)is non\-increasing\. Ifv1−vk≥2​εv\_\{1\}\-v\_\{k\}\\geq 2\\varepsilonthenf1​\(xfk\)≥f1⋆≥v1−ε≥vk\+εf\_\{1\}\(x\_\{f\_\{k\}\}\)\\geq f\_\{1\}^\{\\star\}\\geq v\_\{1\}\-\\varepsilon\\geq v\_\{k\}\+\\varepsilonand the pair\(1,k\)\(1,k\)contributesε2\\varepsilon^\{2\}\. Otherwise cut the ordered tuple intobbconsecutive blocks ofssfunctions; the sum of the value spreads of the blocks is less than2​ε2\\varepsilon, so fewer than2​ε/δ=2​c​h2\\varepsilon/\\delta=2chblocks have spread larger thanδ\\delta, and at leastb−2​c​h=2​c​hb\-2ch=2chblocks have spread at mostδ\\delta\. Each such block, together withf¯\\bar\{f\}, satisfies Definition[3\.2](https://arxiv.org/html/2609.10981#S3.Thmtheorem2)\(its elements haverf∈\(ε/2,ε\]r\_\{f\}\\in\(\\varepsilon/2,\\varepsilon\]and distinct minimisers\) and hass=2​G=G\+Gs=2G=G\+Gelements, so Lemma[6\.1](https://arxiv.org/html/2609.10981#S6.Thmtheorem1)withq=Gq=Gshows that it contributes at leastG​δ2G\\delta^\{2\}; the blocks are disjoint, so

S≥2​c​h⋅G​δ2=2​Gc​h​ε2=8​h296​h2​ε2=ε212\.S\\geq 2ch\\cdot G\\delta^\{2\}=\\frac\{2G\}\{ch\}\\,\\varepsilon^\{2\}=\\frac\{8h^\{2\}\}\{96h^\{2\}\}\\,\\varepsilon^\{2\}=\\frac\{\\varepsilon^\{2\}\}\{12\}\.Sinceε2/4\\varepsilon^\{2\}/4andε2\\varepsilon^\{2\}are not smaller, \([4](https://arxiv.org/html/2609.10981#S6.E4)\) holds for every tuple\. Lemma[2\.1](https://arxiv.org/html/2609.10981#S2.Thmtheorem1)gives\(α,12​k​\(k−1\)​mα\)∈IR⁡\(ℱblr\)\(\\alpha,12k\(k\-1\)m\_\{\\alpha\}\)\\in\\mathrm\{IR\}\(\\mathcal\{F\}\_\{\\mathrm\{blr\}\}\), and12​k2=12⋅30722​h8=113,246,208​h812k^\{2\}=12\\cdot 3072^\{2\}h^\{8\}=113\{,\}246\{,\}208\\,h^\{8\}\. Nothing in the argument depends on which measurable selection was fixed\. ∎

In\[[1](https://arxiv.org/html/2609.10981#bib.bib1)\]the role of Lemma[6\.1](https://arxiv.org/html/2609.10981#S6.Thmtheorem1)is played by their Lemma 9, which iterates their John\-ellipsoid dichotomy \(Lemma 8\); Proposition[3\.6](https://arxiv.org/html/2609.10981#S3.Thmtheorem6)shows that no such dichotomy holds forℱblr\\mathcal\{F\}\_\{\\mathrm\{blr\}\}, which is why we count through a cardinality bound instead\.

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

The transfer theorem of\[[1](https://arxiv.org/html/2609.10981#bib.bib1), Theorem 28\]bounds the regret of \(approximate\) TS from an information\-ratio bound and a cover of the function class, and its covering argument for ridge classes uses, as the authors note, that ties among minimisers are broken consistently\. Forℱblr\\mathcal\{F\}\_\{\\mathrm\{blr\}\}minimisers can be non\-unique \(an interior minimising projection level produces a positive\-dimensional minimising section whend≥2d\\geq 2\), so we give a self\-contained transfer theorem for exact TS that is valid for any fixed measurable selection rule\. Two ingredients differ from\[[1](https://arxiv.org/html/2609.10981#bib.bib1)\]: the cover is built from infimal\-convolution approximations, so that the selected minimiser offfis an exact minimiser of its approximation \(Lemma[7\.4](https://arxiv.org/html/2609.10981#S7.Thmtheorem4)\); and the information\-ratio hypothesis is required uniformly over selection rules and extended to finitely\-supported randomised minimisers \(Lemma[7\.1](https://arxiv.org/html/2609.10981#S7.Thmtheorem1)\), which is what the proof actually uses\. The three preparatory lemmas below are proved in Appendix[C](https://arxiv.org/html/2609.10981#A3)\.

###### Lemma 7\.1\(Uniform bounds extend to randomised minimisers\)\.

Suppose\(α,β\)∈IR⁡\(ℱ\)\(\\alpha,\\beta\)\\in\\mathrm\{IR\}\(\\mathcal\{F\}\)for every measurable selection, whereℱ⊆ℱblr\\mathcal\{F\}\\subseteq\\mathcal\{F\}\_\{\\mathrm\{blr\}\}\. Letξ∈𝒫⁡\(ℱ\)\\xi\\in\\mathcal\{P\}\(\\mathcal\{F\}\)and let\(f,X\)\(f,X\)be a random pair withf∼ξf\\sim\\xiandX∈arg​minK​fX\\in\\mathrm\{arg\\,min\}\_\{K\}falmost surely, given by a measurable kernel\. ThenΔ⁡\(ℒ⁡\(X\),ξ\)≤α\+β​I​\(ℒ⁡\(X\),ξ\)\\Delta\(\\mathcal\{L\}\(X\),\\xi\)\\leq\\alpha\+\\sqrt\{\\beta I\(\\mathcal\{L\}\(X\),\\xi\)\}\.

Lemma[7\.1](https://arxiv.org/html/2609.10981#S7.Thmtheorem1)is where uniformity over selections is used: a randomised minimiser is a mixture of measurable selections \(by Kallenberg’s randomisation lemma\), and bothΔ\\DeltaandIIare linear in the policy\.

###### Lemma 7\.2\(Continuity and near\-minimisers\)\.

1. \(a\)Letf,gf,gbe Borel random elements ofC⁡\(K\)C\(K\)with values in\[0,1\]\[0,1\]\(no convexity or ridge assumption\), coupled with∥f−g∥∞≤ρ\\lVert f\-g\\rVert\_\{\\infty\}\\leq\\rhoa\.s\., and letπ\\pibe independent of them\. ThenI⁡\(π,ℒ⁡\(g\)\)≤I⁡\(π,ℒ⁡\(f\)\)\+ρ\\sqrt\{I\(\\pi,\\mathcal\{L\}\(g\)\)\}\\leq\\sqrt\{I\(\\pi,\\mathcal\{L\}\(f\)\)\}\+\\rho\.
2. \(b\)Letν\\nube the law of a Borel random element ofC⁡\(K\)C\(K\)that is a\.s\.11\-Lipschitz with values in\[0,1\]\[0,1\], and let actionsX,ZX,Zbe coupled with∥X−Z∥≤ρ\\lVert X\-Z\\rVert\\leq\\rhoa\.s\. and independent of the function\. ThenI⁡\(ℒ⁡\(Z\),ν\)≤I⁡\(ℒ⁡\(X\),ν\)\+ρ\\sqrt\{I\(\\mathcal\{L\}\(Z\),\\nu\)\}\\leq\\sqrt\{I\(\\mathcal\{L\}\(X\),\\nu\)\}\+\\rho\.
3. \(c\)Suppose\(α,β\)∈IR⁡\(ℱblr\)\(\\alpha,\\beta\)\\in\\mathrm\{IR\}\(\\mathcal\{F\}\_\{\\mathrm\{blr\}\}\)uniformly over selections\. Let\(f,X\)\(f,X\)be a random pair taking finitely many values, withf∈ℱblrf\\in\\mathcal\{F\}\_\{\\mathrm\{blr\}\}andf⁡\(X\)≤f⋆\+ρf\(X\)\\leq f^\{\\star\}\+\\rhoa\.s\. ThenΔ⁡\(ℒ⁡\(X\),ℒ⁡\(f\)\)≤α\+β​I​\(ℒ⁡\(X\),ℒ⁡\(f\)\)\+ρ⁡\(1\+β\)\\Delta\(\\mathcal\{L\}\(X\),\\mathcal\{L\}\(f\)\)\\leq\\alpha\+\\sqrt\{\\beta I\(\\mathcal\{L\}\(X\),\\mathcal\{L\}\(f\)\)\}\+\\rho\(1\+\\sqrt\{\\beta\}\)\.

Parts \(a\) and \(b\) say thatI\\sqrt\{I\}is11\-Lipschitz under uniform perturbations of the function and, for Lipschitz functions, of the action; both are proved with a single conditional\-centring operator, which is anL2L^\{2\}contraction\. Part \(c\) passes from near\-minimisers to exact minimisers by flatteningffat the levelf⁡\(X\)f\(X\); sinceI⁡\(π,ν\)I\(\\pi,\\nu\)depends only on the marginal laws of the policy and of the random function, part \(a\) can then be applied on a product coupling with an independent copy ofXX, even thoughXXandffare dependent\. Finite support is assumed so that the flattened proxy is a finitely\-valued, hence𝒜\\mathcal\{A\}\-measurable, kernel\.

###### Lemma 7\.3\(Measurable representations\)\.

There are a Borel mapf↦θf∈Sd−1f\\mapsto\\theta\_\{f\}\\in S^\{d\-1\}on\(ℱblr,ℬ\)\(\\mathcal\{F\}\_\{\\mathrm\{blr\}\},\\mathcal\{B\}\)and a jointly continuous map\(f,θ,t\)↦L⁡\(f,θ,t\)\(f,\\theta,t\)\\mapsto L\(f,\\theta,t\)onℱblr×Sd−1×ℝ\\mathcal\{F\}\_\{\\mathrm\{blr\}\}\\times S^\{d\-1\}\\times\\mathbb\{R\},

L⁡\(f,θ,t\)=miny∈K⁡\[f⁡\(y\)\+\|t−⟨θ,y⟩\|\],L\(f,\\theta,t\)=\\min\_\{y\\in K\}\\big\[f\(y\)\+\|t\-\\langle\\theta,y\\rangle\|\\big\],such that, for everyff,\(θf,L\(f,θf,⋅\)\)\(\\theta\_\{f\},L\(f,\\theta\_\{f\},\\cdot\)\)is a representation offfas in Lemma[4\.1](https://arxiv.org/html/2609.10981#S4.Thmtheorem1)\.

The direction map exists by the Kuratowski–Ryll\-Nardzewski selection theorem, applied to the closed\-valued, weakly measurable correspondencef↦\{θ:\|f\(x\)−f\(y\)\|≤\|⟨θ,x−y⟩\|∀x,y\}f\\mapsto\\\{\\theta:\|f\(x\)\-f\(y\)\|\\leq\|\\langle\\theta,x\-y\\rangle\|\\ \\forall x,y\\\}on the compact setℱblr⊂C⁡\(K\)\\mathcal\{F\}\_\{\\mathrm\{blr\}\}\\subset C\(K\);LLis the infimal convolution offfwith\|t−⟨θ,⋅⟩\|\|t\-\\langle\\theta,\\cdot\\rangle\|\.

###### Lemma 7\.4\(Cover by infimal\-convolution approximations\)\.

Let0<ρ<10<\\rho<1, and choose aρ\\rho\-netCKC\_\{K\}ofKKand aρ/\(2​D\)\\rho/\(2D\)\-netCSC\_\{S\}ofSd−1S^\{d\-1\}with\|CK\|≤\(1\+2​D/ρ\)d\|C\_\{K\}\|\\leq\(1\+2D/\\rho\)^\{d\}and\|CS\|≤\(1\+8​D/ρ\)d\|C\_\{S\}\|\\leq\(1\+8D/\\rho\)^\{d\}\(such nets exist by the standard volume argument\), soNρ:=\|CK\|​\|CS\|≤\(1\+2​D/ρ\)d​\(1\+8​D/ρ\)dN\_\{\\rho\}:=\|C\_\{K\}\|\|C\_\{S\}\|\\leq\(1\+2D/\\rho\)^\{d\}\(1\+8D/\\rho\)^\{d\}\. For\(x,θ\)∈CK×CS\(x,\\theta\)\\in C\_\{K\}\\times C\_\{S\}let

ℱx,θval=\{g∈ℱblr:gis a ridge function in directionθ,g\(x\)≤g⋆\+2ρ\}\.\\mathcal\{F\}^\{\\mathrm\{val\}\}\_\{x,\\theta\}=\\\{g\\in\\mathcal\{F\}\_\{\\mathrm\{blr\}\}:\\ g\\text\{ is a ridge function in direction \}\\theta,\\ g\(x\)\\leq g^\{\\star\}\+2\\rho\\\}\.Then \(i\) every probability average of functions inℱx,θval\\mathcal\{F\}^\{\\mathrm\{val\}\}\_\{x,\\theta\}lies inℱblr\\mathcal\{F\}\_\{\\mathrm\{blr\}\}, is a ridge function in directionθ\\theta, and is2​ρ2\\rho\-near\-minimal atxx; \(ii\) for every measurable selection there are measurable mapsf↦κ⁡\(f\)=\(xκ,θκ\)∈CK×CSf\\mapsto\\kappa\(f\)=\(x\_\{\\kappa\},\\theta\_\{\\kappa\}\)\\in C\_\{K\}\\times C\_\{S\}andf↦gf∈ℱκ⁡\(f\)valf\\mapsto g\_\{f\}\\in\\mathcal\{F\}^\{\\mathrm\{val\}\}\_\{\\kappa\(f\)\}with∥f−gf∥∞≤ρ/2\\lVert f\-g\_\{f\}\\rVert\_\{\\infty\}\\leq\\rho/2,∥xf−xκ∥≤ρ\\lVert x\_\{f\}\-x\_\{\\kappa\}\\rVert\\leq\\rho, and such thatxfx\_\{f\}is an exact minimiser ofgfg\_\{f\}withgf⋆=f⋆g\_\{f\}^\{\\star\}=f^\{\\star\}\.

#### Proof idea\.

\(i\) is closed under averaging because all functions in a piece share the directionθ\\theta, and near\-minimality atxxis preserved since the minimum of an average is at least the average of the minima\. For \(ii\), letθf\\theta\_\{f\}andLLbe as in Lemma[7\.3](https://arxiv.org/html/2609.10981#S7.Thmtheorem3), letκ⁡\(f\)\\kappa\(f\)be the first pair in a fixed enumeration ofCK×CSC\_\{K\}\\times C\_\{S\}with∥xκ−xf∥≤ρ\\lVert x\_\{\\kappa\}\-x\_\{f\}\\rVert\\leq\\rhoand∥θκ−θf∥≤ρ/\(2​D\)\\lVert\\theta\_\{\\kappa\}\-\\theta\_\{f\}\\rVert\\leq\\rho/\(2D\), and setgf​\(x\)=L⁡\(f,θκ,⟨x,θκ⟩\)=miny∈K⁡\[f⁡\(y\)\+\|⟨θκ,x−y⟩\|\]g\_\{f\}\(x\)=L\(f,\\theta\_\{\\kappa\},\\langle x,\\theta\_\{\\kappa\}\\rangle\)=\\min\_\{y\\in K\}\[f\(y\)\+\|\\langle\\theta\_\{\\kappa\},x\-y\\rangle\|\], the infimal convolution offfwith the ridge kernel\|⟨θκ,⋅⟩\|\|\\langle\\theta\_\{\\kappa\},\\cdot\\rangle\|\. Its profile is convex and11\-Lipschitz, sogfg\_\{f\}is a ridge function in directionθκ\\theta\_\{\\kappa\};y=xy=xgivesgf≤fg\_\{f\}\\leq fandf≥f⋆f\\geq f^\{\\star\}givesgf≥f⋆g\_\{f\}\\geq f^\{\\star\}, so no rescaling is needed; the inequalityf⁡\(x\)−f⁡\(y\)≤\|⟨θf,x−y⟩\|f\(x\)\-f\(y\)\\leq\|\\langle\\theta\_\{f\},x\-y\\rangle\|of Lemma[4\.1](https://arxiv.org/html/2609.10981#S4.Thmtheorem1)and∥θκ−θf∥≤ρ/\(2​D\)\\lVert\\theta\_\{\\kappa\}\-\\theta\_\{f\}\\rVert\\leq\\rho/\(2D\)givef−ρ/2≤gff\-\\rho/2\\leq g\_\{f\}; andf⋆≤gf​\(xf\)≤f⁡\(xf\)=f⋆f^\{\\star\}\\leq g\_\{f\}\(x\_\{f\}\)\\leq f\(x\_\{f\}\)=f^\{\\star\}shows thatxfx\_\{f\}is an exact minimiser ofgfg\_\{f\}\. The details, including measurability, are in Appendix[C](https://arxiv.org/html/2609.10981#A3)\.

###### Theorem 7\.5\(Transfer under any fixed measurable selection rule\)\.

Suppose\(α,β\)∈IR⁡\(ℱblr\)\(\\alpha,\\beta\)\\in\\mathrm\{IR\}\(\\mathcal\{F\}\_\{\\mathrm\{blr\}\}\)uniformly over measurable selections\. Then for every measurable selection, every priorξ\\xionℱblr\\mathcal\{F\}\_\{\\mathrm\{blr\}\}, everyn≥1n\\geq 1and everyρ∈\(0,1\)\\rho\\in\(0,1\), exact Thompson sampling satisfies

BRegn​\(TS,ξ\)≤n​α\+n​ρ​\(6\+4​β\)\+12​β​n​log⁡Nρ\.\\mathrm\{BReg\}\_\{n\}\(\\mathrm\{TS\},\\xi\)\\leq n\\alpha\+n\\rho\(6\+4\\sqrt\{\\beta\}\)\+\\sqrt\{\\tfrac\{1\}\{2\}\\beta n\\log N\_\{\\rho\}\}\.

#### Proof idea\.

Fix a round, letf∼ξf\\sim\\xibe the current posterior,X⋆=xfX^\{\\star\}=x\_\{f\}, and letXXbe an independent copy ofX⋆X^\{\\star\}, soℒ⁡\(X\)=πTS\\mathcal\{L\}\(X\)=\\pi\_\{\\mathrm\{TS\}\}\. Withκ=κ⁡\(f\)\\kappa=\\kappa\(f\),g=gfg=g\_\{f\}andz=xκz=x\_\{\\kappa\}from Lemma[7\.4](https://arxiv.org/html/2609.10981#S7.Thmtheorem4), setHκ=𝔼⁡\[f∣κ\]H\_\{\\kappa\}=\\mathbb\{E\}\[f\\mid\\kappa\]andGκ=𝔼⁡\[g∣κ\]G\_\{\\kappa\}=\\mathbb\{E\}\[g\\mid\\kappa\]\. Both take finitely many values \(one per label\)\.GκG\_\{\\kappa\}is a finitely\-valued\(ℱblr,𝒜\)\(\\mathcal\{F\}\_\{\\mathrm\{blr\}\},\\mathcal\{A\}\)\-valued random element, a ridge function in directionθκ\\theta\_\{\\kappa\}that is2​ρ2\\rho\-near\-minimal atzz\(Lemma[7\.4](https://arxiv.org/html/2609.10981#S7.Thmtheorem4)\(i\)\);HκH\_\{\\kappa\}is only a convex11\-Lipschitz function inℱbl\\mathcal\{F\}\_\{\\mathrm\{bl\}\}\(an average of ridge functions with nearby but different directions is in general not a ridge function\), viewed as a BorelC⁡\(K\)C\(K\)\-valued element, and∥Gκ−Hκ∥∞≤ρ/2\\lVert G\_\{\\kappa\}\-H\_\{\\kappa\}\\rVert\_\{\\infty\}\\leq\\rho/2\. The information\-ratio hypothesis is applied, via Lemmas[7\.1](https://arxiv.org/html/2609.10981#S7.Thmtheorem1)and[7\.2](https://arxiv.org/html/2609.10981#S7.Thmtheorem2)\(c\), only to the finitely\-valued flattened proxymax⁡\{Gκ,Gκ​\(z\)\}\\max\\\{G\_\{\\kappa\},G\_\{\\kappa\}\(z\)\\\}, never toHκH\_\{\\kappa\}\. Sinceg≤fg\\leq f,∥f−g∥∞≤ρ/2\\lVert f\-g\\rVert\_\{\\infty\}\\leq\\rho/2and∥X⋆−z∥≤ρ\\lVert X^\{\\star\}\-z\\rVert\\leq\\rho, the one\-step regret satisfiesΔ⁡\(πTS,ξ\)≤Δ⁡\(πz,νG\)\+52​ρ\\Delta\(\\pi\_\{\\mathrm\{TS\}\},\\xi\)\\leq\\Delta\(\\pi\_\{z\},\\nu\_\{G\}\)\+\\tfrac\{5\}\{2\}\\rhowithνG=ℒ⁡\(Gκ\)\\nu\_\{G\}=\\mathcal\{L\}\(G\_\{\\kappa\}\)andπz=ℒ⁡\(z\)\\pi\_\{z\}=\\mathcal\{L\}\(z\); Lemma[7\.2](https://arxiv.org/html/2609.10981#S7.Thmtheorem2)\(c\) givesΔ⁡\(πz,νG\)≤α\+β​I​\(πz,νG\)\+2​ρ​\(1\+β\)\\Delta\(\\pi\_\{z\},\\nu\_\{G\}\)\\leq\\alpha\+\\sqrt\{\\beta I\(\\pi\_\{z\},\\nu\_\{G\}\)\}\+2\\rho\(1\+\\sqrt\{\\beta\}\); and Lemma[7\.2](https://arxiv.org/html/2609.10981#S7.Thmtheorem2)\(a\),\(b\), applied on a product space built from two independent posterior draws, giveI⁡\(πz,νG\)≤I⁡\(πTS,ℒ⁡\(Hκ\)\)\+32​ρ\\sqrt\{I\(\\pi\_\{z\},\\nu\_\{G\}\)\}\\leq\\sqrt\{I\(\\pi\_\{\\mathrm\{TS\}\},\\mathcal\{L\}\(H\_\{\\kappa\}\)\)\}\+\\tfrac\{3\}\{2\}\\rho\. AltogetherΔ⁡\(πTS,ξ\)≤α\+β​I​\(πTS,ℒ⁡\(Hκ\)\)\+ρ⁡\(6\+4​β\)\\Delta\(\\pi\_\{\\mathrm\{TS\}\},\\xi\)\\leq\\alpha\+\\sqrt\{\\beta I\(\\pi\_\{\\mathrm\{TS\}\},\\mathcal\{L\}\(H\_\{\\kappa\}\)\)\}\+\\rho\(6\+4\\sqrt\{\\beta\}\)\. For Bernoulli observationsI⁡\(πTS,ℒ⁡\(Hκ\)\)≤12​𝖨​\(κ,X,Y\)I\(\\pi\_\{\\mathrm\{TS\}\},\\mathcal\{L\}\(H\_\{\\kappa\}\)\)\\leq\\tfrac\{1\}\{2\}\\mathsf\{I\}\(\\kappa;X,Y\)by Pinsker’s inequality; the labelκ⁡\(f\)\\kappa\(f\)is a fixed function of the environment, so the chain rule for mutual information gives𝔼​∑t𝖨t−1​\(κ,Xt,Yt\)≤log⁡Nρ\\mathbb\{E\}\\sum\_\{t\}\\mathsf\{I\}\_\{t\-1\}\(\\kappa;X\_\{t\},Y\_\{t\}\)\\leq\\log N\_\{\\rho\}, and Cauchy–Schwarz over rounds finishes\. The full proof is in Appendix[C](https://arxiv.org/html/2609.10981#A3)\.

#### Proof of Theorem[3\.1](https://arxiv.org/html/2609.10981#S3.Thmtheorem1)\.

Forn=1n=1the regret is at most1≤71\\leq 7\. Forn≥2n\\geq 2takeα=ρ=1/n\\alpha=\\rho=1/nandL=log⁡\(e\+n​d​max⁡\{1,D\}\)L=\\log\(e\+nd\\max\\\{1,D\\\}\): Theorem[3\.4](https://arxiv.org/html/2609.10981#S3.Thmtheorem4)givesβ≤12,288​3​\(d\+1\)4​L\\sqrt\{\\beta\}\\leq 12\{,\}288\\sqrt\{3\}\\,\(d\+1\)^\{4\}\\sqrt\{L\}\(usingm1/n≤4​Lm\_\{1/n\}\\leq 4L\), Lemma[7\.4](https://arxiv.org/html/2609.10981#S7.Thmtheorem4)giveslog⁡N1/n≤8​d​L\\log N\_\{1/n\}\\leq 8dL, and Theorem[7\.5](https://arxiv.org/html/2609.10981#S7.Thmtheorem5)yieldsBRegn≤7\+6​β​n​d​L=7\+73,728​3​\(d\+1\)4​d1/2​n​L\\mathrm\{BReg\}\_\{n\}\\leq 7\+6\\sqrt\{\\beta\}\\sqrt\{ndL\}=7\+73\{,\}728\\sqrt\{3\}\\,\(d\+1\)^\{4\}d^\{1/2\}\\sqrt\{n\}\\,L; the arithmetic is in Appendix[C](https://arxiv.org/html/2609.10981#A3)\.

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

The proofs of Propositions[3\.5](https://arxiv.org/html/2609.10981#S3.Thmtheorem5)and[3\.6](https://arxiv.org/html/2609.10981#S3.Thmtheorem6)are in Appendix[D](https://arxiv.org/html/2609.10981#A4); we describe the constructions\. For Proposition[3\.5](https://arxiv.org/html/2609.10981#S3.Thmtheorem5)take the standarddd\-simplex with verticesv0,…,vdv\_\{0\},\\dots,v\_\{d\}, a smallτ=1/\(4​c​\(d\+1\)\)\\tau=1/\(4c\(d\+1\)\), and thed⁡\(d\+1\)d\(d\+1\)pointsxi​j=\(1−τ\)​vi\+τ​vjx\_\{ij\}=\(1\-\\tau\)v\_\{i\}\+\\tau v\_\{j\}\(i≠ji\\neq j\), which are the vertices of a truncated simplexKK\. The lossfi​jf\_\{ij\}is a V\-shaped ridge function of the affine coordinateui​j=1−λi\+τ​λju\_\{ij\}=1\-\\lambda\_\{i\}\+\\tau\\lambda\_\{j\}\(barycentric coordinatesλ\\lambda\), with a steep left slope and a shallow right slope, minimised atxi​jx\_\{ij\}and equal to the constant comparison functionf¯≡1/4\\bar\{f\}\\equiv 1/4at every other point up to a cross error belowδ\\delta; the gap isε=τ2/\(4​d\)\\varepsilon=\\tau^\{2\}/\(4d\)\. Along its own direction, row\(i,j\)\(i,j\)sees thed−1d\-1pointsxi​lx\_\{il\}with the same base vertex in a near band atuu\-distanceτ2\\tau^\{2\}and the otherd2d^\{2\}points in a far band atuu\-distance about11; every row is two\-sided, and the ratio of the band distances is of order1/τ21/\\tau^\{2\}, unbounded in the family\. For Proposition[3\.6](https://arxiv.org/html/2609.10981#S3.Thmtheorem6)taked=3d=3and the regular tetrahedron: the twelve pointsxi​jx\_\{ij\}are the vertices of a truncated tetrahedronPP, removing any one vertex cutsPPby a plane through its three neighbours, and bothPPand the cut body still contain the inscribed ball of the tetrahedron and are contained in the tetrahedron enlarged by the smoothing radius; an arithmetic–geometric mean bound on the determinant of any inscribed ellipsoid shows that the maximum\-volume inscribed ellipsoid of both bodies is that ball, so no single removal shrinks it\.

In the monotone case an uninformative row has all other minimisers on one side of its own along the ridge direction, and\[[1](https://arxiv.org/html/2609.10981#bib.bib1)\]show that they then lie beyond the centre of the John ellipsoid, so removing the row cuts the ellipsoid through its centre; for non\-monotone links both bands of Lemma[4\.2](https://arxiv.org/html/2609.10981#S4.Thmtheorem2)can be non\-empty and arbitrarily imbalanced, and Proposition[3\.6](https://arxiv.org/html/2609.10981#S3.Thmtheorem6)shows that the single\-removal, fixed\-shrink\-factor dichotomy cannot hold\. We do not obtain the required uniform cardinality estimate from polynomial approximation \(a univariate polynomial that is11at the row’s own projection and small on both bands\); the mask argument of Lemma[5\.3](https://arxiv.org/html/2609.10981#S5.Thmtheorem3)avoids the need to control the imbalance ratio of the two band distances\.

## 9Discussion

Theorem[3\.1](https://arxiv.org/html/2609.10981#S3.Thmtheorem1)resolves the qualitative question of\[[1](https://arxiv.org/html/2609.10981#bib.bib1)\]: monotonicity of the link is not needed for exact\-posterior Thompson sampling to achieve Bayesian regret polynomial inddandn\\sqrt\{n\}innn\. The quantitative question of the dimension dependence remains open: the information\-ratio certificate we construct has sizeO⁡\(\(d\+1\)8​\(1\+log⁡\(1/α\)\)\)O\(\(d\+1\)^\{8\}\(1\+\\log\(1/\\alpha\)\)\)againstO~​\(d4\)\\tilde\{O\}\(d^\{4\}\)in the monotone analysis \(this is the size of our certificate, not a lower bound on the best information ratio\), and the resulting regret exponent is9/29/2against5/25/2\. The loss comes from two places\. The cardinality boundΘ⁡\(d2\)\\Theta\(d^\{2\}\)is tight \(Proposition[3\.5](https://arxiv.org/html/2609.10981#S3.Thmtheorem5)\), so the number of functions per block in Lemma[2\.1](https://arxiv.org/html/2609.10981#S2.Thmtheorem1)isΘ⁡\(d2\)\\Theta\(d^\{2\}\)and the number of blocks isΘ⁡\(c​d\)\\Theta\(cd\); and the constantc=96​\(d\+1\)c=96\(d\+1\)is dictated by the rounding threshold1/\(4​r\)1/\(4r\)of Lemma[5\.3](https://arxiv.org/html/2609.10981#S5.Thmtheorem3), which forcesη≲1/d2\\eta\\lesssim 1/d^\{2\}\. The order1/r1/rof this tolerance cannot be improved to order1/r1/\\sqrt\{r\}for arbitrary00\-11matrices: Proposition[E\.1](https://arxiv.org/html/2609.10981#A5.Thmtheorem1)\(Appendix[E](https://arxiv.org/html/2609.10981#A5)\) exhibits, for everyr=2j−1r=2^\{j\}\-1withj≥2j\\geq 2, a rank\-rrmatrix within2/\(r\+1\)2/\(r\+1\)in max\-norm of a00\-11matrix of rank2​r2r\. This rules out only a better uniform rounding theorem for arbitrary00\-11matrices; the band\-membership matrices of Section[5](https://arxiv.org/html/2609.10981#S5)have additional structure, and any improvement of the exponent through a larger rounding tolerance would have to exploit it\. We do not claim that the exponent9/29/2is optimal\. Whether the monotone exponent5/25/2can be reached, and what the correct dimension dependence of TS on this class is \(no lower bound specific to non\-monotone links is known\), are left open\. Three remarks on scope\. \(1\) The statement is about Bayesian regret with an arbitrary prior; it does not give a frequentist guarantee for every fixed environment, and it concerns exact\-posterior TS without addressing computation, which remains open\. \(2\) The selection rule is arbitrary but fixed in advance; rules that change with the history are not covered\. \(3\) The observation model is Bernoulli; the only place the model enters is Pinsker’s inequality for the conditional means of\[0,1\]\[0,1\]\-valued observations, so the same constants hold for observationsYt∈\[0,1\]Y\_\{t\}\\in\[0,1\]satisfying𝔼\[Yt∣ℋt−1,Xt,f\]=f\(Xt\)\\mathbb\{E\}\[Y\_\{t\}\\mid\\mathcal\{H\}\_\{t\-1\},X\_\{t\},f\]=f\(X\_\{t\}\)almost surely, whereℋt−1=σ⁡\(X1,Y1,…,Xt−1,Yt−1\)\\mathcal\{H\}\_\{t\-1\}=\\sigma\(X\_\{1\},Y\_\{1\},\\dots,X\_\{t\-1\},Y\_\{t\-1\}\), provided that a complete observation model is specified under which the posterior is well defined and TS uses fresh internal randomness conditionally on the history \(the condition𝔼\[Yt∣Xt,f\]=f\(Xt\)\\mathbb\{E\}\[Y\_\{t\}\\mid X\_\{t\},f\]=f\(X\_\{t\}\)alone is not sufficient\)\. The second question in the same paragraph of\[[1](https://arxiv.org/html/2609.10981#bib.bib1)\], the information ratio for a*known*convex link, is not touched here; see also the MSc thesis of Bakhtiari\[[2](https://arxiv.org/html/2609.10981#bib.bib2)\]\.

## References

- \[1\]A\. Bakhtiari, T\. Lattimore, and Cs\. Szepesvári\. Thompson sampling for bandit convex optimisation\. In*Proceedings of the 38th Conference on Learning Theory \(COLT\)*, PMLR 291:231–263, 2025\.
- \[2\]A\. Bakhtiari\.*Thompson Sampling for Bandit Convex Optimization*\. MSc thesis, University of Alberta, 2025\.
- \[3\]T\. Lattimore\. Minimax regret for bandit convex optimisation of ridge functions\. arXiv preprint arXiv:2106\.00444, 2021\.
- \[4\]T\. Lattimore\. Improved regret for zeroth\-order adversarial bandit convex optimisation\.*Mathematical Statistics and Learning*, 2\(3/4\):311–334, 2020\.
- \[5\]S\. Bubeck, O\. Dekel, T\. Koren, and Y\. Peres\. Bandit convex optimization:T\\sqrt\{T\}regret in one dimension\. In*COLT*, 2015\.
- \[6\]S\. Bubeck and R\. Eldan\. Exploratory distributions for convex functions\.*Mathematical Statistics and Learning*, 1\(1\):73–100, 2018\.
- \[7\]D\. Russo and B\. Van Roy\. An information\-theoretic analysis of Thompson sampling\.*Journal of Machine Learning Research*, 17\(1\):2442–2471, 2016\.
- \[8\]N\. Alon\. Perturbed identity matrices have high rank: proof and applications\.*Combinatorics, Probability and Computing*, 18\(1–2\):3–15, 2009\.
- \[9\]N\. Alon, T\. Lee, A\. Shraibman, and S\. Vempala\. The approximate rank of a matrix and its algorithmic applications\. In*Proceedings of the 45th ACM Symposium on Theory of Computing \(STOC\)*, pages 675–684, 2013\.
- \[10\]N\. Rajaraman, Y\. Han, J\. Jiao, and K\. Ramchandran\. Statistical complexity and optimal algorithms for nonlinear ridge bandits\.*Annals of Statistics*, 52\(6\):2557–2582, 2024\.
- \[11\]N\. Rajaraman and Y\. Han\. Interactive learning of single\-index models via stochastic gradient descent\. In*International Conference on Learning Representations \(ICLR\)*, 2026\. arXiv:2602\.17876\.
- \[12\]N\. Rajaraman and Y\. Han\. The price of hidden curvature: improved lower bounds for bandit convex optimization\. arXiv:2607\.18652 \(v3\), 2026\.
- \[13\]Y\. Kang, M\. Liu, B\. Yi, J\. Lyu, Z\. Zhang, D\. Zhou, and Y\. Li\. Single index bandits: generalized linear contextual bandits with unknown reward functions\. In*International Conference on Learning Representations \(ICLR\)*, 2026\. arXiv:2506\.12751\.
- \[14\]O\. Kallenberg\.*Foundations of Modern Probability*\. Springer, 1997\. Lemma 2\.22\.
- \[15\]K\. Kuratowski and C\. Ryll\-Nardzewski\. A general theorem on selectors\.*Bull\. Acad\. Polon\. Sci\.*, 13:397–403, 1965\.

## Appendix AProofs for Sections[2](https://arxiv.org/html/2609.10981#S2)and[4](https://arxiv.org/html/2609.10981#S4)

###### Proof of Lemma[2\.1](https://arxiv.org/html/2609.10981#S2.Thmtheorem1)\.

Letwi=ξ⁡\(ℱi\)w\_\{i\}=\\xi\(\\mathcal\{F\}\_\{i\}\), discard pieces withwi=0w\_\{i\}=0, letξi\\xi\_\{i\}be the conditional law onℱi\\mathcal\{F\}\_\{i\}, andJi=𝔼ξi⊗ξi​\[\(f⁡\(xg\)−f¯​\(xg\)\)2\]J\_\{i\}=\\mathbb\{E\}\_\{\\xi\_\{i\}\\otimes\\xi\_\{i\}\}\[\(f\(x\_\{g\}\)\-\\bar\{f\}\(x\_\{g\}\)\)^\{2\}\]\. Taking expectations of the hypothesis overkkindependent draws fromξi\\xi\_\{i\}givessupf∈ℱi\(f¯​\(xf\)−f⋆\)≤α\+β0​k​\(k−1\)​Ji\\sup\_\{f\\in\\mathcal\{F\}\_\{i\}\}\(\\bar\{f\}\(x\_\{f\}\)\-f^\{\\star\}\)\\leq\\alpha\+\\sqrt\{\\beta\_\{0\}k\(k\-1\)J\_\{i\}\}\. Hence

Δ⁡\(πTSξ,ξ\)\\displaystyle\\Delta\(\\pi^\{\\xi\}\_\{\\mathrm\{TS\}\},\\xi\)=∑iwi​𝔼ξi​\[f¯​\(xf\)−f⋆\]≤α\+β0​k​\(k−1\)​∑iwi​Ji\\displaystyle=\\sum\_\{i\}w\_\{i\}\\,\\mathbb\{E\}\_\{\\xi\_\{i\}\}\[\\bar\{f\}\(x\_\{f\}\)\-f^\{\\star\}\]\\leq\\alpha\+\\sqrt\{\\beta\_\{0\}k\(k\-1\)\}\\sum\_\{i\}w\_\{i\}\\sqrt\{J\_\{i\}\}≤α\+β0​k​\(k−1\)​m​∑iwi2​Ji≤α\+β0​k​\(k−1\)​m​I​\(πTSξ,ξ\),\\displaystyle\\leq\\alpha\+\\sqrt\{\\beta\_\{0\}k\(k\-1\)m\\textstyle\\sum\_\{i\}w\_\{i\}^\{2\}J\_\{i\}\}\\leq\\alpha\+\\sqrt\{\\beta\_\{0\}k\(k\-1\)m\\,I\(\\pi^\{\\xi\}\_\{\\mathrm\{TS\}\},\\xi\)\},by Cauchy–Schwarz and becauseI⁡\(πTSξ,ξ\)=∑i,jwi​wj​Ji​j≥∑iwi2​JiI\(\\pi^\{\\xi\}\_\{\\mathrm\{TS\}\},\\xi\)=\\sum\_\{i,j\}w\_\{i\}w\_\{j\}J\_\{ij\}\\geq\\sum\_\{i\}w\_\{i\}^\{2\}J\_\{i\}withJi​j=𝔼ξi⊗ξj​\[\(f⁡\(xg\)−f¯​\(xg\)\)2\]≥0J\_\{ij\}=\\mathbb\{E\}\_\{\\xi\_\{i\}\\otimes\\xi\_\{j\}\}\[\(f\(x\_\{g\}\)\-\\bar\{f\}\(x\_\{g\}\)\)^\{2\}\]\\geq 0\. ∎

###### Proof of Lemma[4\.1](https://arxiv.org/html/2609.10981#S4.Thmtheorem1)\.

Ifffis constant, any unitθ\\thetaand the constant link work\. Otherwise normalise the ridge direction and letuube the link onI=\{⟨x,θ⟩:x∈K\}=\[a,b\]I=\\\{\\langle x,\\theta\\rangle:x\\in K\\\}=\[a,b\]\. Fort∈\(a,b\)t\\in\(a,b\)there isz∈int​Kz\\in\\mathrm\{int\}\\,Kwith⟨z,θ⟩=t\\langle z,\\theta\\rangle=tand a short segment throughzzin directionθ\\thetainsideKK, along whichffis11\-Lipschitz, souuis locally11\-Lipschitz on\(a,b\)\(a,b\)and, by continuity of convex functions,11\-Lipschitz onII\. Defineℓ⁡\(t\)=u⁡\(a\)\+a−t\\ell\(t\)=u\(a\)\+a\-tfort<at<a,ℓ=u\\ell=uonII, andℓ⁡\(t\)=u⁡\(b\)\+t−b\\ell\(t\)=u\(b\)\+t\-bfort\>bt\>b\. The slopes−1\-1on the left and\+1\+1on the right bracket every secant slope ofuu, soℓ\\ellis convex and11\-Lipschitz; outsideIIit exceeds the endpoint values, sominℝ⁡ℓ=minI⁡u=f⋆\\min\_\{\\mathbb\{R\}\}\\ell=\\min\_\{I\}u=f^\{\\star\}, attained at the projections of the minimisers offf\. The last claim is the11\-Lipschitz property ofℓ\\ell\. ∎

###### Proof of Lemma[4\.2](https://arxiv.org/html/2609.10981#S4.Thmtheorem2)\.

Uninformativeness and the comparison condition givef⁡\(xg\)\>f¯​\(xg\)−δ≥f¯​\(xf\)−2​δ=f⋆\+rf−2​δ≥f⋆\+ε/2−2​δf\(x\_\{g\}\)\>\\bar\{f\}\(x\_\{g\}\)\-\\delta\\geq\\bar\{f\}\(x\_\{f\}\)\-2\\delta=f^\{\\star\}\+r\_\{f\}\-2\\delta\\geq f^\{\\star\}\+\\varepsilon/2\-2\\delta; with11\-Lipschitzness ofℓf\\ell\_\{f\}this is \(i\), andε/2−2​δ≥5​ε/12\\varepsilon/2\-2\\delta\\geq 5\\varepsilon/12becausec≥12c\\geq 12\. For \(ii\) takeggwithtg\>st\_\{g\}\>sand lethhattainth=bt\_\{h\}=b\(soh≠fh\\neq fandb\>sb\>s\)\. Withλ=\(b−tg\)/\(b−s\)∈\[0,1\)\\lambda=\(b\-t\_\{g\}\)/\(b\-s\)\\in\[0,1\), convexity ofℓf\\ell\_\{f\}givesf⁡\(xg\)≤λ​f⋆\+\(1−λ\)​f​\(xh\)f\(x\_\{g\}\)\\leq\\lambda f^\{\\star\}\+\(1\-\\lambda\)f\(x\_\{h\}\)\. Usingf⋆≤f¯​\(xg\)\+δ−ε/2f^\{\\star\}\\leq\\bar\{f\}\(x\_\{g\}\)\+\\delta\-\\varepsilon/2andf⁡\(xh\)<f¯​\(xh\)\+δ≤f¯​\(xg\)\+2​δf\(x\_\{h\}\)<\\bar\{f\}\(x\_\{h\}\)\+\\delta\\leq\\bar\{f\}\(x\_\{g\}\)\+2\\delta,

f⁡\(xg\)<f¯​\(xg\)\+2​δ−λ⁡\(ε/2\+δ\),f\(x\_\{g\}\)<\\bar\{f\}\(x\_\{g\}\)\+2\\delta\-\\lambda\(\\varepsilon/2\+\\delta\),and combining withf⁡\(xg\)\>f¯​\(xg\)−δf\(x\_\{g\}\)\>\\bar\{f\}\(x\_\{g\}\)\-\\deltayieldsλ<η\\lambda<\\eta\. The left side is symmetric\. ∎

## Appendix BProofs for Sections[5](https://arxiv.org/html/2609.10981#S5)and[6](https://arxiv.org/html/2609.10981#S6)

###### Proof of Lemma[5\.1](https://arxiv.org/html/2609.10981#S5.Thmtheorem1)\.

For symmetricMMthe second claim is\[[8](https://arxiv.org/html/2609.10981#bib.bib8), Lemma 2\.2\], which Alon attributes to earlier sources; the trace–rank inequality for arbitrary real matrices also appears as\[[7](https://arxiv.org/html/2609.10981#bib.bib7), Fact 10\], and we include the short argument\. LetΠ\\Pibe the orthogonal projection onto the column space ofMM, of rankq=rank​Mq=\\mathrm\{rank\}M\. Then\|tr​M\|=\|tr⁡\(Π​M\)\|=\|⟨Π,M⟩F\|≤∥Π∥F​∥M∥F=q​∥M∥F\|\\mathrm\{tr\}M\|=\|\\mathrm\{tr\}\(\\Pi M\)\|=\|\\langle\\Pi,M\\rangle\_\{F\}\|\\leq\\lVert\\Pi\\rVert\_\{F\}\\lVert M\\rVert\_\{F\}=\\sqrt\{q\}\\lVert M\\rVert\_\{F\}\. Insertingtr​M=N\\mathrm\{tr\}M=Nand∥M∥F2≤N\+N⁡\(N−1\)​t2\\lVert M\\rVert\_\{F\}^\{2\}\\leq N\+N\(N\-1\)t^\{2\}gives the second claim\. For the third,\(Q\+1\)−Q⁡\(1−t2\)/\(1−Q​t2\)=\(1−Q2​t2\)/\(1−Q​t2\)\>0\(Q\+1\)\-Q\(1\-t^\{2\}\)/\(1\-Qt^\{2\}\)=\(1\-Q^\{2\}t^\{2\}\)/\(1\-Qt^\{2\}\)\>0whent<1/Qt<1/Q, soN<Q\+1N<Q\+1\. ∎

###### Proof of Lemma[5\.3](https://arxiv.org/html/2609.10981#S5.Thmtheorem3)\.

Supposerank​B≥2​r\\mathrm\{rank\}B\\geq 2rand take a non\-singular2​r×2​r2r\\times 2rsubmatrixB0B\_\{0\}ofBB; letA0A\_\{0\}be the corresponding submatrix ofAAandE=B0−A0E=B\_\{0\}\-A\_\{0\}, sorank​A0≤r\\mathrm\{rank\}A\_\{0\}\\leq rand∥E∥F2≤4​r2​γ2\\lVert E\\rVert\_\{F\}^\{2\}\\leq 4r^\{2\}\\gamma^\{2\}\. Letσ1≥⋯≥σ2​r\>0\\sigma\_\{1\}\\geq\\dots\\geq\\sigma\_\{2r\}\>0be the singular values ofB0B\_\{0\}\. Sincedimker⁡A0≥r\\dim\\ker A\_\{0\}\\geq r, letΠ\\Pibe the orthogonal projection onto anrr\-dimensional subspace ofker⁡A0\\ker A\_\{0\}; thenB0​Π=E​ΠB\_\{0\}\\Pi=E\\Pi, so∥B0​Π∥F2≤∥E∥F2\\lVert B\_\{0\}\\Pi\\rVert\_\{F\}^\{2\}\\leq\\lVert E\\rVert\_\{F\}^\{2\}\. In an orthonormal basis of right singular vectors ofB0B\_\{0\},∥B0​Π∥F2=∑kσk2​wk\\lVert B\_\{0\}\\Pi\\rVert\_\{F\}^\{2\}=\\sum\_\{k\}\\sigma\_\{k\}^\{2\}w\_\{k\}with0≤wk≤10\\leq w\_\{k\}\\leq 1and∑kwk=r\\sum\_\{k\}w\_\{k\}=r, which is at least the sum of therrsmallestσk2\\sigma\_\{k\}^\{2\}\. Hence

∑k=r\+12​rσk2≤4​r2​γ2,∑k=1rσk2≤∥B0∥F2≤4​r2−1,\\sum\_\{k=r\+1\}^\{2r\}\\sigma\_\{k\}^\{2\}\\leq 4r^\{2\}\\gamma^\{2\},\\qquad\\sum\_\{k=1\}^\{r\}\\sigma\_\{k\}^\{2\}\\leq\\lVert B\_\{0\}\\rVert\_\{F\}^\{2\}\\leq 4r^\{2\}\-1,the latter because a non\-singular2​r×2​r2r\\times 2r00\-11matrix has at least one zero entry\. By the arithmetic–geometric mean inequality applied to each group ofrrsquared singular values,

\|detB0\|=∏k=12​rσk≤\(4​r2−1r⋅4​r2​γ2r\)r/2=\(4​r​γ\)r​\(1−14​r2\)r/2<1for​γ≤14​r,\|\\det B\_\{0\}\|=\\prod\_\{k=1\}^\{2r\}\\sigma\_\{k\}\\leq\\Big\(\\frac\{4r^\{2\}\-1\}\{r\}\\cdot\\frac\{4r^\{2\}\\gamma^\{2\}\}\{r\}\\Big\)^\{r/2\}=\(4r\\gamma\)^\{r\}\\Big\(1\-\\frac\{1\}\{4r^\{2\}\}\\Big\)^\{r/2\}<1\\qquad\\text\{for \}\\gamma\\leq\\frac\{1\}\{4r\},contradicting\|detB0\|≥1\|\\det B\_\{0\}\|\\geq 1for a non\-singular integer matrix\. ∎

###### Proof of Lemma[6\.1](https://arxiv.org/html/2609.10981#S6.Thmtheorem1)\.

As long as the remaining set has more thanGGelements it is not uninformative, so it contains an ordered pair\(f,g\)\(f,g\)with\|f⁡\(xg\)−f¯​\(xg\)\|≥δ\|f\(x\_\{g\}\)\-\\bar\{f\}\(x\_\{g\}\)\|\\geq\\delta; deleteff\(only the first endpoint\)\. The hypotheses of Definition[3\.2](https://arxiv.org/html/2609.10981#S3.Thmtheorem2)are per\-element and pairwise, so they survive deletion, and before the\(j\+1\)\(j\+1\)\-st deletion \(0≤j≤q−10\\leq j\\leq q\-1\) at leastG\+q−j≥G\+1G\+q\-j\\geq G\+1elements remain\. Theqqrecorded ordered pairs have distinct first endpoints, hence are distinct, and each contributes at leastδ2\\delta^\{2\}\. ∎

## Appendix CProofs for Section[7](https://arxiv.org/html/2609.10981#S7)

###### Proof of Lemma[7\.1](https://arxiv.org/html/2609.10981#S7.Thmtheorem1)\.

By the randomisation lemma for kernels into Borel spaces\[[14](https://arxiv.org/html/2609.10981#bib.bib14), Lemma 2\.22\]there is a jointly measurablea⁡\(f,u\)a\(f,u\)withX=a⁡\(f,U\)X=a\(f,U\)forUUuniform on\[0,1\]\[0,1\]independent offf\. Leta0a\_\{0\}be a fixed measurable selection,B=\{\(f,u\):f⁡\(a⁡\(f,u\)\)\>f⋆\}B=\\\{\(f,u\):f\(a\(f,u\)\)\>f^\{\\star\}\\\}, anda~=a\\tilde\{a\}=aoffBB,a~=a0\\tilde\{a\}=a\_\{0\}onBB; thena~\\tilde\{a\}is jointly measurable,f↦a~​\(f,u\)f\\mapsto\\tilde\{a\}\(f,u\)is a measurable selection for everyuu, and\(f,a~​\(f,U\)\)\(f,\\tilde\{a\}\(f,U\)\)has the same law as\(f,X\)\(f,X\)\. Letπu\\pi\_\{u\}be the law ofa~​\(f,u\)\\tilde\{a\}\(f,u\)\. BothΔ⁡\(⋅,ξ\)\\Delta\(\\cdot,\\xi\)andI⁡\(⋅,ξ\)I\(\\cdot,\\xi\)are linear in the policy, soΔ⁡\(ℒ⁡\(X\),ξ\)=∫Δ⁡\(πu,ξ\)​𝑑u≤α\+∫β​I​\(πu,ξ\)​𝑑u≤α\+β​∫I⁡\(πu,ξ\)​𝑑u\\Delta\(\\mathcal\{L\}\(X\),\\xi\)=\\int\\Delta\(\\pi\_\{u\},\\xi\)\\,du\\leq\\alpha\+\\int\\sqrt\{\\beta I\(\\pi\_\{u\},\\xi\)\}\\,du\\leq\\alpha\+\\sqrt\{\\beta\\int I\(\\pi\_\{u\},\\xi\)\\,du\}by concavity of the square root\. ∎

###### Proof of Lemma[7\.2](https://arxiv.org/html/2609.10981#S7.Thmtheorem2)\.

For\(X,h\)∼π⊗ν\(X,h\)\\sim\\pi\\otimes\\nuone hash¯​\(X\)=𝔼​\[h​\(X\)∣X\]\\bar\{h\}\(X\)=\\mathbb\{E\}\[h\(X\)\\mid X\], soI​\(π,ν\)1/2=∥h⁡\(X\)−𝔼⁡\[h⁡\(X\)∣X\]∥L2I\(\\pi,\\nu\)^\{1/2\}=\\lVert h\(X\)\-\\mathbb\{E\}\[h\(X\)\\mid X\]\\rVert\_\{L^\{2\}\}\. \(a\): realiseX∼πX\\sim\\piindependently of the coupled pair\(f,g\)\(f,g\)and letQ​W=W−𝔼⁡\[W∣X\]QW=W\-\\mathbb\{E\}\[W\\mid X\], anL2L^\{2\}contraction; thenI⁡\(π,ℒ⁡\(f\)\)=∥Q​f​\(X\)∥L2\\sqrt\{I\(\\pi,\\mathcal\{L\}\(f\)\)\}=\\lVert Qf\(X\)\\rVert\_\{L^\{2\}\},I⁡\(π,ℒ⁡\(g\)\)=∥Q​g​\(X\)∥L2\\sqrt\{I\(\\pi,\\mathcal\{L\}\(g\)\)\}=\\lVert Qg\(X\)\\rVert\_\{L^\{2\}\}, and the two differ by at most∥Q⁡\(g⁡\(X\)−f⁡\(X\)\)∥L2≤∥g⁡\(X\)−f⁡\(X\)∥L2≤ρ\\lVert Q\(g\(X\)\-f\(X\)\)\\rVert\_\{L^\{2\}\}\\leq\\lVert g\(X\)\-f\(X\)\\rVert\_\{L^\{2\}\}\\leq\\rho\. \(b\): realiseh∼νh\\sim\\nuindependently of the coupled pair\(X,Z\)\(X,Z\)and use the single centring operatorQW=W−𝔼\[W∣X,Z\]QW=W\-\\mathbb\{E\}\[W\\mid X,Z\]; independence givesQ​h​\(X\)=h​\(X\)−h¯​\(X\)Qh\(X\)=h\(X\)\-\\bar\{h\}\(X\)andQ​h​\(Z\)=h​\(Z\)−h¯​\(Z\)Qh\(Z\)=h\(Z\)\-\\bar\{h\}\(Z\), soI⁡\(ℒ⁡\(Z\),ν\)\\sqrt\{I\(\\mathcal\{L\}\(Z\),\\nu\)\}andI⁡\(ℒ⁡\(X\),ν\)\\sqrt\{I\(\\mathcal\{L\}\(X\),\\nu\)\}differ by at most∥Q⁡\(h⁡\(Z\)−h⁡\(X\)\)∥L2≤∥h⁡\(Z\)−h⁡\(X\)∥L2≤ρ\\lVert Q\(h\(Z\)\-h\(X\)\)\\rVert\_\{L^\{2\}\}\\leq\\lVert h\(Z\)\-h\(X\)\\rVert\_\{L^\{2\}\}\\leq\\rhoby the Lipschitz bound\. \(c\): letg=max⁡\(f,f⁡\(X\)\)g=\\max\(f,f\(X\)\); truncation at a level in\[0,1\]\[0,1\]preserves convexity, range, Lipschitzness and the ridge direction, sog∈ℱblrg\\in\\mathcal\{F\}\_\{\\mathrm\{blr\}\};XXis an exact minimiser ofgg,∥g−f∥∞≤ρ\\lVert g\-f\\rVert\_\{\\infty\}\\leq\\rho,f¯≤g¯\\bar\{f\}\\leq\\bar\{g\}andf⋆≥g⋆−ρf^\{\\star\}\\geq g^\{\\star\}\-\\rho\. Since\(f,X\)\(f,X\)takes finitely many values,\(g,X\)\(g,X\)is a finitely\-valued measurable kernel of exact minimisers \(distinct values of\(f,X\)\(f,X\)may shareggbut notXX, which is why a kernel rather than a selection is needed\), and Lemma[7\.1](https://arxiv.org/html/2609.10981#S7.Thmtheorem1)givesΔ⁡\(ℒ⁡\(X\),ℒ⁡\(f\)\)≤Δ⁡\(ℒ⁡\(X\),ℒ⁡\(g\)\)\+ρ≤α\+β​I​\(ℒ⁡\(X\),ℒ⁡\(g\)\)\+ρ\\Delta\(\\mathcal\{L\}\(X\),\\mathcal\{L\}\(f\)\)\\leq\\Delta\(\\mathcal\{L\}\(X\),\\mathcal\{L\}\(g\)\)\+\\rho\\leq\\alpha\+\\sqrt\{\\beta I\(\\mathcal\{L\}\(X\),\\mathcal\{L\}\(g\)\)\}\+\\rho\. Finally, sinceI⁡\(π,ν\)I\(\\pi,\\nu\)depends only on the marginal law of the policy and the marginal law of the random function, part \(a\) may be applied on a product coupling in which an independentX′∼ℒ⁡\(X\)X^\{\\prime\}\\sim\\mathcal\{L\}\(X\)is used together with the coupled pair\(f,g\)\(f,g\),∥g−f∥∞≤ρ\\lVert g\-f\\rVert\_\{\\infty\}\\leq\\rho; this givesI⁡\(ℒ⁡\(X\),ℒ⁡\(g\)\)≤I⁡\(ℒ⁡\(X\),ℒ⁡\(f\)\)\+ρ\\sqrt\{I\(\\mathcal\{L\}\(X\),\\mathcal\{L\}\(g\)\)\}\\leq\\sqrt\{I\(\\mathcal\{L\}\(X\),\\mathcal\{L\}\(f\)\)\}\+\\rhoand finishes the proof\. ∎

###### Proof of Lemma[7\.3](https://arxiv.org/html/2609.10981#S7.Thmtheorem3)\.

A unit vectorθ\\thetais a ridge direction offfif and only if\|f⁡\(x\)−f⁡\(y\)\|≤\|⟨θ,x−y⟩\|\|f\(x\)\-f\(y\)\|\\leq\|\\langle\\theta,x\-y\\rangle\|for allx,y∈Kx,y\\in K\(the forward direction is Lemma[4\.1](https://arxiv.org/html/2609.10981#S4.Thmtheorem1), the backward direction yields a profile that is constant on fibres, convex and11\-Lipschitz\)\. LetΦ⁡\(f\)\\Phi\(f\)be the set of suchθ\\theta\. Profiles extended as in Lemma[4\.1](https://arxiv.org/html/2609.10981#S4.Thmtheorem1)satisfyℓ⁡\(0\)=f⁡\(0\)∈\[0,1\]\\ell\(0\)=f\(0\)\\in\[0,1\]andLip⁡\(ℓ\)≤1\\mathrm\{Lip\}\(\\ell\)\\leq 1, so they are uniformly bounded and equicontinuous on\[−D,D\]\[\-D,D\]; iffj→ff\_\{j\}\\to funiformly andθj→θ\\theta\_\{j\}\\to\\theta, a uniformly convergent subsequence of profiles showsf=ℓ⁡\(⟨⋅,θ⟩\)f=\\ell\(\\langle\\cdot,\\theta\\rangle\)\. Henceℱblr\\mathcal\{F\}\_\{\\mathrm\{blr\}\}is compact inC⁡\(K\)C\(K\)\(Arzelà–Ascoli\) and the graph ofΦ\\Phiis closed inℱblr×Sd−1\\mathcal\{F\}\_\{\\mathrm\{blr\}\}\\times S^\{d\-1\}, soΦ\\Phihas non\-empty closed values\. For an openO⊆Sd−1O\\subseteq S^\{d\-1\}writeO=⋃jCjO=\\bigcup\_\{j\}C\_\{j\}withCjC\_\{j\}compact; then\{f:Φ⁡\(f\)∩O≠∅\}=⋃jproj⁡\(Graph⁡\(Φ\)∩\(ℱblr×Cj\)\)\\\{f:\\Phi\(f\)\\cap O\\neq\\emptyset\\\}=\\bigcup\_\{j\}\\mathrm\{proj\}\(\\mathrm\{Graph\}\(\\Phi\)\\cap\(\\mathcal\{F\}\_\{\\mathrm\{blr\}\}\\times C\_\{j\}\)\)is a countable union of compact sets, hence Borel, soΦ\\Phiis weakly measurable and the Kuratowski–Ryll\-Nardzewski selection theorem\[[15](https://arxiv.org/html/2609.10981#bib.bib15)\]gives a Borel selectionθf∈Φ⁡\(f\)\\theta\_\{f\}\\in\\Phi\(f\)\. The mapLLsatisfies\|L⁡\(f,θ,t\)−L⁡\(g,ψ,s\)\|≤∥f−g∥∞\+D⁡∥θ−ψ∥\+\|t−s\|\|L\(f,\\theta,t\)\-L\(g,\\psi,s\)\|\\leq\\lVert f\-g\\rVert\_\{\\infty\}\+D\\lVert\\theta\-\\psi\\rVert\+\|t\-s\|, hence is jointly continuous, and forθ∈Φ⁡\(f\)\\theta\\in\\Phi\(f\)it coincides with the profile offfon the projection interval and with the∓1\\mp 1\-slope extension of Lemma[4\.1](https://arxiv.org/html/2609.10981#S4.Thmtheorem1)outside it\. ∎

###### Proof of Lemma[7\.4](https://arxiv.org/html/2609.10981#S7.Thmtheorem4)\.

\(i\) Averages of convex ridge functions with a common direction are convex ridge functions with that direction; range and Lipschitz bounds are preserved; and ifgν=∫g​𝑑νg\_\{\\nu\}=\\int g\\,d\\nuthengν​\(x\)≤∫g⋆​𝑑ν\+2​ρ≤gν⋆\+2​ρg\_\{\\nu\}\(x\)\\leq\\int g^\{\\star\}d\\nu\+2\\rho\\leq g\_\{\\nu\}^\{\\star\}\+2\\rhosince the minimum of an average is at least the average of the minima\. \(ii\) Letθf\\theta\_\{f\}andLLbe as in Lemma[7\.3](https://arxiv.org/html/2609.10981#S7.Thmtheorem3)and letκ⁡\(f\)\\kappa\(f\)be the first pair in a fixed enumeration ofCK×CSC\_\{K\}\\times C\_\{S\}with∥xκ−xf∥≤ρ\\lVert x\_\{\\kappa\}\-x\_\{f\}\\rVert\\leq\\rhoand∥θκ−θf∥≤ρ/\(2​D\)\\lVert\\theta\_\{\\kappa\}\-\\theta\_\{f\}\\rVert\\leq\\rho/\(2D\); sincexfx\_\{f\}is𝒜\\mathcal\{A\}\-measurable andθf\\theta\_\{f\}is Borel,κ\\kappais𝒜\\mathcal\{A\}\-measurable\. Define

gf​\(x\)=L⁡\(f,θκ,⟨x,θκ⟩\)=miny∈K⁡\[f⁡\(y\)\+\|⟨θκ,x−y⟩\|\]\.g\_\{f\}\(x\)=L\(f,\\theta\_\{\\kappa\},\\langle x,\\theta\_\{\\kappa\}\\rangle\)=\\min\_\{y\\in K\}\\big\[f\(y\)\+\|\\langle\\theta\_\{\\kappa\},x\-y\\rangle\|\\big\]\.The profilet↦L⁡\(f,θκ,t\)t\\mapsto L\(f,\\theta\_\{\\kappa\},t\)is convex \(the minimand is jointly convex in\(t,y\)\(t,y\)and partial minimisation over the convex setKKpreserves convexity\) and11\-Lipschitz \(eachyycontributes a11\-Lipschitz function oftt\), sogfg\_\{f\}is a convex ridge function in directionθκ\\theta\_\{\\kappa\}withLip⁡\(gf\)≤1\\mathrm\{Lip\}\(g\_\{f\}\)\\leq 1\. Takingy=xy=xgivesgf≤f≤1g\_\{f\}\\leq f\\leq 1, andf≥f⋆f\\geq f^\{\\star\}givesgf≥f⋆≥0g\_\{f\}\\geq f^\{\\star\}\\geq 0; hencegf∈ℱblrg\_\{f\}\\in\\mathcal\{F\}\_\{\\mathrm\{blr\}\}with no rescaling\. By Lemma[4\.1](https://arxiv.org/html/2609.10981#S4.Thmtheorem1), for allx,y∈Kx,y\\in K,f⁡\(x\)−f⁡\(y\)≤\|⟨θf,x−y⟩\|≤\|⟨θκ,x−y⟩\|\+D⁡∥θκ−θf∥≤\|⟨θκ,x−y⟩\|\+ρ/2f\(x\)\-f\(y\)\\leq\|\\langle\\theta\_\{f\},x\-y\\rangle\|\\leq\|\\langle\\theta\_\{\\kappa\},x\-y\\rangle\|\+D\\lVert\\theta\_\{\\kappa\}\-\\theta\_\{f\}\\rVert\\leq\|\\langle\\theta\_\{\\kappa\},x\-y\\rangle\|\+\\rho/2\(using∥x−y∥≤D\\lVert x\-y\\rVert\\leq D\); minimising overyygivesf⁡\(x\)−ρ/2≤gf​\(x\)≤f⁡\(x\)f\(x\)\-\\rho/2\\leq g\_\{f\}\(x\)\\leq f\(x\), i\.e\.∥gf−f∥∞≤ρ/2\\lVert g\_\{f\}\-f\\rVert\_\{\\infty\}\\leq\\rho/2\. At the selected minimiser,f⋆≤gf​\(xf\)≤f⁡\(xf\)=f⋆f^\{\\star\}\\leq g\_\{f\}\(x\_\{f\}\)\\leq f\(x\_\{f\}\)=f^\{\\star\}, soxfx\_\{f\}minimisesgfg\_\{f\}andgf⋆=f⋆g\_\{f\}^\{\\star\}=f^\{\\star\}; by11\-Lipschitznessgf​\(xκ\)−gf⋆≤∥xκ−xf∥≤ρ≤2​ρg\_\{f\}\(x\_\{\\kappa\}\)\-g\_\{f\}^\{\\star\}\\leq\\lVert x\_\{\\kappa\}\-x\_\{f\}\\rVert\\leq\\rho\\leq 2\\rho, sogf∈ℱκ⁡\(f\)valg\_\{f\}\\in\\mathcal\{F\}^\{\\mathrm\{val\}\}\_\{\\kappa\(f\)\}\. Finallyf↦gff\\mapsto g\_\{f\}is measurable as a\(C⁡\(K\),ℬ\)\(C\(K\),\\mathcal\{B\}\)\-valued map and\(f,x\)↦gf​\(x\)\(f,x\)\\mapsto g\_\{f\}\(x\)is jointly measurable, by the joint continuity ofLLand the measurability ofκ\\kappa\. ∎

###### Proof of Theorem[7\.5](https://arxiv.org/html/2609.10981#S7.Thmtheorem5)\.

We bound the one\-step regret under an arbitrary posterior and then sum\. Letf∼ξf\\sim\\xi\(a posterior at some round\),X⋆=xfX^\{\\star\}=x\_\{f\}, and letXXbe an independent copy ofX⋆X^\{\\star\}, soℒ⁡\(X\)=πTS\\mathcal\{L\}\(X\)=\\pi\_\{\\mathrm\{TS\}\}\. Letκ=κ⁡\(f\)\\kappa=\\kappa\(f\),g=gfg=g\_\{f\},z=xκz=x\_\{\\kappa\}be as in Lemma[7\.4](https://arxiv.org/html/2609.10981#S7.Thmtheorem4), and

Hκ=𝔼⁡\[f∣κ\],Gκ=𝔼⁡\[g∣κ\],νG=ℒ⁡\(Gκ\),πz=ℒ⁡\(z\)\.H\_\{\\kappa\}=\\mathbb\{E\}\[f\\mid\\kappa\],\\qquad G\_\{\\kappa\}=\\mathbb\{E\}\[g\\mid\\kappa\],\\qquad\\nu\_\{G\}=\\mathcal\{L\}\(G\_\{\\kappa\}\),\\qquad\\pi\_\{z\}=\\mathcal\{L\}\(z\)\.BothHκH\_\{\\kappa\}andGκG\_\{\\kappa\}take finitely many values \(one per label\)\.GκG\_\{\\kappa\}is a finitely\-valued\(ℱblr,𝒜\)\(\\mathcal\{F\}\_\{\\mathrm\{blr\}\},\\mathcal\{A\}\)\-valued random element;HκH\_\{\\kappa\}is viewed only as a BorelC⁡\(K\)C\(K\)\-valued random element with values inℱbl\\mathcal\{F\}\_\{\\mathrm\{bl\}\}\. By Lemma[7\.4](https://arxiv.org/html/2609.10981#S7.Thmtheorem4)\(i\),Gκ∈ℱblrG\_\{\\kappa\}\\in\\mathcal\{F\}\_\{\\mathrm\{blr\}\}is a ridge function in directionθκ\\theta\_\{\\kappa\}and is2​ρ2\\rho\-near\-minimal atzz;HκH\_\{\\kappa\}is merely a convex11\-Lipschitz functionK→\[0,1\]K\\to\[0,1\]\(an average of ridge functions with nearby but different directions is in general not a ridge function\), and∥Gκ−Hκ∥∞≤ρ/2\\lVert G\_\{\\kappa\}\-H\_\{\\kappa\}\\rVert\_\{\\infty\}\\leq\\rho/2\. In this proof the information\-ratio hypothesis is applied, via Lemmas[7\.1](https://arxiv.org/html/2609.10981#S7.Thmtheorem1)and[7\.2](https://arxiv.org/html/2609.10981#S7.Thmtheorem2)\(c\), to the finitely\-valued flattened proxymax⁡\{Gκ,Gκ​\(z\)\}\\max\\\{G\_\{\\kappa\},G\_\{\\kappa\}\(z\)\\\}, never toHκH\_\{\\kappa\};HκH\_\{\\kappa\}enters only through the continuity statements of Lemma[7\.2](https://arxiv.org/html/2609.10981#S7.Thmtheorem2)\(a\),\(b\), which do not require the ridge structure\.

First,𝔼⁡\[f⋆∣κ\]=𝔼⁡\[f⁡\(X⋆\)∣κ\]≥𝔼⁡\[g⁡\(X⋆\)∣κ\]≥Gκ​\(z\)−ρ≥Gκ⋆−ρ\\mathbb\{E\}\[f^\{\\star\}\\mid\\kappa\]=\\mathbb\{E\}\[f\(X^\{\\star\}\)\\mid\\kappa\]\\geq\\mathbb\{E\}\[g\(X^\{\\star\}\)\\mid\\kappa\]\\geq G\_\{\\kappa\}\(z\)\-\\rho\\geq G\_\{\\kappa\}^\{\\star\}\-\\rho\(usingg≤fg\\leq f,∥X⋆−z∥≤ρ\\lVert X^\{\\star\}\-z\\rVert\\leq\\rhoand Lipschitzness\), and∥𝔼​f−𝔼​g∥∞≤ρ/2\\lVert\\mathbb\{E\}f\-\\mathbb\{E\}g\\rVert\_\{\\infty\}\\leq\\rho/2; hence

Δ⁡\(πTS,ξ\)=𝔼⁡\[f¯​\(X\)−f⋆\]≤𝔼⁡\[g¯​\(X\)−Gκ⋆\]\+32​ρ≤𝔼⁡\[g¯​\(z\)−Gκ⋆\]\+52​ρ=Δ⁡\(πz,νG\)\+52​ρ\.\\Delta\(\\pi\_\{\\mathrm\{TS\}\},\\xi\)=\\mathbb\{E\}\[\\bar\{f\}\(X\)\-f^\{\\star\}\]\\leq\\mathbb\{E\}\[\\bar\{g\}\(X\)\-G\_\{\\kappa\}^\{\\star\}\]\+\\tfrac\{3\}\{2\}\\rho\\leq\\mathbb\{E\}\[\\bar\{g\}\(z\)\-G\_\{\\kappa\}^\{\\star\}\]\+\\tfrac\{5\}\{2\}\\rho=\\Delta\(\\pi\_\{z\},\\nu\_\{G\}\)\+\\tfrac\{5\}\{2\}\\rho\.By Lemma[7\.2](https://arxiv.org/html/2609.10981#S7.Thmtheorem2)\(c\) applied to the finitely\-valued pair\(Gκ,z\)\(G\_\{\\kappa\},z\),Δ⁡\(πz,νG\)≤α\+β​I​\(πz,νG\)\+2​ρ​\(1\+β\)\\Delta\(\\pi\_\{z\},\\nu\_\{G\}\)\\leq\\alpha\+\\sqrt\{\\beta I\(\\pi\_\{z\},\\nu\_\{G\}\)\}\+2\\rho\(1\+\\sqrt\{\\beta\}\)\. The information terms depend only on the product of the marginal laws, so the continuity statements may be applied on a product space: letF1,F2F\_\{1\},F\_\{2\}be independent draws from the current posterior, build\(G1,H1\)=\(Gκ⁡\(F1\),Hκ⁡\(F1\)\)\(G\_\{1\},H\_\{1\}\)=\(G\_\{\\kappa\(F\_\{1\}\)\},H\_\{\\kappa\(F\_\{1\}\)\}\)fromF1F\_\{1\}and\(Z2,A2\)=\(xκ⁡\(F2\),xF2\)\(Z\_\{2\},A\_\{2\}\)=\(x\_\{\\kappa\(F\_\{2\}\)\},x\_\{F\_\{2\}\}\)fromF2F\_\{2\}\. Lemma[7\.2](https://arxiv.org/html/2609.10981#S7.Thmtheorem2)\(a\) with the coupling\(G1,H1\)\(G\_\{1\},H\_\{1\}\),∥G1−H1∥∞≤ρ/2\\lVert G\_\{1\}\-H\_\{1\}\\rVert\_\{\\infty\}\\leq\\rho/2, independent ofZ2∼πzZ\_\{2\}\\sim\\pi\_\{z\}, givesI⁡\(πz,νG\)≤I⁡\(πz,ℒ⁡\(Hκ\)\)\+ρ/2\\sqrt\{I\(\\pi\_\{z\},\\nu\_\{G\}\)\}\\leq\\sqrt\{I\(\\pi\_\{z\},\\mathcal\{L\}\(H\_\{\\kappa\}\)\)\}\+\\rho/2; Lemma[7\.2](https://arxiv.org/html/2609.10981#S7.Thmtheorem2)\(b\) with the coupling\(Z2,A2\)\(Z\_\{2\},A\_\{2\}\),∥Z2−A2∥≤ρ\\lVert Z\_\{2\}\-A\_\{2\}\\rVert\\leq\\rho, independent ofH1∼ℒ⁡\(Hκ\)H\_\{1\}\\sim\\mathcal\{L\}\(H\_\{\\kappa\}\), givesI⁡\(πz,ℒ⁡\(Hκ\)\)≤I⁡\(πTS,ℒ⁡\(Hκ\)\)\+ρ\\sqrt\{I\(\\pi\_\{z\},\\mathcal\{L\}\(H\_\{\\kappa\}\)\)\}\\leq\\sqrt\{I\(\\pi\_\{\\mathrm\{TS\}\},\\mathcal\{L\}\(H\_\{\\kappa\}\)\)\}\+\\rho\. TogetherI⁡\(πz,νG\)≤I⁡\(πTS,ℒ⁡\(Hκ\)\)\+32​ρ\\sqrt\{I\(\\pi\_\{z\},\\nu\_\{G\}\)\}\\leq\\sqrt\{I\(\\pi\_\{\\mathrm\{TS\}\},\\mathcal\{L\}\(H\_\{\\kappa\}\)\)\}\+\\tfrac\{3\}\{2\}\\rho\. Altogether

Δ⁡\(πTS,ξ\)≤α\+β​I​\(πTS,ℒ⁡\(Hκ\)\)\+ρ⁡\(92\+72​β\)≤α\+β​I​\(πTS,ℒ⁡\(Hκ\)\)\+ρ⁡\(6\+4​β\)\.\\Delta\(\\pi\_\{\\mathrm\{TS\}\},\\xi\)\\leq\\alpha\+\\sqrt\{\\beta I\(\\pi\_\{\\mathrm\{TS\}\},\\mathcal\{L\}\(H\_\{\\kappa\}\)\)\}\+\\rho\\big\(\\tfrac\{9\}\{2\}\+\\tfrac\{7\}\{2\}\\sqrt\{\\beta\}\\big\)\\leq\\alpha\+\\sqrt\{\\beta I\(\\pi\_\{\\mathrm\{TS\}\},\\mathcal\{L\}\(H\_\{\\kappa\}\)\)\}\+\\rho\(6\+4\\sqrt\{\\beta\}\)\.For Bernoulli observations,I\(πTS,ℒ\(Hκ\)\)=𝔼\[\(𝔼\[Y∣X\]−𝔼\[Y∣X,κ\]\)2\]≤12𝔼\[KL\(PY\|X,κ∥PY\|X\)\]=12𝖨\(κ;X,Y\)I\(\\pi\_\{\\mathrm\{TS\}\},\\mathcal\{L\}\(H\_\{\\kappa\}\)\)=\\mathbb\{E\}\[\(\\mathbb\{E\}\[Y\\mid X\]\-\\mathbb\{E\}\[Y\\mid X,\\kappa\]\)^\{2\}\]\\leq\\tfrac\{1\}\{2\}\\mathbb\{E\}\[\\mathrm\{KL\}\(P\_\{Y\\mid X,\\kappa\}\\,\\\|\\,P\_\{Y\\mid X\}\)\]=\\tfrac\{1\}\{2\}\\mathsf\{I\}\(\\kappa;X,Y\)by Pinsker’s inequality\. The labelκ=κ⁡\(f\)\\kappa=\\kappa\(f\)is a fixed finite\-valued function of the environment \(it depends on the fixed nets, the fixed direction map of Lemma[7\.3](https://arxiv.org/html/2609.10981#S7.Thmtheorem3)and the fixed selection, not on the round\), so summing over rounds and using the chain rule for mutual information and Cauchy–Schwarz,

BRegn​\(TS,ξ\)≤n​α\+n​ρ​\(6\+4​β\)\+12​β​n​𝔼​∑t𝖨t−1​\(κ,Xt,Yt\)≤n​α\+n​ρ​\(6\+4​β\)\+12​β​n​log⁡Nρ\.∎\\mathrm\{BReg\}\_\{n\}\(\\mathrm\{TS\},\\xi\)\\leq n\\alpha\+n\\rho\(6\+4\\sqrt\{\\beta\}\)\+\\sqrt\{\\tfrac\{1\}\{2\}\\beta n\\,\\mathbb\{E\}\\textstyle\\sum\_\{t\}\\mathsf\{I\}\_\{t\-1\}\(\\kappa;X\_\{t\},Y\_\{t\}\)\}\\leq n\\alpha\+n\\rho\(6\+4\\sqrt\{\\beta\}\)\+\\sqrt\{\\tfrac\{1\}\{2\}\\beta n\\log N\_\{\\rho\}\}\.\\qed

###### Proof of Theorem[3\.1](https://arxiv.org/html/2609.10981#S3.Thmtheorem1)\.

Forn=1n=1the regret is at most1≤71\\leq 7\. Letn≥2n\\geq 2,α=ρ=1/n\\alpha=\\rho=1/n,L=log⁡\(e\+n​d​max⁡\{1,D\}\)L=\\log\(e\+nd\\max\\\{1,D\\\}\), andh=d\+1h=d\+1\. From Theorem[3\.4](https://arxiv.org/html/2609.10981#S3.Thmtheorem4),k=3072​h4k=3072h^\{4\}andm1/n≤4​Lm\_\{1/n\}\\leq 4L, soβ≤12⋅4​L​k=4​3⋅3072​h4​L=12,288​3​h4​L\\sqrt\{\\beta\}\\leq\\sqrt\{12\\cdot 4L\}\\,k=4\\sqrt\{3\}\\cdot 3072\\,h^\{4\}\\sqrt\{L\}=12\{,\}288\\sqrt\{3\}\\,h^\{4\}\\sqrt\{L\}\. From Lemma[7\.4](https://arxiv.org/html/2609.10981#S7.Thmtheorem4),log⁡N1/n≤d​log⁡\(1\+2​n​D\)\+d​log⁡\(1\+8​n​D\)≤8​d​L\\log N\_\{1/n\}\\leq d\\log\(1\+2nD\)\+d\\log\(1\+8nD\)\\leq 8dL\. Theorem[7\.5](https://arxiv.org/html/2609.10981#S7.Thmtheorem5)givesBRegn≤1\+6\+4​β\+β​4​n​d​L≤7\+β​\(4\+2​n​d​L\)≤7\+6​β​n​d​L\\mathrm\{BReg\}\_\{n\}\\leq 1\+6\+4\\sqrt\{\\beta\}\+\\sqrt\{\\beta\}\\sqrt\{4ndL\}\\leq 7\+\\sqrt\{\\beta\}\\,\(4\+2\\sqrt\{ndL\}\)\\leq 7\+6\\sqrt\{\\beta\}\\sqrt\{ndL\}becausen​d​L≥1\\sqrt\{ndL\}\\geq 1, i\.e\.BRegn≤7\+73,728​3​h4​d1/2​n​L\\mathrm\{BReg\}\_\{n\}\\leq 7\+73\{,\}728\\sqrt\{3\}\\,h^\{4\}d^\{1/2\}\\sqrt\{n\}\\,L\. ∎

## Appendix DProofs for Section[8](https://arxiv.org/html/2609.10981#S8)

###### Proof of Proposition[3\.5](https://arxiv.org/html/2609.10981#S3.Thmtheorem5)\.

Letd≥2d\\geq 2,c≥12c\\geq 12,τ=1/\(4​c​\(d\+1\)\)\\tau=1/\(4c\(d\+1\)\)\. Take the standarddd\-simplex with verticesv0,…,vdv\_\{0\},\\dots,v\_\{d\}and barycentric coordinatesλ0,…,λd\\lambda\_\{0\},\\dots,\\lambda\_\{d\}\(translated so that the average of the points below is00\)\. For each ordered pairi≠ji\\neq jletxi​j=\(1−τ\)​vi\+τ​vjx\_\{ij\}=\(1\-\\tau\)v\_\{i\}\+\\tau v\_\{j\}, and letK=conv​\{xi​j\}K=\\mathrm\{conv\}\\\{x\_\{ij\}\\\}\(full\-dimensional, containing00,D≤2D\\leq\\sqrt\{2\}\)\. Letui​j​\(x\)=1−λi​\(x\)\+τ​λj​\(x\)u\_\{ij\}\(x\)=1\-\\lambda\_\{i\}\(x\)\+\\tau\\lambda\_\{j\}\(x\), an affine function, and setv=1/4v=1/4,ε=τ2/\(4​d\)\\varepsilon=\\tau^\{2\}/\(4d\),f¯≡v\\bar\{f\}\\equiv v,su=τ\+τ2s^\{u\}=\\tau\+\\tau^\{2\}, and

fi​j​\(x\)=v−ε\+ε​max⁡\{su−ui​j​\(x\)τ2,ui​j​\(x\)−su1−2​τ2\},xfi​j=xi​j\.f\_\{ij\}\(x\)=v\-\\varepsilon\+\\varepsilon\\max\\Big\\\{\\frac\{s^\{u\}\-u\_\{ij\}\(x\)\}\{\\tau^\{2\}\},\\ \\frac\{u\_\{ij\}\(x\)\-s^\{u\}\}\{1\-2\\tau^\{2\}\}\\Big\\\},\\qquad x\_\{f\_\{ij\}\}=x\_\{ij\}\.Eachfi​jf\_\{ij\}is the maximum of two affine functions, hence a convex ridge function, minimised exactly whereui​j=suu\_\{ij\}=s^\{u\}, in particular atxi​jx\_\{ij\}, with minimumv−εv\-\\varepsilon\. Evaluatingui​ju\_\{ij\}at thed⁡\(d\+1\)d\(d\+1\)points gives exactly the valuesτ\+τ2\\tau\+\\tau^\{2\}\(atxi​jx\_\{ij\}\),τ\\tau\(thed−1d\-1pointsxi​lx\_\{il\}\),1−τ21\-\\tau^\{2\}\(xj​ix\_\{ji\}\),1\+τ−τ21\+\\tau\-\\tau^\{2\}\(xj​lx\_\{jl\}\),1−τ1\-\\tau\(xk​ix\_\{ki\}\),1\+τ21\+\\tau^\{2\}\(xk​jx\_\{kj\}\) and11\(the remaining\(d−1\)​\(d−2\)\(d\-1\)\(d\-2\)points\), so onKKthe values offi​jf\_\{ij\}lie in\[v−ε,v\]\[v\-\\varepsilon,v\], the pointsxi​lx\_\{il\}havefi​j=vf\_\{ij\}=vexactly, and all other cross values satisfy\|fi​j​\(xk​l\)−v\|≤ε​Eτ\|f\_\{ij\}\(x\_\{kl\}\)\-v\|\\leq\\varepsilon E\_\{\\tau\}withEτ=\(2​τ−τ2\)/\(1−2​τ2\)<3​τE\_\{\\tau\}=\(2\\tau\-\\tau^\{2\}\)/\(1\-2\\tau^\{2\}\)<3\\tau\. Sinceδ=ε/\(c⁡\(d\+1\)\)=4​τ​ε\\delta=\\varepsilon/\(c\(d\+1\)\)=4\\tau\\varepsilon, every ordered pair is uninformative; the gaps arerf=εr\_\{f\}=\\varepsilonand the comparison values coincide\. Lipschitzness:∥∇ui​j∥≤\(1\+τ\)​d\\lVert\\nabla u\_\{ij\}\\rVert\\leq\(1\+\\tau\)\\sqrt\{d\}in the standard simplex coordinates, soLip⁡\(fi​j\)≤ε⁡\(1\+τ\)​d/τ2=\(1\+τ\)/\(4​d\)<1\\mathrm\{Lip\}\(f\_\{ij\}\)\\leq\\varepsilon\(1\+\\tau\)\\sqrt\{d\}/\\tau^\{2\}=\(1\+\\tau\)/\(4\\sqrt\{d\}\)<1\. The functions are pairwise distinct because onlyfi​jf\_\{ij\}attainsv−εv\-\\varepsilonatxi​jx\_\{ij\}\. Along its own direction each row sees thed−1d\-1pointsxi​lx\_\{il\}at distanceτ2\\tau^\{2\}inui​ju\_\{ij\}\-coordinates \(the near band; the unit\-direction distances of Lemma[4\.2](https://arxiv.org/html/2609.10981#S4.Thmtheorem2)are these values divided by∥∇ui​j∥\\lVert\\nabla u\_\{ij\}\\rVert\) and the otherd2d^\{2\}points atui​ju\_\{ij\}\-distance about11\(the far band\)\. FinallyD/ε≤2⋅4​d/τ2=64​2​c2​d​\(d\+1\)2D/\\varepsilon\\leq\\sqrt\{2\}\\cdot 4d/\\tau^\{2\}=64\\sqrt\{2\}\\,c^\{2\}d\(d\+1\)^\{2\}; for every0<ε′≤ε0<\\varepsilon^\{\\prime\}\\leq\\varepsilonkeepKK, the selected points and the ridge directions fixed and replace each function byfi​j′=v\+\(ε′/ε\)​\(fi​j−v\)f^\{\\prime\}\_\{ij\}=v\+\(\\varepsilon^\{\\prime\}/\\varepsilon\)\(f\_\{ij\}\-v\), with comparison functionf¯′≡v\\bar\{f\}^\{\\prime\}\\equiv v: the diagonal gaps and the cross errors are multiplied byε′/ε\\varepsilon^\{\\prime\}/\\varepsilonwhile the Lipschitz constants do not increase, so the new configuration is uninformative at scaleε′\\varepsilon^\{\\prime\}\(withδ′=ε′/\(c⁡\(d\+1\)\)\\delta^\{\\prime\}=\\varepsilon^\{\\prime\}/\(c\(d\+1\)\)\) and every larger ratioD/ε′D/\\varepsilon^\{\\prime\}is attained\. The stated parameter cost forc=96​\(d\+1\)c=96\(d\+1\)follows by substitutingτ=1/\(384​\(d\+1\)2\)\\tau=1/\(384\(d\+1\)^\{2\}\)andε=τ2/\(4​d\)\\varepsilon=\\tau^\{2\}/\(4d\); the upper bound is Theorem[3\.3](https://arxiv.org/html/2609.10981#S3.Thmtheorem3)\. Ford=1d=1takeK=\[0,1\]K=\[0,1\],f¯≡1/4\\bar\{f\}\\equiv 1/4,f1=1/4−ε\+ε​xf\_\{1\}=1/4\-\\varepsilon\+\\varepsilon x,f2=1/4−ε\+ε⁡\(1−x\)f\_\{2\}=1/4\-\\varepsilon\+\\varepsilon\(1\-x\)with minimisers0,10,1and0<ε≤1/40<\\varepsilon\\leq 1/4, which requiresD/ε≥4D/\\varepsilon\\geq 4\. The bound\|C\|≤2\|C\|\\leq 2in dimension one follows from Lemma[4\.2](https://arxiv.org/html/2609.10981#S4.Thmtheorem2)\(ii\): ifx1<x2<x3x\_\{1\}<x\_\{2\}<x\_\{3\}are three minimisers of an uninformative configuration, the row ofx1x\_\{1\}seesx2x\_\{2\}in its far band,x2≥x3−η⁡\(x3−x1\)x\_\{2\}\\geq x\_\{3\}\-\\eta\(x\_\{3\}\-x\_\{1\}\), and the row ofx3x\_\{3\}seesx2x\_\{2\}in its far band,x2≤x1\+η⁡\(x3−x1\)x\_\{2\}\\leq x\_\{1\}\+\\eta\(x\_\{3\}\-x\_\{1\}\); together\(1−2​η\)​\(x3−x1\)≤0\(1\-2\\eta\)\(x\_\{3\}\-x\_\{1\}\)\\leq 0, contradictingη<1/2\\eta<1/2\. \(ForD/ε≤5/12D/\\varepsilon\\leq 5/12not even two points fit, since Lemma[4\.2](https://arxiv.org/html/2609.10981#S4.Thmtheorem2)\(i\) forces a distance larger than5​ε/125\\varepsilon/12\.\) ∎

###### Proof of Proposition[3\.6](https://arxiv.org/html/2609.10981#S3.Thmtheorem6)\.

Take the regular tetrahedronv0=12​\(1,1,1\)v\_\{0\}=\\tfrac\{1\}\{2\}\(1,1,1\),v1=12​\(1,−1,−1\)v\_\{1\}=\\tfrac\{1\}\{2\}\(1,\-1,\-1\),v2=12​\(−1,1,−1\)v\_\{2\}=\\tfrac\{1\}\{2\}\(\-1,1,\-1\),v3=12​\(−1,−1,1\)v\_\{3\}=\\tfrac\{1\}\{2\}\(\-1,\-1,1\), soλi​\(x\)=14\+⟨vi,x⟩\\lambda\_\{i\}\(x\)=\\tfrac\{1\}\{4\}\+\\langle v\_\{i\},x\\rangle, and use the configuration of Proposition[3\.5](https://arxiv.org/html/2609.10981#S3.Thmtheorem5)withK=P:=conv​\{xi​j\}K=P:=\\mathrm\{conv\}\\\{x\_\{ij\}\\\}\(a truncated tetrahedron; the twelve points are its vertices\)\. The inscribed ball of the tetrahedronS=conv​\{vi\}S=\\mathrm\{conv\}\\\{v\_\{i\}\\\}isBrB\_\{r\}withr=1/\(2​3\)r=1/\(2\\sqrt\{3\}\), and onBrB\_\{r\}one has0≤λi≤1/20\\leq\\lambda\_\{i\}\\leq 1/2, soBr⊂PB\_\{r\}\\subset P\. Fix a vertexxi​jx\_\{ij\}and letb0=\(1−2​τ\)/\(1−τ\)b\_\{0\}=\(1\-2\\tau\)/\(1\-\\tau\)\. The affine inequalityλi\+b0​λj≤1−τ\\lambda\_\{i\}\+b\_\{0\}\\lambda\_\{j\}\\leq 1\-\\tauis violated byxi​jx\_\{ij\}, holds with equality at its three neighboursxi​kx\_\{ik\}\(k≠i,jk\\neq i,j\) andxj​ix\_\{ji\}, and holds at all other vertices; since the cutting plane meets every edge fromxi​jx\_\{ij\}exactly at a neighbour,P−i​j:=conv\{xk​l:\(k,l\)≠\(i,j\)\}=P∩\{λi\+b0λj≤1−τ\}P\_\{\-ij\}:=\\mathrm\{conv\}\\\{x\_\{kl\}:\(k,l\)\\neq\(i,j\)\\\}=P\\cap\\\{\\lambda\_\{i\}\+b\_\{0\}\\lambda\_\{j\}\\leq 1\-\\tau\\\}\. OnBrB\_\{r\},max⁡\(λi\+b0​λj\)=\(1\+b0\+1\+b02−2​b0/3\)/4≤\(2\+2\)/4<1−τ\\max\(\\lambda\_\{i\}\+b\_\{0\}\\lambda\_\{j\}\)=\\big\(1\+b\_\{0\}\+\\sqrt\{1\+b\_\{0\}^\{2\}\-2b\_\{0\}/3\}\\big\)/4\\leq\(2\+\\sqrt\{2\}\)/4<1\-\\tauforτ≤1/192\\tau\\leq 1/192, which holds for allc≥12c\\geq 12; henceBr⊂P−i​jB\_\{r\}\\subset P\_\{\-ij\}for alli≠ji\\neq j\. Now letζ\>0\\zeta\>0\. BothJζ​\(C\)=P\+BζJ\_\{\\zeta\}\(C\)=P\+B\_\{\\zeta\}andJζ​\(C∖\{fi​j\}\)=P−i​j\+BζJ\_\{\\zeta\}\(C\\setminus\\\{f\_\{ij\}\\\}\)=P\_\{\-ij\}\+B\_\{\\zeta\}containBr\+ζB\_\{r\+\\zeta\}and are contained in the enlarged tetrahedronSζ=\{x:⟨uk,x⟩≤r\+ζ,k=0,…,3\}S\_\{\\zeta\}=\\\{x:\\langle u\_\{k\},x\\rangle\\leq r\+\\zeta,\\ k=0,\\dots,3\\\}, whereuku\_\{k\}are the unit outer normals ofSS, which satisfy∑kuk=0\\sum\_\{k\}u\_\{k\}=0and∑kuk​uk⊤=43​I\\sum\_\{k\}u\_\{k\}u\_\{k\}^\{\\top\}=\\tfrac\{4\}\{3\}I\. If an ellipsoidz\+A​B1z\+AB\_\{1\}\(A≻0A\\succ 0symmetric\) lies inSζS\_\{\\zeta\}then⟨uk,z⟩\+∥A​uk∥≤r\+ζ\\langle u\_\{k\},z\\rangle\+\\lVert Au\_\{k\}\\rVert\\leq r\+\\zetafor eachkk; summing and using∥A​uk∥≥uk⊤​A​uk\\lVert Au\_\{k\}\\rVert\\geq u\_\{k\}^\{\\top\}Au\_\{k\}gives43​tr​A≤4​\(r\+ζ\)\\tfrac\{4\}\{3\}\\mathrm\{tr\}A\\leq 4\(r\+\\zeta\), sodetA≤\(tr​A/3\)3≤\(r\+ζ\)3\\det A\\leq\(\\mathrm\{tr\}A/3\)^\{3\}\\leq\(r\+\\zeta\)^\{3\}\. Hence the maximum\-volume inscribed ellipsoid of both bodies isBr\+ζB\_\{r\+\\zeta\}\(equality in the arithmetic–geometric mean inequality forcesA=\(r\+ζ\)​IA=\(r\+\\zeta\)Iand thenz=0z=0\), and every single\-vertex removal leaves it unchanged\. ∎

## Appendix EA limit of max\-norm rounding

The tolerance1/\(4​r\)1/\(4r\)in Lemma[5\.3](https://arxiv.org/html/2609.10981#S5.Thmtheorem3)has the order1/r1/r\. The following proposition shows that, for arbitrary00\-11matrices, no tolerance of order1/r1/\\sqrt\{r\}can work; it is used only in the discussion of Section[9](https://arxiv.org/html/2609.10981#S9)\.

###### Proposition E\.1\(Max\-norm rounding cannot have a uniform1/r1/\\sqrt\{r\}tolerance\)\.

For everyr=2j−1r=2^\{j\}\-1withj≥2j\\geq 2there areA,B∈ℝ2​r×2​rA,B\\in\\mathbb\{R\}^\{2r\\times 2r\}such thatrank​A=r\\mathrm\{rank\}A=r,BBis a00\-11matrix withrank​B=2​r\\mathrm\{rank\}B=2r, and∥A−B∥max=2/\(r\+1\)\\lVert A\-B\\rVert\_\{\\max\}=2/\(r\+1\)\. Consequently, for every constanta\>0a\>0there are infinitely manyrrfor which the implication “rank​A≤r\\mathrm\{rank\}A\\leq rand∥A−B∥max≤a/r\\lVert A\-B\\rVert\_\{\\max\}\\leq a/\\sqrt\{r\}for a00\-11matrixBBimplyrank​B≤2​r−1\\mathrm\{rank\}B\\leq 2r\-1” fails\.

###### Proof\.

Lets=r\+1=2js=r\+1=2^\{j\}and letSsS\_\{s\}be the Sylvester–Hadamard matrix of orderss, defined byS1=\(1\)S\_\{1\}=\(1\)andS2​m=\(SmSmSm−Sm\)S\_\{2m\}=\\begin\{pmatrix\}S\_\{m\}&S\_\{m\}\\\\ S\_\{m\}&\-S\_\{m\}\\end\{pmatrix\}; it is symmetric with entries±1\\pm 1, its first row and column consist of ones, andSs​Ss⊤=s​IsS\_\{s\}S\_\{s\}^\{\\top\}=sI\_\{s\}\. WriteSs=\(1𝟏⊤𝟏C\)S\_\{s\}=\\begin\{pmatrix\}1&\\mathbf\{1\}^\{\\top\}\\\\ \\mathbf\{1\}&C\\end\{pmatrix\}withCCa symmetricr×rr\\times rmatrix with entries±1\\pm 1\. Orthogonality of each of the rows2,…,s2,\\dots,sto the first row givesC​𝟏=−𝟏C\\mathbf\{1\}=\-\\mathbf\{1\}, and orthogonality among the rows2,…,s2,\\dots,sgivesJ\+C​C⊤=s​IrJ\+CC^\{\\top\}=sI\_\{r\}, whereJ=𝟏𝟏⊤J=\\mathbf\{1\}\\mathbf\{1\}^\{\\top\}; that is,C​C⊤=s​Ir−JCC^\{\\top\}=sI\_\{r\}\-J\. LetW=\(J−C\)/2W=\(J\-C\)/2, a00\-11matrix\. UsingJ​C⊤=𝟏​\(C​𝟏\)⊤=−JJC^\{\\top\}=\\mathbf\{1\}\(C\\mathbf\{1\}\)^\{\\top\}=\-J,

W⁡\(−2s​C⊤\)=−1s​\(J​C⊤−C​C⊤\)=−1s​\(−J−s​Ir\+J\)=Ir,W\\Big\(\-\\frac\{2\}\{s\}C^\{\\top\}\\Big\)=\-\\frac\{1\}\{s\}\\big\(JC^\{\\top\}\-CC^\{\\top\}\\big\)=\-\\frac\{1\}\{s\}\\big\(\-J\-sI\_\{r\}\+J\\big\)=I\_\{r\},soWWis non\-singular withW−1=−2s​C⊤W^\{\-1\}=\-\\tfrac\{2\}\{s\}C^\{\\top\}, whose entries are±2/s\\pm 2/s; hence∥W−1∥max=2/\(r\+1\)\\lVert W^\{\-1\}\\rVert\_\{\\max\}=2/\(r\+1\)\. Now set

A=\(IrWW−1Ir\)=\(IrW−1\)​\(IrW\),B=\(IrW0Ir\)\.A=\\begin\{pmatrix\}I\_\{r\}&W\\\\ W^\{\-1\}&I\_\{r\}\\end\{pmatrix\}=\\begin\{pmatrix\}I\_\{r\}\\\\ W^\{\-1\}\\end\{pmatrix\}\\begin\{pmatrix\}I\_\{r\}&W\\end\{pmatrix\},\\qquad B=\\begin\{pmatrix\}I\_\{r\}&W\\\\ 0&I\_\{r\}\\end\{pmatrix\}\.The factorisation showsrank​A≤r\\mathrm\{rank\}A\\leq r, and the top\-left blockIrI\_\{r\}showsrank​A≥r\\mathrm\{rank\}A\\geq r\.BBis a00\-11matrix, block upper triangular with identity diagonal blocks, sodetB=1\\det B=1andrank​B=2​r\\mathrm\{rank\}B=2r\. FinallyA−BA\-Bhas the single non\-zero blockW−1W^\{\-1\}, so∥A−B∥max=∥W−1∥max=2/\(r\+1\)\\lVert A\-B\\rVert\_\{\\max\}=\\lVert W^\{\-1\}\\rVert\_\{\\max\}=2/\(r\+1\)\. For the consequence,2/\(r\+1\)≤a/r2/\(r\+1\)\\leq a/\\sqrt\{r\}as soon as2​r/\(r\+1\)≤a2\\sqrt\{r\}/\(r\+1\)\\leq a, which holds for all largerrsince2​r/\(r\+1\)→02\\sqrt\{r\}/\(r\+1\)\\to 0\. ∎

The smallest instance isr=3r=3, where the construction givesW=J3−I3W=J\_\{3\}\-I\_\{3\}up to a row permutation, with∥A−B∥max=1/2<1/3\\lVert A\-B\\rVert\_\{\\max\}=1/2<1/\\sqrt\{3\}\. The proposition concerns arbitrary00\-11matrices only; the band\-membership matrices of Section[5](https://arxiv.org/html/2609.10981#S5)have additional structure \(two bands, one of them extremely thin\), and whether that structure admits a rounding statement with a larger tolerance is open\.