Bandits via Additive Quantized Representations

# Bandits via Additive Quantized Representations
Source: [https://arxiv.org/html/2610.02440](https://arxiv.org/html/2610.02440)
###### Abstract

Contextual bandits require balancing nonlinear reward modeling with online efficiency\. Tree ensembles and neural methods capture nonlinearities but require periodic retraining and large replay buffers\. Linear models update efficiently per observation withO⁡\(1\)O\(1\)memory, but are fundamentally restricted to linear reward structures\. We propose Residual Quantization \(RQ\) as a representation layer to bridge this gap\. An offline\-trained RQ codebook maps continuous contexts into discrete centroid assignments acrossℓ\\elllevels, set dynamically through a shadow mechanism\. This enables a spectrum of additive bandit algorithms that achieve nonlinear expressivity with strictly bounded memory\. Across 13 datasets, RQ variants beat their non\-RQ counterparts on 11 of 13 datasets, often by wide margins, while matching doubling\-retrain XGBoost and neural baselines at up to1000×1000\\timesless memory\.

## 1Introduction

In contextual bandits, an agent repeatedly observes a context, selects an action, and receives a reward, learning to improve its choices from each interaction\. Every decision is made once and in real time, so the algorithm should ideally update from each observation as it arrives\.

Tree ensembles[Nilsson et al\. \(2024\)](https://arxiv.org/html/2610.02440#bib.bib24)and neural methods[Zhou et al\. \(2020\)](https://arxiv.org/html/2610.02440#bib.bib13);[Zhang et al\. \(2021\)](https://arxiv.org/html/2610.02440#bib.bib25)capture nonlinear reward structure, but they periodically retrain on a replay buffer that can grow linearly with the horizon\. At five million rounds on a 28\-feature dataset, a doubling\-retrain bandit \(retraining at exponentially spaced intervals on all past data\) consumes over 1 GB of replay memory \(Figure[3](https://arxiv.org/html/2610.02440#S1.F3)\)\. Linear methods \(LinTS[Agrawal and Goyal \(2013\)](https://arxiv.org/html/2610.02440#bib.bib8), LinUCB[Abbasi\-Yadkori et al\. \(2011\)](https://arxiv.org/html/2610.02440#bib.bib9)\) avoid memory and spiky retraining issues, but are structurally restricted to linear rewards\.

This is not a smooth tradeoff\. Practitioners face a binary choice: expressive models with unbounded memory, or bounded memory with linear rewards\. The gap between the two regimes, nonlinear expressiveness at fixed memory cost, is the problem we address\.

Our approach\.We use Residual Quantization \(RQ\)[Chen et al\. \(2010\)](https://arxiv.org/html/2610.02440#bib.bib16)as a bandit representation layer to enable gradient\-boosted reward modeling with fixedO⁡\(1\)O\(1\)memory\. We train an RQ codebook ofℓ\\elllevels withbbcentroids each via unsupervisedkk\-means on unlabeled contexts \(assumed available and cheap\) and freeze it before the bandit starts\. RQ codebooks were originally developed for efficient retrieval; we repurpose them for gradient\-boosted bandits, where we fit a bandit model at each level to predict the*pseudo\-target*, the gap between the observed reward and the cumulative prediction of shallower levels\. Withℓ\\elllevels andbbcentroids, this yieldsbℓb^\{\\ell\}effective cells using onlyℓ​b\\ell bparameters, a potentially exponential compression\. The online phase requires no replay buffer, no retraining, and fixedO⁡\(1\)O\(1\)memory at every horizon\.

The algorithm adapts depth online via a*shadow*mechanism: a shadow model trains at the next depth but does not influence arm selection, so the active model’s performance is unaffected during evaluation\. A statistical test at pre\-committed check times promotes the shadow if it improves prediction; otherwise the method defaults to its initial depth \(Section[2](https://arxiv.org/html/2610.02440#S2)\)\.

We evaluate the architecture across three variants that span the efficiency–robustness spectrum:*TS\-RQ*\(O⁡\(ℓ​K\)O\(\\ell K\)/round\) uses per\-centroid scalar counters with no features, robust and simple\.*SGD\-LinTS\-RQ*\(O⁡\(ℓ​d​K\)O\(\\ell dK\)\) fits diagonal linear models on the context residuals at each level\.*LinTS\-RQ*\(O⁡\(ℓ​d2​K\)O\(\\ell d^\{2\}K\)\) fits full\-covariance LinTS, the quality ceiling, competitive with XGBoost and NeuralCB at1000×1000\\timesless memory when data per parameter suffices \(Section[4\.2](https://arxiv.org/html/2610.02440#S4.SS2)\)\. All three use shadow promotion and maintain fixed memory\.

Contributions\.

1. 1\.*RQ as a bandit model*: we repurpose residual quantization from retrieval to bandits, using the additive codebook as a nonlinear reward model that maintains fixedO⁡\(1\)O\(1\)memory and requires no replay buffer\.
2. 2\.*Analysis*: under three base\-learner convergence properties \(verified for all variants\), the asymptotic regret rate is bounded by the additive misspecificationΔℓ\\Delta\_\{\\ell\}\(Theorem[3\.1](https://arxiv.org/html/2610.02440#S3.Thmtheorem1)\)\. We decompose depth\-dependent approximation error exactly into saturated quantization and additive\-interaction terms, and prove geometric convergence to the irreducible floor when reconstruction and additive\-tail errors contract geometrically \(Theorem[3\.2](https://arxiv.org/html/2610.02440#S3.Thmtheorem2)and Corollary[3\.1](https://arxiv.org/html/2610.02440#S3.Thmcorollary1)\)\. A shadow mechanism adapts depth online with false\-promotion probability≤α\\leq\\alpha\(Theorem[3\.3](https://arxiv.org/html/2610.02440#S3.Thmtheorem3)\)\.
3. 3\.*Scale experiments*: we evaluate on 13 datasets with up to1111M rounds and 30 seeds each, showing that RQ methods improve over their within\-class baselines on 11 of 13 datasets and that LinTS\-RQ is competitive with XGBoost \(7W/4L/2T\) at1000×1000\\timesless memory\.

Flatbℓ=64b^\{\\ell\}\{=\}64parameters⋅\\cdot1 obs→\\to1 cell updatedFactorialbℓ=64b^\{\\ell\}\{=\}64parameters⋅\\cdot1 obs→\\to1 cell updatedAdditive \(Ours\)ℓ​b=12\\ell b\{=\}12parameters⋅\\cdot1 obs→\\toℓ=3\\ell\{=\}3params updated→\\to5858% of cells informed

Figure 1:Partitioning the context space creates nonlinear reward models from linear per\-cell learners, but finer partitions fragment the data: each cell sees fewer observations\. All three schemes realizebℓ=64b^\{\\ell\}\{=\}64cells \(b=4b\{=\}4,ℓ=3\\ell\{=\}3\)\.Top/Bottom left:Flat and factorial parameterizations learn each cell from its own data alone\.Bottom right:Additive RQ achieves the same6464\-cell granularity withℓ​b=12\\ell b\{=\}12shared parameters—each observation updatesℓ=3\\ell\{=\}3centroids, pooling information across cells\. Fine partition without data starvation\.Figure 2:Regret gap \(%\) of each RQ method relative to its within\-class baseline on 13 datasets \(30 seeds, 95% CIs\)\. Negative = RQ method has lower regret\. Black: significant win \(CI excludes zero\)\. Gray: not significant\. Red: significant loss\.Left:LinTS\-RQ vs LinTS wins on 11/13 datasets; the sole loss \(year\_prediction,d=90d\{=\}90,K=84K\{=\}84\) is explained by the data sufficiency conditionN/\(b​K​d2\)≪1N/\(bKd^\{2\}\)\\ll 1\(Section[4\.2](https://arxiv.org/html/2610.02440#S4.SS2)\)\.Center:SGD\-LinTS\-RQ vs SGD\-LinTS wins on 12/13\.Right:TS\-RQ vs TS wins on 11/13\.Figure 3:Memory vs\. quality across 13 datasets\. Each point is one \(method, dataset\) pair\. Hollow gray: linear baselines \(O⁡\(1\)O\(1\)memory, high regret\)\. Solid gray: RQ methods \(O⁡\(1\)O\(1\)memory, low regret\)\. Red: doubling methods \(O⁡\(T\)O\(T\)replay buffers, low regret\)\. RQ methods match tree/neural regret at1000×1000\\timesless memory\. The vertical drop from hollow to solid at the samexx\-position shows the regret gain from the RQ codebook\.
## 2Method

Setting\.We consider the standard stochastic contextual bandit setting[Lattimore and Szepesvári \(2020\)](https://arxiv.org/html/2610.02440#bib.bib11): at each roundtt, the agent observes a contextxt∈ℝdx\_\{t\}\\in\\mathbb\{R\}^\{d\}, selects an armat∈\[K\]a\_\{t\}\\in\[K\], and receives a rewardrt∈\{0,1\}r\_\{t\}\\in\\\{0,1\\\}\. The goal is to minimize cumulative regretR⁡\(T\)=∑t=1T\[r∗​\(xt\)−rt\]R\(T\)=\\sum\_\{t=1\}^\{T\}\[r^\{\*\}\(x\_\{t\}\)\-r\_\{t\}\], wherer∗r^\{\*\}is the oracle reward\.

We assume access to a pool ofnrqn\_\{\\mathrm\{rq\}\}*unlabeled*contexts—separate from the bandit evaluation pool—on which we train the RQ codebook via sequentialkk\-means\. We train the codebook once and freeze it before the bandit starts\. This is a standard assumption in settings where unlabeled contexts are abundant \(user profiles, item catalogs, sensor readings\) but rewards require costly sequential interaction\. The codebook encodes each context via greedykk\-means assignment:

ki=arg⁡mink∈\[b\]⁡‖x\(i−1\)−ck\(i\)‖2,x\(i\)=x\(i−1\)−cki\(i\),x\(0\)=x,k\_\{i\}=\\arg\\min\_\{k\\in\[b\]\}\\\|x^\{\(i\-1\)\}\-c\_\{k\}^\{\(i\)\}\\\|^\{2\},\\qquad x^\{\(i\)\}=x^\{\(i\-1\)\}\-c\_\{k\_\{i\}\}^\{\(i\)\},\\qquad x^\{\(0\)\}=x,\(1\)producing a code sequencez=\[k1,…,kℓ\]z=\[k\_\{1\},\\ldots,k\_\{\\ell\}\]that partitions the context space, and context residualsx\(0\),x\(1\),…,x\(ℓ−1\)x^\{\(0\)\},x^\{\(1\)\},\\ldots,x^\{\(\\ell\-1\)\}that serve as per\-level feature inputs to the bandit model below\.

Gradient\-boosted bandit over RQ levels\.All methods share the architecture in Algorithm[1](https://arxiv.org/html/2610.02440#alg1)\. Each RQ level operates on the context residual left by shallower levels, and boosts[Friedman \(2001\)](https://arxiv.org/html/2610.02440#bib.bib1)the reward prediction: level00predicts the raw reward; leveli\>0i\>0predicts the*pseudo\-target*—the gap between the observed reward and the cumulative prediction of levels0,…,i−10,\\ldots,i\{\-\}1\. A damping factorη∈\(0,1\]\\eta\\in\(0,1\]controls each level’s contribution\.

Algorithm 1RQ Bandit with Shadow Promotion1:Codebook

𝒞\(1\),…,𝒞\(ℓmax\)\\mathcal\{C\}^\{\(1\)\},\\ldots,\\mathcal\{C\}^\{\(\\ell\_\{\\max\}\)\}; model array

ℳ⁡\[i,c,a\]\\mathcal\{M\}\[i,c,a\]for each level

i∈\[ℓmax\]i\\in\[\\ell\_\{\\max\}\], centroid

c∈\[b\]c\\in\[b\], arm

a∈\[K\]a\\in\[K\]; clipping function

σ⁡\(z\)=clip⁡\(z\+0\.5,0,1\)\\sigma\(z\)=\\mathrm\{clip\}\(z\+0\.5,0,1\); damping

η\\eta; initial depth

ℓ0\\ell\_\{0\}; significance level

α\\alpha
2:

ℓact←ℓ0\\ell\_\{\\mathrm\{act\}\}\\leftarrow\\ell\_\{0\}; initialize shadow at level

ℓ0\+1\\ell\_\{0\}\{\+\}1
3:for

t=1,…,Tt=1,\\ldots,Tdo

4:Encode:observe

xtx\_\{t\}; compute codes

\(k1,…,kℓmax\)\(k\_\{1\},\\ldots,k\_\{\\ell\_\{\\max\}\}\)and context residuals

\(xt\(0\),xt\(1\),…\)\(x\_\{t\}^\{\(0\)\},x\_\{t\}^\{\(1\)\},\\ldots\)via \([1](https://arxiv.org/html/2610.02440#S2.E1)\)

5:Score:

sa←∑i=1ℓactηi−1⋅ℳ⁡\[i,ki,a\]\.sample⁡\(xt\(i−1\)\)s\_\{a\}\\leftarrow\\sum\_\{i=1\}^\{\\ell\_\{\\mathrm\{act\}\}\}\\eta^\{i\-1\}\\cdot\\mathcal\{M\}\[i,\\,k\_\{i\},\\,a\]\.\\mathrm\{sample\}\(x\_\{t\}^\{\(i\-1\)\}\)for each arm

aa
6:Select:

at←arg⁡maxa⁡saa\_\{t\}\\leftarrow\\arg\\max\_\{a\}s\_\{a\}; observe reward

rt∈\{0,1\}r\_\{t\}\\in\\\{0,1\\\}
7:Targets \(residual cascade\):

y^0←0\\hat\{y\}\_\{0\}\\leftarrow 0
8:for

i=1,…,ℓacti=1,\\ldots,\\ell\_\{\\mathrm\{act\}\}do

9:

μ^i←ℳ⁡\[i,ki,at\]\.mean⁡\(xt\(i−1\)\)\\hat\{\\mu\}\_\{i\}\\leftarrow\\mathcal\{M\}\[i,\\,k\_\{i\},\\,a\_\{t\}\]\.\\mathrm\{mean\}\(x\_\{t\}^\{\(i\-1\)\}\)⊳\\trianglerightlevel\-iiprediction

10:

r~i←rt−σ⁡\(y^i−1\)\\tilde\{r\}\_\{i\}\\leftarrow r\_\{t\}\-\\sigma\(\\hat\{y\}\_\{i\-1\}\)⊳\\trianglerightresidual target

11:

y^i←y^i−1\+ηi−1​μ^i\\hat\{y\}\_\{i\}\\leftarrow\\hat\{y\}\_\{i\-1\}\+\\eta^\{i\-1\}\\hat\{\\mu\}\_\{i\}⊳\\trianglerightaccumulate

12:endfor

13:Update:

ℳ⁡\[i,ki,at\]\.update⁡\(xt\(i−1\),r~i\)\\mathcal\{M\}\[i,\\,k\_\{i\},\\,a\_\{t\}\]\.\\mathrm\{update\}\(x\_\{t\}^\{\(i\-1\)\},\\tilde\{r\}\_\{i\}\)for

i=1,…,ℓacti=1,\\ldots,\\ell\_\{\\mathrm\{act\}\}
14:Shadow:

ℳ⁡\[ℓact\+1,kℓact\+1,at\]\.update⁡\(xt\(ℓact\),r~ℓact\+1\)\\mathcal\{M\}\[\\ell\_\{\\mathrm\{act\}\}\{\+\}1,\\,k\_\{\\ell\_\{\\mathrm\{act\}\}\+1\},\\,a\_\{t\}\]\.\\mathrm\{update\}\(x\_\{t\}^\{\(\\ell\_\{\\mathrm\{act\}\}\)\},\\tilde\{r\}\_\{\\ell\_\{\\mathrm\{act\}\}\+1\}\)
15:if

t∈\{T0,2​T0,4​T0,…\}t\\in\\\{T\_\{0\},2T\_\{0\},4T\_\{0\},\\ldots\\\}and

ℓact<ℓmax\\ell\_\{\\mathrm\{act\}\}<\\ell\_\{\\max\}then

16:ifFreedman test \(Theorem[3\.3](https://arxiv.org/html/2610.02440#S3.Thmtheorem3), Appendix[D](https://arxiv.org/html/2610.02440#A4)\): shadow significantly better at level

α/\(nc⋅\(ℓmax−1\)\)\\alpha/\(n\_\{c\}\\cdot\(\\ell\_\{\\max\}\{\-\}1\)\), where

ncn\_\{c\}is the number of checksthen

17:

ℓact\+=1\\ell\_\{\\mathrm\{act\}\}\\mathrel\{\+\}=1; spawn new shadow

18:endif

19:endif

20:endfor

The three instantiations differ only in the per\-level model classℳ\\mathcal\{M\}\(Table[1](https://arxiv.org/html/2610.02440#S2.T1)\)\.

Table 1:Model variants sharing Algorithm[1](https://arxiv.org/html/2610.02440#alg1), differing only in per\-cell learnerℳ\\mathcal\{M\}\(full pseudocode in Appendix[A](https://arxiv.org/html/2610.02440#A1)\)\.For LinTS\-RQ, pseudo\-targets at deeper levels have smaller magnitude and fewer effective samples; we describe the per\-level regularization and numerical scaling in Section[4\.1](https://arxiv.org/html/2610.02440#S4.SS1)\.

Shadow promotion\.Algorithm[1](https://arxiv.org/html/2610.02440#alg1)adapts depthℓ\\ellonline via a shadow level that trains alongside the active model but does not influence arm selection \(line[14](https://arxiv.org/html/2610.02440#alg1.l14)\)\. At pre\-committed check times \(line[17](https://arxiv.org/html/2610.02440#alg1.l17)\), a statistical test compares the shadow’s prediction accuracy against the active model over a trailing window\. If the shadow wins, it is promoted and a new shadow spawned; otherwise the active depth is unchanged\. We analyze the false\-promotion guarantee in Section[3\.3](https://arxiv.org/html/2610.02440#S3.SS3)\.

## 3Analysis

We analyze Algorithm[1](https://arxiv.org/html/2610.02440#alg1)along three axes: asymptotic regret under base\-learner convergence properties, the effect of depth on misspecification, and false\-promotion control for the shadow mechanism\.

### 3\.1Asymptotic regret

###### Definition 3\.1\(Additive misspecification\)\.

The*additive misspecification*at depthℓ\\ellis

Δℓ​\(ℳ\)=inff1,…,fℓ∈ℳ𝔼x​\[maxa⁡\|r∗​\(x,a\)−σ⁡\(∑i=1ℓfi​\(ki​\(x\),a\)\)\|\]\.\\Delta\_\{\\ell\}\(\\mathcal\{M\}\)=\\inf\_\{f\_\{1\},\\ldots,f\_\{\\ell\}\\in\\mathcal\{M\}\}\\mathbb\{E\}\_\{x\}\\\!\\left\[\\max\_\{a\}\\left\|r^\{\*\}\(x,a\)\-\\sigma\\\!\\left\(\\sum\_\{i=1\}^\{\\ell\}f\_\{i\}\(k\_\{i\}\(x\),a\)\\right\)\\right\|\\right\]\.\(2\)

We require three properties of the per\-cell base learnerℳ\\mathcal\{M\}, stated informally here \(formal definitions and verification for all three variants in Appendix[B](https://arxiv.org/html/2610.02440#A2)\):

1. 1\.*Eventual boundedness*: score means do not diverge\.
2. 2\.*Exploration*: if an arm rarely visits a centroid, its score variance remains positive, ensuring continued exploration\.
3. 3\.*Consistency*: when shallower levels stabilize, each level’s predictions converge to the best predictor in its function class\.

###### Theorem 3\.1\(Asymptotic regret\)\.

For any base learnerℳ\\mathcal\{M\}satisfying Properties 1–3, letr^∞\\hat\{r\}\_\{\\infty\}denote the converged prediction of the sequential residual\-fitting procedure \(Appendix[C](https://arxiv.org/html/2610.02440#A3)\)\. Then

lim supT→∞R⁡\(T,ℓ\)T≤2​𝔼x​\[maxa⁡\|r∗​\(x,a\)−r^∞​\(x,a\)\|\]\.\\limsup\_\{T\\to\\infty\}\\;\\frac\{R\(T,\\ell\)\}\{T\}\\;\\leq\\;2\\,\\mathbb\{E\}\_\{x\}\\\!\\left\[\\max\_\{a\}\\left\|r^\{\*\}\(x,a\)\-\\hat\{r\}\_\{\\infty\}\(x,a\)\\right\|\\right\]\.\(3\)Sincer^∞\\hat\{r\}\_\{\\infty\}is one feasible additive predictor, the right\-hand side equals2​Δℓ​\(ℳ\)2\\,\\Delta\_\{\\ell\}\(\\mathcal\{M\}\)when the stagewise and joint optima coincide; in general it is controlled by the stagewise approximation error\.

The key technical step is an inductive convergence proof across boosting levels: each level’s targets depend on all shallower levels’ estimates, creating a coupled system not covered by single\-model analysis\. We establish Properties 1–3 for TS\-RQ, SGD\-LinTS\-RQ, and LinTS\-RQ in Appendix[B](https://arxiv.org/html/2610.02440#A2); the full proof appears in Appendix[C](https://arxiv.org/html/2610.02440#A3)\. The verification follows the standard approach in the TS literature[Agrawal and Goyal \(2013\)](https://arxiv.org/html/2610.02440#bib.bib8); a fully rigorous treatment of the strong law under adaptive Thompson Sampling with misspecification remains open in general, as noted by[Agrawal and Goyal \(2012\)](https://arxiv.org/html/2610.02440#bib.bib22)\. The bound says that average regret per round depends on the stagewise approximation error, not directly on the horizonTT\. When that error is zero, the method achieves sublinear regret; under misspecification, regret may grow linearly at the residual error rate\. This is not the optimalO⁡\(T\)O\(\\sqrt\{T\}\)rate that LinTS achieves under correct specification; the tradeoff is a richer non\-linear reward model at fixed memory\.

### 3\.2Misspecification and depth

The additive parameterization resolvesbℓb^\{\\ell\}effective cells with onlyℓ​b\\ell bparameters per arm, and each observation updatesℓ\\ellcentroid models—so exploration cost grows linearly inℓ\\ellwhile resolution grows exponentially\. Since deeper models contain shallower ones \(fℓ\+1≡0f\_\{\\ell\+1\}\\equiv 0\),Δℓ\+1≤Δℓ\\Delta\_\{\\ell\+1\}\\leq\\Delta\_\{\\ell\}trivially; the question is the*rate*of decay\.

We can now separate the two mechanisms that determine this rate\. For one arm and the identity\-link readout, letSℓS\_\{\\ell\}be the saturated space of square\-integrable functions of the prefix codez1:ℓz\_\{1:\\ell\}, and letAℓ=\{∑j≤ℓgj​\(zj\)\}A\_\{\\ell\}=\\\{\\sum\_\{j\\leq\\ell\}g\_\{j\}\(z\_\{j\}\)\\\}be the compact additive space used by RQ\. Writeδℓ=dist⁡\(r∗,Aℓ\)\\delta\_\{\\ell\}=\\operatorname\{dist\}\(r^\{\*\},A\_\{\\ell\}\),δℓsat=dist⁡\(r∗,Sℓ\)\\delta\_\{\\ell\}^\{\\rm sat\}=\\operatorname\{dist\}\(r^\{\*\},S\_\{\\ell\}\), andιℓ=dist⁡\(PSℓ​r∗,Aℓ\)\\iota\_\{\\ell\}=\\operatorname\{dist\}\(P\_\{S\_\{\\ell\}\}r^\{\*\},A\_\{\\ell\}\)\. LetA∞=⋃ℓAℓ¯A\_\{\\infty\}=\\overline\{\\bigcup\_\{\\ell\}A\_\{\\ell\}\},δ∞=dist⁡\(r∗,A∞\)\\delta\_\{\\infty\}=\\operatorname\{dist\}\(r^\{\*\},A\_\{\\infty\}\), andτℓ=dist⁡\(PA∞​r∗,Aℓ\)\\tau\_\{\\ell\}=\\operatorname\{dist\}\(P\_\{A\_\{\\infty\}\}r^\{\*\},A\_\{\\ell\}\)\.

###### Theorem 3\.2\(Depth\-rate decomposition\)\.

Ifr∗r^\{\*\}isLL\-Lipschitz andMSEℓ=𝔼​‖x−x^ℓ‖2\\mathrm\{MSE\}\_\{\\ell\}=\\mathbb\{E\}\\\|x\-\\hat\{x\}\_\{\\ell\}\\\|^\{2\}is the depth\-ℓ\\ellRQ reconstruction error, then

δℓ2\\displaystyle\\delta\_\{\\ell\}^\{2\}=\(δℓsat\)2\+ιℓ2,\\displaystyle=\(\\delta\_\{\\ell\}^\{\\rm sat\}\)^\{2\}\+\\iota\_\{\\ell\}^\{2\},\(δℓsat\)2\\displaystyle\(\\delta\_\{\\ell\}^\{\\rm sat\}\)^\{2\}≤L2​MSEℓ,\\displaystyle\\leq L^\{2\}\\mathrm\{MSE\}\_\{\\ell\},ιℓ\\displaystyle\\iota\_\{\\ell\}≤δ∞\+τℓ\.\\displaystyle\\leq\\delta\_\{\\infty\}\+\\tau\_\{\\ell\}\.\(4\)Consequently,

δℓ2−δ∞2≤L2​MSEℓ\+2​δ∞​τℓ\+τℓ2\.\\delta\_\{\\ell\}^\{2\}\-\\delta\_\{\\infty\}^\{2\}\\leq L^\{2\}\\mathrm\{MSE\}\_\{\\ell\}\+2\\delta\_\{\\infty\}\\tau\_\{\\ell\}\+\\tau\_\{\\ell\}^\{2\}\.\(5\)

###### Corollary 3\.1\(Conditional geometric decay\)\.

IfMSEℓ≤M0​ρxℓ\\mathrm\{MSE\}\_\{\\ell\}\\leq M\_\{0\}\\rho\_\{x\}^\{\\ell\}andτℓ≤Cτ​ρτℓ\\tau\_\{\\ell\}\\leq C\_\{\\tau\}\\rho\_\{\\tau\}^\{\\ell\}, withρx,ρτ∈\(0,1\)\\rho\_\{x\},\\rho\_\{\\tau\}\\in\(0,1\), then

δℓ≤δ∞\+L​M0​ρxℓ/2\+Cτ​ρτℓ=δ∞\+O⁡\(ρℓ\),\\delta\_\{\\ell\}\\leq\\delta\_\{\\infty\}\+L\\sqrt\{M\_\{0\}\}\\,\\rho\_\{x\}^\{\\ell/2\}\+C\_\{\\tau\}\\rho\_\{\\tau\}^\{\\ell\}=\\delta\_\{\\infty\}\+O\(\\rho^\{\\ell\}\),\(6\)whereρ=max⁡\{ρx,ρτ\}<1\\rho=\\max\\\{\\sqrt\{\\rho\_\{x\}\},\\rho\_\{\\tau\}\\\}<1\.

The proof is in Appendix[C](https://arxiv.org/html/2610.02440#A3)\. Reconstruction controls the saturatedbℓb^\{\\ell\}\-cell benchmark, whileτℓ\\tau\_\{\\ell\}measures the additional interaction tail imposed by the compactO⁡\(ℓ​b\)O\(\\ell b\)additive readout\. Thus geometric reconstruction decay alone is insufficient; geometric additive\-tail decay is the explicit additional condition\. For multiple arms,𝔼​maxa​\|ea\|≤\(∑a𝔼​ea2\)1/2\\mathbb\{E\}\\max\_\{a\}\|e\_\{a\}\|\\leq\(\\sum\_\{a\}\\mathbb\{E\}e\_\{a\}^\{2\}\)^\{1/2\}, so the per\-arm result transfers to Definition[3\.1](https://arxiv.org/html/2610.02440#S3.Thmdefinition1)up to aK\\sqrt\{K\}factor\. A Lipschitz output link similarly transfers a pre\-link score bound after multiplication by its Lipschitz constant\.

Figure[4](https://arxiv.org/html/2610.02440#S3.F4)is consistent with the conditional geometric law: fittinga\+b​ρℓa\+b\\rho^\{\\ell\}to regret rates at depths11–55yields medianR2=0\.99R^\{2\}=0\.99across 39 \(dataset, method\) pairs\. This finite\-depth evidence does not establish the assumptions of Corollary[3\.1](https://arxiv.org/html/2610.02440#S3.Thmcorollary1)universally\. Within\-cell reward variance contracts with median per\-level ratio0\.830\.83\(Appendix[E](https://arxiv.org/html/2610.02440#A5)\)\.

Figure 4:Empirical behavior consistent with the conditional geometric depth\-rate law\.Left:MedianR2R^\{2\}of the exponential fita\+b​ρℓa\+b\\rho^\{\\ell\}improves with horizonTT\.Right:Normalized regret decay\(Δℓ−Δ5\)/\(Δ1−Δ5\)\(\\Delta\_\{\\ell\}\-\\Delta\_\{5\}\)/\(\\Delta\_\{1\}\-\\Delta\_\{5\}\)at terminalTTfor each dataset; curves cluster along exponential trajectories\.
### 3\.3Shadow false\-promotion control

###### Theorem 3\.3\(Shadow false\-promotion control\)\.

The probability that the shadow is promoted despite having no lower expected squared prediction error than the active model, under the active policy’s data distribution over the tested window, is at mostα\\alphaover the full horizon\.

We test the paired squared\-error differences via Freedman’s martingale inequality[Freedman \(1975\)](https://arxiv.org/html/2610.02440#bib.bib18), which applies without requiring i\.i\.d\. observations\. Given a finite planning horizonTT\(or an upper bound on the deployment length\), the number of check times per depth isnc=⌊log2⁡\(T/T0\)⌋n\_\{c\}=\\lfloor\\log\_\{2\}\(T/T\_\{0\}\)\\rfloor, known before the first observation\. The per\-test significance level is Bonferroni\-corrected over allnc⋅\(ℓmax−1\)n\_\{c\}\\cdot\(\\ell\_\{\\max\}\{\-\}1\)comparisons, giving total false\-promotion probability≤α\\leq\\alpha\. Proof in Appendix[D](https://arxiv.org/html/2610.02440#A4)\.

## 4Experiments

### 4\.1Setup

Following the supervised\-to\-bandit protocol[Riquelme et al\. \(2018\)](https://arxiv.org/html/2610.02440#bib.bib12), we convert datasets by assigning reward11for the correct class and00otherwise\. We evaluate on 13 tabular datasets from OpenML and UCI withNNranging from130​K130\\text\{K\}to11​M11\\text\{M\}, feature dimensiond∈\[3,90\]d\\in\[3,90\], andK∈\[2,104\]K\\in\[2,104\]arms \(Table[6](https://arxiv.org/html/2610.02440#A7.T6)in Appendix[G](https://arxiv.org/html/2610.02440#A7)\)\. Following the codebook training protocol \(Section[2](https://arxiv.org/html/2610.02440#S2)\),nrq=50​Kn\_\{\\mathrm\{rq\}\}\{=\}50\\text\{K\}contexts are held out for codebook training; the bandit runs on the remaining pool with contexts drawn uniformly at random without replacement, each seen once, so the horizonT=N−nrqT=N\-n\_\{\\mathrm\{rq\}\}\. All methods useb=16b\{=\}16centroids per level, initial depthℓ0=2\\ell\_\{0\}\{=\}2,ℓmax=8\\ell\_\{\\max\}\{=\}8,ν=0\.1\\nu\{=\}0\.1,η=0\.5\\eta\{=\}0\.5,λ=1\.0\\lambda\{=\}1\.0, shadowα=0\.05\\alpha\{=\}0\.05,W=1000W\{=\}1000\(trailing window\),T0=50⋅b⋅KT\_\{0\}=50\\cdot b\\cdot K, and 30 bandit seeds per configuration\. For LinTS\-RQ, we scale the per\-level regularization asλi=λ⋅0\.25i−1\\lambda\_\{i\}=\\lambda\\cdot 0\.25^\{i\-1\}and add numerical jitter10i−1×10−610^\{i\-1\}\\times 10^\{\-6\}for Cholesky stability\. We fix all hyperparameters across all datasets—no per\-dataset tuning\. Code is available at[https://github\.com/atavory/rqb](https://github.com/atavory/rqb)\. Each seed initializes all random number generators \(arm selection, posterior sampling\) deterministically\.

We compare six methods: three baselines \(TS, SGD\-LinTS, LinTS\) and their RQ variants with adaptive depth \(TS\-RQ, SGD\-LinTS\-RQ, LinTS\-RQ\)\. We additionally compare against three nonlinear baselines: Doubling\-XGB \(XGBoost: 100 trees, max depth 6, learning rate 0\.1, subsample 0\.8, colsample\_bytree 0\.8,ϵ=0\.1\\epsilon\{=\}0\.1greedy, doubling retrain schedule\), Doubling\-NeuralCB \(2\-layer MLP, 128 hidden units, ReLU activations, Adam optimizer with learning rate10−310^\{\-3\}, batch size 256, doubling retrain schedule, LinTS head\), and TabNet\-LinTS[Arik and Pfister \(2021\)](https://arxiv.org/html/2610.02440#bib.bib26)\(unsupervised TabNet pre\-training with default hyperparameters:Nsteps=3N\_\{\\mathrm\{steps\}\}\{=\}3,Na=Nd=8N\_\{a\}\{=\}N\_\{d\}\{=\}8,γ=1\.3\\gamma\{=\}1\.3,λsparse=10−3\\lambda\_\{\\mathrm\{sparse\}\}\{=\}10^\{\-3\}; encoder frozen on the same 50K holdout, LinTS on learned features\)\. All representation\-based methods \(RQ, TabNet, Neural\-Linear\) use the same 50K unlabeled holdout; the baselines \(TS, LinTS, SGD\-LinTS\) operate without any representation layer by design—they have no mechanism to consume unlabeled data—and evaluate on the sameTT\-context pool, ensuring identical evaluation conditions\. We fix all hyperparameters—both for RQ methods and for the nonlinear baselines \(XGBoost, NeuralCB, TabNet\)—across all 13 datasets with no per\-dataset tuning\.

We report regret*rate*\(cumulative regret divided byTT\) throughout, making results length\-invariant across datasets\. Win/loss calls use 95% CIs from 30 seeds; a method “wins” only when the CI excludes zero\.

### 4\.2Results

Memory–quality tradeoff\.Figure[3](https://arxiv.org/html/2610.02440#S1.F3)places all methods on a memory–regret scatter, and Table[2](https://arxiv.org/html/2610.02440#S4.T2)gives the details\. Regret is normalized by the context\-free oracle rate \(1−maxa⁡P⁡\(Y=a\)1\-\\max\_\{a\}P\(Y\{=\}a\)\), so 1\.0 corresponds to majority\-class guessing\. Values above 1\.0 occur when squared\-loss exploration produces overconfident wrong predictions on skewed datasets\. Doubling\-XGB and Doubling\-NeuralCB match LinTS\-RQ regret but requireO⁡\(T\)O\(T\)replay memory \(Table[2](https://arxiv.org/html/2610.02440#S4.T2)\)\.

Table 2:Model memory at shadow\-promoted depths \(b=16b\{=\}16\)\. XGB replay buffer growsO⁡\(T\)O\(T\); all RQ methods are fixedO⁡\(1\)O\(1\)\.Within\-family comparisons\.Figure[2](https://arxiv.org/html/2610.02440#S1.F2)shows the regret gap of each RQ method relative to its within\-class baseline, and Table[3](https://arxiv.org/html/2610.02440#S4.T3)gives the details\. LinTS\-RQ wins significantly on 10 of 13 datasets, with gaps up to96%96\\%\(skin\_segmentation\); SGD\-LinTS\-RQ wins on 12 of 13; TS\-RQ wins on 11 of 13 versus context\-free TS\. The common failure case is year\_prediction \(d=90d\{=\}90,K=84K\{=\}84\), where all three RQ variants show small losses \(\+0\.4%\+0\.4\\%to\+4\.5%\+4\.5\\%\); we discuss this in the data sufficiency analysis below\.

Nonlinear baselines\.LinTS\-RQ achieves regret competitive with Doubling\-XGB \(7W/4L/2T\)\. The key differentiator is memory: atT=5​MT\{=\}5\\text\{M\}, LinTS\-RQ uses 620 KB vs\. XGB’s 1\.1 GB—a gap that grows linearly withTT\. Against TabNet\-LinTS \(same 50K holdout\), LinTS\-RQ wins on 11 of 13 datasets \(11W/2L\), with losses only on hepmass \(\+0\.5%\+0\.5\\%\) and year\_prediction \(\+1\.7%\+1\.7\\%\), showing that unsupervisedkk\-means produces a partition that matches or exceeds TabNet’s neural embedding, while the RQ codebook trains in seconds viakk\-means versus minutes for TabNet pretraining\. Per\-step latency is also low: TS\-RQ runs at5050–750​μ​s750\\,\\mu\\text\{s\}/step across all datasets \(Appendix[Q](https://arxiv.org/html/2610.02440#A17)\)\.

Table 3:Win/loss/tie \(W/L/T\) summary across 13 datasets \(30 seeds, 95% CIs\)\. Negative gap = RQ method has lower regret\.Data sufficiency\.LinTS\-RQ maintains ad×dd\\times dcovariance matrix for each of theb​KbKcentroid\-arm pairs, so the total parameter count scales asb​K​d2bKd^\{2\}\. The ratioN/\(b​K​d2\)N/\(bKd^\{2\}\)measures contexts per parameter and is computable before any bandit interaction \(Figure[5](https://arxiv.org/html/2610.02440#S4.F5)\)\. On 12 of 13 datasets this ratio exceeds1\.11\.1and LinTS\-RQ wins; on year\_prediction \(d=90d\{=\}90,K=84K\{=\}84, ratio=0\.04\{=\}0\.04\), LinTS\-RQ degrades even at depth 1\. TS\-RQ needs onlyO⁡\(1\)O\(1\)parameters per cell \(a count and a reward sum\), so it is unaffected: it matches the TS baseline on year\_prediction \(93\.0%93\.0\\%vs93\.4%93\.4\\%\)\. The failure is structural, not fixable by tuning: LinTS\-RQ degrades with depth \(96\.3%96\.3\\%atℓ=1\\ell\{=\}1,97\.4%97\.4\\%atℓ=4\\ell\{=\}4\) as each level fragments the already\-sparse data further, while TS\-RQ stays flat at93\.0%93\.0\\%across all depths\. On synthetic data, LinTS\-RQ wins at all ratios≥14\\geq 14\(Appendix[K](https://arxiv.org/html/2610.02440#A11)\)\.

Figure 5:Data sufficiency diagnostic: regret gap of LinTS\-RQ vs\. LinTS as a function ofN/\(b​K​d2\)N/\(bKd^\{2\}\)\. All real datasets with ratio\>1\>1\(outside the shaded region\) are wins or ties; year\_prediction \(ratio=0\.04=0\.04\) is the sole loss\. Synthetic Gaussian data \(gray squares\) confirm the threshold \(Appendix[K](https://arxiv.org/html/2610.02440#A11)\)\.Effective rank\.On datasets with effective rank \(tr⁡\(Σ\)/λmax​\(Σ\)\\mathrm\{tr\}\(\\Sigma\)/\\lambda\_\{\\max\}\(\\Sigma\)\) below1\.51\.5\(skin\_segmentation, miniboone\), SGD\-LinTS performs*worse than context\-free TS*: the diagonal covariance approximation spreads itsddparameters uniformly across coordinates, wastingd−1d\{\-\}1of them on noise when most variance lies on a single axis\. TS\-RQ avoids this failure mode entirely—the codebook geometry captures dominant directions through centroid placement, without estimating any covariance—and achieves2\.6%2\.6\\%and14\.7%14\.7\\%normalized regret on these two datasets \(Appendix[N](https://arxiv.org/html/2610.02440#A14)\)\.

Depth adaptation\.Table[4](https://arxiv.org/html/2610.02440#S4.T4)compares TS\-RQ at fixed depths against shadow\-promoted adaptive depth\. On covertype, shadow promotion discovers depth 4 and gains3\.43\.4percentage points over fixedℓ=2\\ell\{=\}2\. On higgs, the benefit beyond depth 2 is marginal, and the adaptive method correctly settles at depth 3 with matching regret: the marginal gain from depth 4 falls within the noise floor of the Freedman test, so the shadow is never promoted\.

Table 4:TS\-RQ regret rate \(%\) at fixed vs\. adaptive depth\.

## 5Related Work

Linear and GLM bandits\.LinTS[Agrawal and Goyal \(2013\)](https://arxiv.org/html/2610.02440#bib.bib8)and LinUCB[Li et al\. \(2010\)](https://arxiv.org/html/2610.02440#bib.bib10);[Abbasi\-Yadkori et al\. \(2011\)](https://arxiv.org/html/2610.02440#bib.bib9);[Dani et al\. \(2008\)](https://arxiv.org/html/2610.02440#bib.bib4)achieveO⁡\(d​K​T​log⁡T\)O\(d\\sqrt\{KT\\log T\}\)regret under linear rewards\. The misspecification bound[Lattimore et al\. \(2020\)](https://arxiv.org/html/2610.02440#bib.bib23)givesΔ⋅T\\Delta\\cdot Tlinear regret under misspecification—the basis for our asymptotic analysis \(Appendix[C](https://arxiv.org/html/2610.02440#A3)\)\.

Neural and tree\-based bandits\.NeuralUCB[Zhou et al\. \(2020\)](https://arxiv.org/html/2610.02440#bib.bib13)and Neural TS[Zhang et al\. \(2021\)](https://arxiv.org/html/2610.02440#bib.bib25)require per\-step gradient and inverse\-Hessian computation; efficient approximations \(EE\-Net[Ban and He \(2022\)](https://arxiv.org/html/2610.02440#bib.bib35), Neural\-Linear[Riquelme et al\. \(2018\)](https://arxiv.org/html/2610.02440#bib.bib12)\) reduce to LinTS on last\-layer features\. TETS[Nilsson et al\. \(2024\)](https://arxiv.org/html/2610.02440#bib.bib24)combines XGBoost with TS but must refit on accumulated history, incurringO⁡\(T2\)O\(T^\{2\}\)cumulative cost\. Our offline codebook avoids both: no gradients, no refitting\.

Partition\-based bandits\.The X\-armed bandit framework[Bubeck et al\. \(2011\)](https://arxiv.org/html/2610.02440#bib.bib2)and the Zooming algorithm[Kleinberg et al\. \(2008\)](https://arxiv.org/html/2610.02440#bib.bib3);[Slivkins \(2014\)](https://arxiv.org/html/2610.02440#bib.bib19)adaptively refine partitions to balance resolution against sample complexity\. Nonparametric histogram bandits[Rigollet and Zeevi \(2010\)](https://arxiv.org/html/2610.02440#bib.bib33);[Perchet and Rigollet \(2013\)](https://arxiv.org/html/2610.02440#bib.bib34)achieve regretO⁡\(T\(d\+2\)/\(d\+1\)\)O\(T^\{\(d\+2\)/\(d\+1\)\}\)with flat partitions\. Tile coding[Sutton and Barto \(2018\)](https://arxiv.org/html/2610.02440#bib.bib17)uses additive partitions in RL but with uniform tilings; our data\-driven RQ codebook adapts toP⁡\(X\)P\(X\)\. The additive parameterization usesℓ​b\\ell bparameters forbℓb^\{\\ell\}cells—a potentially exponential compression\.

Model selection and quantization\.CORRAL[Agarwal et al\. \(2017\)](https://arxiv.org/html/2610.02440#bib.bib21)and Regret Balancing[Pacchiano et al\. \(2020\)](https://arxiv.org/html/2610.02440#bib.bib20)run multiple base learners in parallel\. Our shadow promotion monitors one additional depth level sequentially without influencing arm selection \(Theorem[3\.3](https://arxiv.org/html/2610.02440#S3.Thmtheorem3)\)\. Product quantization[Jegou et al\. \(2010\)](https://arxiv.org/html/2610.02440#bib.bib15), residual quantization[Chen et al\. \(2010\)](https://arxiv.org/html/2610.02440#bib.bib16), and VQ\-VAE[van den Oord et al\. \(2017\)](https://arxiv.org/html/2610.02440#bib.bib14)compress representations; we show the same structure compresses*exploration*\(bℓb^\{\\ell\}cells fromℓ​b\\ell bparameters\)\. Self\-supervised methods \(SCARF[Bahri et al\. \(2022\)](https://arxiv.org/html/2610.02440#bib.bib5), VIME[Yoon et al\. \(2020\)](https://arxiv.org/html/2610.02440#bib.bib6), SubTab[Ucar et al\. \(2021\)](https://arxiv.org/html/2610.02440#bib.bib7), TabNet[Arik and Pfister \(2021\)](https://arxiv.org/html/2610.02440#bib.bib26)\) learn representations from unlabeled data; our codebook achieves this via unsupervisedkk\-means\.

## 6Conclusion

We repurposed RQ codebooks as a representation layer for contextual bandits, enabling gradient\-boosted reward models with fixedO⁡\(1\)O\(1\)memory\. RQ variants improve on most datasets at orders\-of\-magnitude less memory than replay\-based methods, while TS\-RQ remains robust when LinTS\-RQ’s covariance starves\. Extensions to continuous rewards, online codebook adaptation, and alternative per\-level features \(PCA, neural\-linear\) are straightforward\.

## 7Limitations

The data sufficiency conditionN/\(b​K​d2\)≫1N/\(bKd^\{2\}\)\\gg 1is the sharpest limitation: on year\_prediction \(d=90d\{=\}90,K=84K\{=\}84, ratio0\.040\.04\), LinTS\-RQ degrades even at depth 1; app\-dimensional projection \(p≪dp\\ll d\) would relax this toN/\(b​K​p2\)N/\(bKp^\{2\}\)\. The linear variants use squared loss for binary rewards \(Pólya\-Gamma augmentation could eliminate this\)\. Shadow promotion provides false\-promotion control, though post\-promotion performance depends on the new policy’s data distribution \(Remark[D\.2](https://arxiv.org/html/2610.02440#A4.Thmremark2)\)\. The fixed\-depth asymptotic analysis \(Appendix[C](https://arxiv.org/html/2610.02440#A3)\) is conditional on base\-learner convergence properties; the appendix makes these assumptions explicit and verifies them for our model classes\. The codebook is trained via unsupervisedkk\-means, which minimizes reconstruction error rather than reward prediction; a reward\-aware partition \(e\.g\., CART splits\) could reduce the misspecificationΔℓ\\Delta\_\{\\ell\}directly, at the cost of requiring labeled data for codebook construction\. The codebook requires an offline holdout; in cold\-start settings it may degrade\. As with all bandit methods, reward\-signal biases may be amplified; our method neither exacerbates nor mitigates this\.

## 8Broader Impact

This work introduces a general\-purpose bandit representation and does not target a specific application domain\. Standard fairness and privacy concerns for bandit algorithms apply; we do not foresee risks specific to residual quantization\.

## Acknowledgments and Disclosures

This work received no external funding\. The authors declare no competing interests\.

## References

- Abbasi\-Yadkoriet al\.\(2011\)Y\. Abbasi\-Yadkori, D\. Pál, and C\. SzepesváriImproved algorithms for linear stochastic bandits\.InAdvances in Neural Information Processing Systems,Vol\.24,pp\. 2312–2320\.Cited by:[§1](https://arxiv.org/html/2610.02440#S1.p2.1),[§5](https://arxiv.org/html/2610.02440#S5.p1.1)\.
- Agarwalet al\.\(2017\)A\. Agarwal, H\. Luo, B\. Neyshabur, and R\. E\. SchapireCorralling a band of bandit algorithms\.InConference on Learning Theory,pp\. 12–38\.External Links:1612\.06246Cited by:[Appendix D](https://arxiv.org/html/2610.02440#A4.p2.1),[§5](https://arxiv.org/html/2610.02440#S5.p4.1)\.
- Agrawal and Goyal \(2012\)S\. Agrawal and N\. GoyalAnalysis of Thompson Sampling for the multi\-armed bandit problem\.InConference on Learning Theory,pp\. 39\.1–39\.26\.Cited by:[Remark B\.1](https://arxiv.org/html/2610.02440#A2.Thmremark1.p1.1),[§3\.1](https://arxiv.org/html/2610.02440#S3.SS1.p2.1)\.
- Agrawal and Goyal \(2013\)S\. Agrawal and N\. GoyalThompson sampling for contextual bandits with linear payoffs\.InInternational Conference on Machine Learning,pp\. 127–135\.Cited by:[Remark B\.1](https://arxiv.org/html/2610.02440#A2.Thmremark1.p1.1),[Appendix F](https://arxiv.org/html/2610.02440#A6.p1.1),[Appendix F](https://arxiv.org/html/2610.02440#A6.p5.1),[Appendix F](https://arxiv.org/html/2610.02440#A6.p7.1.1),[§1](https://arxiv.org/html/2610.02440#S1.p2.1),[§3\.1](https://arxiv.org/html/2610.02440#S3.SS1.p2.1),[§5](https://arxiv.org/html/2610.02440#S5.p1.1)\.
- Arik and Pfister \(2021\)S\. O\. Arik and T\. PfisterTabNet: attentive interpretable tabular learning\.InAAAI Conference on Artificial Intelligence,Vol\.35,pp\. 6679–6687\.Cited by:[§4\.1](https://arxiv.org/html/2610.02440#S4.SS1.p2.1),[§5](https://arxiv.org/html/2610.02440#S5.p4.1)\.
- Bahriet al\.\(2022\)D\. Bahri, H\. Jiang, Y\. Tay, and D\. MetzlerSCARF: self\-supervised contrastive learning using random feature corruption\.InInternational Conference on Learning Representations,Cited by:[§5](https://arxiv.org/html/2610.02440#S5.p4.1)\.
- Baldiet al\.\(2016\)P\. Baldi, K\. Cranmer, T\. Faucett, P\. Sadowski, and D\. WhitesonParameterized neural networks for high\-energy physics\.The European Physical Journal C76\(5\),pp\. 235\.External Links:[Document](https://dx.doi.org/10.1140/epjc/s10052-016-4099-4)Cited by:[Table 6](https://arxiv.org/html/2610.02440#A7.T6)\.
- Baldiet al\.\(2014\)P\. Baldi, P\. Sadowski, and D\. WhitesonSearching for exotic particles in high\-energy physics with deep learning\.Nature Communications5,pp\. 4308\.External Links:[Document](https://dx.doi.org/10.1038/ncomms5308)Cited by:[Table 6](https://arxiv.org/html/2610.02440#A7.T6)\.
- Ban and He \(2022\)Y\. Ban and J\. HeEE\-Net: exploitation\-exploration neural networks in contextual bandits\.InInternational Conference on Learning Representations,Cited by:[§5](https://arxiv.org/html/2610.02440#S5.p2.1)\.
- Bertin\-Mahieuxet al\.\(2011\)T\. Bertin\-Mahieux, D\. P\.W\. Ellis, B\. Whitman, and P\. LamereThe million song dataset\.InInternational Society for Music Information Retrieval Conference,Cited by:[Table 6](https://arxiv.org/html/2610.02440#A7.T6)\.
- Blackard and Dean \(1999\)J\. A\. Blackard and D\. J\. DeanComparative accuracies of artificial neural networks and discriminant analysis in predicting forest cover types from cartographic variables\.Computers and Electronics in Agriculture24\(3\),pp\. 131–151\.External Links:[Document](https://dx.doi.org/10.1016/S0168-1699%2899%2900046-0)Cited by:[Table 6](https://arxiv.org/html/2610.02440#A7.T6)\.
- Bubecket al\.\(2011\)S\. Bubeck, R\. Munos, G\. Stoltz, and C\. SzepesváriX\-armed bandits\.Journal of Machine Learning Research12,pp\. 1655–1695\.External Links:1001\.4475Cited by:[§5](https://arxiv.org/html/2610.02440#S5.p3.1)\.
- Chenet al\.\(2010\)Y\. Chen, T\. Guan, and C\. WangApproximate nearest neighbor search by residual vector quantization\.Sensors10\(12\),pp\. 11259–11273\.External Links:[Document](https://dx.doi.org/10.3390/s101211259)Cited by:[§1](https://arxiv.org/html/2610.02440#S1.p4.1),[§5](https://arxiv.org/html/2610.02440#S5.p4.1)\.
- Daniet al\.\(2008\)V\. Dani, T\. P\. Hayes, and S\. M\. KakadeStochastic linear optimization under bandit feedback\.InConference on Learning Theory,pp\. 355–366\.Cited by:[§5](https://arxiv.org/html/2610.02440#S5.p1.1)\.
- Dua and Graff \(2019\)D\. Dua and C\. GraffUCI machine learning repository\.University of California, Irvine\.External Links:[Link](https://archive.ics.uci.edu/ml)Cited by:[Table 6](https://arxiv.org/html/2610.02440#A7.T6)\.
- Freedman \(1975\)D\. A\. FreedmanOn tail probabilities for martingales\.The Annals of Probability3\(1\),pp\. 100–118\.External Links:[Document](https://dx.doi.org/10.1214/aop/1176996452)Cited by:[Appendix D](https://arxiv.org/html/2610.02440#A4.p2.1),[Appendix D](https://arxiv.org/html/2610.02440#A4.p6.2),[§3\.3](https://arxiv.org/html/2610.02440#S3.SS3.p1.1)\.
- Friedman \(2001\)J\. H\. FriedmanGreedy function approximation: a gradient boosting machine\.Annals of Statistics29\(5\),pp\. 1189–1232\.External Links:[Document](https://dx.doi.org/10.1214/aos/1013203451)Cited by:[§2](https://arxiv.org/html/2610.02440#S2.p3.1)\.
- Horn and Johnson \(2013\)R\. A\. Horn and C\. R\. JohnsonMatrix analysis\.2nd edition,Cambridge University Press\.External Links:ISBN 978\-0521548236Cited by:[Appendix F](https://arxiv.org/html/2610.02440#A6.p11.3.1)\.
- Jegouet al\.\(2010\)H\. Jegou, M\. Douze, and C\. SchmidProduct quantization for nearest neighbor search\.IEEE Transactions on Pattern Analysis and Machine Intelligence33\(1\),pp\. 117–128\.External Links:[Document](https://dx.doi.org/10.1109/TPAMI.2010.57)Cited by:[§5](https://arxiv.org/html/2610.02440#S5.p4.1)\.
- Kleinberget al\.\(2008\)R\. Kleinberg, A\. Slivkins, and E\. UpfalMulti\-armed bandits in metric spaces\.InACM Symposium on Theory of Computing,pp\. 681–690\.Cited by:[§5](https://arxiv.org/html/2610.02440#S5.p3.1)\.
- Lattimoreet al\.\(2020\)T\. Lattimore, C\. Szepesvari, and G\. WeiszLearning with good feature representations in bandits and in RL with a generative model\.InInternational Conference on Machine Learning,pp\. 5662–5671\.External Links:1911\.07676Cited by:[Appendix F](https://arxiv.org/html/2610.02440#A6.p9.1.1),[§5](https://arxiv.org/html/2610.02440#S5.p1.1)\.
- Lattimore and Szepesvári \(2020\)T\. Lattimore and C\. SzepesváriBandit algorithms\.Cambridge University Press\.Cited by:[Appendix F](https://arxiv.org/html/2610.02440#A6.p7.1.1),[Appendix F](https://arxiv.org/html/2610.02440#A6.p9.1.1),[§2](https://arxiv.org/html/2610.02440#S2.p1.1)\.
- Liet al\.\(2010\)L\. Li, W\. Chu, J\. Langford, and R\. E\. SchapireA contextual\-bandit approach to personalized news article recommendation\.InProceedings of the 19th international conference on World wide web,pp\. 661–670\.Cited by:[§5](https://arxiv.org/html/2610.02440#S5.p1.1)\.
- Nilssonet al\.\(2024\)H\. Nilsson, R\. Johansson, N\. Åkerblom, and M\. Haghir ChehreghaniTree ensembles for contextual bandits\.Transactions on Machine Learning Research\.Cited by:[§1](https://arxiv.org/html/2610.02440#S1.p2.1),[§5](https://arxiv.org/html/2610.02440#S5.p2.1)\.
- Pacchianoet al\.\(2020\)A\. Pacchiano, C\. Dann, C\. Gentile, and P\. BartlettRegret bound balancing and elimination for model selection in bandits and RL\.arXiv preprint arXiv:2012\.13045\.External Links:2012\.13045Cited by:[§5](https://arxiv.org/html/2610.02440#S5.p4.1)\.
- Perchet and Rigollet \(2013\)V\. Perchet and P\. RigolletThe multi\-armed bandit problem with covariates\.Annals of Statistics41\(2\),pp\. 693–721\.External Links:[Document](https://dx.doi.org/10.1214/13-AOS1101)Cited by:[§5](https://arxiv.org/html/2610.02440#S5.p3.1)\.
- Rigollet and Zeevi \(2010\)P\. Rigollet and A\. ZeeviNonparametric bandits with covariates\.InProceedings of the 23rd Conference on Learning Theory,pp\. 54–66\.Cited by:[§5](https://arxiv.org/html/2610.02440#S5.p3.1)\.
- Riquelmeet al\.\(2018\)C\. Riquelme, G\. Tucker, and J\. SnoekDeep Bayesian bandits showdown: an empirical comparison of Bayesian deep networks for Thompson sampling\.InInternational Conference on Learning Representations,External Links:1802\.09127Cited by:[§4\.1](https://arxiv.org/html/2610.02440#S4.SS1.p1.1),[§5](https://arxiv.org/html/2610.02440#S5.p2.1)\.
- Roeet al\.\(2005\)B\. P\. Roe, H\. Yang, J\. Zhu, Y\. Liu, I\. Stancu, and G\. McGregorBoosted decision trees as an alternative to artificial neural networks for particle identification\.Nuclear Instruments and Methods in Physics Research Section A543\(2–3\),pp\. 577–584\.External Links:[Document](https://dx.doi.org/10.1016/j.nima.2004.12.018)Cited by:[Table 6](https://arxiv.org/html/2610.02440#A7.T6)\.
- Slivkins \(2014\)A\. SlivkinsContextual bandits with similarity information\.Journal of Machine Learning Research15,pp\. 2533–2568\.Cited by:[§5](https://arxiv.org/html/2610.02440#S5.p3.1)\.
- Sutton and Barto \(2018\)R\. S\. Sutton and A\. G\. BartoReinforcement Learning: an introduction\.2nd edition,MIT Press\.Cited by:[§5](https://arxiv.org/html/2610.02440#S5.p3.1)\.
- Ucaret al\.\(2021\)T\. Ucar, E\. Hajiramezanali, and L\. EdwardsSubTab: subsetting features of tabular data for self\-supervised representation learning\.InAdvances in Neural Information Processing Systems,Vol\.34\.Cited by:[§5](https://arxiv.org/html/2610.02440#S5.p4.1)\.
- van den Oordet al\.\(2017\)A\. van den Oord, O\. Vinyals, and K\. KavukcuogluNeural discrete representation learning\.InAdvances in Neural Information Processing Systems,pp\. 6306–6315\.External Links:1711\.00937Cited by:[§5](https://arxiv.org/html/2610.02440#S5.p4.1)\.
- Yoonet al\.\(2020\)J\. Yoon, Y\. Zhang, J\. Jordon, and M\. van der SchaarVIME: extending the success of self\- and semi\-supervised learning to tabular data\.InAdvances in Neural Information Processing Systems,Vol\.33\.Cited by:[§5](https://arxiv.org/html/2610.02440#S5.p4.1)\.
- Zhanget al\.\(2021\)W\. Zhang, D\. Zhou, L\. Li, and Q\. GuNeural Thompson Sampling\.InInternational Conference on Learning Representations,External Links:2010\.00827Cited by:[§1](https://arxiv.org/html/2610.02440#S1.p2.1),[§5](https://arxiv.org/html/2610.02440#S5.p2.1)\.
- Zhouet al\.\(2020\)D\. Zhou, L\. Li, and Q\. GuNeural contextual bandits with UCB\-based exploration\.InInternational Conference on Machine Learning,pp\. 11492–11502\.Cited by:[§1](https://arxiv.org/html/2610.02440#S1.p2.1),[§5](https://arxiv.org/html/2610.02440#S5.p2.1)\.

## Appendix ABase Learner Details

This appendix specifies the per\-cell operations for each model classℳ\\mathcal\{M\}in Algorithm[1](https://arxiv.org/html/2610.02440#alg1)\. All three variants share the same outer loop; they differ only in how each cellℳ⁡\[i,c,a\]\\mathcal\{M\}\[i,c,a\]maintains its posterior and produces predictions\. Each cell exposes three operations:sample\(x′x^\{\\prime\}\) returns a Thompson\-sampling draw \(used for arm selection in theScorestep\);mean\(x′x^\{\\prime\}\) returns the posterior mean prediction \(used to build the cumulative predictiony^i\\hat\{y\}\_\{i\}in theTargetsstep\);update\(x′x^\{\\prime\},r~\\tilde\{r\}\) incorporates a new observation\. Herex′=x\(i−1\)x^\{\\prime\}=x^\{\(i\-1\)\}is the context residual from \([1](https://arxiv.org/html/2610.02440#S2.E1)\) andr~\\tilde\{r\}is the pseudo\-target from Algorithm[1](https://arxiv.org/html/2610.02440#alg1), line[7](https://arxiv.org/html/2610.02440#alg1.l7)\. For the linear variants \(SGD\-LinTS\-RQ, LinTS\-RQ\), a constant intercept feature is appended:x′←\[x\(i−1\);1\]x^\{\\prime\}\\leftarrow\[x^\{\(i\-1\)\};1\], so the effective per\-centroid dimension isd\+1d\{\+\}1\. This ensures‖ϕi​\(x\)‖≥1\\\|\\phi\_\{i\}\(x\)\\\|\\geq 1\(Assumption[C\.1](https://arxiv.org/html/2610.02440#A3.Thmassumption1)\), which is needed for the exploration guarantee even when deep\-level residuals are small\.

Algorithm 2TS\-RQ cell operations \(count/sum\)1:Regularization

λ\\lambda; exploration scale

ν\\nu
2:State:count

n←0n\\leftarrow 0; sum

s←0s\\leftarrow 0
3:functionsample\(

x′x^\{\\prime\}\)⊳\\trianglerightx′x^\{\\prime\}is ignored

4:

μ^←s/\(λ\+n\)\\hat\{\\mu\}\\leftarrow s\\,/\(\\lambda\+n\)
5:returnsample from

𝒩⁡\(μ^,ν2/\(λ\+n\)\)\\mathcal\{N\}\\\!\\left\(\\hat\{\\mu\},\\;\\nu^\{2\}/\(\\lambda\+n\)\\right\)
6:endfunction

7:functionmean\(

x′x^\{\\prime\}\)⊳\\trianglerightx′x^\{\\prime\}is ignored

8:return

s/\(λ\+n\)s\\,/\(\\lambda\+n\)
9:endfunction

10:functionupdate\(

x′,r~x^\{\\prime\},\\,\\tilde\{r\}\)⊳\\trianglerightx′x^\{\\prime\}is ignored

11:

n←n\+1n\\leftarrow n\+1;

s←s\+r~s\\leftarrow s\+\\tilde\{r\}
12:endfunction

Algorithm 3SGD\-LinTS\-RQ cell operations \(diagonal linear\)1:Regularization

λ\\lambda; exploration scale

ν\\nu
2:State:diagonal precision

p∈ℝd\+1←λ​𝟏p\\in\\mathbb\{R\}^\{d\+1\}\\leftarrow\\lambda\\mathbf\{1\}; sufficient statistic

f∈ℝd\+1←𝟎f\\in\\mathbb\{R\}^\{d\+1\}\\leftarrow\\mathbf\{0\}⊳\\trianglerightx′←\[x′;1\]x^\{\\prime\}\\leftarrow\[x^\{\\prime\};1\]\(intercept appended\)

3:functionsample\(

x′x^\{\\prime\}\)

4:

θ^←f⊘p\\hat\{\\theta\}\\leftarrow f\\oslash p⊳\\trianglerightelement\-wise division

5:

θ~∼𝒩⁡\(θ^,ν2​diag​\(p\)−1\)\\tilde\{\\theta\}\\sim\\mathcal\{N\}\\\!\\left\(\\hat\{\\theta\},\\;\\nu^\{2\}\\,\\mathrm\{diag\}\(p\)^\{\-1\}\\right\)
6:return

θ~⊤​x′\\tilde\{\\theta\}^\{\\top\}x^\{\\prime\}
7:endfunction

8:functionmean\(

x′x^\{\\prime\}\)

9:return

\(f⊘p\)⊤​x′\(f\\oslash p\)^\{\\top\}x^\{\\prime\}
10:endfunction

11:functionupdate\(

x′,r~x^\{\\prime\},\\,\\tilde\{r\}\)

12:

p←p\+x′⊙x′p\\leftarrow p\+x^\{\\prime\}\\odot x^\{\\prime\}⊳\\trianglerightelement\-wise

13:

f←f\+r~⋅x′f\\leftarrow f\+\\tilde\{r\}\\cdot x^\{\\prime\}
14:endfunction

Algorithm 4LinTS\-RQ cell operations \(full\-covariance LinTS\)1:Regularization

λi=λ⋅0\.25i−1\\lambda\_\{i\}=\\lambda\\cdot 0\.25^\{i\-1\}; exploration scale

ν\\nu
2:State:inverse precision

B−1∈ℝ\(d\+1\)×\(d\+1\)←λi−1​IB^\{\-1\}\\in\\mathbb\{R\}^\{\(d\+1\)\\times\(d\+1\)\}\\leftarrow\\lambda\_\{i\}^\{\-1\}I;

f∈ℝd\+1←𝟎f\\in\\mathbb\{R\}^\{d\+1\}\\leftarrow\\mathbf\{0\}⊳\\trianglerightx′←\[x′;1\]x^\{\\prime\}\\leftarrow\[x^\{\\prime\};1\]\(intercept appended\)

3:functionsample\(

x′x^\{\\prime\}\)

4:

θ^←B−1​f\\hat\{\\theta\}\\leftarrow B^\{\-1\}f
5:

θ~∼𝒩⁡\(θ^,ν2​B−1\)\\tilde\{\\theta\}\\sim\\mathcal\{N\}\\\!\\left\(\\hat\{\\theta\},\\,\\nu^\{2\}B^\{\-1\}\\right\)
6:return

θ~⊤​x′\\tilde\{\\theta\}^\{\\top\}x^\{\\prime\}
7:endfunction

8:functionmean\(

x′x^\{\\prime\}\)

9:return

\(B−1​f\)⊤​x′\(B^\{\-1\}f\)^\{\\top\}x^\{\\prime\}
10:endfunction

11:functionupdate\(

x′,r~x^\{\\prime\},\\,\\tilde\{r\}\)⊳\\trianglerightSherman–Morrison onB−1B^\{\-1\}

12:

v←B−1​x′v\\leftarrow B^\{\-1\}x^\{\\prime\}
13:

B−1←B−1−v​v⊤/\(1\+x′⁣⊤​v\)B^\{\-1\}\\leftarrow B^\{\-1\}\-v\\,v^\{\\top\}/\(1\+x^\{\\prime\\top\}v\)
14:

f←f\+r~⋅x′f\\leftarrow f\+\\tilde\{r\}\\cdot x^\{\\prime\}
15:endfunction

## Appendix BBase Learner Properties

Algorithm[1](https://arxiv.org/html/2610.02440#alg1)is parameterized by a per\-cell base learnerℳ\\mathcal\{M\}\. Theorem[3\.1](https://arxiv.org/html/2610.02440#S3.Thmtheorem1)\(§[3](https://arxiv.org/html/2610.02440#S3)\) establishes asymptotic regret under three properties ofℳ\\mathcal\{M\}; the full proof is in Appendix[C](https://arxiv.org/html/2610.02440#A3)\. We state these properties below and establish them for each variant\. We use the notation from Appendix[C](https://arxiv.org/html/2610.02440#A3):ϕi​\(x\)\\phi\_\{i\}\(x\)is the level\-iifeature vector,μa​\(xt\)\\mu\_\{a\}\(x\_\{t\}\)the score mean \([22](https://arxiv.org/html/2610.02440#A3.E22)\),Var⁡\(sa∣xt,ℱt−1\)\\mathrm\{Var\}\(s\_\{a\}\\mid x\_\{t\},\\mathcal\{F\}\_\{t\-1\}\)the score variance \([23](https://arxiv.org/html/2610.02440#A3.E23)\),Ta,c,i​\(t\)T\_\{a,c,i\}\(t\)the visit count for armaaat centroidccand levelii, andr~i,t\\tilde\{r\}\_\{i,t\}the per\-level target \([24](https://arxiv.org/html/2610.02440#A3.E24)\)\.

Property 1 \(Eventual boundedness\)\.Score means are eventually bounded almost surely:

∃t0,B∀a,t\>t0\|μa​\(xt\)\|≤Ba\.s\.\\exists\_\{t\_\{0\},B\}\\;\\forall\_\{a,\\,t\>t\_\{0\}\}\\;\|\\mu\_\{a\}\(x\_\{t\}\)\|\\leq B\\qquad\\text\{a\.s\.\}\(7\)
Property 2 \(Starvation⇒\\Rightarrowpositive variance\)\.If armaavisits centroidccat leveliiat mostMMtimes \(Ta,c,i​\(t\)≤MT\_\{a,c,i\}\(t\)\\leq Mfor alltt\), then

Var⁡\(sa∣xt,ℱt−1\)≥σmin2\>0∀t​with​ki​\(xt\)=c,\\mathrm\{Var\}\(s\_\{a\}\\mid x\_\{t\},\\mathcal\{F\}\_\{t\-1\}\)\\geq\\sigma\_\{\\min\}^\{2\}\>0\\qquad\\forall\\,t\\text\{ with \}k\_\{i\}\(x\_\{t\}\)=c,\(8\)whereσmin2\\sigma\_\{\\min\}^\{2\}depends onM,λ,ν,CM,\\lambda,\\nu,Cbut not ontt\.

Property 3 \(Robust consistency\)\.Suppose all centroids at leveliiare visited infinitely often by armaa:Ta,c,i​\(t\)→∞T\_\{a,c,i\}\(t\)\\to\\inftyfor allccwithP⁡\(ki​\(x\)=c\)\>0P\(k\_\{i\}\(x\)=c\)\>0\. Suppose the targets have vanishing perturbation:r~i,t=r~i,t∞\+δt\\tilde\{r\}\_\{i,t\}=\\tilde\{r\}\_\{i,t\}^\{\\infty\}\+\\delta\_\{t\}withδt→0\\delta\_\{t\}\\to 0a\.s\., wherer~i,t∞\\tilde\{r\}\_\{i,t\}^\{\\infty\}is the stationary target under converged shallower levels\. Then predictions converge:

ϕi​\(x\)⊤​θ^a,i,t→ϕi​\(x\)⊤​θa,i∗a\.s\. for all​x​in the support,\\phi\_\{i\}\(x\)^\{\\top\}\\hat\{\\theta\}\_\{a,i,t\}\\;\\to\\;\\phi\_\{i\}\(x\)^\{\\top\}\\theta\_\{a,i\}^\{\*\}\\qquad\\text\{a\.s\.\\ for all \}x\\text\{ in the support\},\(9\)whereθa,i∗\\theta\_\{a,i\}^\{\*\}is the best predictor ofr~i∞\\tilde\{r\}\_\{i\}^\{\\infty\}fromϕi​\(x\)\\phi\_\{i\}\(x\)in the function class ofℳ\\mathcal\{M\}\.

### B\.1Verification for LinTS\-RQ

LinTS\-RQ maintains a full\-covariance precisionVa,i,t=λiI\+∑s≤t:as=aϕi\(xs\)ϕi\(xs\)⊤V\_\{a,i,t\}=\\lambda\_\{i\}I\+\\sum\_\{s\\leq t:\\,a\_\{s\}=a\}\\phi\_\{i\}\(x\_\{s\}\)\\,\\phi\_\{i\}\(x\_\{s\}\)^\{\\top\}and posterior meanθ^a,i,t=Va,i,t−1∑s:as=aϕi\(xs\)r~i,s\\hat\{\\theta\}\_\{a,i,t\}=V\_\{a,i,t\}^\{\-1\}\\sum\_\{s:a\_\{s\}=a\}\\phi\_\{i\}\(x\_\{s\}\)\\,\\tilde\{r\}\_\{i,s\}\.

Property 1\.For any armaa, levelii, and centroidcc: ifTa,c,i​\(t\)≤MT\_\{a,c,i\}\(t\)\\leq Mfor alltt, the estimate receives at mostMMupdates with bounded targets \(\|r~\|≤1\|\\tilde\{r\}\|\\leq 1\), so‖θ^a,i,c‖≤M​C/λ\\\|\\hat\{\\theta\}\_\{a,i,c\}\\\|\\leq MC/\\lambda\(since‖V−1‖≤1/λ\\\|V^\{\-1\}\\\|\\leq 1/\\lambdaand‖∑ϕ​r~‖≤M​C\\\|\\sum\\phi\\tilde\{r\}\\\|\\leq MC\), giving\|θ^a,i,c⊤​ϕi​\(x\)\|≤M​C2/λ\|\\hat\{\\theta\}\_\{a,i,c\}^\{\\top\}\\phi\_\{i\}\(x\)\|\\leq MC^\{2\}/\\lambda, deterministically bounded\. IfTa,c,i​\(t\)→∞T\_\{a,c,i\}\(t\)\\to\\infty, the strong law givesθ^a,i,c→θa,i,c∗\\hat\{\\theta\}\_\{a,i,c\}\\to\\theta\_\{a,i,c\}^\{\*\}, which is finite\. Since the number of arm/centroid combinations is finite, score means are eventually bounded\.

Property 2\.IfTa,c,i​\(t\)≤MT\_\{a,c,i\}\(t\)\\leq Mfor alltt, the centroid\-ccblock ofVa,i,tV\_\{a,i,t\}has at mostMMrank\-one updates, giving the time\-uniform boundVa,i,t\|c⪯\(λ\+M​C2\)​IV\_\{a,i,t\}\\big\|\_\{c\}\\preceq\(\\lambda\+MC^\{2\}\)I\. Whenki​\(xt\)=ck\_\{i\}\(x\_\{t\}\)=c:

Var⁡\(sa∣xt,ℱt−1\)\\displaystyle\\mathrm\{Var\}\(s\_\{a\}\\mid x\_\{t\},\\mathcal\{F\}\_\{t\-1\}\)≥ν2​ϕi​\(xt\)⊤​Va,i,t−1​ϕi​\(xt\)≥ν2λ\+M​C2≕σmin2\>0\.\\displaystyle\\geq\\nu^\{2\}\\,\\phi\_\{i\}\(x\_\{t\}\)^\{\\top\}V\_\{a,i,t\}^\{\-1\}\\phi\_\{i\}\(x\_\{t\}\)\\geq\\frac\{\\nu^\{2\}\}\{\\lambda\+MC^\{2\}\}\\eqqcolon\\sigma\_\{\\min\}^\{2\}\>0\.\(10\)
Property 3\.SupposeTa,c,i​\(t\)→∞T\_\{a,c,i\}\(t\)\\to\\inftyfor all centroidsccand targets satisfyr~i,s=r~i,s∞\+δs\\tilde\{r\}\_\{i,s\}=\\tilde\{r\}\_\{i,s\}^\{\\infty\}\+\\delta\_\{s\}withδs→0\\delta\_\{s\}\\to 0\. The ridge estimator decomposes as

θ^a,i,t\\displaystyle\\hat\{\\theta\}\_\{a,i,t\}=Va,i,t−1∑s:as=aϕi\(xs\)r~i,s∞⏟→θa,i∗\+Va,i,t−1∑s:as=aϕi\(xs\)δs⏟transient bias\.\\displaystyle=\\underbrace\{V\_\{a,i,t\}^\{\-1\}\\sum\_\{s:a\_\{s\}=a\}\\phi\_\{i\}\(x\_\{s\}\)\\,\\tilde\{r\}\_\{i,s\}^\{\\infty\}\}\_\{\\to\\,\\theta\_\{a,i\}^\{\*\}\}\\;\+\\;\\underbrace\{V\_\{a,i,t\}^\{\-1\}\\sum\_\{s:a\_\{s\}=a\}\\phi\_\{i\}\(x\_\{s\}\)\\,\\delta\_\{s\}\}\_\{\\text\{transient bias\}\}\.\(11\)The first term converges by standard ridge consistency \(stationary targets,Ta,c,i→∞T\_\{a,c,i\}\\to\\infty\)\. For the transient bias, apply Cauchy–Schwarz under‖v‖M=v⊤​M​v\\\|v\\\|\_\{M\}=\\sqrt\{v^\{\\top\}M\\,v\}withM=Va,i,t−1M=V\_\{a,i,t\}^\{\-1\}:

\|ϕi\(x\)⊤Va,i,t−1∑s:as=aϕi\(xs\)δs\|≤∥ϕi\(x\)∥Va,i,t−1⋅∥∑s:as=aϕi\(xs\)δs∥Va,i,t−1\.\\displaystyle\\biggl\|\\phi\_\{i\}\(x\)^\{\\top\}V\_\{a,i,t\}^\{\-1\}\\sum\_\{s:a\_\{s\}=a\}\\phi\_\{i\}\(x\_\{s\}\)\\,\\delta\_\{s\}\\biggr\|\\leq\\\|\\phi\_\{i\}\(x\)\\\|\_\{V\_\{a,i,t\}^\{\-1\}\}\\cdot\\biggl\\\|\\sum\_\{s:a\_\{s\}=a\}\\phi\_\{i\}\(x\_\{s\}\)\\,\\delta\_\{s\}\\biggr\\\|\_\{V\_\{a,i,t\}^\{\-1\}\}\.\(12\)
*First factor\.*WriteΣ^t=1Ta​\(t\)∑s:as=aϕi\(xs\)ϕi\(xs\)⊤\\hat\{\\Sigma\}\_\{t\}=\\frac\{1\}\{T\_\{a\}\(t\)\}\\sum\_\{s:a\_\{s\}=a\}\\phi\_\{i\}\(x\_\{s\}\)\\,\\phi\_\{i\}\(x\_\{s\}\)^\{\\top\}andΣ=𝔼⁡\[ϕi​\(x\)​ϕi​\(x\)⊤∣a\]\\Sigma=\\mathbb\{E\}\[\\phi\_\{i\}\(x\)\\phi\_\{i\}\(x\)^\{\\top\}\\mid a\]\. SinceVa,i,t=Ta​\(t\)​\(λTa​\(t\)​I\+Σ^t\)V\_\{a,i,t\}=T\_\{a\}\(t\)\\bigl\(\\tfrac\{\\lambda\}\{T\_\{a\}\(t\)\}\\,I\+\\hat\{\\Sigma\}\_\{t\}\\bigr\):

‖ϕi​\(x\)‖Va,i,t−12\\displaystyle\\\|\\phi\_\{i\}\(x\)\\\|\_\{V\_\{a,i,t\}^\{\-1\}\}^\{2\}=ϕi​\(x\)⊤​Va,i,t−1​ϕi​\(x\)\\displaystyle=\\phi\_\{i\}\(x\)^\{\\top\}V\_\{a,i,t\}^\{\-1\}\\,\\phi\_\{i\}\(x\)=1Ta​\(t\)​ϕi​\(x\)⊤​\(λTa​\(t\)​I\+Σ^t\)−1​ϕi​\(x\)\\displaystyle=\\frac\{1\}\{T\_\{a\}\(t\)\}\\;\\phi\_\{i\}\(x\)^\{\\top\}\\\!\\left\(\\tfrac\{\\lambda\}\{T\_\{a\}\(t\)\}\\,I\+\\hat\{\\Sigma\}\_\{t\}\\right\)^\{\\\!\-1\}\\phi\_\{i\}\(x\)→a\.s\.1Ta​\(t\)​ϕi​\(x\)⊤​Σ−1​ϕi​\(x\)\\displaystyle\\xrightarrow\{\\text\{a\.s\.\}\}\\;\\frac\{1\}\{T\_\{a\}\(t\)\}\\;\\phi\_\{i\}\(x\)^\{\\top\}\\Sigma^\{\-1\}\\phi\_\{i\}\(x\)≤cTa​\(t\)eventually,\\displaystyle\\leq\\frac\{c\}\{T\_\{a\}\(t\)\}\\qquad\\text\{eventually\},\(13\)where the third line usesΣ^t→a\.s\.Σ\\hat\{\\Sigma\}\_\{t\}\\xrightarrow\{\\text\{a\.s\.\}\}\\Sigma\(the strong law\), andc=2​C2/minc⁡λmin​\(Σc\)<∞c=2C^\{2\}/\\min\_\{c\}\\lambda\_\{\\min\}\(\\Sigma\_\{c\}\)<\\infty\. Each centroid blockΣc\\Sigma\_\{c\}is positive definite under a mild nondegeneracy condition: the conditional distribution ofϕi​\(x\)\\phi\_\{i\}\(x\)givenki​\(x\)=ck\_\{i\}\(x\)=chas full\-rank covariance\. In practice, the intercept feature ensures at least one nonzero direction, and the RQ residuals within each centroid span the remaining coordinates whenTa,cT\_\{a,c\}is large enough\. IfΣc\\Sigma\_\{c\}is rank\-deficient, the regularized estimator still converges in prediction space: sinceϕi​\(x\)\\phi\_\{i\}\(x\)for centroidcclies in the column space ofΣc\\Sigma\_\{c\}, the predictionϕi​\(x\)⊤​θ^\\phi\_\{i\}\(x\)^\{\\top\}\\hat\{\\theta\}converges regardless\. Also,‖ϕi​\(x\)‖≤C\\\|\\phi\_\{i\}\(x\)\\\|\\leq Cby Assumption[C\.1](https://arxiv.org/html/2610.02440#A3.Thmassumption1)\.

*Second factor\.*WriteΦ∈ℝb​p×Ta​\(t\)\\Phi\\in\\mathbb\{R\}^\{bp\\times T\_\{a\}\(t\)\}for the matrix whose columns areϕi​\(xs\)\\phi\_\{i\}\(x\_\{s\}\)andΔ∈ℝTa​\(t\)\\Delta\\in\\mathbb\{R\}^\{T\_\{a\}\(t\)\}for the vector of driftsδs\\delta\_\{s\}\. By the push\-through identity\(λ​I\+A​B\)−1​A=A​\(λ​I\+B​A\)−1\(\\lambda I\+AB\)^\{\-1\}A=A\(\\lambda I\+BA\)^\{\-1\}:

∥∑s:as=aϕi\(xs\)δs∥Va,i,t−12\\displaystyle\\biggl\\\|\\sum\_\{s:a\_\{s\}=a\}\\phi\_\{i\}\(x\_\{s\}\)\\,\\delta\_\{s\}\\biggr\\\|\_\{V\_\{a,i,t\}^\{\-1\}\}^\{2\}=Δ⊤​Φ⊤​\(λ​I\+Φ​Φ⊤\)−1​Φ​Δ\\displaystyle=\\Delta^\{\\top\}\\Phi^\{\\top\}\(\\lambda I\+\\Phi\\Phi^\{\\top\}\)^\{\-1\}\\Phi\\,\\Delta=Δ⊤​\(λ​I\+Φ⊤​Φ\)−1​Φ⊤​Φ⏟⪯I​Δ\\displaystyle=\\Delta^\{\\top\}\\underbrace\{\(\\lambda I\+\\Phi^\{\\top\}\\Phi\)^\{\-1\}\\Phi^\{\\top\}\\Phi\}\_\{\\preceq\\,I\}\\,\\Delta≤∥Δ∥2=∑s:as=aδs2\.\\displaystyle\\leq\\\|\\Delta\\\|^\{2\}=\\sum\_\{s:a\_\{s\}=a\}\\delta\_\{s\}^\{2\}\.\(14\)
*Combining\.*

\|ϕi\(x\)⊤Va,i,t−1∑s:as=aϕi\(xs\)δs\|2≤cTa​\(t\)∑s:as=aδs2\.\\displaystyle\\biggl\|\\phi\_\{i\}\(x\)^\{\\top\}V\_\{a,i,t\}^\{\-1\}\\sum\_\{s:a\_\{s\}=a\}\\phi\_\{i\}\(x\_\{s\}\)\\,\\delta\_\{s\}\\biggr\|^\{2\}\\leq\\frac\{c\}\{T\_\{a\}\(t\)\}\\sum\_\{s:a\_\{s\}=a\}\\delta\_\{s\}^\{2\}\.\(15\)Sinceδs→0\\delta\_\{s\}\\to 0andTa​\(t\)→∞T\_\{a\}\(t\)\\to\\infty, the Cesàro mean1Ta​\(t\)∑s:as=aδs2→0\\frac\{1\}\{T\_\{a\}\(t\)\}\\sum\_\{s:a\_\{s\}=a\}\\delta\_\{s\}^\{2\}\\to 0, so the transient bias prediction vanishes\. ∎

### B\.2Verification for SGD\-LinTS\-RQ

SGD\-LinTS\-RQ maintains a diagonal precisionp∈ℝdp\\in\\mathbb\{R\}^\{d\}withpk=λ\+∑s:as=ax′2s,kp\_\{k\}=\\lambda\+\\sum\_\{s:a\_\{s\}=a\}x^\{\\prime 2\}\_\{s,k\}and sufficient statisticfk=∑s:as=ar~sx′s,kf\_\{k\}=\\sum\_\{s:a\_\{s\}=a\}\\tilde\{r\}\_\{s\}\\,x^\{\\prime\}\_\{s,k\}, yielding the coordinate\-wise estimatorθ^k=fk/pk\\hat\{\\theta\}\_\{k\}=f\_\{k\}/p\_\{k\}\. This isddindependent scalar regressions, one per feature coordinate\.

Property 1\.Same structure as LinTS\-RQ: bounded updates when starved, SLLN when explored, applied coordinate\-wise\.

Property 2\.IfTa,c,i​\(t\)≤MT\_\{a,c,i\}\(t\)\\leq M, thenpa,i,k,t≤λ\+M​C2p\_\{a,i,k,t\}\\leq\\lambda\+MC^\{2\}for every coordinatekk, giving

Var⁡\(sa∣xt,ℱt−1\)\\displaystyle\\mathrm\{Var\}\(s\_\{a\}\\mid x\_\{t\},\\mathcal\{F\}\_\{t\-1\}\)=∑j=1ℓν2​∑k=1d\+1\(ϕj,k\)2pa,j,k,t≥ν2​‖ϕi​\(xt\)‖2λ\+M​C2≥ν2λ\+M​C2\>0\\displaystyle=\\sum\_\{j=1\}^\{\\ell\}\\nu^\{2\}\\sum\_\{k=1\}^\{d\+1\}\\frac\{\(\\phi\_\{j,k\}\)^\{2\}\}\{p\_\{a,j,k,t\}\}\\geq\\frac\{\\nu^\{2\}\\\|\\phi\_\{i\}\(x\_\{t\}\)\\\|^\{2\}\}\{\\lambda\+MC^\{2\}\}\\geq\\frac\{\\nu^\{2\}\}\{\\lambda\+MC^\{2\}\}\>0\(16\)by Assumption[C\.1](https://arxiv.org/html/2610.02440#A3.Thmassumption1), where the sum is overd\+1d\{\+\}1coordinates \(including the intercept that ensures‖ϕi​\(x\)‖≥1\\\|\\phi\_\{i\}\(x\)\\\|\\geq 1even when context residuals are small at deep levels\)\.

Property 3\.By the strong law applied to each coordinate independently:

θ^a,i,k,t→θa,i,k∗≔𝔼⁡\[r~i∞⋅xk′\]𝔼⁡\[xk′2\],\\displaystyle\\hat\{\\theta\}\_\{a,i,k,t\}\\to\\theta^\{\*\}\_\{a,i,k\}\\coloneqq\\frac\{\\mathbb\{E\}\[\\tilde\{r\}\_\{i\}^\{\\infty\}\\cdot x^\{\\prime\}\_\{k\}\]\}\{\\mathbb\{E\}\[x^\{\\prime 2\}\_\{k\}\]\},\(17\)the coordinate\-wise optimal coefficient\. The transient bias at coordinatekksatisfies

\|fbiask/pk\|≤C1Ta​\(t\)∑s:as=a\|δs\|→0\\displaystyle\|f^\{\\mathrm\{bias\}\}\_\{k\}/p\_\{k\}\|\\leq C\\,\\frac\{1\}\{T\_\{a\}\(t\)\}\\sum\_\{s:a\_\{s\}=a\}\|\\delta\_\{s\}\|\\to 0\(18\)by the Cesàro argument\. Note thatθa,i∗\\theta^\{\*\}\_\{a,i\}is the coordinate\-wise optimal, which may differ from the full\-linear optimal when features are correlated; consequentlyΔℓ​\(ℳ\)\\Delta\_\{\\ell\}\(\\mathcal\{M\}\)for SGD\-LinTS\-RQ is evaluated over the coordinate\-wise linear function class\. ∎

### B\.3Verification for TS\-RQ

TS\-RQ is the scalar special case: the per\-cell model ignores features and maintains only a countnnand sumss\(Algorithm[2](https://arxiv.org/html/2610.02440#alg2)\)\. The estimateμ^=s/\(λ\+n\)\\hat\{\\mu\}=s/\(\\lambda\+n\)is a scalar ridge regression with constant feature11\. All three properties follow from the LinTS\-RQ checks withd=1d=1andϕi​\(x\)=1\\phi\_\{i\}\(x\)=1\. ∎

## Appendix CFixed\-Depth Regret Analysis

This appendix develops the full fixed\-depth analysis for Algorithm[1](https://arxiv.org/html/2610.02440#alg1), including the asymptotic regret theorem and the depth\-rate decomposition of Theorem[3\.2](https://arxiv.org/html/2610.02440#S3.Thmtheorem2)\.

###### Assumption C\.1\.

All per\-level feature vectors are bounded:1≤‖ϕi​\(x\)‖≤C1\\leq\\\|\\phi\_\{i\}\(x\)\\\|\\leq Cfor alli,xi,x\.

The lower bound‖ϕi​\(x\)‖≥1\\\|\\phi\_\{i\}\(x\)\\\|\\geq 1is ensured by appending a constant intercept feature to eachϕi​\(x\)\\phi\_\{i\}\(x\)\.

Definition[3\.1](https://arxiv.org/html/2610.02440#S3.Thmdefinition1)\(Additive misspecification, restated from §[3](https://arxiv.org/html/2610.02440#S3)\)\. The additive misspecificationΔℓ​\(ℳ\)\\Delta\_\{\\ell\}\(\\mathcal\{M\}\)is defined in \([2](https://arxiv.org/html/2610.02440#S3.E2)\)\. Since deeper models contain shallower ones \(fℓ\+1≡0f\_\{\\ell\+1\}\\equiv 0\),Δℓ\+1≤Δℓ\\Delta\_\{\\ell\+1\}\\leq\\Delta\_\{\\ell\}\.

Theorem[3\.1](https://arxiv.org/html/2610.02440#S3.Thmtheorem1)\(Asymptotic regret, restated from §[3](https://arxiv.org/html/2610.02440#S3)\)\.For any base learnerℳ\\mathcal\{M\}satisfying Properties 1–3 \(Appendix[B](https://arxiv.org/html/2610.02440#A2)\), the asymptotic regret rate satisfies \([3](https://arxiv.org/html/2610.02440#S3.E3)\), wherer^∞\\hat\{r\}\_\{\\infty\}is the converged prediction of the sequential residual\-fitting limit \(Lemma[C\.1](https://arxiv.org/html/2610.02440#A3.Thmlemma1)\(b\)\)\. Sincer^∞\\hat\{r\}\_\{\\infty\}is one feasible additive predictor, the right\-hand side is≥2​Δℓ​\(ℳ\)\\geq 2\\,\\Delta\_\{\\ell\}\(\\mathcal\{M\}\), with equality when the stagewise and joint optima coincide\.

###### Lemma C\.1\(Exploration and convergence\)\.

For any base learnerℳ\\mathcal\{M\}satisfying Properties 1–3, for each armaaand leveli∈\{1,…,ℓ\}i\\in\\\{1,\\ldots,\\ell\\\}:

1. *\(a\)*Every arm visits every centroid at leveliiinfinitely often:Ta,c​\(T\)→∞T\_\{a,c\}\(T\)\\to\\inftya\.s\. for all centroidsccwithP⁡\(ki​\(x\)=c\)\>0P\(k\_\{i\}\(x\)=c\)\>0\.
2. *\(b\)*The per\-level predictions converge:ϕi​\(x\)⊤​θ^a,i,t→ϕi​\(x\)⊤​θa,i∗\\phi\_\{i\}\(x\)^\{\\top\}\\hat\{\\theta\}\_\{a,i,t\}\\to\\phi\_\{i\}\(x\)^\{\\top\}\\theta\_\{a,i\}^\{\*\}for allxxin the support\.

The proof proceeds by induction on the levelii\. Each level’s targets depend on all shallower levels’ estimates, creating a coupled non\-stationary system\. Properties 1–3 \(Appendix[B](https://arxiv.org/html/2610.02440#A2)\) abstract this coupling for three distinct base learners\. The per\-level posterior can be viewed as a block\-diagonal approximation of the joint posterior analyzed in Appendix[F](https://arxiv.org/html/2610.02440#A6)\.

Notation\.Each feature vectorϕj​\(x\)\\phi\_\{j\}\(x\)is supported on a single centroid block at leveljj\(placing the context residualx\(j−1\)x^\{\(j\-1\)\}at centroidkj​\(x\)k\_\{j\}\(x\)and zeros elsewhere\)\. The TS draw, score, and selection for armaaat contextxtx\_\{t\}are

∀aθ~a,j\\displaystyle\\forall\_\{a\}\\tilde\{\\theta\}\_\{a,j\}∼ℳ⁡\[j,kj,a\]\.sample⁡\(xt\(j−1\)\),\\displaystyle\\sim\\mathcal\{M\}\[j,\\,k\_\{j\},\\,a\]\.\\mathrm\{sample\}\(x\_\{t\}^\{\(j\-1\)\}\),\(19\)∀asa\\displaystyle\\forall\_\{a\}s\_\{a\}=∑j=1ℓθ~a,j⊤​ϕj​\(xt\),\\displaystyle=\\sum\_\{j=1\}^\{\\ell\}\\tilde\{\\theta\}\_\{a,j\}^\{\\top\}\\phi\_\{j\}\(x\_\{t\}\),\(20\)at\\displaystyle a\_\{t\}=arg⁡maxa⁡sa=arg⁡maxa⁡σ⁡\(sa\)\\displaystyle=\\arg\\max\_\{a\}s\_\{a\}=\\arg\\max\_\{a\}\\sigma\(s\_\{a\}\)\(21\)independently across levels; the last equality holds sinceσ\\sigmais monotone\. The*score mean*and conditional variance are

μa​\(xt\)\\displaystyle\\mu\_\{a\}\(x\_\{t\}\)=𝔼\[sa∣xt,ℱt−1\]=∑j=1ℓθ^a,j,t⊤ϕj\(xt\),\\displaystyle=\\mathbb\{E\}\[s\_\{a\}\\mid x\_\{t\},\\mathcal\{F\}\_\{t\-1\}\]=\\sum\_\{j=1\}^\{\\ell\}\\hat\{\\theta\}\_\{a,j,t\}^\{\\top\}\\phi\_\{j\}\(x\_\{t\}\),\(22\)Var⁡\(sa∣xt,ℱt−1\)\\displaystyle\\mathrm\{Var\}\(s\_\{a\}\\mid x\_\{t\},\\mathcal\{F\}\_\{t\-1\}\)=∑j=1ℓν2​ϕj​\(xt\)⊤​Va,j,t−1​ϕj​\(xt\)\.\\displaystyle=\\sum\_\{j=1\}^\{\\ell\}\\nu^\{2\}\\,\\phi\_\{j\}\(x\_\{t\}\)^\{\\top\}V\_\{a,j,t\}^\{\-1\}\\phi\_\{j\}\(x\_\{t\}\)\.\(23\)The reward prediction isy^a=σ⁡\(μa\)∈\[0,1\]\\hat\{y\}\_\{a\}=\\sigma\(\\mu\_\{a\}\)\\in\[0,1\], and the per\-level target \(Algorithm[1](https://arxiv.org/html/2610.02440#alg1), line[7](https://arxiv.org/html/2610.02440#alg1.l7)\) is

r~j,t=rt−σ⁡\(∑i=1j−1θ^at,i,t⊤​ϕi​\(xt\)\)∈\[−1,1\]\.\\tilde\{r\}\_\{j,t\}=r\_\{t\}\-\\sigma\\\!\\left\(\\sum\_\{i=1\}^\{j\-1\}\\hat\{\\theta\}\_\{a\_\{t\},i,t\}^\{\\top\}\\phi\_\{i\}\(x\_\{t\}\)\\right\)\\in\[\-1,1\]\.\(24\)For clarity, the damping factorη\\etafrom Algorithm[1](https://arxiv.org/html/2610.02440#alg1)is set to11in the analysis; absorbingηj−1\\eta^\{j\-1\}intoϕj\\phi\_\{j\}does not affect the proof structure, though it scales the effective variance at leveljjbyη2​\(j−1\)\\eta^\{2\(j\-1\)\}, which slows exploration at deeper levels whenη<1\\eta<1\. The asymptotic result is unaffected \(the lower boundσmin2\\sigma\_\{\\min\}^\{2\}remains positive\), but the pre\-asymptotic exploration cost at deep levels grows asη−2​\(j−1\)\\eta^\{\-2\(j\-1\)\}\.

###### Lemma C\.2\(Score means are eventually bounded\)\.

All arm score means are eventually bounded:

∃t0,B∀a,t\>t0\|μa​\(xt\)\|≤Ba\.s\.\\displaystyle\\exists\_\{t\_\{0\},B\}\\forall\_\{a,\\,t\>t\_\{0\}\}\|\\mu\_\{a\}\(x\_\{t\}\)\|\\leq B\\qquad\\text\{a\.s\.\}\(25\)

###### Proof\.

Immediate from Property 1 \(Appendix[B](https://arxiv.org/html/2610.02440#A2)\)\. ∎

###### Lemma C\.3\(Exploration and convergence, restated\)\.

For any base learnerℳ\\mathcal\{M\}satisfying Properties 1–3 \(Appendix[B](https://arxiv.org/html/2610.02440#A2)\), for each armaaand leveli∈\{1,…,ℓ\}i\\in\\\{1,\\ldots,\\ell\\\}:

1. *\(a\)*Every arm visits every centroid at leveliiinfinitely often:Ta,c​\(T\)→∞T\_\{a,c\}\(T\)\\to\\inftya\.s\. for all centroidsccwithP⁡\(ki​\(x\)=c\)\>0P\(k\_\{i\}\(x\)=c\)\>0\.
2. *\(b\)*The per\-level predictions converge:ϕi​\(x\)⊤​θ^a,i,t→ϕi​\(x\)⊤​θa,i∗\\phi\_\{i\}\(x\)^\{\\top\}\\hat\{\\theta\}\_\{a,i,t\}\\to\\phi\_\{i\}\(x\)^\{\\top\}\\theta\_\{a,i\}^\{\*\}for allxxin the support, whereθa,i∗\\theta\_\{a,i\}^\{\*\}is the best linear predictor for the clipped residual at leveliigiven converged shallower levels\.

###### Proof of Lemma[C\.1](https://arxiv.org/html/2610.02440#A3.Thmlemma1)\.

The proof is by induction on the leveliiand applies to any base learnerℳ\\mathcal\{M\}satisfying Properties 1–3\.

*Induction base \(i=1i=1\)\.*

*\(a\) Per\-centroid exploration\.*Assume that for somea,ca,c,

Ta,c​\(T\)\\displaystyle T\_\{a,c\}\(T\)≤M<∞,\\displaystyle\\leq M<\\infty,\(26\)P​\(k1​\(x\)=c\)\\displaystyle P\(k\_\{1\}\(x\)=c\)≕pc\>0\.\\displaystyle\\eqqcolon p\_\{c\}\>0\.\(27\)By Property 2, the score variance satisfies

Var⁡\(sa∣xt,ℱt−1\)≥σmin2\>0∀t​with​k1​\(xt\)=c\.\\displaystyle\\mathrm\{Var\}\(s\_\{a\}\\mid x\_\{t\},\\mathcal\{F\}\_\{t\-1\}\)\\geq\\sigma\_\{\\min\}^\{2\}\>0\\qquad\\forall\\,t\\text\{ with \}k\_\{1\}\(x\_\{t\}\)=c\.\(28\)By Lemma[C\.2](https://arxiv.org/html/2610.02440#A3.Thmlemma2), there exist \(a\.s\.\) finiteBBandt0t\_\{0\}such that every arm’s score mean satisfies\|μa′​\(xt\)\|≤B\|\\mu\_\{a^\{\\prime\}\}\(x\_\{t\}\)\|\\leq Bfor allt≥t0t\\geq t\_\{0\}\. Fort≥t0t\\geq t\_\{0\}withk1​\(xt\)=ck\_\{1\}\(x\_\{t\}\)=c, the probability that armaais selected satisfies

P⁡\(at=a∣xt,ℱt−1\)\\displaystyle P\(a\_\{t\}=a\\mid x\_\{t\},\\mathcal\{F\}\_\{t\-1\}\)≥P⁡\(sa\>B\)​∏a′≠aP⁡\(sa′≤B\)\\displaystyle\\geq P\(s\_\{a\}\>B\)\\,\\prod\_\{a^\{\\prime\}\\neq a\}P\(s\_\{a^\{\\prime\}\}\\leq B\)≥\[1−Φ⁡\(2​B/σmin\)\]⋅\(12\)K−1≕pmin\>0,\\displaystyle\\geq\\bigl\[1\-\\Phi\(2B/\\sigma\_\{\\min\}\)\\bigr\]\\cdot\(\{\\tfrac\{1\}\{2\}\}\)^\{K\-1\}\\eqqcolon p\_\{\\min\}\>0,\(29\)where the first factor uses anti\-concentration of the score distribution: all three variants use Gaussian sampling \(Algorithms[2](https://arxiv.org/html/2610.02440#alg2)–[4](https://arxiv.org/html/2610.02440#alg4)\), sosas\_\{a\}is Gaussian with variance≥σmin2\\geq\\sigma\_\{\\min\}^\{2\}and mean≥−B\\geq\-B, giving the stated normal tail bound\. Each factor in the product is≥12\\geq\\tfrac\{1\}\{2\}becauseμa′≤B\\mu\_\{a^\{\\prime\}\}\\leq B\. Sincek1​\(xt\)=ck\_\{1\}\(x\_\{t\}\)=coccurs infinitely often \(i\.i\.d\. contexts withpc\>0p\_\{c\}\>0\) and each occurrence satisfiesP⁡\(at=a∣xt,ℱt−1\)≥pminP\(a\_\{t\}=a\\mid x\_\{t\},\\mathcal\{F\}\_\{t\-1\}\)\\geq p\_\{\\min\}\(a uniform conditional lower bound, not independence\), the Lévy extension of the Borel–Cantelli lemma givesTa,c→∞T\_\{a,c\}\\to\\infty, contradicting \([27](https://arxiv.org/html/2610.02440#A3.E27)\)\.

*\(b\) Prediction convergence\.*The targetsr~1,t=rt−σ⁡\(0\)\\tilde\{r\}\_\{1,t\}=r\_\{t\}\-\\sigma\(0\)are stationary \(no dependence on shallower levels\), soδt=0\\delta\_\{t\}=0\. By \(a\),Ta,c​\(T\)→∞T\_\{a,c\}\(T\)\\to\\inftyfor every centroidcc\. Property 3 \(withδt=0\\delta\_\{t\}=0\) givesϕ1​\(x\)⊤​θ^a,1,t→ϕ1​\(x\)⊤​θa,1∗\\phi\_\{1\}\(x\)^\{\\top\}\\hat\{\\theta\}\_\{a,1,t\}\\to\\phi\_\{1\}\(x\)^\{\\top\}\\theta\_\{a,1\}^\{\*\}\.

*Induction step \(i≥2i\\geq 2\)\.*Assume \(a\) and \(b\) hold for levels1,…,i−11,\\ldots,i\{\-\}1\.

*\(a\) Per\-centroid exploration\.*Similar to the induction base: ifTa,c​\(T\)≤MT\_\{a,c\}\(T\)\\leq Mfor some centroidccat levelii, Property 2 givesVar⁡\(sa\)≥σmin2\>0\\mathrm\{Var\}\(s\_\{a\}\)\\geq\\sigma\_\{\\min\}^\{2\}\>0whenki​\(xt\)=ck\_\{i\}\(x\_\{t\}\)=c\. By Lemma[C\.2](https://arxiv.org/html/2610.02440#A3.Thmlemma2), score means are eventually bounded, so Gaussian anti\-concentration and Borel–Cantelli yield the contradictionTa,c→∞T\_\{a,c\}\\to\\infty\.

*\(b\) Prediction convergence\.*The clipped residual target for leveliiis

r~i,t=rt−σ⁡\(∑j=1i−1θ^a,j,t⊤​ϕj​\(xt\)\)\.\\tilde\{r\}\_\{i,t\}=r\_\{t\}\-\\sigma\\\!\\left\(\\sum\_\{j=1\}^\{i\-1\}\\hat\{\\theta\}\_\{a,j,t\}^\{\\top\}\\phi\_\{j\}\(x\_\{t\}\)\\right\)\.\(30\)Sinceσ\\sigmais11\-Lipschitz and levels1,…,i−11,\\ldots,i\{\-\}1have converged in prediction space by the induction hypothesis \(b\), the target drift satisfies

\|r~i,t−r~i,t∞\|≤∑j=1i−1\|\(θ^a,j,t−θa,j∗\)⊤​ϕj​\(xt\)\|≕δt→0,\|\\tilde\{r\}\_\{i,t\}\-\\tilde\{r\}\_\{i,t\}^\{\\infty\}\|\\leq\\sum\_\{j=1\}^\{i\-1\}\\left\|\(\\hat\{\\theta\}\_\{a,j,t\}\-\\theta\_\{a,j\}^\{\*\}\)^\{\\top\}\\phi\_\{j\}\(x\_\{t\}\)\\right\|\\eqqcolon\\delta\_\{t\}\\to 0,\(31\)where each summand vanishes by the induction hypothesis\. By \(a\),Ta,c,i​\(t\)→∞T\_\{a,c,i\}\(t\)\\to\\inftyfor all centroids\. Property 3 \(withδt→0\\delta\_\{t\}\\to 0\) givesϕi​\(x\)⊤​θ^a,i,t→ϕi​\(x\)⊤​θa,i∗\\phi\_\{i\}\(x\)^\{\\top\}\\hat\{\\theta\}\_\{a,i,t\}\\to\\phi\_\{i\}\(x\)^\{\\top\}\\theta\_\{a,i\}^\{\*\}\.

∎

###### Proof of Theorem[3\.1](https://arxiv.org/html/2610.02440#S3.Thmtheorem1)\(Asymptotic regret for Algorithm[1](https://arxiv.org/html/2610.02440#alg1)\)\.

By Lemma[C\.1](https://arxiv.org/html/2610.02440#A3.Thmlemma1)\(b\), for each armaa, the converged prediction is

r^∞​\(x,a\)=σ⁡\(∑i=1ℓθa,i∗⁣⊤​ϕi​\(x\)\)\.\\displaystyle\\hat\{r\}\_\{\\infty\}\(x,a\)=\\sigma\\\!\\left\(\\sum\_\{i=1\}^\{\\ell\}\\theta\_\{a,i\}^\{\*\\top\}\\phi\_\{i\}\(x\)\\right\)\.\(32\)Define

a^​\(x\)=arg⁡maxa​r^∞​\(x,a\)\\displaystyle\\hat\{a\}\(x\)=\\arg\\max\_\{a\}\\hat\{r\}\_\{\\infty\}\(x,a\)\(33\)as the arm selected under the converged model\.

*Post\-convergence regret\.*Once predictions have converged, TS selectsa^​\(xt\)\\hat\{a\}\(x\_\{t\}\)at every round \(the posterior variance vanishes; model\-level tiesr^∞​\(x,a\)=r^∞​\(x,a′\)\\hat\{r\}\_\{\\infty\}\(x,a\)=\\hat\{r\}\_\{\\infty\}\(x,a^\{\\prime\}\)occur on a measure\-zero set of contexts under continuous features, and contribute at most2​Δℓ2\\Delta\_\{\\ell\}regret per round regardless\)\. The per\-round regret is

r∗​\(xt,at∗\)−r∗​\(xt,a^​\(xt\)\)\\displaystyle r^\{\*\}\(x\_\{t\},a\_\{t\}^\{\*\}\)\-r^\{\*\}\(x\_\{t\},\\hat\{a\}\(x\_\{t\}\)\)=\[r∗​\(xt,at∗\)−r^∞​\(xt,at∗\)\]\\displaystyle=\\bigl\[r^\{\*\}\(x\_\{t\},a\_\{t\}^\{\*\}\)\-\\hat\{r\}\_\{\\infty\}\(x\_\{t\},a\_\{t\}^\{\*\}\)\\bigr\]−\[r∗​\(xt,a^\)−r^∞​\(xt,a^\)\]\\displaystyle\\quad\-\\bigl\[r^\{\*\}\(x\_\{t\},\\hat\{a\}\)\-\\hat\{r\}\_\{\\infty\}\(x\_\{t\},\\hat\{a\}\)\\bigr\]\+\[r^∞​\(xt,at∗\)−r^∞​\(xt,a^\)\]⏟≤0,\\displaystyle\\quad\+\\underbrace\{\\bigl\[\\hat\{r\}\_\{\\infty\}\(x\_\{t\},a\_\{t\}^\{\*\}\)\-\\hat\{r\}\_\{\\infty\}\(x\_\{t\},\\hat\{a\}\)\\bigr\]\}\_\{\\leq\\,0\},\(34\)where the last term is≤0\\leq 0becausea^\\hat\{a\}maximizesr^∞\\hat\{r\}\_\{\\infty\}\. Therefore

r∗​\(xt,at∗\)−r∗​\(xt,a^​\(xt\)\)≤2​maxa​\|r∗​\(xt,a\)−r^∞​\(xt,a\)\|\.r^\{\*\}\(x\_\{t\},a\_\{t\}^\{\*\}\)\-r^\{\*\}\(x\_\{t\},\\hat\{a\}\(x\_\{t\}\)\)\\leq 2\\max\_\{a\}\\left\|r^\{\*\}\(x\_\{t\},a\)\-\\hat\{r\}\_\{\\infty\}\(x\_\{t\},a\)\\right\|\.\(35\)Taking expectation overxtx\_\{t\}:

𝔼⁡\[r∗​\(xt,at∗\)−r∗​\(xt,a^​\(xt\)\)\]≤2​𝔼x​\[maxa⁡\|r∗​\(x,a\)−r^∞​\(x,a\)\|\]≕2​Δ¯ℓ​\(ℳ\),\\mathbb\{E\}\\\!\\left\[r^\{\*\}\(x\_\{t\},a\_\{t\}^\{\*\}\)\-r^\{\*\}\(x\_\{t\},\\hat\{a\}\(x\_\{t\}\)\)\\right\]\\leq 2\\,\\mathbb\{E\}\_\{x\}\\\!\\left\[\\max\_\{a\}\\left\|r^\{\*\}\(x,a\)\-\\hat\{r\}\_\{\\infty\}\(x,a\)\\right\|\\right\]\\eqqcolon 2\\,\\bar\{\\Delta\}\_\{\\ell\}\(\\mathcal\{M\}\),\(36\)whereΔ¯ℓ\\bar\{\\Delta\}\_\{\\ell\}is the approximation error of the sequential residual\-fitting limitr^∞​\(x,a\)=σ⁡\(∑iθa,i∗⁣⊤​ϕi​\(x\)\)\\hat\{r\}\_\{\\infty\}\(x,a\)=\\sigma\(\\sum\_\{i\}\\theta\_\{a,i\}^\{\*\\top\}\\phi\_\{i\}\(x\)\)\. Sincer^∞\\hat\{r\}\_\{\\infty\}is one feasible additive predictor,Δ¯ℓ≥Δℓ\\bar\{\\Delta\}\_\{\\ell\}\\geq\\Delta\_\{\\ell\}\(Definition[3\.1](https://arxiv.org/html/2610.02440#S3.Thmdefinition1)\), with equality when the stagewise and joint optima coincide\.

*Exploration regret\.*Before convergence, TS may select suboptimal arms\. By Lemma[C\.1](https://arxiv.org/html/2610.02440#A3.Thmlemma1)\(b\),θ^a,i,t→θa,i∗\\hat\{\\theta\}\_\{a,i,t\}\\to\\theta\_\{a,i\}^\{\*\}for all arms and levels \(in prediction space\), so the posterior means converge\. Since the posterior variances vanish \(ν2​Va,i,t−1→0\\nu^\{2\}V\_\{a,i,t\}^\{\-1\}\\to 0asTa​\(t\)→∞T\_\{a\}\(t\)\\to\\inftyby Lemma[C\.1](https://arxiv.org/html/2610.02440#A3.Thmlemma1)\(a\)\), the TS draws converge:

θ~a,i,t→θa,i∗\\displaystyle\\tilde\{\\theta\}\_\{a,i,t\}\\to\\theta\_\{a,i\}^\{\*\}\(37\)a\.s\., and arm selection converges toa^​\(xt\)\\hat\{a\}\(x\_\{t\}\)\. For contexts where the optimal arm gapr^∞​\(x,a^​\(x\)\)−maxa≠a^​\(x\)⁡r^∞​\(x,a\)\>0\\hat\{r\}\_\{\\infty\}\(x,\\hat\{a\}\(x\)\)\-\\max\_\{a\\neq\\hat\{a\}\(x\)\}\\hat\{r\}\_\{\\infty\}\(x,a\)\>0, the TS draws eventually resolve to the correct arm; exact ties have zero probability under continuous TS draws\. For anyϵ\>0\\epsilon\>0, there existsT0T\_\{0\}such that fort\>T0t\>T\_\{0\},at=a^​\(xt\)a\_\{t\}=\\hat\{a\}\(x\_\{t\}\)except on a set of measure<ϵ<\\epsilon\. The exploration regret \(rounds whereat≠a^​\(xt\)a\_\{t\}\\neq\\hat\{a\}\(x\_\{t\}\)\) therefore satisfies

∑t=1T𝟏\[at≠a^\(xt\)\]=o\(T\)\.\\displaystyle\\sum\_\{t=1\}^\{T\}\\mathbf\{1\}\[a\_\{t\}\\neq\\hat\{a\}\(x\_\{t\}\)\]=o\(T\)\.\(38\)Since per\-round regret is bounded by11, the cumulative exploration regret iso⁡\(T\)o\(T\)\.

*Total\.*

R⁡\(T,ℓ\)T=o⁡\(T\)T⏟→0\+2​Δ¯ℓ​\(ℳ\)⏟from \([36](https://arxiv.org/html/2610.02440#A3.E36)\),\\frac\{R\(T,\\ell\)\}\{T\}=\\underbrace\{\\frac\{o\(T\)\}\{T\}\}\_\{\\to\\,0\}\+\\underbrace\{2\\,\\bar\{\\Delta\}\_\{\\ell\}\(\\mathcal\{M\}\)\}\_\{\\text\{from~\\eqref\{eq:post\_conv\}\}\},\(39\)givinglim supT→∞R⁡\(T,ℓ\)/T≤2​Δ¯ℓ​\(ℳ\)=2​𝔼x​\[maxa⁡\|r∗−r^∞\|\]\\limsup\_\{T\\to\\infty\}R\(T,\\ell\)/T\\leq 2\\,\\bar\{\\Delta\}\_\{\\ell\}\(\\mathcal\{M\}\)=2\\,\\mathbb\{E\}\_\{x\}\[\\max\_\{a\}\|r^\{\*\}\-\\hat\{r\}\_\{\\infty\}\|\]\. ∎

### C\.1Proof of the depth\-rate result

Fix one arm and letℋ=L2​\(P\)\\mathcal\{H\}=L^\{2\}\(P\)\. Because each RQ symbol takes finitely many values,AℓA\_\{\\ell\}is a closed finite\-dimensional subspace of the closed saturated spaceSℓS\_\{\\ell\}\. Denote their orthogonal projections byPAℓP\_\{A\_\{\\ell\}\}andPSℓP\_\{S\_\{\\ell\}\}\.

###### Proof of Theorem[3\.2](https://arxiv.org/html/2610.02440#S3.Thmtheorem2)\.

SinceAℓ⊆SℓA\_\{\\ell\}\\subseteq S\_\{\\ell\},PAℓ=PAℓ​PSℓP\_\{A\_\{\\ell\}\}=P\_\{A\_\{\\ell\}\}P\_\{S\_\{\\ell\}\}\. We may therefore write

r∗−PAℓ​r∗=\(r∗−PSℓ​r∗\)\+\(PSℓ​r∗−PAℓ​r∗\)\.r^\{\*\}\-P\_\{A\_\{\\ell\}\}r^\{\*\}=\\bigl\(r^\{\*\}\-P\_\{S\_\{\\ell\}\}r^\{\*\}\\bigr\)\+\\bigl\(P\_\{S\_\{\\ell\}\}r^\{\*\}\-P\_\{A\_\{\\ell\}\}r^\{\*\}\\bigr\)\.\(40\)The first summand lies inSℓ⟂S\_\{\\ell\}^\{\\perp\}and the second inSℓS\_\{\\ell\}\. Pythagoras gives the first identity in \([4](https://arxiv.org/html/2610.02440#S3.E4)\)\. For the reconstruction bound, conditional expectation is theL2L^\{2\}projection ontoSℓS\_\{\\ell\}, so

\(δℓsat\)2=𝔼\[Var\(r∗\(x\)∣z1:ℓ\)\]\.\(\\delta\_\{\\ell\}^\{\\rm sat\}\)^\{2\}=\\mathbb\{E\}\\\!\\left\[\\operatorname\{Var\}\(r^\{\*\}\(x\)\\mid z\_\{1:\\ell\}\)\\right\]\.\(41\)Within a prefix cellcc, letx,x′x,x^\{\\prime\}be independent draws fromP\(⋅∣c\)P\(\\cdot\\mid c\)\. Lipschitz continuity yields

Var⁡\(r∗​\(x\)∣c\)\\displaystyle\\operatorname\{Var\}\(r^\{\*\}\(x\)\\mid c\)=12​𝔼​\[\(r∗​\(x\)−r∗​\(x′\)\)2∣c\]\\displaystyle=\\tfrac\{1\}\{2\}\\mathbb\{E\}\[\(r^\{\*\}\(x\)\-r^\{\*\}\(x^\{\\prime\}\)\)^\{2\}\\mid c\]\(42\)≤L22​𝔼​\[‖x−x′‖2∣c\]=L2​Var⁡\(x∣c\)\.\\displaystyle\\leq\\tfrac\{L^\{2\}\}\{2\}\\mathbb\{E\}\[\\\|x\-x^\{\\prime\}\\\|^\{2\}\\mid c\]=L^\{2\}\\operatorname\{Var\}\(x\\mid c\)\.\(43\)The conditional mean minimizes squared reconstruction error, whereasx^ℓ\\hat\{x\}\_\{\\ell\}is merely constant on each prefix cell\. HenceVar⁡\(x∣c\)≤𝔼⁡\[‖x−x^ℓ‖2∣c\]\\operatorname\{Var\}\(x\\mid c\)\\leq\\mathbb\{E\}\[\\\|x\-\\hat\{x\}\_\{\\ell\}\\\|^\{2\}\\mid c\]\. Averaging over cells proves the second inequality in \([4](https://arxiv.org/html/2610.02440#S3.E4)\)\.

Finally, puta∗=PA∞​r∗a^\{\*\}=P\_\{A\_\{\\infty\}\}r^\{\*\}andr⟂=r∗−a∗r\_\{\\perp\}=r^\{\*\}\-a^\{\*\}\. Then‖r⟂‖=δ∞\\\|r\_\{\\perp\}\\\|=\\delta\_\{\\infty\}\. For anyaℓ∈Aℓa\_\{\\ell\}\\in A\_\{\\ell\}, projection contraction gives

dist⁡\(PSℓ​r∗,Aℓ\)\\displaystyle\\operatorname\{dist\}\(P\_\{S\_\{\\ell\}\}r^\{\*\},A\_\{\\ell\}\)≤‖PSℓ​r∗−aℓ‖\\displaystyle\\leq\\\|P\_\{S\_\{\\ell\}\}r^\{\*\}\-a\_\{\\ell\}\\\|\(44\)≤‖PSℓ​\(a∗−aℓ\)‖\+‖PSℓ​r⟂‖\\displaystyle\\leq\\\|P\_\{S\_\{\\ell\}\}\(a^\{\*\}\-a\_\{\\ell\}\)\\\|\+\\\|P\_\{S\_\{\\ell\}\}r\_\{\\perp\}\\\|\(45\)≤‖a∗−aℓ‖\+δ∞\.\\displaystyle\\leq\\\|a^\{\*\}\-a\_\{\\ell\}\\\|\+\\delta\_\{\\infty\}\.\(46\)Taking the infimum overaℓa\_\{\\ell\}proves the interaction\-tail bound\. Combining it with the first two claims gives \([5](https://arxiv.org/html/2610.02440#S3.E5)\)\. ∎

###### Proof of Corollary[3\.1](https://arxiv.org/html/2610.02440#S3.Thmcorollary1)\.

Theorem[3\.2](https://arxiv.org/html/2610.02440#S3.Thmtheorem2)andu2\+v2≤u\+v\\sqrt\{u^\{2\}\+v^\{2\}\}\\leq u\+vforu,v≥0u,v\\geq 0imply

δℓ≤L​MSEℓ\+δ∞\+τℓ\.\\delta\_\{\\ell\}\\leq L\\sqrt\{\\mathrm\{MSE\}\_\{\\ell\}\}\+\\delta\_\{\\infty\}\+\\tau\_\{\\ell\}\.\(47\)Substitution of the two geometric assumptions gives the stated bound withρ=max⁡\{ρx,ρτ\}\\rho=\\max\\\{\\sqrt\{\\rho\_\{x\}\},\\rho\_\{\\tau\}\\\}\. ∎

## Appendix DPromotion Proofs

Theorem[3\.3](https://arxiv.org/html/2610.02440#S3.Thmtheorem3)\(Shadow false\-promotion control, restated\)\.The probability that the shadow is promoted despite having no lower expected squared prediction error than the active model, under the active policy’s data distribution over the tested window, is≤α\\leq\\alphaover the full horizon\.

Shadow promotion differs from CORRAL[Agarwal et al\. \(2017\)](https://arxiv.org/html/2610.02440#bib.bib21)in a structurally important way: CORRAL runsMMlearners simultaneously and paysO~​\(M\)\\tilde\{O\}\(\\sqrt\{M\}\)regret overhead from model selection; our shadow trains passively and incurs*zero*regret overhead during evaluation\. The regret during each phase is bounded by Theorem[3\.1](https://arxiv.org/html/2610.02440#S3.Thmtheorem1)at the*active*depth, with no model\-selection penalty\. We test the paired squared\-error differences via Freedman’s inequality[Freedman \(1975\)](https://arxiv.org/html/2610.02440#bib.bib18)\(no i\.i\.d\. assumption needed\)\.

###### Proof of Theorem[3\.3](https://arxiv.org/html/2610.02440#S3.Thmtheorem3)\(Shadow false\-promotion control\)\.

*Martingale formulation\.*Since the shadow updates only its own statistics \(line[14](https://arxiv.org/html/2610.02440#alg1.l14)\) and does not appear in the scoring \(line[5](https://arxiv.org/html/2610.02440#alg1.l5)\) or arm selection \(line[6](https://arxiv.org/html/2610.02440#alg1.l6)\), the action sequence is identical to Algorithm[1](https://arxiv.org/html/2610.02440#alg1)at fixed depth\. To decide whether the shadow model genuinely outperforms the active model, we construct a statistical test\. At each roundtt, define the paired squared\-error difference between the active and shadow predictions\. Lety^act​\(xt,at\)\\hat\{y\}\_\{\\mathrm\{act\}\}\(x\_\{t\},a\_\{t\}\)andy^shd​\(xt,at\)\\hat\{y\}\_\{\\mathrm\{shd\}\}\(x\_\{t\},a\_\{t\}\)denote the posterior mean predictions of the active and shadow models, respectively\. Define:

Dt=\(rt−y^act​\(xt,at\)\)2−\(rt−y^shd​\(xt,at\)\)2\.D\_\{t\}=\\left\(r\_\{t\}\-\\hat\{y\}\_\{\\mathrm\{act\}\}\(x\_\{t\},a\_\{t\}\)\\right\)^\{2\}\-\\left\(r\_\{t\}\-\\hat\{y\}\_\{\\mathrm\{shd\}\}\(x\_\{t\},a\_\{t\}\)\\right\)^\{2\}\.\(48\)WhenDt\>0D\_\{t\}\>0, the shadow’s prediction was closer to the observed reward at roundtt\.

Since the shadow does not influenceata\_\{t\}, the conditional expectation𝔼⁡\[Dt∣ℱt−1\]\\mathbb\{E\}\[D\_\{t\}\\mid\\mathcal\{F\}\_\{t\-1\}\]is a deterministic function of the models’ states\. Define the centered differences:

Zt=Dt−𝔼⁡\[Dt∣ℱt−1\]\.Z\_\{t\}=D\_\{t\}\-\\mathbb\{E\}\[D\_\{t\}\\mid\\mathcal\{F\}\_\{t\-1\}\]\.\(49\)By construction,𝔼⁡\[Zt∣ℱt−1\]=0\\mathbb\{E\}\[Z\_\{t\}\\mid\\mathcal\{F\}\_\{t\-1\}\]=0, so\(Zt\)t≥1\(Z\_\{t\}\)\_\{t\\geq 1\}is a martingale difference sequence adapted to\(ℱt\)\(\\mathcal\{F\}\_\{t\}\)\. Rewards lie in\{0,1\}\\\{0,1\\\}\. Sinceσ\\sigmamaps to\[0,1\]\[0,1\], the posterior mean predictions satisfyy^act,y^shd∈\[0,1\]\\hat\{y\}\_\{\\mathrm\{act\}\},\\hat\{y\}\_\{\\mathrm\{shd\}\}\\in\[0,1\]for all three variants\. Each squared error is therefore in\[0,1\]\[0,1\], so\|Dt\|≤1≕RD\|D\_\{t\}\|\\leq 1\\eqqcolon R\_\{D\}and:

\|Zt\|≤\|Dt\|\+\|𝔼⁡\[Dt∣ℱt−1\]\|≤2​RDa\.s\.\|Z\_\{t\}\|\\leq\|D\_\{t\}\|\+\|\\mathbb\{E\}\[D\_\{t\}\\mid\\mathcal\{F\}\_\{t\-1\}\]\|\\leq 2R\_\{D\}\\quad\\text\{a\.s\.\}\(50\)
*Freedman\-based promotion test\.*Fix a check timeτ\\tauand a trailing window ofWWobservations\. The cumulative difference decomposes into signal and noise:

D¯W=∑t=τ−W\+1τDt=∑t=τ−W\+1τ𝔼⁡\[Dt∣ℱt−1\]⏟signal:μW\+∑t=τ−W\+1τZt⏟noise:MW\.\\bar\{D\}\_\{W\}=\\sum\_\{t=\\tau\-W\+1\}^\{\\tau\}D\_\{t\}=\\underbrace\{\\sum\_\{t=\\tau\-W\+1\}^\{\\tau\}\\mathbb\{E\}\[D\_\{t\}\\mid\\mathcal\{F\}\_\{t\-1\}\]\}\_\{\\text\{signal: \}\\mu\_\{W\}\}\+\\underbrace\{\\sum\_\{t=\\tau\-W\+1\}^\{\\tau\}Z\_\{t\}\}\_\{\\text\{noise: \}M\_\{W\}\}\.\(51\)The signalμW\\mu\_\{W\}is positive when the shadow is genuinely better \(in expected squared error\) over the window\. We need to distinguishμW\>0\\mu\_\{W\}\>0from noise fluctuations\.

The noiseMW=∑tZtM\_\{W\}=\\sum\_\{t\}Z\_\{t\}is a sum of martingale differences with\|Zt\|≤R≔2​RD\|Z\_\{t\}\|\\leq R\\coloneqq 2R\_\{D\}\. Its predictable quadratic variation is:

VW=∑t=τ−W\+1τ𝔼⁡\[Zt2∣ℱt−1\]≤R2​W\.V\_\{W\}=\\sum\_\{t=\\tau\-W\+1\}^\{\\tau\}\\mathbb\{E\}\\\!\\left\[Z\_\{t\}^\{2\}\\mid\\mathcal\{F\}\_\{t\-1\}\\right\]\\leq R^\{2\}W\.\(52\)By Freedman’s inequality[Freedman \(1975\)](https://arxiv.org/html/2610.02440#bib.bib18):

P⁡\(MW≥a​and​VW≤v\)≤exp⁡\(−a2/2v\+R​a/3\)\.P\\\!\\left\(M\_\{W\}\\geq a\\;\\text\{ and \}\\;V\_\{W\}\\leq v\\right\)\\leq\\exp\\\!\\left\(\\frac\{\-a^\{2\}/2\}\{v\+Ra/3\}\\right\)\.\(53\)
To derive the thresholda∗a^\{\*\}, we setv=R2​Wv=R^\{2\}W\(the worst\-case variance bound\) and require the right\-hand side of \([53](https://arxiv.org/html/2610.02440#A4.E53)\) to equal the per\-test significance levelαk\\alpha\_\{k\}\. This gives the equation:

exp⁡\(−a2/2R2​W\+R​a/3\)=αk\.\\exp\\\!\\left\(\\frac\{\-a^\{2\}/2\}\{R^\{2\}W\+Ra/3\}\\right\)=\\alpha\_\{k\}\.\(54\)Taking logarithms and writingL=log⁡\(1/αk\)L=\\log\(1/\\alpha\_\{k\}\):

a22=L⁡\(R2​W\+R​a3\)⟹a2−2​R​L3​a−2​R2​W​L=0\.\\frac\{a^\{2\}\}\{2\}=L\\\!\\left\(R^\{2\}W\+\\frac\{Ra\}\{3\}\\right\)\\quad\\Longrightarrow\\quad a^\{2\}\-\\frac\{2RL\}\{3\}\\,a\-2R^\{2\}WL=0\.\(55\)Applying the quadratic formula \(a\>0a\>0\):

a∗​\(αk,W\)\\displaystyle a^\{\*\}\(\\alpha\_\{k\},W\)=R​L3\+R2​L29\+2​R2​W​L\\displaystyle=\\frac\{RL\}\{3\}\+\\sqrt\{\\frac\{R^\{2\}L^\{2\}\}\{9\}\+2R^\{2\}WL\}=R3​log⁡1αk\+R​19​\(log⁡1αk\)2\+2​W​log⁡1αk\.\\displaystyle=\\frac\{R\}\{3\}\\log\\frac\{1\}\{\\alpha\_\{k\}\}\+R\\sqrt\{\\frac\{1\}\{9\}\\\!\\left\(\\log\\frac\{1\}\{\\alpha\_\{k\}\}\\right\)^\{\\\!2\}\+2W\\log\\frac\{1\}\{\\alpha\_\{k\}\}\}\.\(56\)We promote ifD¯W\>a∗​\(αk,W\)\\bar\{D\}\_\{W\}\>a^\{\*\}\(\\alpha\_\{k\},W\)\.

Under the null hypothesis \(shadow is not better,μW≤0\\mu\_\{W\}\\leq 0\), the signal is non\-positive, so from \([51](https://arxiv.org/html/2610.02440#A4.E51)\):

D¯W=μW\+MW≤MW\.\\bar\{D\}\_\{W\}=\\mu\_\{W\}\+M\_\{W\}\\leq M\_\{W\}\.\(57\)Therefore, a promotion requiresMW\>a∗M\_\{W\}\>a^\{\*\}, which by Freedman’s inequality \([53](https://arxiv.org/html/2610.02440#A4.E53)\) occurs with probability at mostαk\\alpha\_\{k\}:

P⁡\(promote∣μW≤0\)≤P⁡\(MW\>a∗\)≤αk\.P\(\\text\{promote\}\\mid\\mu\_\{W\}\\leq 0\)\\leq P\(M\_\{W\}\>a^\{\*\}\)\\leq\\alpha\_\{k\}\.\(58\)Here,a∗a^\{\*\}is the critical value that makes the noise term unlikely to exceed the threshold, ensuring false promotions are rare\.

*Bonferroni correction\.*The doubling schedule checks at times\{T0,2​T0,4​T0,…\}\\\{T\_\{0\},2T\_\{0\},4T\_\{0\},\\ldots\\\}, producing at mostncn\_\{c\}check intervals:

nc=⌊log2⁡\(T/T0\)⌋\+1\.n\_\{c\}=\\lfloor\\log\_\{2\}\(T/T\_\{0\}\)\\rfloor\+1\.\(59\)At each check time, the algorithm only evaluates the immediate shadow depthk\+1k\{\+\}1extending from the current active depthkk\. Therefore, it conducts exactly one hypothesis test per scheduled check interval\. An additional test is only conducted if a promotion successfully advances the active frontier, prompting the algorithm to immediately evaluate the next depth\. Note that this immediate re\-test uses the trailing windowWW, which contains data collected under the previous depth’s policy; the conservatism of the Freedman\-based test \(Theorem[3\.3](https://arxiv.org/html/2610.02440#S3.Thmtheorem3)\) provides robustness against this distribution shift\. Because at mostℓmax−1\\ell\_\{\\max\}\-1promotions can ever occur \(from depth 1 to depthℓmax\\ell\_\{\\max\}\), the total number of hypothesis tests over the entire horizon is bounded by:

N≤nc\+\(ℓmax−1\)\.N\\leq n\_\{c\}\+\(\\ell\_\{\\max\}\-1\)\.\(60\)Settingαk=α/N\\alpha\_\{k\}=\\alpha/Nfor each individual test and applying the union bound:

P⁡\(any false promotion\)≤∑k=1Nαk=N⋅αN=α\.P\(\\text\{any false promotion\}\)\\leq\\sum\_\{k=1\}^\{N\}\\alpha\_\{k\}=N\\cdot\\frac\{\\alpha\}\{N\}=\\alpha\.\(61\)By tracking only the frontier tests, the multiplicity penalty is additive𝒪⁡\(nc\+ℓmax\)\\mathcal\{O\}\(n\_\{c\}\+\\ell\_\{\\max\}\)rather than multiplicative𝒪⁡\(nc⋅ℓmax\)\\mathcal\{O\}\(n\_\{c\}\\cdot\\ell\_\{\\max\}\)\. The doubling schedule keepsnc=𝒪⁡\(log⁡T\)n\_\{c\}=\\mathcal\{O\}\(\\log T\)\.

*Combining\.*By \([61](https://arxiv.org/html/2610.02440#A4.E61)\), with probability at least1−α1\-\\alpha,*every*promotion is a true improvement under the active policy’s data distribution:

meaning the shadow has strictly lower expected squared error on the\(xt,at\)\(x\_\{t\},a\_\{t\}\)pairs generated byπact\\pi\_\{\\mathrm\{act\}\}\. This is a*pre\-promotion*guarantee; post\-promotion, the policy changes and the data distribution shifts \(see Remark[D\.2](https://arxiv.org/html/2610.02440#A4.Thmremark2)\)\.

Regardless of whether any individual promotion is true or false, the shadow never influences arm selection, so the regret during each phase \(at fixed depthℓk\\ell\_\{k\}\) is bounded by Theorem[3\.1](https://arxiv.org/html/2610.02440#S3.Thmtheorem1)\. If promotions occur at timesT1,T2,…T\_\{1\},T\_\{2\},\\ldotswith depthsℓ1,ℓ2,…\\ell\_\{1\},\\ell\_\{2\},\\ldots, the total regret is the sum across phases:

R⁡\(T\)≤∑kR⁡\(Tk−Tk−1,ℓk\),R\(T\)\\leq\\sum\_\{k\}R\(T\_\{k\}\-T\_\{k\-1\},\\,\\ell\_\{k\}\),\(63\)where each term is bounded by Theorem[3\.1](https://arxiv.org/html/2610.02440#S3.Thmtheorem1)at the corresponding depth\. SinceΔℓk\+1≤Δℓk\\Delta\_\{\\ell\_\{k\+1\}\}\\leq\\Delta\_\{\\ell\_\{k\}\}\(deeper models have lower bias\), promotions can only reduce the bias term in subsequent phases\. ∎

## Appendix EDepth Ablation and Exponential Decay

This appendix examines empirical behavior relevant to the conditional geometric rate in Corollary[3\.1](https://arxiv.org/html/2610.02440#S3.Thmcorollary1)\(§[3](https://arxiv.org/html/2610.02440#S3)\) and the depth results in §[4\.2](https://arxiv.org/html/2610.02440#S4.SS2)\.

### E\.1Exponential Decay of Misspecification

Conditional depth\-rate prediction\.Corollary[3\.1](https://arxiv.org/html/2610.02440#S3.Thmcorollary1)gives geometric convergence to an irreducible floor when both RQ reconstruction error and the additive interaction tail contract geometrically\.

To test whether the observed behavior is consistent with this prediction, we compute the regret rateR⁡\(T\)/TR\(T\)/Tat the terminal round for each \(dataset, method, depth\) combination using depthsℓ=1,…,5\\ell=1,\\ldots,5\. SinceR⁡\(T\)/T→O⁡\(Δℓ\)R\(T\)/T\\to O\(\\Delta\_\{\\ell\}\)asT→∞T\\to\\infty\(Theorem[3\.1](https://arxiv.org/html/2610.02440#S3.Thmtheorem1)\), the converged regret rate provides a proxy forΔℓ\\Delta\_\{\\ell\}\.

Figure 6:Empirical behavior consistent with the conditional geometric depth\-rate law, one column per method\.Top:MedianR2R^\{2\}of the exponential fita\+b​ρℓa\+b\\rho^\{\\ell\}as a function of horizonTT; fit quality improves with more data\.Bottom:Normalized regret decay\(Δℓ−Δ5\)/\(Δ1−Δ5\)\(\\Delta\_\{\\ell\}\-\\Delta\_\{5\}\)/\(\\Delta\_\{1\}\-\\Delta\_\{5\}\)at terminalTTfor each dataset\.Exponential fit\.We fitR⁡\(T\)/T≈a\+b​ρℓR\(T\)/T\\approx a\+b\\rho^\{\\ell\}to each \(dataset, method\) pair via nonlinear least squares, yielding 39 fits \(13 datasets×\\times3 RQ methods, 30 seeds each\)\. The table below reports the median fit quality\.

Leave\-one\-out cross\-validation\.For each \(dataset, method\), we hold out one depth, fit on the remaining four, and predict the held\-out regret rate\. This produces 135 predictions \(some fits fail on 3 points\)\. The median prediction error is0\.3%0\.3\\%; 73% of predictions fall within1%1\\%of the observed value \(Figure[7](https://arxiv.org/html/2610.02440#A5.F7)\)\.

Figure 7:Leave\-one\-out cross\-validation of the exponential decay modelΔℓ≈a\+b​ρℓ\\Delta\_\{\\ell\}\\approx a\+b\\rho^\{\\ell\}\.Left:Predicted vs\. actual regret rateR⁡\(T\)/TR\(T\)/Tfor all \(dataset, method, held\-out depth\) triples; the gray band shows±5%\\pm 5\\%\.Right:Prediction error by held\-out depth; depths22–55are predicted within∼1%\\sim\\\!1\\%, while depth11\(furthest fromΔ∞\\Delta\_\{\\infty\}\) shows larger extrapolation error\.Exponential decay rate\.Figure[9](https://arxiv.org/html/2610.02440#A5.F9)fitsa\+b​ρℓa\+b\\rho^\{\\ell\}to the normalized within\-cell varianceWCV⁡\(ℓ\)/WCV⁡\(0\)\\mathrm\{WCV\}\(\\ell\)/\\mathrm\{WCV\}\(0\)for each dataset\. The median fitted decay rate isρ=0\.86\\rho=0\.86\(range0\.170\.17–0\.930\.93\), with medianR2=0\.83R^\{2\}=0\.83\.

Figure 8:Regret rateR⁡\(T\)/TR\(T\)/Tvs\. depthℓ\\ellfor each RQ method, with fitted exponential decay curvesa\+b​ρℓa\+b\\rho^\{\\ell\}overlaid\. Each line is a dataset; error bars show±1\\pm 1std over 30 seeds\. MedianR2R^\{2\}is reported per method\.
### E\.2Within\-Cell Reward Variance

Figure[9](https://arxiv.org/html/2610.02440#A5.F9)measures within\-cell reward heterogeneity directly\. For each dataset we train an RQ codebook \(b=16b\{=\}16, depth 5\) and compute the weighted average within\-cell reward varianceWCV⁡\(ℓ\)=∑c\(nc/N\)​Var​\(r∣cellℓ=c\)\\mathrm\{WCV\}\(\\ell\)=\\sum\_\{c\}\(n\_\{c\}/N\)\\,\\mathrm\{Var\}\(r\\mid\\text\{cell\}\_\{\\ell\}\{=\}c\), where cells at depthℓ\\ellare defined by the firstℓ\\ellcentroid assignments\. On a log scale, all 13 datasets decay roughly linearly, consistent with geometric shrinkage over the measured depths, with median per\-level ratioρ=0\.83\\rho=0\.83\(range0\.240\.24–0\.930\.93\)\.

Figure 9:Normalized within\-cell reward varianceWCV⁡\(ℓ\)/WCV⁡\(0\)\\mathrm\{WCV\}\(\\ell\)/\\mathrm\{WCV\}\(0\)vs\. RQ depthℓ\\ellfor all 13 datasets \(log scale\)\. Every dataset decays monotonically; the near\-linear trajectories are consistent with geometric decay with medianρ=0\.83\\rho=0\.83\.
### E\.3Fixed\-Depth vs\. Shadow Promotion

We compare TS\-RQ at fixed depthsℓ=1\\ell\{=\}1andℓ=2\\ell\{=\}2against the adaptive shadow\-promoted variant \(TS\-RQ\) on two representative datasets\.

On covertype, shadow promotion discovers depth 4 and gains3\.43\.4percentage points over fixedℓ=2\\ell\{=\}2, confirming that adaptive depth selection adds value beyond simply committing toℓ=2\\ell\{=\}2\. On higgs, the benefit of depth beyond 2 is marginal, and the adaptive method correctly settles at depth 3 with regret matchingℓ=2\\ell\{=\}2\.

## Appendix FAnalytical Variant: Finite\-Time Bound

This appendix analyzes an analytical variant of Algorithm[1](https://arxiv.org/html/2610.02440#alg1)that maintains the fullD×DD\\times Djoint posterior covariance rather than the block\-diagonal approximation used in practice\. The variant admits an explicit finite\-time regret bound \(Proposition[F\.1](https://arxiv.org/html/2610.02440#A6.Thmremark1)below\), complementing the asymptotic guarantee for Algorithm[1](https://arxiv.org/html/2610.02440#alg1)\(Theorem[3\.1](https://arxiv.org/html/2610.02440#S3.Thmtheorem1)\)\. The finite\-time bound is a standard application of LinTS analysis[Agrawal and Goyal \(2013\)](https://arxiv.org/html/2610.02440#bib.bib8)to our feature map; the contribution is not the proof technique but the*architectural insight*that the RQ additive structure ensuresD=b​ℓ​pD=b\\ell pwhile achieving the approximation power ofbℓb^\{\\ell\}cells—an exponential compression not available to flat partitions\.

Analytical variant details\.The analytical variant \(Proposition[F\.1](https://arxiv.org/html/2610.02440#A6.Thmremark1)\) concatenates all per\-level features into a block vectorΦℳ​\(x\)∈ℝD\\Phi\_\{\\mathcal\{M\}\}\(x\)\\in\\mathbb\{R\}^\{D\}withD=b​ℓ​p​\(ℳ\)D=b\\ell\\,p\(\\mathcal\{M\}\):

Φℳ​\(x\)=\(ϕ1​\(x\)ϕ2​\(x\)ϕℓ​\(x\)\)∈ℝD,Σa=\(Σ11⋯Σ1​ℓ⋱Σℓ​1⋯Σℓ​ℓ\)∈ℝD×D,\\Phi\_\{\\mathcal\{M\}\}\(x\)=\\begin\{pmatrix\}\\phi\_\{1\}\(x\)\\\\ \\phi\_\{2\}\(x\)\\\\ \\vdots\\\\ \\phi\_\{\\ell\}\(x\)\\end\{pmatrix\}\\\!\\in\\mathbb\{R\}^\{D\},\\qquad\\Sigma\_\{a\}=\\begin\{pmatrix\}\\Sigma\_\{11\}&\\cdots&\\Sigma\_\{1\\ell\}\\\\ \\vdots&\\ddots&\\vdots\\\\ \\Sigma\_\{\\ell 1\}&\\cdots&\\Sigma\_\{\\ell\\ell\}\\end\{pmatrix\}\\\!\\in\\mathbb\{R\}^\{D\\times D\},\(64\)where eachϕi​\(x\)∈ℝb​p\\phi\_\{i\}\(x\)\\in\\mathbb\{R\}^\{bp\}encodes the level\-iiassignment \(one\-hot for TS\-RQ, context\-at\-centroid for LinTS\-RQ\) andΣi​j∈ℝb​p×b​p\\Sigma\_\{ij\}\\in\\mathbb\{R\}^\{bp\\times bp\}captures cross\-level correlations\. A single parameter vectorθa∈ℝD\\theta\_\{a\}\\in\\mathbb\{R\}^\{D\}recovers the*unclipped*additive model:r⁡\(x,a\)=θa⊤​Φℳ​\(x\)r\(x,a\)=\\theta\_\{a\}^\{\\top\}\\Phi\_\{\\mathcal\{M\}\}\(x\)\.

The analytical variant runs LinTS onΦℳ​\(x\)\\Phi\_\{\\mathcal\{M\}\}\(x\)with the fullD×DD\\times Dposterior covarianceΣa\\Sigma\_\{a\}\. Define the*variant misspecification*Δ⁡\(Φ\)=𝔼x​\[maxa⁡\|r∗​\(x,a\)−θa∗⁣⊤​Φ​\(x\)\|\]\\Delta\(\\Phi\)=\\mathbb\{E\}\_\{x\}\[\\max\_\{a\}\|r^\{\*\}\(x,a\)\-\\theta\_\{a\}^\{\*\\top\}\\Phi\(x\)\|\], whereθa∗\\theta\_\{a\}^\{\*\}is the best linear predictor for armaaonΦ\\Phi\. Sinceθa⊤​Φ​\(x\)=∑ifi​\(ki​\(x\),a\)\\theta\_\{a\}^\{\\top\}\\Phi\(x\)=\\sum\_\{i\}f\_\{i\}\(k\_\{i\}\(x\),a\)recovers any unclipped additive model,Δ⁡\(Φ\)≤Δℓuncl\\Delta\(\\Phi\)\\leq\\Delta\_\{\\ell\}^\{\\mathrm\{uncl\}\}whereΔℓuncl\\Delta\_\{\\ell\}^\{\\mathrm\{uncl\}\}is the error of the stagewise limit without clipping\. In practice, clipping \(σ\\sigma\) can only reduce approximation error for bounded rewards, soΔℓ​\(ℳ\)≤Δℓuncl\\Delta\_\{\\ell\}\(\\mathcal\{M\}\)\\leq\\Delta\_\{\\ell\}^\{\\mathrm\{uncl\}\}, givingΔ⁡\(Φ\)\\Delta\(\\Phi\)andΔℓ​\(ℳ\)\\Delta\_\{\\ell\}\(\\mathcal\{M\}\)the same asymptotic scaling in depth\.

Complexity comparison\.Table[5](https://arxiv.org/html/2610.02440#A6.T5)summarizes the exploration and memory costs of the analytical variant versus Algorithm[1](https://arxiv.org/html/2610.02440#alg1)\.

Table 5:Exploration and memory scaling by base learner\. “Joint” columns refer to the analytical variant; “Actual” is Algorithm[1](https://arxiv.org/html/2610.02440#alg1)\.The analytical variant runsKKindependent LinTS instances[Agrawal and Goyal \(2013\)](https://arxiv.org/html/2610.02440#bib.bib8), one per arm, on theDD\-dimensional feature vectorΦℳ​\(x\)∈ℝD\\Phi\_\{\\mathcal\{M\}\}\(x\)\\in\\mathbb\{R\}^\{D\}withD=b​ℓ​p​\(ℳ\)D=b\\ell\\,p\(\\mathcal\{M\}\)\([64](https://arxiv.org/html/2610.02440#A6.E64)\)\. Each armaamaintains a ridge precision matrix

Va,t=λI\+∑s≤t:as=aΦ\(xs\)Φ\(xs\)⊤∈ℝD×D\.V\_\{a,t\}=\\lambda I\+\\sum\_\{s\\leq t:\\,a\_\{s\}=a\}\\Phi\(x\_\{s\}\)\\Phi\(x\_\{s\}\)^\{\\top\}\\in\\mathbb\{R\}^\{D\\times D\}\.\(65\)Letr∗\(x,a\)=𝔼\[rt∣xt=x,at=a\]r^\{\*\}\(x,a\)=\\mathbb\{E\}\[r\_\{t\}\\mid x\_\{t\}\{=\}x,\\,a\_\{t\}\{=\}a\]denote the true expected reward, and letθa∗=arg⁡minθ​𝔼x​\[\(r∗​\(x,a\)−θ⊤​Φ​\(x\)\)2\]\\theta\_\{a\}^\{\*\}=\\arg\\min\_\{\\theta\}\\mathbb\{E\}\_\{x\}\[\(r^\{\*\}\(x,a\)\-\\theta^\{\\top\}\\Phi\(x\)\)^\{2\}\]be the best linear predictor for armaa\. Define the misspecification functionϵ⁡\(x,a\)=r∗​\(x,a\)−θa∗⁣⊤​Φ​\(x\)\\epsilon\(x,a\)=r^\{\*\}\(x,a\)\-\\theta\_\{a\}^\{\*\\top\}\\Phi\(x\)and the observation noiseηt=rt−r∗​\(xt,at\)\\eta\_\{t\}=r\_\{t\}\-r^\{\*\}\(x\_\{t\},a\_\{t\}\)\. Note thatΔ⁡\(Φ\)=𝔼x​\[maxa⁡\|ϵ⁡\(x,a\)\|\]\\Delta\(\\Phi\)=\\mathbb\{E\}\_\{x\}\[\\max\_\{a\}\|\\epsilon\(x,a\)\|\]\. The observed reward decomposes as

rt=θat∗⁣⊤​Φ​\(xt\)\+ϵ⁡\(xt,at\)⏟bias\+ηt⏟noise\.r\_\{t\}=\\theta\_\{a\_\{t\}\}^\{\*\\top\}\\Phi\(x\_\{t\}\)\+\\underbrace\{\\epsilon\(x\_\{t\},a\_\{t\}\)\}\_\{\\text\{bias\}\}\+\\underbrace\{\\eta\_\{t\}\}\_\{\\text\{noise\}\}\.\(66\)At timett, the ridge posterior mean estimatesθa∗\\theta\_\{a\}^\{\*\}by

θ^a,t\\displaystyle\\hat\{\\theta\}\_\{a,t\}=Va,t−1∑s:as=aΦ\(xs\)rs\\displaystyle=V\_\{a,t\}^\{\-1\}\\sum\_\{s:a\_\{s\}=a\}\\Phi\(x\_\{s\}\)\\,r\_\{s\}=Va,t−1∑s:as=aΦ\(xs\)\(θa∗⁣⊤Φ\(xs\)\+ηs\)⏟θ^a,tperf\+Va,t−1∑s:as=aΦ\(xs\)ϵ\(xs,as\)⏟θ^a,tbias,\\displaystyle=\\underbrace\{V\_\{a,t\}^\{\-1\}\\sum\_\{s:a\_\{s\}=a\}\\Phi\(x\_\{s\}\)\(\\theta\_\{a\}^\{\*\\top\}\\Phi\(x\_\{s\}\)\+\\eta\_\{s\}\)\}\_\{\\hat\{\\theta\}\_\{a,t\}^\{\\mathrm\{perf\}\}\}\\;\+\\;\\underbrace\{V\_\{a,t\}^\{\-1\}\\sum\_\{s:a\_\{s\}=a\}\\Phi\(x\_\{s\}\)\\,\\epsilon\(x\_\{s\},a\_\{s\}\)\}\_\{\\hat\{\\theta\}\_\{a,t\}^\{\\mathrm\{bias\}\}\},\(67\)where the first term is the solution under perfect specification, and the second is the bias due to misspecification\.

###### Lemma F\.1\(Bias regret\)\.

For i\.i\.d\. contexts,𝔼x​\[maxa⁡\|ϵ⁡\(x,a\)\|\]=Δ⁡\(Φ\)\\mathbb\{E\}\_\{x\}\[\\max\_\{a\}\|\\epsilon\(x,a\)\|\]=\\Delta\(\\Phi\)\.

###### Proof\.

Immediate from the definitions ofϵ\\epsilonandΔ⁡\(Φ\)\\Delta\(\\Phi\)\. ∎

###### Lemma F\.2\(Exploration regret under realizability\)\.

For the analytical variant under realizability \(Δ⁡\(Φ\)=0\\Delta\(\\Phi\)=0, i\.e\.ϵ≡0\\epsilon\\equiv 0\), with bounded features‖Φ⁡\(x\)‖≤C\\\|\\Phi\(x\)\\\|\\leq C, rewards in\[0,1\]\[0,1\], andDD\-dimensional parameter vectors, the cumulative regret satisfies, with probability≥1−δ\\geq 1\-\\delta,

R⁡\(T,ℓ\)=O⁡\(D​K​T​log⁡\(T/δ\)\)\.R\(T,\\ell\)=O\\\!\\left\(D\\sqrt\{KT\\log\(T/\\delta\)\}\\right\)\.\(68\)

###### Proof\.

Under realizability,r∗​\(x,a\)=θa∗⁣⊤​Φ​\(x\)r^\{\*\}\(x,a\)=\\theta\_\{a\}^\{\*\\top\}\\Phi\(x\)for all\(x,a\)\(x,a\), so the reward noiseηt=rt−θat∗⁣⊤​Φ​\(xt\)\\eta\_\{t\}=r\_\{t\}\-\\theta\_\{a\_\{t\}\}^\{\*\\top\}\\Phi\(x\_\{t\}\)is zero\-mean conditional on\(xt,at\)\(x\_\{t\},a\_\{t\}\)\. This is exactly the setting of[Agrawal and Goyal \(2013\)](https://arxiv.org/html/2610.02440#bib.bib8), Theorem 2 \(stated for Gaussian noise; the extension to sub\-Gaussian noise, which covers our bounded binary rewards, is standard[Lattimore and Szepesvári \(2020\)](https://arxiv.org/html/2610.02440#bib.bib11)\), giving per\-arm regretO⁡\(D​Ta​log⁡\(T/δ\)\)O\(D\\sqrt\{T\_\{a\}\\log\(T/\\delta\)\}\)\. Summing over arms \(∑aTa=T\\sum\_\{a\}T\_\{a\}=T\):

∑a=1KO⁡\(D​Ta​log⁡\(T/δ\)\)\\displaystyle\\sum\_\{a=1\}^\{K\}O\\\!\\left\(D\\sqrt\{T\_\{a\}\\log\(T/\\delta\)\}\\right\)=O⁡\(D​log⁡\(T/δ\)\)​∑a=1KTa\\displaystyle=O\\\!\\left\(D\\sqrt\{\\log\(T/\\delta\)\}\\right\)\\sum\_\{a=1\}^\{K\}\\sqrt\{T\_\{a\}\}≤JensenO⁡\(D​log⁡\(T/δ\)\)​K​∑a=1KTa\\displaystyle\\stackrel\{\{\\scriptstyle\\text\{Jensen\}\}\}\{\{\\leq\}\}O\\\!\\left\(D\\sqrt\{\\log\(T/\\delta\)\}\\right\)\\sqrt\{K\\sum\_\{a=1\}^\{K\}T\_\{a\}\}=∑Ta=TO⁡\(D​K​T​log⁡\(T/δ\)\)\.∎\\displaystyle\\stackrel\{\{\\scriptstyle\\sum T\_\{a\}=T\}\}\{\{=\}\}O\\\!\\left\(D\\sqrt\{KT\\log\(T/\\delta\)\}\\right\)\.\\qed\(69\)

###### Argument for Remark[F\.1](https://arxiv.org/html/2610.02440#A6.Thmremark1)\.

Letat∗=arg⁡maxa​r∗​\(xt,a\)a\_\{t\}^\{\*\}=\\arg\\max\_\{a\}r^\{\*\}\(x\_\{t\},a\)\. The per\-round regret decomposes as

r∗​\(xt,at∗\)−r∗​\(xt,at\)\\displaystyle r^\{\*\}\(x\_\{t\},a\_\{t\}^\{\*\}\)\-r^\{\*\}\(x\_\{t\},a\_\{t\}\)=\[θat∗∗⁣⊤​Φ​\(xt\)−θat∗⁣⊤​Φ​\(xt\)\]⏟linear suboptimality\\displaystyle=\\underbrace\{\\bigl\[\\theta\_\{a\_\{t\}^\{\*\}\}^\{\*\\top\}\\Phi\(x\_\{t\}\)\-\\theta\_\{a\_\{t\}\}^\{\*\\top\}\\Phi\(x\_\{t\}\)\\bigr\]\}\_\{\\text\{linear suboptimality\}\}\+\[ϵ⁡\(xt,at∗\)−ϵ⁡\(xt,at\)\]⏟misspecification\.\\displaystyle\\quad\+\\underbrace\{\\bigl\[\\epsilon\(x\_\{t\},a\_\{t\}^\{\*\}\)\-\\epsilon\(x\_\{t\},a\_\{t\}\)\\bigr\]\}\_\{\\text\{misspecification\}\}\.\(71\)The misspecification bracket satisfies\|ϵ⁡\(xt,at∗\)−ϵ⁡\(xt,at\)\|≤2​maxa​\|ϵ⁡\(xt,a\)\|\|\\epsilon\(x\_\{t\},a\_\{t\}^\{\*\}\)\-\\epsilon\(x\_\{t\},a\_\{t\}\)\|\\leq 2\\max\_\{a\}\|\\epsilon\(x\_\{t\},a\)\|\. Since contexts are i\.i\.d\., Hoeffding’s inequality gives∑t=1Tmaxa⁡\|ϵ⁡\(xt,a\)\|≤T⋅Δ⁡\(Φ\)\+O⁡\(T​log⁡\(1/δ\)\)\\sum\_\{t=1\}^\{T\}\\max\_\{a\}\|\\epsilon\(x\_\{t\},a\)\|\\leq T\\cdot\\Delta\(\\Phi\)\+O\(\\sqrt\{T\\log\(1/\\delta\)\}\)with probability≥1−δ\\geq 1\-\\delta; the second term is absorbed into the exploration term below\.

For the linear suboptimality, we apply Lemma[F\.2](https://arxiv.org/html/2610.02440#A6.Thmlemma2)\. Strictly, Lemma[F\.2](https://arxiv.org/html/2610.02440#A6.Thmlemma2)is stated under realizability \(ϵ≡0\\epsilon\\equiv 0\); in the misspecified case, the systematic biasϵ\\epsilonshifts the posterior mean, which can affect the algorithm’s exploration behavior\. For UCB\-style algorithms, this additive decomposition is standard[Lattimore and Szepesvári \(2020\)](https://arxiv.org/html/2610.02440#bib.bib11); for Thompson Sampling, the shifted posterior may alter the sampling distribution in non\-additive ways\. Following[Lattimore et al\. \(2020\)](https://arxiv.org/html/2610.02440#bib.bib23), we treat the two terms as independent, yielding the bound below as an upper bound on the well\-specified component of regret\. The asymptotic guarantee \(Theorem[3\.1](https://arxiv.org/html/2610.02440#S3.Thmtheorem1)\) is established independently via the property\-based proof and does not rely on this decomposition\. WithD=b​ℓ​p​\(ℳ\)D=b\\ell\\,p\(\\mathcal\{M\}\):

R⁡\(T,ℓ\)≤O⁡\(b​ℓ​p​\(ℳ\)​K​T​log⁡\(T/δ\)\)⏟exploration\+O⁡\(Δ⁡\(Φ\)⋅T\)⏟misspecification bias\.∎R\(T,\\ell\)\\leq\\underbrace\{O\\\!\\left\(b\\ell\\,p\(\\mathcal\{M\}\)\\sqrt\{KT\\log\(T/\\delta\)\}\\right\)\}\_\{\\text\{exploration\}\}\+\\underbrace\{O\\\!\\left\(\\Delta\(\\Phi\)\\cdot T\\right\)\}\_\{\\text\{misspecification bias\}\}\.\\qed\(72\)

Variance deflation\.The block\-diagonal approximation used by Algorithm[1](https://arxiv.org/html/2610.02440#alg1)inverts each level’s precision block independently\. The following lemma shows that this yields a posterior that is*tighter*than the exact marginal of the joint posterior above\. For UCB\-style algorithms, tighter confidence sets imply lower regret; for Thompson Sampling, the relationship between posterior width and regret is not monotone, so the finite\-time bound above applies to the analytical variant only\. The asymptotic guarantee for Algorithm[1](https://arxiv.org/html/2610.02440#alg1)\(Theorem[3\.1](https://arxiv.org/html/2610.02440#S3.Thmtheorem1)\) is established independently via the property\-based proof in Appendix[C](https://arxiv.org/html/2610.02440#A3)\.

###### Lemma F\.3\(Marginal variance deflation\)\.

LetΣ≻0\\Sigma\\succ 0be the joint posterior covariance over allℓ\\elllevels \([64](https://arxiv.org/html/2610.02440#A6.E64)\), partitioned intob​p×b​pbp\\times bpblocks\. For every leveli∈\{1,…,ℓ\}i\\in\\\{1,\\ldots,\\ell\\\},\(\[Σ−1\]i​i\)−1⪯\[Σ\]i​i\(\[\\Sigma^\{\-1\}\]\_\{ii\}\)^\{\-1\}\\preceq\[\\Sigma\]\_\{ii\}\.

###### Proof\.

PartitionΣ−1≻0\\Sigma^\{\-1\}\\succ 0into leveliiversus the remainingℓ−1\\ell\-1levels:

Σ−1=\(ABB⊤C\),\\Sigma^\{\-1\}=\\begin\{pmatrix\}A&B\\\\ B^\{\\top\}&C\\end\{pmatrix\},whereA=\[Σ−1\]i​i∈ℝb​p×b​pA=\[\\Sigma^\{\-1\}\]\_\{ii\}\\in\\mathbb\{R\}^\{bp\\times bp\}andC∈ℝ\(ℓ−1\)​b​p×\(ℓ−1\)​b​pC\\in\\mathbb\{R\}^\{\(\\ell\{\-\}1\)bp\\times\(\\ell\{\-\}1\)bp\}\. SinceΣ−1≻0\\Sigma^\{\-1\}\\succ 0, bothAAandCCare positive definite\. By the block inversion formula,

\[Σ\]i​i=\(A−B​C−1​B⊤\)−1\.\[\\Sigma\]\_\{ii\}=\(A\-BC^\{\-1\}B^\{\\top\}\)^\{\-1\}\.\(73\)SinceC≻0C\\succ 0, the Schur complement satisfiesB​C−1​B⊤⪰0BC^\{\-1\}B^\{\\top\}\\succeq 0, givingA−B​C−1​B⊤⪯AA\-BC^\{\-1\}B^\{\\top\}\\preceq A\. Both sides are positive definite \(the left\-hand side byΣ−1≻0\\Sigma^\{\-1\}\\succ 0\), so inverting reverses the Loewner order\([Horn and Johnson, 2013](https://arxiv.org/html/2610.02440#bib.bib36), Theorem 7\.7\.6\):

\(\[Σ−1\]i​i\)−1=A−1⪯\(A−B​C−1​B⊤\)−1=\[Σ\]i​i\.∎\(\[\\Sigma^\{\-1\}\]\_\{ii\}\)^\{\-1\}=A^\{\-1\}\\preceq\(A\-BC^\{\-1\}B^\{\\top\}\)^\{\-1\}=\[\\Sigma\]\_\{ii\}\.\\qed

## Appendix GDataset Details

Codebook training\.We train the RQ codebook via scikit\-learn’sMiniBatchKMeans\(k=16k\{=\}16,init=’k\-means\+\+’,n\_init=3,max\_iter=100,batch\_size=1024,random\_state=42\) applied sequentially: we train leveliion the context residualsx\(i−1\)x^\{\(i\-1\)\}from thenrq=50​Kn\_\{\\mathrm\{rq\}\}\{=\}50\\text\{K\}holdout contexts\. All features are standardized to zero mean and unit variance before codebook training\.

Preprocessing\.We label\-encode categorical features\. We apply no feature selection, imputation, or augmentation\.

Table 6:Datasets used in the evaluation\.NN= total samples,dd= feature dimension,KK= number of arms \(classes\),pmaxp\_\{\\max\}= majority class frequency,eff\. rank= effective rank of the feature covariance\. All datasets are publicly available from OpenML and UCI[Dua and Graff \(2019\)](https://arxiv.org/html/2610.02440#bib.bib32); codebook trained onnrq=50​Kn\_\{\\mathrm\{rq\}\}\{=\}50\\text\{K\}held\-out samples\. Individual sources: HIGGS and SUSY[Baldi et al\. \(2014\)](https://arxiv.org/html/2610.02440#bib.bib27), HEPMASS[Baldi et al\. \(2016\)](https://arxiv.org/html/2610.02440#bib.bib28), covertype[Blackard and Dean \(1999\)](https://arxiv.org/html/2610.02440#bib.bib29), MiniBooNE[Roe et al\. \(2005\)](https://arxiv.org/html/2610.02440#bib.bib30), year\_prediction[Bertin\-Mahieux et al\. \(2011\)](https://arxiv.org/html/2610.02440#bib.bib31)\.
## Appendix HFull Per\-Dataset Results

Tables[7](https://arxiv.org/html/2610.02440#A8.T7)–[9](https://arxiv.org/html/2610.02440#A8.T9)show per\-dataset results for all three method families\.

Table 7:LinTS\-RQ vs LinTS: per\-dataset regret rates \(%\) and gap with 95% CIs\.DatasetddKKBase \(%\)RQ \(%\)Gap \(%\)TTairlines7241\.339\.8−3\.6±0\.1\-3\.6\\pm 0\.1450Kbeer\_rev\.1210485\.683\.0−2\.9±0\.5\-2\.9\\pm 0\.5450Kbng\_elev\.181075\.175\.0−0\.2±0\.0\-0\.2\\pm 0\.0950Kbng\_letter162652\.446\.6−11\.0±0\.2\-11\.0\\pm 0\.2950Kcovertype54728\.123\.9−15\.0±0\.2\-15\.0\\pm 0\.2530Khepmass27218\.618\.4−1\.1±0\.1\-1\.1\\pm 0\.1830Khiggs28235\.532\.6−8\.0±0\.1\-8\.0\\pm 0\.16\.7Mkddcup9941170\.20\.2−16\.0±17\.8\-16\.0\\pm 17\.8440Kminiboone50211\.09\.9−10\.1±0\.7\-10\.1\\pm 0\.780Kpoker10949\.446\.9−5\.0±0\.3\-5\.0\\pm 0\.3445Kskin\_seg\.328\.30\.3−96\.1±0\.2\-96\.1\\pm 0\.2195Ksusy18221\.620\.3−6\.1±0\.1\-6\.1\\pm 0\.13\.5Myear\_pred\.908493\.697\.8\+4\.5±0\.1\+4\.5\\pm 0\.1445K11W / 1L / 1TTable 8:TS\-RQ vs TS: per\-dataset regret rates \(%\) and gap with 95% CIs\.DatasetddKKBase \(%\)RQ \(%\)Gap \(%\)TTairlines7245\.642\.8−6\.2±2\.5\-6\.2\\pm 2\.5450Kbeer\_rev\.1210492\.789\.8−3\.2±0\.3\-3\.2\\pm 0\.3450Kbng\_elev\.181081\.777\.9−4\.6±0\.2\-4\.6\\pm 0\.2950Kbng\_letter162696\.071\.4−25\.6±0\.5\-25\.6\\pm 0\.5950Kcovertype54751\.338\.8−24\.4±0\.7\-24\.4\\pm 0\.7530Khepmass27250\.021\.7−56\.6±0\.2\-56\.6\\pm 0\.2830Khiggs28248\.043\.7−9\.0±1\.6\-9\.0\\pm 1\.66\.7Mkddcup99411742\.71\.1−97\.4±0\.1\-97\.4\\pm 0\.1440Kminiboone50228\.314\.7−48\.1±0\.8\-48\.1\\pm 0\.880Kpoker10949\.850\.4\+1\.1±0\.6\+1\.1\\pm 0\.6445Kskin\_seg\.3220\.82\.6−87\.4±2\.4\-87\.4\\pm 2\.4195Ksusy18246\.624\.8−46\.8±1\.1\-46\.8\\pm 1\.13\.5Myear\_pred\.908492\.893\.2\+0\.4±0\.2\+0\.4\\pm 0\.2445K11W / 2L / 0TTable 9:SGD\-RQ vs SGD\-LinTS: per\-dataset regret rates \(%\) and gap with 95% CIs\.DatasetddKKBase \(%\)RQ \(%\)Gap \(%\)TTairlines7246\.242\.4−8\.2±1\.1\-8\.2\\pm 1\.1450Kbeer\_rev\.1210491\.789\.2−2\.8±0\.2\-2\.8\\pm 0\.2450Kbng\_elev\.181080\.077\.6−3\.0±0\.6\-3\.0\\pm 0\.6950Kbng\_letter162681\.664\.3−21\.2±0\.7\-21\.2\\pm 0\.7950Kcovertype54748\.932\.0−34\.6±1\.4\-34\.6\\pm 1\.4530Khepmass27220\.519\.1−7\.1±0\.2\-7\.1\\pm 0\.2830Khiggs28249\.036\.2−26\.2±2\.3\-26\.2\\pm 2\.36\.7Mkddcup99411720\.71\.2−94\.3±2\.4\-94\.3\\pm 2\.4440Kminiboone50232\.914\.1−57\.3±6\.1\-57\.3\\pm 6\.180Kpoker10953\.649\.4−7\.8±0\.8\-7\.8\\pm 0\.8445Kskin\_seg\.3242\.02\.5−94\.2±1\.1\-94\.2\\pm 1\.1195Ksusy18229\.223\.0−21\.2±0\.6\-21\.2\\pm 0\.63\.5Myear\_pred\.908493\.394\.0\+0\.7±0\.1\+0\.7\\pm 0\.1445K12W / 1L / 0T
## Appendix IPer\-Dataset Regret Curves

Figure 10:Regret rate vs\.TTfor all 9 methods on each dataset\. Shaded bands show±1\\pm 1std across seeds\.
## Appendix JRegret Scaling Analysis

To empirically validate consistency with the regret bound \([70](https://arxiv.org/html/2610.02440#A6.E70)\), we fit two models to the TS\-RQ cumulative regret curves across all datasets\.

Power\-law fit\.We fitR⁡\(T\)=a⋅TαR\(T\)=a\\cdot T^\{\\alpha\}via log\-log regression\. If regret were dominated by theO⁡\(T​log⁡T\)O\(\\sqrt\{T\\log T\}\)exploration term, we would expectα≈0\.5\\alpha\\approx 0\.5\. If dominated by theO⁡\(Δℓ​T\)O\(\\Delta\_\{\\ell\}T\)bias term, we expectα≈1\.0\\alpha\\approx 1\.0\. Figure[11](https://arxiv.org/html/2610.02440#A10.F11)\(left\) shows that all 13 datasets yieldα∈\[0\.87,1\.00\]\\alpha\\in\[0\.87,1\.00\], indicating that regret is overwhelmingly dominated by the linear bias term at the horizons in our experiments \(TTup to1111M\)\.

Decomposition fit\.We also fitR⁡\(T\)=a​T\+c⋅TR\(T\)=a\\sqrt\{T\}\+c\\cdot Tdirectly, separating exploration and bias contributions\. The bias coefficientccestimates the asymptotic regret rateR⁡\(T\)/T→O⁡\(Δℓ​\(ℳ\)\)R\(T\)/T\\to O\(\\Delta\_\{\\ell\}\(\\mathcal\{M\}\)\)\. Figure[11](https://arxiv.org/html/2610.02440#A10.F11)\(right\) shows the regret rate converging to a constant on selected datasets, confirming the linear bias term dominates\.

Interpretation\.This is exactly what Theorem[3\.1](https://arxiv.org/html/2610.02440#S3.Thmtheorem1)predicts: the exploration termO⁡\(b​ℓ​p​K​T​log⁡\(T/δ\)\)O\(b\\ell p\\sqrt\{KT\\log\(T/\\delta\)\}\)grows asT​log⁡T\\sqrt\{T\\log T\}and becomes negligible relative toO⁡\(Δℓ​T\)O\(\\Delta\_\{\\ell\}T\)for largeTT\. The practical implication is that reducingΔℓ\\Delta\_\{\\ell\}\(via deeper codebooks or richer base learners\) is more impactful than reducing exploration cost—consistent with TS\-RQ’s strong empirical performance despite its greedy approximation of the joint model\.

Figure 11:Regret scaling analysis for TS\-RQ\.Left:Power\-law exponentα\\alphaper dataset \(R⁡\(T\)∼TαR\(T\)\\sim T^\{\\alpha\}\); all values are near1\.01\.0, indicating bias\-dominated regret\.Right:Regret rateR⁡\(T\)/TR\(T\)/Tvs\.TTfor selected datasets, converging to a constant consistent with theO⁡\(Δℓ​T\)O\(\\Delta\_\{\\ell\}T\)bias term in Theorem[3\.1](https://arxiv.org/html/2610.02440#S3.Thmtheorem1)\.
## Appendix KData Sufficiency: Synthetic Validation

We validate the data sufficiency conditionN/\(b​K​d2\)N/\(bKd^\{2\}\)on synthetic data with two feature distributions:

Gaussian features\.N=500​KN\{=\}500\\text\{K\}i\.i\.d\. standard normal inℝd\\mathbb\{R\}^\{d\}\. Random per\-centroid reward structure\. LinTS\-RQ wins whenN/\(b​K​d2\)\>100N/\(bKd^\{2\}\)\>100, ties at30−10030\{\-\}100, loses below3030\. This is the pessimistic bound: structureless features provide no exploitable correlation for the codebook\.

Structured features\.Correlated continuous groups, binary categoricals, planted decision tree for class assignment\. LinTS\-RQ wins at*all*tested ratios \(≥14\\geq 14\), because the planted structure aligns with the RQ codebook’s partition\.

Real datasets behave like the structured synthetic: 12 of 13 datasets win at ratios as low as1\.11\.1\. The sole failure \(year\_prediction, ratio0\.040\.04\) is25×25\\timesbelow any tested threshold\.

Figure 12:Data sufficiency:N/\(b​K​d2\)N/\(bKd^\{2\}\)vs\. LinTS\-RQ regret gap\. Real datasets \(filled circles\) win at ratios as low as1\.11\.1\. Synthetic Gaussian \(open squares\) requires ratio\>30\>30\. year\_prediction is the sole outlier at ratio0\.040\.04\.
## Appendix Lyear\_prediction Depth Analysis

On year\_prediction \(d=90d\{=\}90,K=84K\{=\}84\), LinTS\-RQ degrades even at depth 1 \(96\.3%96\.3\\%vs\. LinTS baseline93\.4%93\.4\\%\)\. Adding depth makes it progressively worse \(96\.9%96\.9\\%atℓ=2\\ell\{=\}2,97\.4%97\.4\\%atℓ=4\\ell\{=\}4\)\.

TS\-RQ is unaffected:93\.0%93\.0\\%at all depths, matching the baseline\. SGD\-LinTS\-RQ improves slightly with depth \(96\.9%→95\.0%96\.9\\%\\to 95\.0\\%\) because diagonal estimation is more data\-efficient than full covariance inℝ90\\mathbb\{R\}^\{90\}\.

The root cause is data fragmentation: withb=16b\{=\}16centroids, each centroid receives≈28​K\\approx 28\\text\{K\}samples to estimated2​K=680​Kd^\{2\}K=680\\text\{K\}parameters—a ratio of0\.040\.04\. Context\-free TS achieves92\.7%92\.7\\%, outperforming all feature\-based methods, confirming that the features carry negligible signal for the 84\-way quantile\-binned target\.

## Appendix MReconstruction Error

The normalized reconstruction error‖x−x^‖2/‖x‖2\\\|x\-\\hat\{x\}\\\|^\{2\}/\\\|x\\\|^\{2\}at depth 4 ranges from0\.0050\.005\(skin\_segmentation\) to0\.6480\.648\(year\_prediction\)\. year\_prediction’s high error confirms thatb=16b\{=\}16centroids inℝ90\\mathbb\{R\}^\{90\}cannot capture the feature geometry, consistent with its status as the sole LinTS\-RQ failure\.

Table 10:Normalized reconstruction error at depth 4\.
## Appendix NEffective Rank and SGD\-LinTS Failure

On datasets with effective rank<1\.5<1\.5—skin\_segmentation \(eff\. rank1\.31\.3,d=3d\{=\}3\) and miniboone \(eff\. rank1\.11\.1,d=50d\{=\}50\)—SGD\-LinTS performs*worse than context\-free TS*\(42\.0%42\.0\\%vs20\.8%20\.8\\%and32\.9%32\.9\\%vs28\.3%28\.3\\%regret rate\)\. The diagonal approximation treats each feature coordinate independently; when most variance lies on a single axis, it wastesd−1d\{\-\}1coordinates on noise\. TS\-RQ is unaffected:2\.6%2\.6\\%on skin\_segmentation and14\.7%14\.7\\%on miniboone\.

Figure 13:Effective rank vs\. regret rate\. SGD\-LinTS \(squares\) fails severely when eff\. rank<1\.5<1\.5\(red zone\), performing worse than context\-free TS \(diamonds\)\. TS\-RQ \(circles\) is unaffected\.
## Appendix OXGBoost and NeuralCB Comparison

LinTS\-RQ achieves regret competitive with both nonlinear replay baselines\. Against Doubling\-XGB: 7 wins, 4 losses, 2 ties \(30 LinTS\-RQ seeds, 10 XGB seeds, 95% CIs; Table[11](https://arxiv.org/html/2610.02440#A15.T11)\)\. Against Doubling\-NeuralCB: 5 wins, 2 losses, 5 ties \(30 LinTS\-RQ seeds, 10 NeuralCB seeds; Table[12](https://arxiv.org/html/2610.02440#A15.T12)\)\. Wins tend to be larger in magnitude than losses for both comparisons\. The key differentiator is memory: both baselines require anO⁡\(T\)O\(T\)replay buffer while LinTS\-RQ uses fixedO⁡\(1\)O\(1\)memory \(Table[2](https://arxiv.org/html/2610.02440#S4.T2)\)\.

Table 11:Per\-dataset regret rate \(%\): LinTS\-RQ vs\. Doubling\-XGB\. Negative gap = LinTS\-RQ has lower regret\.Table 12:Per\-dataset regret rate \(%\): LinTS\-RQ vs\. Doubling\-NeuralCB \(30 LinTS\-RQ seeds, 10 NeuralCB seeds\)\. Negative gap = LinTS\-RQ has lower regret\.DatasetLinTS\-RQD\-NeuralCBGapCallbeer\_reviews83\.087\.7−4\.6\-4\.6Winbng\_letter46\.652\.8−6\.2\-6\.2Wincovertype23\.927\.6−3\.7\-3\.7Winkddcup990\.21\.4−1\.2\-1\.2Winskin\_seg0\.31\.6−1\.3\-1\.3Winairlines\_delay39\.840\.2−0\.4\-0\.4Tiebng\_elevators75\.075\.0\+0\.1\+0\.1Tiehepmass18\.418\.2\+0\.1\+0\.1Tiehiggs32\.632\.4\+0\.3\+0\.3Tiesusy20\.320\.4−0\.1\-0\.1Tiepoker\_hand46\.945\.8\+1\.1\+1\.1Lossyear\_prediction97\.893\.1\+4\.6\+4\.6LossFigure 14:Per\-dataset regret rate: LinTS\-RQ vs\. Doubling\-XGB\.
## Appendix PTabNet\-LinTS Comparison

LinTS\-RQ wins on 11 of 13 datasets against TabNet\-LinTS \(11W/2L; losses: hepmass\+0\.5%\+0\.5\\%, year\_prediction\+1\.7%\+1\.7\\%; Welch’stt\-test, 30 seeds each, 95% CIs\)\. Both use the same 50K holdout \(unsupervised\); the RQ codebook matches or exceeds TabNet’s reconstruction\-based embedding\.

Figure 15:Per\-dataset regret rate: LinTS\-RQ vs\. TabNet\-LinTS\.
## Appendix QTiming

Figure 16:Wall\-clockμ\\mus/step per method at adapted DRQm depths\. TS\-RQ is consistently the cheapest RQ variant \(50−750​μ50\{\-\}750\\,\\mus\)\. LinTS\-RQ on year\_prediction \(d=90d\{=\}90,K=84K\{=\}84\) reaches2828ms\.
## Appendix RMemory Formulas

Model memory = \(codebook \+ model parameters\)×\\times8 bytes\.

Adapted depthℓ\\ellfrom shadow promotion varies by dataset \(median across 30 seeds\)\. TS\-RQ goes deepest \(up toℓ=8\\ell\{=\}8on bng\_letter\); LinTS\-RQ stays shallowest \(ℓ=2−3\\ell\{=\}2\{\-\}3, limited by cascaded convergence\)\.

## NeurIPS Paper Checklist

1. 1\.Claims
2. Question: Do the main claims made in the abstract and introduction accurately reflect the paper’s contributions and scope?
3. Answer:\[Yes\]
4. Justification: The abstract claims RQ codebooks improve contextual bandits with fixed memory; this is supported by the asymptotic regret analysis \(Theorem[3\.1](https://arxiv.org/html/2610.02440#S3.Thmtheorem1)\), shadow false\-promotion control \(Theorem[3\.3](https://arxiv.org/html/2610.02440#S3.Thmtheorem3)\), and experiments across 13 datasets \(§[4](https://arxiv.org/html/2610.02440#S4)\)\.
5. 2\.Limitations
6. Question: Does the paper discuss the limitations of the work performed by the authors?
7. Answer:\[Yes\]
8. Justification: §[6](https://arxiv.org/html/2610.02440#S6)discusses three limitations: the squared\-loss approximation for binary rewards, the data sufficiency conditionN/\(b​K​d2\)≫1N/\(bKd^\{2\}\)\\gg 1\(with year\_prediction as a concrete failure case\), and the dependence on a holdout set for codebook training\.
9. 3\.Theory assumptions and proofs
10. Question: For each theoretical result, does the paper provide the full set of assumptions and a complete \(and correct\) proof?
11. Answer:\[Yes\]
12. Justification: Theorem[3\.1](https://arxiv.org/html/2610.02440#S3.Thmtheorem1)\(asymptotic regret, Appendix[C](https://arxiv.org/html/2610.02440#A3)\) is conditional on three base\-learner convergence properties, which are stated explicitly and verified for all three model classes \(Appendix[B](https://arxiv.org/html/2610.02440#A2)\)\. Theorem[3\.3](https://arxiv.org/html/2610.02440#S3.Thmtheorem3)\(false\-promotion control\) is proved in Appendix[D](https://arxiv.org/html/2610.02440#A4)\. Theorem[3\.2](https://arxiv.org/html/2610.02440#S3.Thmtheorem2)exactly decomposes depth\-dependent approximation error, and Corollary[3\.1](https://arxiv.org/html/2610.02440#S3.Thmcorollary1)proves geometric decay under explicit reconstruction\- and additive\-tail contraction assumptions; their proofs are in Appendix[C](https://arxiv.org/html/2610.02440#A3)\.
13. 4\.Experimental result reproducibility
14. Question: Does the paper fully disclose all the information needed to reproduce the main experimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper \(regardless of whether the code and data are provided or not\)?
15. Answer:\[Yes\]
16. Justification: Algorithm[1](https://arxiv.org/html/2610.02440#alg1)specifies the method\. §[4](https://arxiv.org/html/2610.02440#S4)describes all datasets \(publicly available from OpenML\), codebook parameters \(b=16b\{=\}16, depths 1–5\), number of seeds \(30\), and baselines\.
17. 5\.Open access to data and code
18. Question: Does the paper provide open access to the data and code, with sufficient instructions to faithfully reproduce the main experimental results, as described in supplemental material?
19. Answer:\[Yes\]
21. 6\.Experimental setting/details
22. Question: Does the paper specify all the training and test details \(e\.g\., data splits, hyperparameters, how they were chosen, type of optimizer\) necessary to understand the results?
23. Answer:\[Yes\]
24. Justification: §[4](https://arxiv.org/html/2610.02440#S4)specifies codebook size \(b=16b\{=\}16\), clipping parameter \(σ\\sigma\), Thompson sampling noise scale, and the holdout/bandit split\. Appendix tables provide per\-dataset details\.
25. 7\.Experiment statistical significance
26. Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
27. Answer:\[Yes\]
28. Justification: All experiments use 30 seeds\. Figures show±1\\pm 1standard deviation; tables report 95% CIs\. The shadow promotion test uses Freedman’s martingale inequality with Bonferroni correction at significance levelα=0\.05\\alpha\{=\}0\.05\.
29. 8\.Experiments compute resources
30. Question: For each experiment, does the paper provide sufficient information on the computer resources \(type of compute workers, memory, time of execution\) needed to reproduce the experiments?
31. Answer:\[Yes\]
32. Justification: Timing benchmarks are reported in Appendix \(Table and Figure\)\. All experiments are CPU\-only \(no GPU required\)\. Memory usage is analyzed in Appendix\.
33. 9\.Code of ethics
35. Answer:\[Yes\]
36. Justification: The research uses only publicly available datasets and proposes a general\-purpose bandit algorithm with no foreseeable ethical concerns\.
37. 10\.Broader impacts
38. Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
39. Answer:\[Yes\]
40. Justification: Section[8](https://arxiv.org/html/2610.02440#S8)discusses positive impacts \(efficient personalization, resource\-constrained deployments\) and notes that standard fairness and privacy concerns for bandit algorithms apply\.
41. 11\.Safeguards
42. Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse \(e\.g\., pre\-trained language models, image generators, or scraped datasets\)?
43. Answer:\[N/A\]
44. Justification: The paper does not release pre\-trained models, generative models, or scraped datasets\. RQ\-Bandit is a lightweight bandit algorithm\.
45. 12\.Licenses for existing assets
46. Question: Are the creators or original owners of assets \(e\.g\., code, data, models\), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
47. Answer:\[Yes\]
48. Justification: All datasets are cited with their original publications in Appendix[G](https://arxiv.org/html/2610.02440#A7)\. All are publicly available from OpenML and UCI under open licenses\.
49. 13\.New assets
50. Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
51. Answer:\[Yes\]
52. Justification: The RQ\-Bandit implementation will be released as supplementary code with documentation and scripts to reproduce the main experiments\.
53. 14\.Crowdsourcing and research with human subjects
54. Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation \(if any\)?
55. Answer:\[N/A\]
56. Justification: No crowdsourcing or human subjects research was conducted\.
57. 15\.Institutional review board \(IRB\) approvals or equivalent for research with human subjects
58. Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board \(IRB\) approvals \(or an equivalent approval/review based on the requirements of your country or institution\) were obtained?
59. Answer:\[N/A\]
60. Justification: No human subjects research was conducted\.
61. 16\.Declaration of LLM usage
62. Question: Does the paper describe the usage of LLMs if it is an important, original, or non\-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, or formatting purposes and does*not*impact the core methodology, scientific rigor, or originality of the research, declaration is not required\.
63. Answer:\[N/A\]
64. Justification: LLMs were used only for writing assistance and editorial polishing\. They are not a component of the RQ\-Bandit method or experimental pipeline\.