Catching a Moving Subspace: Low-Rank Bandits Beyond Stationarity

# Catching a Moving Subspace: Low-Rank Bandits Beyond Stationarity
Source: [https://arxiv.org/html/2605.20269](https://arxiv.org/html/2605.20269)
Hamed Khosravi H\. Milton Stewart School of Industrial and Systems Engineering Georgia Institute of Technology Atlanta, GA 30332 hkhosravi7@gatech\.edu &Xiaoming Huo H\. Milton Stewart School of Industrial and Systems Engineering Georgia Institute of Technology Atlanta, GA 30332 huo@gatech\.edu

###### Abstract

Many real bandit deployments \(recommendation, clinical dosing, ad targeting\) share two structural facts handled only in isolation by prior work: rewards live on a low\-dimensional latent subspace, and that subspace drifts\. Stationary low\-rank bandits exploit the rank but break under any subspace change; non\-stationary linear bandits adapt to drift but pay the ambient rate𝒪~​\(d​T\)\\widetilde\{\\mathcal\{O\}\}\(d\\sqrt\{T\}\)\. We study*piecewise\-stationary low\-rank*linear contextual bandits with scalar feedback:θt=Bk⋆​wt\\theta\_\{t\}=B\_\{k\}^\{\\star\}w\_\{t\}for a rank\-rrfactorBk⋆∈ℝd×rB\_\{k\}^\{\\star\}\\in\\mathbb\{R\}^\{d\\times r\}that is constant within each ofKKunknown segments and may shift at the boundaries\. Our results are tight along three axes\.\(i\) Identification boundary\.With single\-play scalar rewards, the moving subspace is recoverable through quadratic functionals of rewards if and only if three probe\-side conditions hold \(known noise variance, bounded state\-noise coupling, full\-dimensional probe support\)\. Each is individually necessary in the unrestricted\-second\-moment problem, and the three are jointly sufficient: a characterization of the boundary of the solvable region, not just a sufficient interior point\.\(ii\) Algorithm and dynamic regret\.SPSC\(Single\-Play Subspace\-Calibrated Optimism\) interleaves isotropic probes with windowed projected ridge\-UCB exploitation inside the learnedrr\-dimensional subspace; a CUSUM\-style adaptive variant discovers segment boundaries online\. The costed dynamic regret is𝒪~​\(r​T\)\+𝒪~​\(T2/3\)\+O​\(W​Vin\)\\widetilde\{\\mathcal\{O\}\}\(r\\sqrt\{T\}\)\+\\widetilde\{\\mathcal\{O\}\}\(T^\{2/3\}\)\+O\(W\\,V\_\{\\rm in\}\), replacing the ambientd​Td\\sqrt\{T\}rate with the intrinsic rank\.\(iii\) Empirics\.On eleven benchmarks spanning synthetic, UCI/MovieLens, semi\-synthetic clinical, and ZOZOTOWN production\-log data, SPSC outperforms non\-stationary and low\-rank baselines wheneverd−r≳T1/6d\-r\\gtrsim T^\{1/6\}, matching the analytical crossover\. To our knowledge, this is the first work to characterize the identification boundary and attain the intrinsic\-rank dynamic\-regret rate in this setting\.

## 1Introduction

High\-dimensional sequential decisions \(personalized recommendation, clinical dosing, ad allocation\) share two structural facts that the linear\-bandit literature has so far treated only in isolation: rewards live on a low\-dimensional latent subspace, and that subspace drifts\. User preferences, clinical responses, and ad\-creative effects occupy a thin slice of the ambientℝd\\mathbb\{R\}^\{d\}with intrinsic rankr≪dr\\ll d; but the slice is*not static*: tastes drift, cohorts change, treatment regimes get revised, and the latent factor itself moves across unknown change points\. Production deployments make both facts visible: Spotify’s homepage contextual bandit explicitly targets daily shifts in user intent\(Feijeret al\.,[2025](https://arxiv.org/html/2605.20269#bib.bib21)\); the IWPC warfarin cohort\(Consortium,[2009](https://arxiv.org/html/2605.20269#bib.bib1)\)has been re\-analyzed to expose three latent patient subgroups whose dose–response coefficients flip sign across boundaries\(Liuet al\.,[2025](https://arxiv.org/html/2605.20269#bib.bib22)\); the public Open Bandit logs\(Saitoet al\.,[2021](https://arxiv.org/html/2605.20269#bib.bib17)\)ship scalar feedback collected across multiple ad campaigns at ZOZOTOWN\.

#### Where the literature stops\.

Stationary low\-rank bandits\(Junet al\.,[2019](https://arxiv.org/html/2605.20269#bib.bib3); Jedraet al\.,[2024](https://arxiv.org/html/2605.20269#bib.bib16); Janget al\.,[2024](https://arxiv.org/html/2605.20269#bib.bib15)\)deliver the𝒪~​\(r​T\)\\widetilde\{\\mathcal\{O\}\}\(r\\sqrt\{T\}\)rate but assume a fixed factor; any non\-trivial subspace change voids the analysis \(𝒪~\\widetilde\{\\mathcal\{O\}\}suppresses polylog factors inT,d,r,1/δT,d,r,1/\\delta\)\. Non\-stationary linear bandits\(Russacet al\.,[2019](https://arxiv.org/html/2605.20269#bib.bib6); Cheunget al\.,[2019](https://arxiv.org/html/2605.20269#bib.bib5)\)absorb drift through sliding windows or discounting but operate inℝd\\mathbb\{R\}^\{d\}and pay𝒪~​\(d​T\)\\widetilde\{\\mathcal\{O\}\}\(d\\sqrt\{T\}\)within each segment, ignoring intrinsic rank entirely\. Naive combinations fail in instructive ways: sliding\-window ridge inℝd\\mathbb\{R\}^\{d\}never recovers the subspace; a one\-shot subspace estimate breaks the moment a change point fires; per\-segment re\-runs of stationary low\-rank algorithms require oracle access to the boundaries\. No prior algorithm recovers a changing subspace under scalar feedback, and no prior analysis prices that recovery against the exploitation regret it buys\.

#### This work\.

We study*piecewise\-stationary low\-rank*linear contextual bandits with scalar feedback:θt=Bk⋆​wt\\theta\_\{t\}=B\_\{k\}^\{\\star\}w\_\{t\}for a rank\-rrfactorBk⋆∈ℝd×rB\_\{k\}^\{\\star\}\\in\\mathbb\{R\}^\{d\\times r\}that is constant within each ofKKunknown segmentsℐk=\[τk−1,τk\)\\mathcal\{I\}\_\{k\}=\[\\tau\_\{k\-1\},\\tau\_\{k\}\)delimited by change points1=τ0<τ1<⋯<τK=T\+11=\\tau\_\{0\}<\\tau\_\{1\}<\\dots<\\tau\_\{K\}=T\{\+\}1and may shift at the boundaries, with the learner only observing scalar responsesyt=xt⊤​θt\+εty\_\{t\}=x\_\{t\}^\{\\top\}\\theta\_\{t\}\+\\varepsilon\_\{t\}\(§[2](https://arxiv.org/html/2605.20269#S2)\)\. The genuine difficulty is twofold\. \(a\) A single scalar responseyty\_\{t\}is a rank\-one quadratic measurement ofθt​θt⊤\\theta\_\{t\}\\theta\_\{t\}^\{\\top\}, so the moving subspace is recoverable only through*second\-order*probing\. \(b\) Every probe diverts a round away from exploitation, so probe acquisition must itself be priced against the regret it enables\. Our results are tight along three axes\.

#### Contributions\.

\(i\) Identification boundary \(Theorem[2\.2](https://arxiv.org/html/2605.20269#S2.Thmtheorem2)\)\.Three probe\-side conditions \(known noise variance, bounded state–noise coupling, full\-dimensional probe support\) are individually necessary in the unrestricted\-second\-moment problem and jointly sufficient for recoveringrange​\(Bk⋆\)\\mathrm\{range\}\(B\_\{k\}^\{\\star\}\)from quadratic functionals of scalar rewards\. The necessity half, three matching impossibility results \(Propositions[C\.12](https://arxiv.org/html/2605.20269#A3.Thmtheorem12)–[C\.14](https://arxiv.org/html/2605.20269#A3.Thmtheorem14)\), is what distinguishes this from a generic identifiability statement: it characterizes the boundary of the solvable region, not just a sufficient interior point\.\(ii\) Algorithm and costed dynamic regret \(Theorem[4\.1](https://arxiv.org/html/2605.20269#S4.Thmtheorem1)\)\.SPSC\(Alg\.[1](https://arxiv.org/html/2605.20269#alg1)\) interleaves isotropic probes with windowed projected ridge\-UCB exploitation inside the learnedrr\-dimensional subspace via a quadratic\-measurement identity; aSPSC\-Adaptivevariant \(Alg\.[2](https://arxiv.org/html/2605.20269#alg2)\) uses a CUSUM\-style detector to discover segment changes online\. The costed dynamic regret isDynRegT\(c\)≤𝒪~​\(r​T\)\+𝒪~​\(T2/3\)\+O​\(W​Vin\)\\mathrm\{DynReg\}\_\{T\}^\{\(c\)\}\\leq\\widetilde\{\\mathcal\{O\}\}\(r\\sqrt\{T\}\)\+\\widetilde\{\\mathcal\{O\}\}\(T^\{2/3\}\)\+O\(W\\,V\_\{\\rm in\}\), replacing the ambientd​Td\\sqrt\{T\}rate with the intrinsic rankrr, whereWWis the exploitation window andVinV\_\{\\rm in\}the within\-segment path variation\.\(iii\) Eleven benchmarks against eleven baselines\.A synthetic phase\-transition grid, five UCI environments plus MovieLens, two semi\-synthetic clinical datasets, the small\-ddpiecewise\-stationary stress test ofRussacet al\.\([2019](https://arxiv.org/html/2605.20269#bib.bib6)\), and Open Bandit production logs, against LinUCB, D\-LinUCB, SW\-LinUCB, Restart\-LinUCB, LowOFUL, VOFUL, LowRank\-Reward, LinTS, SW\-LinTS, and adapted stationary low\-rank methods BOSS and Jedra\. SPSC delivers regret reductions wheneverd−r≳T1/6d\-r\\gtrsim T^\{1/6\}, matching the analytical crossover\. A direct necessity stress test \(App\.[H\.3](https://arxiv.org/html/2605.20269#A8.SS3), part C\) restricts probe coverage to a proper subspace and reproduces theΩ​\(T\)\\Omega\(T\)blow\-up predicted by Proposition[C\.14](https://arxiv.org/html/2605.20269#A3.Thmtheorem14), confirming the third identifiability condition is not a proof artifact\.

To our knowledge, this is the first work to characterize the identification boundary and to attain the intrinsic\-rank dynamic\-regret rate in the piecewise\-stationary low\-rank setting under scalar feedback\.

#### Related work\.

Stationary low\-rank bandits\(Junet al\.,[2019](https://arxiv.org/html/2605.20269#bib.bib3); Kanget al\.,[2022](https://arxiv.org/html/2605.20269#bib.bib13); Jedraet al\.,[2024](https://arxiv.org/html/2605.20269#bib.bib16); Janget al\.,[2024](https://arxiv.org/html/2605.20269#bib.bib15); Stojanovicet al\.,[2023](https://arxiv.org/html/2605.20269#bib.bib11); Duonget al\.,[2024](https://arxiv.org/html/2605.20269#bib.bib20); Luet al\.,[2021](https://arxiv.org/html/2605.20269#bib.bib4)\)achieve intrinsic\-rank rates but assume a fixedB⋆B^\{\\star\}; non\-stationary linear bandits\(Russacet al\.,[2019](https://arxiv.org/html/2605.20269#bib.bib6); Cheunget al\.,[2019](https://arxiv.org/html/2605.20269#bib.bib5); Abbasi\-Yadkoriet al\.,[2023](https://arxiv.org/html/2605.20269#bib.bib7); Houet al\.,[2024](https://arxiv.org/html/2605.20269#bib.bib12)\)bound dynamic regret in the ambient dimension and ignore low\-rank structure; cost\-aware observation\(Seldinet al\.,[2014](https://arxiv.org/html/2605.20269#bib.bib8); Tuckeret al\.,[2023](https://arxiv.org/html/2605.20269#bib.bib9); Elumaret al\.,[2024](https://arxiv.org/html/2605.20269#bib.bib10)\)prices information acquisition for fixed parameters, not for identifying a changing subspace\. SPSC sits at the intersection of all three: it \(i\) attains regret scaling with intrinsic rankrr, \(ii\) adapts to changing subspaces without oracle boundaries, and \(iii\) prices probe acquisition explicitly\. Appendix[B](https://arxiv.org/html/2605.20269#A2)gives the full positioning \(Tables[5](https://arxiv.org/html/2605.20269#A2.T5)–[7](https://arxiv.org/html/2605.20269#A2.T7)\)\.

## 2Setting and probe\-based identification

#### Piecewise low\-rank model\.

At every roundttthe reward parameter admits a factorizationθt=Bk⋆​wt\\theta\_\{t\}=B\_\{k\}^\{\\star\}w\_\{t\}, whereBk⋆∈ℝd×rB\_\{k\}^\{\\star\}\\in\\mathbb\{R\}^\{d\\times r\}has orthonormal columns and is piecewise constant overK≥1K\\geq 1segmentsℐk\\mathcal\{I\}\_\{k\}with unknown change points1=τ0<τ1<⋯<τK=T\+11=\\tau\_\{0\}<\\tau\_\{1\}<\\dots<\\tau\_\{K\}=T\{\+\}1, and the latent statewt∈ℝrw\_\{t\}\\in\\mathbb\{R\}^\{r\}follows a stable linear dynamical system inside each segment

wt=Ak​wt−1\+ηt−1,t∈ℐk,w\_\{t\}=A\_\{k\}w\_\{t\-1\}\+\\eta\_\{t\-1\},\\qquad t\\in\\mathcal\{I\}\_\{k\},with unknownAkA\_\{k\}satisfyingρ​\(Ak\)≤1−α0\\rho\(A\_\{k\}\)\\leq 1\{\-\}\\alpha\_\{0\}for someα0\>0\\alpha\_\{0\}\>0\(used only to ensure‖wt‖≤Sw\\\|w\_\{t\}\\\|\\leq S\_\{w\}via the stationary covariance bound\) and zero\-mean innovationηt−1\\eta\_\{t\-1\}with covarianceΣη,k≻0\\Sigma\_\{\\eta,k\}\\succ 0\. We assume uniform action\-boundednesssupx∈𝒜t‖x‖≤R𝒜\\sup\_\{x\\in\\mathcal\{A\}\_\{t\}\}\\\|x\\\|\\leq R\_\{\\mathcal\{A\}\}, a known probe distributionQQwith𝔼​\[u​u⊤\]⪰ρQ​Id\\mathbb\{E\}\[uu^\{\\top\}\]\\succeq\\rho\_\{Q\}I\_\{d\}and sub\-Gaussian marginals \(bounded‖u‖≤L\\\|u\\\|\\leq Lis a special case; see Remark[2\.1](https://arxiv.org/html/2605.20269#S2.Thmtheorem1)\), conditionallyσε\\sigma\_\{\\varepsilon\}\-sub\-Gaussian noise with unknown variance, bounded state\-noise coupling‖𝔼​\[εt​θt\]‖2≤ϵ×\\\|\\mathbb\{E\}\[\\varepsilon\_\{t\}\\theta\_\{t\}\]\\\|\_\{2\}\\leq\\epsilon\_\{\\times\}, and full\-dimensional probe coverage\. Theorem[2\.2](https://arxiv.org/html/2605.20269#S2.Thmtheorem2)below shows these three probe\-side conditions are individually necessary and jointly sufficient for identifying the changing subspace from single\-play scalar rewards\. Throughout,δ∈\(0,1\)\\delta\\in\(0,1\)denotes the global confidence parameter \(concentration bounds hold with probability≥1−δ\\geq 1\-\\delta\) andλ\>0\\lambda\>0denotes the ridge regularizer used by the windowed estimator of §[3](https://arxiv.org/html/2605.20269#S3)\.

#### Quadratic measurement identity\.

Letσ^2\\widehat\{\\sigma\}^\{2\}be the algorithm’s estimate of the noise variance and define the centered probe statisticst:=yt2−σ^2s\_\{t\}:=y\_\{t\}^\{2\}\-\\widehat\{\\sigma\}^\{2\}on every probe roundt∈𝒯probet\\in\\mathcal\{T\}\_\{\\mathrm\{probe\}\}\. Under the probe\-noise assumptions of §[2](https://arxiv.org/html/2605.20269#S2), forδσ:=σ^2−σε2\\delta\_\{\\sigma\}:=\\widehat\{\\sigma\}^\{2\}\-\\sigma\_\{\\varepsilon\}^\{2\},

𝔼​\[st∣ℋt−1,ut\]=ut⊤​M~t​ut\+2​ut⊤​𝔼​\[εt​θt∣ℋt−1,ut\]−δσ,\\mathbb\{E\}\[s\_\{t\}\\mid\\mathcal\{H\}\_\{t\-1\},u\_\{t\}\]=u\_\{t\}^\{\\top\}\\widetilde\{M\}\_\{t\}u\_\{t\}\+2u\_\{t\}^\{\\top\}\\mathbb\{E\}\[\\varepsilon\_\{t\}\\theta\_\{t\}\\mid\\mathcal\{H\}\_\{t\-1\},u\_\{t\}\]\-\\delta\_\{\\sigma\},\(1\)whereM~t:=𝔼​\[θt​θt⊤∣ℋt−1\]\\widetilde\{M\}\_\{t\}:=\\mathbb\{E\}\[\\theta\_\{t\}\\theta\_\{t\}^\{\\top\}\\mid\\mathcal\{H\}\_\{t\-1\}\]is the predictable second moment, whose range is contained inrange​\(Bk⋆\)\\mathrm\{range\}\(B\_\{k\}^\{\\star\}\)fort∈ℐkt\\in\\mathcal\{I\}\_\{k\}; under the non\-degenerate innovation conditionΣη,k≻0\\Sigma\_\{\\eta,k\}\\succ 0\(§[2](https://arxiv.org/html/2605.20269#S2)\), the probe\-time average has range exactlyrange​\(Bk⋆\)\\mathrm\{range\}\(B\_\{k\}^\{\\star\}\)\(Proposition[C\.9](https://arxiv.org/html/2605.20269#A3.Thmtheorem9)\)\. Under exact probe conditions \(δσ=ϵ×=0\\delta\_\{\\sigma\}=\\epsilon\_\{\\times\}=0\) this collapses to𝔼​\[st∣⋅\]=ut⊤​M~t​ut\\mathbb\{E\}\[s\_\{t\}\\mid\\cdot\]=u\_\{t\}^\{\\top\}\\widetilde\{M\}\_\{t\}u\_\{t\}:*a scalar reward carries a quadratic measurement ofM~t\\widetilde\{M\}\_\{t\}*\.

#### Lifted subspace estimator\.

The probe moment operator𝒦:M↦𝔼​\[\(u⊤​M​u\)​u​u⊤\]\\mathcal\{K\}:M\\mapsto\\mathbb\{E\}\[\(u^\{\\top\}Mu\)\\,uu^\{\\top\}\]admits a closed\-form inverse on symmetric matrices for scaled\-sphere probesu=d​vu=\\sqrt\{d\}\\,v,v∼Unif​\(𝕊d−1\)v\\sim\\mathrm\{Unif\}\(\\mathbb\{S\}^\{d\-1\}\):

𝒦​\(M\)=dd\+2​\(tr⁡\(M\)​Id\+2​M\),𝒦−1​\(N\)=d\+22​d​N−tr⁡\(N\)2​d​Id,‖𝒦−1‖op→op≤1\\mathcal\{K\}\(M\)=\\tfrac\{d\}\{d\+2\}\\bigl\(\\operatorname\{tr\}\(M\)\\,I\_\{d\}\+2M\\bigr\),\\qquad\\mathcal\{K\}^\{\-1\}\(N\)=\\tfrac\{d\+2\}\{2d\}\\,N\-\\tfrac\{\\operatorname\{tr\}\(N\)\}\{2d\}\\,I\_\{d\},\\qquad\\\|\\mathcal\{K\}^\{\-1\}\\\|\_\{\\mathrm\{op\}\\to\\mathrm\{op\}\}\\leq 1\(2\)on the symmetric subspace \(Lemma[C\.4](https://arxiv.org/html/2605.20269#A3.Thmtheorem4)\)\. Define the*lifted probe sample*

Gt:=𝒦−1​\(st​ut​ut⊤\),𝔼​\[Gt∣ℋt−1\]=M~t\+B~t,G\_\{t\}:=\\mathcal\{K\}^\{\-1\}\(s\_\{t\}\\,u\_\{t\}u\_\{t\}^\{\\top\}\),\\qquad\\mathbb\{E\}\[G\_\{t\}\\mid\\mathcal\{H\}\_\{t\-1\}\]=\\widetilde\{M\}\_\{t\}\+\\widetilde\{B\}\_\{t\},\(3\)with biasB~t=−\(δσ/d\)​Id\\widetilde\{B\}\_\{t\}=\-\(\\delta\_\{\\sigma\}/d\)\\,I\_\{d\}exactly on scaled\-sphere probes, hence‖B~t‖op=\|δσ\|/d\\\|\\widetilde\{B\}\_\{t\}\\\|\_\{\\mathrm\{op\}\}=\|\\delta\_\{\\sigma\}\|/d\(Lemma[C\.6](https://arxiv.org/html/2605.20269#A3.Thmtheorem6)\)\. Averaging lifted samples across the probe rounds of segmentkkyieldsM^k:=mk−1​∑t∈𝒯kGt\\widehat\{M\}\_\{k\}:=m\_\{k\}^\{\-1\}\\sum\_\{t\\in\\mathcal\{T\}\_\{k\}\}G\_\{t\}\(with𝒯k:=𝒯probe∩ℐk\\mathcal\{T\}\_\{k\}:=\\mathcal\{T\}\_\{\\mathrm\{probe\}\}\\cap\\mathcal\{I\}\_\{k\}the probe rounds in segmentkk,mk:=\|𝒯k\|m\_\{k\}:=\|\\mathcal\{T\}\_\{k\}\|\), whose top\-rreigenvectors formU^k∈ℝd×r\\widehat\{U\}\_\{k\}\\in\\mathbb\{R\}^\{d\\times r\}with‖P^k−Pk⋆‖op≤Csub​log⁡\(d/δ\)/mk\\\|\\widehat\{P\}\_\{k\}\-P\_\{k\}^\{\\star\}\\\|\_\{\\mathrm\{op\}\}\\leq C\_\{\\mathrm\{sub\}\}\\sqrt\{\\log\(d/\\delta\)/m\_\{k\}\}\(Corollary[C\.10](https://arxiv.org/html/2605.20269#A3.Thmtheorem10)below\)\. The variance misspecification biasB~\\widetilde\{B\}is a scaled identity \(population level\), shifting all eigenvalues uniformly and*not rotating eigenvectors*: subspace recovery is robust to the plug\-in estimate ofσε2\\sigma\_\{\\varepsilon\}^\{2\}at the population level\. Finite\-sample projector concentration still has a floorΔσ∝\|σ^2−σε2\|/\(d​λmin\)\\Delta\_\{\\sigma\}\\propto\|\\widehat\{\\sigma\}^\{2\}\-\\sigma\_\{\\varepsilon\}^\{2\}\|/\(d\\,\\lambda\_\{\\min\}\)due to the random fluctuation around the biased mean \(Cor\.[C\.10](https://arxiv.org/html/2605.20269#A3.Thmtheorem10)\)\.

Positive identification through the lifted momentGtG\_\{t\}above and the necessity result that follows together yield the following theorem, the foundational result of the paper\.

###### Theorem 2\.2\(Identification under priced probing\)\.

Consider the model of §[2](https://arxiv.org/html/2605.20269#S2)with scaled\-sphere probesut=d​vtu\_\{t\}=\\sqrt\{d\}\\,v\_\{t\},vt∼Unif​\(𝕊d−1\)v\_\{t\}\\sim\\mathrm\{Unif\}\(\\mathbb\{S\}^\{d\-1\}\), and the lifted probe sampleGt=𝒦−1​\(st​ut​ut⊤\)G\_\{t\}=\\mathcal\{K\}^\{\-1\}\(s\_\{t\}u\_\{t\}u\_\{t\}^\{\\top\}\)from \([3](https://arxiv.org/html/2605.20269#S2.E3)\)\.

1. 1\.Identifiability\.Under \(i\) known noise varianceσε2\\sigma\_\{\\varepsilon\}^\{2\}\(δσ=0\\delta\_\{\\sigma\}=0\), \(ii\) bounded state\-noise coupling‖𝔼​\[εt​θt\]‖2≤ϵ×\\\|\\mathbb\{E\}\[\\varepsilon\_\{t\}\\theta\_\{t\}\]\\\|\_\{2\}\\leq\\epsilon\_\{\\times\}, and \(iii\) full\-dimensional probe support, the lifted sample satisfies𝔼​\[Gt∣ℋt−1\]=M~t\\mathbb\{E\}\[G\_\{t\}\\mid\\mathcal\{H\}\_\{t\-1\}\]=\\widetilde\{M\}\_\{t\}exactly \(the biasB~t=−\(δσ/d\)​Id\\widetilde\{B\}\_\{t\}=\-\(\\delta\_\{\\sigma\}/d\)\\,I\_\{d\}from Lemma[C\.6](https://arxiv.org/html/2605.20269#A3.Thmtheorem6)vanishes under \(i\); the state\-noise coupling term vanishes by sphere symmetry, regardless ofϵ×\\epsilon\_\{\\times\}\), and the segment\-averaged estimatorM^k=mk−1​∑t∈𝒯kGt\\widehat\{M\}\_\{k\}=m\_\{k\}^\{\-1\}\\sum\_\{t\\in\\mathcal\{T\}\_\{k\}\}G\_\{t\}satisfies, with probability at least1−δ1\-\\delta, the projector concentration‖P^k−Pk⋆‖op≤Csub​log⁡\(d/δ\)/mk\\\|\\widehat\{P\}\_\{k\}\-P\_\{k\}^\{\\star\}\\\|\_\{\\mathrm\{op\}\}\\leq C\_\{\\mathrm\{sub\}\}\\sqrt\{\\log\(d/\\delta\)/m\_\{k\}\}; in particularU^k=TopEigr⁡\(M^k\)\\widehat\{U\}\_\{k\}=\\operatorname\{TopEig\}\_\{r\}\(\\widehat\{M\}\_\{k\}\)recoversrange​\(Bk⋆\)\\mathrm\{range\}\(B\_\{k\}^\{\\star\}\)at rate1/mk1/\\sqrt\{m\_\{k\}\}\(Proof in Appendix[C\.2](https://arxiv.org/html/2605.20269#A3.SS2)\)\.
2. 2\.Necessity \(unrestricted\-second\-moment scope\)\.Each of \(i\), \(ii\), \(iii\) is individually necessary in the unrestricted second\-moment problem: removing any one yields two distinct conditional second momentsM~t≠M~t′\\widetilde\{M\}\_\{t\}\\neq\\widetilde\{M\}\_\{t\}^\{\\prime\}that generate identical observation laws𝔼​\[st∣ℋt−1,u\]\\mathbb\{E\}\[s\_\{t\}\\mid\\mathcal\{H\}\_\{t\-1\},u\], soM~t\\widetilde\{M\}\_\{t\}is not identifiable from quadratic measurements\. The three constructions are independent \(each counterexample satisfies the remaining two conditions\), so the three form a minimal identifiability set in this class\. Within the rank\-rrLDS class of §[2](https://arxiv.org/html/2605.20269#S2)\(r<dr<d\), rank deficiency partially relaxes \(i\) sinceσε2\\sigma\_\{\\varepsilon\}^\{2\}is identifiable from thed−rd\-rsmallest eigenvalues; \(ii\) and \(iii\) remain needed \(Proof in Appendix[C\.3](https://arxiv.org/html/2605.20269#A3.SS3)\)\.

## 3Algorithm

SPSC \(Alg\.[1](https://arxiv.org/html/2605.20269#alg1)\) alternates two phases:

- •Probe rounds\(t∈𝒯probet\\in\\mathcal\{T\}\_\{\\mathrm\{probe\}\}\): drawut∼Qu\_\{t\}\\sim Q\(the probe distribution from §[2](https://arxiv.org/html/2605.20269#S2); e\.g\. the scaled\-sphere distribution of Remark[2\.1](https://arxiv.org/html/2605.20269#S2.Thmtheorem1)\), observeyty\_\{t\}, accumulateGtG\_\{t\}in the current\-segment estimatorM^t\\widehat\{M\}\_\{t\}, and refreshU^t=TopEigr⁡\(M^t\)\\widehat\{U\}\_\{t\}=\\operatorname\{TopEig\}\_\{r\}\(\\widehat\{M\}\_\{t\}\)\.
- •Exploitation rounds\(t∉𝒯probet\\notin\\mathcal\{T\}\_\{\\mathrm\{probe\}\}\): project each actionx∈𝒜tx\\in\\mathcal\{A\}\_\{t\}tozt​\(x\)=U^t−1⊤​x∈ℝrz\_\{t\}\(x\)=\\widehat\{U\}\_\{t\-1\}^\{\\top\}x\\in\\mathbb\{R\}^\{r\}, maintain a*windowed*ridge\-UCB estimatea^t=V~t−1​b~t\\widehat\{a\}\_\{t\}=\\widetilde\{V\}\_\{t\}^\{\-1\}\\widetilde\{b\}\_\{t\}over a sliding window𝒲t\\mathcal\{W\}\_\{t\}of the lastWWexploitation rounds, and playxt=arg​maxx∈𝒜t⁡\{zt​\(x\)⊤​a^t\+βt\(r,W\)​‖zt​\(x\)‖V~t−1\+γt​‖x‖2\}x\_\{t\}=\\operatorname\*\{arg\\,max\}\_\{x\\in\\mathcal\{A\}\_\{t\}\}\\bigl\\\{z\_\{t\}\(x\)^\{\\top\}\\widehat\{a\}\_\{t\}\+\\beta\_\{t\}^\{\(r,W\)\}\\\|z\_\{t\}\(x\)\\\|\_\{\\widetilde\{V\}\_\{t\}^\{\-1\}\}\+\\gamma\_\{t\}\\\|x\\\|\_\{2\}\\bigr\\\}\.

The confidence radiusβt\(r,W\)=σε​r​log⁡\(1\+W​R𝒜2/\(λ​r\)\)\+2​log⁡\(2​K/δ\)\+λ​Sw\\beta\_\{t\}^\{\(r,W\)\}=\\sigma\_\{\\varepsilon\}\\sqrt\{r\\log\(1\+WR\_\{\\mathcal\{A\}\}^\{2\}/\(\\lambda r\)\)\+2\\log\(2K/\\delta\)\}\+\\sqrt\{\\lambda\}S\_\{w\}scales withr\\sqrt\{r\}, notd\\sqrt\{d\}: this is where the intrinsic\-rank improvement enters\. The correction termγt=Γk\+Vk,t​\(W\)\\gamma\_\{t\}=\\Gamma\_\{k\}\+V\_\{k,t\}\(W\)absorbs subspace\-mismatch errorΓk∝εk:=‖P^k−Pk⋆‖op\\Gamma\_\{k\}\\propto\\varepsilon\_\{k\}:=\\\|\\widehat\{P\}\_\{k\}\-P\_\{k\}^\{\\star\}\\\|\_\{\\mathrm\{op\}\}and local within\-window driftVk,t​\(W\):=∑s,s\+1∈ℐk,t−W≤s<t‖θs\+1−θs‖2V\_\{k,t\}\(W\):=\\sum\_\{s,s\+1\\in\\mathcal\{I\}\_\{k\},\\,t\-W\\leq s<t\}\\\|\\theta\_\{s\+1\}\-\\theta\_\{s\}\\\|\_\{2\}\(formal definitions in App\.[C\.4](https://arxiv.org/html/2605.20269#A3.SS4)\)\. Per\-round cost isO​\(d​r​\|𝒜t\|\+r2\)O\(dr\|\\mathcal\{A\}\_\{t\}\|\+r^\{2\}\)vs\.O​\(d2​\|𝒜t\|\)O\(d^\{2\}\|\\mathcal\{A\}\_\{t\}\|\)for ambient LinUCB, anO​\(d/r\)O\(d/r\)speed\-up in addition to the statistical gain\.

#### Why interleaved probing recovers the subspace\.

A single scalar response is one\-dimensional, but the lifted statisticGt=𝒦−1​\(st​ut​ut⊤\)G\_\{t\}=\\mathcal\{K\}^\{\-1\}\(s\_\{t\}u\_\{t\}u\_\{t\}^\{\\top\}\)in \([3](https://arxiv.org/html/2605.20269#S2.E3)\) targets the conditional second moment𝔼​\[θt​θt⊤∣ℋt−1\]=Bk⋆​𝔼​\[wt​wt⊤∣ℋt−1\]​\(Bk⋆\)⊤\\mathbb\{E\}\[\\theta\_\{t\}\\theta\_\{t\}^\{\\top\}\\mid\\mathcal\{H\}\_\{t\-1\}\]=B\_\{k\}^\{\\star\}\\,\\mathbb\{E\}\[w\_\{t\}w\_\{t\}^\{\\top\}\\mid\\mathcal\{H\}\_\{t\-1\}\]\\,\(B\_\{k\}^\{\\star\}\)^\{\\top\}up to a controlled bias\. AveragingGtG\_\{t\}across probe rounds inside segmentkkisolates this rank\-rrmatrix, whose top\-rreigenspace is exactlyrange​\(Bk⋆\)\\mathrm\{range\}\(B\_\{k\}^\{\\star\}\)once the innovationwtw\_\{t\}excites allrrfactor directions \(Ση,k≻0\\Sigma\_\{\\eta,k\}\\succ 0\)\. The three identifiability conditions of Theorem[2\.2](https://arxiv.org/html/2605.20269#S2.Thmtheorem2)are precisely what makes the isolation valid in the unrestricted\-second\-moment scope; SPSC inherits subspace recovery at rate1/mk1/\\sqrt\{m\_\{k\}\}from Cor\.[C\.10](https://arxiv.org/html/2605.20269#A3.Thmtheorem10), after which the exploitation phase paysr\\sqrt\{r\}rather thand\\sqrt\{d\}because the projection collapses the geometry to dimensionrr\.

Full pseudocode for Alg\.[1](https://arxiv.org/html/2605.20269#alg1)\(oracle boundaries\) is in Appendix[E](https://arxiv.org/html/2605.20269#A5), alongside the adaptive variant described next\.

#### Adaptive variant \(unknown boundaries\)\.

SPSC\-Adaptive removes the oracle\-boundary assumption by detecting segment changes online: it maintains two non\-overlapping rolling\-window estimatorsM^trecent,M^tpast\\widehat\{M\}\_\{t\}^\{\\mathrm\{recent\}\},\\widehat\{M\}\_\{t\}^\{\\mathrm\{past\}\}of the probe\-time second moment and triggers a subspace reset wheneverSt:=‖M^trecent−M^tpast‖opS\_\{t\}:=\\\|\\widehat\{M\}\_\{t\}^\{\\mathrm\{recent\}\}\-\\widehat\{M\}\_\{t\}^\{\\mathrm\{past\}\}\\\|\_\{\\mathrm\{op\}\}exceeds a calibrated thresholdbb\. The threshold is chosen so that, with probability1−δFA1\-\\delta\_\{\\mathrm\{FA\}\}, no false alarm occurs across the horizon, while every true change of sizeΔk≥2​b\\Delta\_\{k\}\\geq 2bis detected within a bounded delayDmaxD\_\{\\max\}\(specified in Appendix[E](https://arxiv.org/html/2605.20269#A5)together with the full pseudocode, tuning, and CUSUM analysis\)\.

## 4Regret guarantees

#### Balanced probe schedule\.

The probe schedule is*balanced*: there is an absolute constanta0a\_\{0\}such that, for every segmentk∈\{1,…,K\}k\\in\\\{1,\\dots,K\\\}and every prefix\-countj∈\{0,1,…,mk\}j\\in\\\{0,1,\\dots,m\_\{k\}\\\}, the number of exploit rounds inEkE\_\{k\}with exactlyjjprobes collected before them is at mosta0​⌈ℓk/mk⌉a\_\{0\}\\lceil\\ell\_\{k\}/m\_\{k\}\\rceil\. \(Uniformly spaced probes satisfy this\.\)

###### Theorem 4\.1\(Costed dynamic regret of Alg\.[1](https://arxiv.org/html/2605.20269#alg1)\)\.

Run Alg\.[1](https://arxiv.org/html/2605.20269#alg1)with oracle segment boundaries\{ℐk\}k=1K\\\{\\mathcal\{I\}\_\{k\}\\\}\_\{k=1\}^\{K\}, scaled\-sphere probes, and a balanced probe schedule\. Under the model of §[2](https://arxiv.org/html/2605.20269#S2), Assumption[C\.2](https://arxiv.org/html/2605.20269#A3.Thmtheorem2), and exact centeringσ^2=σε2\\widehat\{\\sigma\}^\{2\}=\\sigma\_\{\\varepsilon\}^\{2\}, set the per\-segment probe budget tomk=min⁡\{ℓk,⌈c0​ℓk2/3⌉\}m\_\{k\}=\\min\\\{\\ell\_\{k\},\\lceil c\_\{0\}\\ell\_\{k\}^\{2/3\}\\rceil\\\}for an absolute constantc0\>0c\_\{0\}\>0\(chosen as the closed\-form optimum \([13](https://arxiv.org/html/2605.20269#A3.E13)\); segments shorter than the burn\-in thresholdq⋆=O​\(log⁡\(K​d​T/δ\)/λmin2\)q^\{\\star\}=O\(\\log\(KdT/\\delta\)/\\lambda\_\{\\min\}^\{2\}\)are charged trivially\), whereλmin\>0\\lambda\_\{\\min\}\>0is the predictable probe\-timerrth\-eigenvalue lower bound \(Lem\.[C\.1](https://arxiv.org/html/2605.20269#A3.Thmtheorem1)\)\. Then with probability at least1−δ1\-\\deltaand for fixedKK,

DynRegT\(c\)≤𝒪~​\(r​T\)\+𝒪~​\(T2/3\)\+O​\(W​Vin\)\.\\mathrm\{DynReg\}\_\{T\}^\{\(c\)\}\\;\\leq\\;\\widetilde\{\\mathcal\{O\}\}\\\!\\bigl\(r\\sqrt\{T\}\\bigr\)\\;\+\\;\\widetilde\{\\mathcal\{O\}\}\\\!\\bigl\(T^\{2/3\}\\bigr\)\\;\+\\;O\\\!\\bigl\(WV\_\{\\rm in\}\\bigr\)\.\(4\)Including all constants:DynRegT\(c\)≤𝒪~​\(r​K​T\)\+𝒪~​\(A1/3​B2/3​K1/3​T2/3\)\+O​\(R𝒜​W​Vin\)\+𝒪~​\(K2/3​T1/3/λmin2\)\\mathrm\{DynReg\}\_\{T\}^\{\(c\)\}\\leq\\widetilde\{\\mathcal\{O\}\}\(r\\sqrt\{KT\}\)\+\\widetilde\{\\mathcal\{O\}\}\(A^\{1/3\}B^\{2/3\}K^\{1/3\}T^\{2/3\}\)\+O\(R\_\{\\mathcal\{A\}\}WV\_\{\\rm in\}\)\+\\widetilde\{\\mathcal\{O\}\}\(K^\{2/3\}T^\{1/3\}/\\lambda\_\{\\min\}^\{2\}\), withA:=\(R𝒜\+RQ\)​Sw\+cA:=\(R\_\{\\mathcal\{A\}\}\+R\_\{Q\}\)S\_\{w\}\+c,B:=C​R𝒜​Sw​\(1\+R𝒜​W/λ\)​log⁡\(2​K​d​T/δ\)B:=CR\_\{\\mathcal\{A\}\}S\_\{w\}\(1\+R\_\{\\mathcal\{A\}\}\\sqrt\{W/\\lambda\}\)\\sqrt\{\\log\(2KdT/\\delta\)\},RQ:=supu∈supp​\(Q\)‖u‖2R\_\{Q\}:=\\sup\_\{u\\in\\mathrm\{supp\}\(Q\)\}\\\|u\\\|\_\{2\}\(RQ=dR\_\{Q\}=\\sqrt\{d\}for scaled\-sphere;RQ≤R𝒜R\_\{Q\}\\leq R\_\{\\mathcal\{A\}\}if probes lie inside the action set\); the𝒪~​\(K2/3​T1/3/λmin2\)\\widetilde\{\\mathcal\{O\}\}\(K^\{2/3\}T^\{1/3\}/\\lambda\_\{\\min\}^\{2\}\)summand is the burn\-in cost \(lower order than𝒪~​\(T2/3\)\\widetilde\{\\mathcal\{O\}\}\(T^\{2/3\}\)for fixedKK\)\. HereVin:=∑k∑s,s\+1∈ℐk‖θs\+1−θs‖2V\_\{\\rm in\}:=\\sum\_\{k\}\\sum\_\{s,s\+1\\in\\mathcal\{I\}\_\{k\}\}\\\|\\theta\_\{s\+1\}\-\\theta\_\{s\}\\\|\_\{2\}is the within\-segment path variation andWWis the exploitation window \(cumulative onEkE\_\{k\}whenW≥ℓkW\\geq\\ell\_\{k\}\); the bound is most informative whenVinV\_\{\\rm in\}is small\. Proof in §[C\.5](https://arxiv.org/html/2605.20269#A3.SS5)\.

#### Proof sketch\.

Three near\-decoupled error sources drive the bound\. \(i\) Inside the learnedrr\-dimensional subspace, exploitation is a windowed projected ridge\-UCB problem whose self\-normalized analysis yields𝒪~​\(r​T\)\\widetilde\{\\mathcal\{O\}\}\(r\\sqrt\{T\}\)regret, withr\\sqrt\{r\}entering throughβt\(r,W\)\\beta\_\{t\}^\{\(r,W\)\}rather thand\\sqrt\{d\}\. \(ii\) Probe rounds incurO​\(mk\)O\(m\_\{k\}\)regret per segment while delivering subspace errorεk=𝒪~​\(1/mk\)\\varepsilon\_\{k\}=\\widetilde\{\\mathcal\{O\}\}\(1/\\sqrt\{m\_\{k\}\}\)via Davis–Kahan applied toM^k\\widehat\{M\}\_\{k\}\(Cor\.[C\.10](https://arxiv.org/html/2605.20269#A3.Thmtheorem10)\); the exploitation\-side mismatch cost∝ℓk​εk\\propto\\ell\_\{k\}\\,\\varepsilon\_\{k\}balances probe cost atmk∝ℓk2/3m\_\{k\}\\propto\\ell\_\{k\}^\{2/3\}, summing to𝒪~​\(T2/3\)\\widetilde\{\\mathcal\{O\}\}\(T^\{2/3\}\)across segments\. \(iii\) Within\-segment drift propagates through the windowed estimator at rate proportional toW​VinWV\_\{\\rm in\}\. Two ingredients make this decomposition rigorous: uniform\-in\-ttcontrol of the time\-varying\-basis subspace errorεk,t=‖P^t−Pk⋆‖op\\varepsilon\_\{k,t\}=\\\|\\widehat\{P\}\_\{t\}\-P\_\{k\}^\{\\star\}\\\|\_\{\\mathrm\{op\}\}via prefix concentration \(Lem\.[C\.17](https://arxiv.org/html/2605.20269#A3.Thmtheorem17)\), and the balanced\-schedule condition that prevents any single segment from being starved of probes\. Detailed accounting, including the burn\-in𝒪~​\(K2/3​T1/3/λmin2\)\\widetilde\{\\mathcal\{O\}\}\(K^\{2/3\}T^\{1/3\}/\\lambda\_\{\\min\}^\{2\}\)summand, is in §[C\.5](https://arxiv.org/html/2605.20269#A3.SS5)\.

###### Corollary 4\.2\(Plug\-in variance\)\.

Estimateσ^2\\widehat\{\\sigma\}^\{2\}fromNNprobe\-round residuals \(Lem\.[C\.11](https://arxiv.org/html/2605.20269#A3.Thmtheorem11)\) and writeδσ:=\|σ^2−σε2\|\\delta\_\{\\sigma\}:=\|\\widehat\{\\sigma\}^\{2\}\-\\sigma\_\{\\varepsilon\}^\{2\}\|\. For scaled\-sphere probes, the biasB~=−\(δσ/d\)​Id\\widetilde\{B\}=\-\(\\delta\_\{\\sigma\}/d\)I\_\{d\}from Lem\.[C\.6](https://arxiv.org/html/2605.20269#A3.Thmtheorem6)is a scaled identity, hence preserves the eigenvectors ofM¯kprobe\\bar\{M\}\_\{k\}^\{\\mathrm\{probe\}\}\. Davis–Kahan applied with the biased mean as reference removes theΔσ\\Delta\_\{\\sigma\}floor at population level, so Theorem[4\.1](https://arxiv.org/html/2605.20269#S4.Thmtheorem1)holds with the displayed bound,λmin\\lambda\_\{\\min\}replaced byλmin−δσ/d\\lambda\_\{\\min\}\-\\delta\_\{\\sigma\}/din the constants\. ChoosingN≳T2/3/d2N\\gtrsim T^\{2/3\}/d^\{2\}yieldsδσ/d≪λmin\\delta\_\{\\sigma\}/d\\ll\\lambda\_\{\\min\}with high probability, so the leading rate is preserved\.

###### Corollary 4\.3\(Within\-segment\-stationary special case\)\.

SupposeVin=0V\_\{\\rm in\}=0, i\.e\. within each segmentℐk\\mathcal\{I\}\_\{k\}the parameter is constant \(θt≡θ\(k\)\\theta\_\{t\}\\equiv\\theta^\{\(k\)\}fort∈ℐkt\\in\\mathcal\{I\}\_\{k\}, withθ\(k\)∈range​\(Bk⋆\)\\theta^\{\(k\)\}\\in\\mathrm\{range\}\(B^\{\\star\}\_\{k\}\)\)\. The non\-degenerate innovation assumption \(Ση,k≻0\\Sigma\_\{\\eta,k\}\\succ 0\) still holds*across*the segment family, so the rank\-rrsubspacerange​\(Bk⋆\)\\mathrm\{range\}\(B^\{\\star\}\_\{k\}\)is well\-defined and identifiable through SPSC’s probe channel\. The bound of Theorem[4\.1](https://arxiv.org/html/2605.20269#S4.Thmtheorem1)reduces to

DynRegT\(c\)≤𝒪~​\(r​T\)\+𝒪~​\(T2/3\)\\mathrm\{DynReg\}\_\{T\}^\{\(c\)\}\\;\\leq\\;\\widetilde\{\\mathcal\{O\}\}\(r\\sqrt\{T\}\)\+\\widetilde\{\\mathcal\{O\}\}\(T^\{2/3\}\)for fixedKK\(suppressing polylog factors\)\. The leading𝒪~​\(r​T\)\\widetilde\{\\mathcal\{O\}\}\(r\\sqrt\{T\}\)term comes from LinUCB on therr\-dimensional projected targetzt⊤​a\(k\)z\_\{t\}^\{\\top\}a^\{\(k\)\}\(this does not require the within\-segment target to itself span anrr\-dimensional set; the projector is what collapses the geometry to dimensionrr, not the trajectory ofθt\\theta\_\{t\}\)\. This is the regime that class\- or cohort\-induced segment shifts approximate empirically\.

#### Scope of the bound\.

Theorem[4\.1](https://arxiv.org/html/2605.20269#S4.Thmtheorem1)analyzes exactly the practical Alg\.[1](https://arxiv.org/html/2605.20269#alg1): probes are interleaved according to a balanced schedule,U^t\\widehat\{U\}\_\{t\}is refreshed online, and exploitation rounds re\-project the windowed history through the current basis\. The time\-varying\-basis subspace errorεk,t=‖P^t−Pk⋆‖op\\varepsilon\_\{k,t\}=\\\|\\widehat\{P\}\_\{t\}\-P\_\{k\}^\{\\star\}\\\|\_\{\\mathrm\{op\}\}is controlled uniformly inttvia a prefix concentration argument \(Lemma[C\.17](https://arxiv.org/html/2605.20269#A3.Thmtheorem17)\)\.

The leading𝒪~​\(r​T\)\\widetilde\{\\mathcal\{O\}\}\(r\\sqrt\{T\}\)term beats the ambient baseline𝒪~​\(d​T\)\\widetilde\{\\mathcal\{O\}\}\(d\\sqrt\{T\}\)wheneverr≪dr\\ll d; the𝒪~​\(T2/3\)\\widetilde\{\\mathcal\{O\}\}\(T^\{2/3\}\)term is the price of acquiring the subspace information online\. The constantBBdepends on the exploitation windowWWasW\\sqrt\{W\}; forWWtreated as a problem parameter \(the setting throughout this paper, consistent withW≤mink⁡ℓkW\\leq\\min\_\{k\}\\ell\_\{k\}onℓk\\ell\_\{k\}\-bounded segments\), this is absorbed into the constants and the𝒪~​\(T2/3\)\\widetilde\{\\mathcal\{O\}\}\(T^\{2/3\}\)rate is preserved\. IfWWis allowed to scale withTT, the second term becomes𝒪~​\(W1/3​T2/3\)\\widetilde\{\\mathcal\{O\}\}\(W^\{1/3\}T^\{2/3\}\)\. Solvingr​T≲T2/3r\\sqrt\{T\}\\lesssim T^\{2/3\}gives a simple rule of thumb: SPSC tends to outperform ambient LinUCB wheneverd−r≳T1/6d\-r\\gtrsim T^\{1/6\}\. The experiments in §[5](https://arxiv.org/html/2605.20269#S5)show a crossover qualitatively consistent with this rule of thumb\.

###### Corollary 4\.4\(Rank\-adaptive guarantee\)\.

If the true rankrris unknown, thresholdingM^k\\widehat\{M\}\_\{k\}atτkrank:=2​RX​log⁡\(2​d/δ\)/mk\\tau\_\{k\}^\{\\rm rank\}:=2R\_\{X\}\\sqrt\{\\log\(2d/\\delta\)/m\_\{k\}\}\(RXR\_\{X\}the lifted\-sample envelope from App\.[C\.2](https://arxiv.org/html/2605.20269#A3.SS2)\) recovers the true rank with probability≥1−δ\\geq 1\-\\deltawhenever the population eigengap exceeds4​τkrank4\\tau\_\{k\}^\{\\rm rank\}, and the bound \([4](https://arxiv.org/html/2605.20269#S4.E4)\) applies unchanged\. Proof in §[C\.6](https://arxiv.org/html/2605.20269#A3.SS6)\.

###### Proposition 4\.5\(Adaptive SPSC\)\.

Suppose every true change satisfiesΔk≥2​b\\Delta\_\{k\}\\geq 2bfor the thresholdbbset in Appendix[C\.7](https://arxiv.org/html/2605.20269#A3.SS7)\. Then with probability at least1−δFA1\-\\delta\_\{\\mathrm\{FA\}\}, SPSC\-Adaptive \(Alg\.[2](https://arxiv.org/html/2605.20269#alg2)\) attains the same leading rate as Theorem[4\.1](https://arxiv.org/html/2605.20269#S4.Thmtheorem1)with an additiveO​\(K​Wdet\)O\(KW\_\{\\mathrm\{det\}\}\)delay overhead\. Proof in Appendix[C\.7](https://arxiv.org/html/2605.20269#A3.SS7)\.

## 5Experiments

We evaluate SPSC and SPSC\-Adaptive on eleven benchmarks: a synthetic phase\-transition grid; UCI/MovieLens \(Covertype, Pendigits, Satimage, MNIST, Fashion\-MNIST, MovieLens\); clinical \(Warfarin, Vancomycin\); the small\-ddpiecewise\-stationary stress test ofRussacet al\.\([2019](https://arxiv.org/html/2605.20269#bib.bib6)\)\(§[5\.4](https://arxiv.org/html/2605.20269#S5.SS4)\); and Open Bandit production logs \(§[5\.5](https://arxiv.org/html/2605.20269#S5.SS5)\)\.111Code:[https://github\.com/HamedKhosravi99/spsc\-code](https://github.com/HamedKhosravi99/spsc-code)\.Baselines: LinUCB\(Abbasi\-Yadkoriet al\.,[2011](https://arxiv.org/html/2605.20269#bib.bib2)\), D\-LinUCB\(Russacet al\.,[2019](https://arxiv.org/html/2605.20269#bib.bib6)\), SW\-LinUCB\(Cheunget al\.,[2019](https://arxiv.org/html/2605.20269#bib.bib5)\), Restart\-LinUCB, LowRank\-Reward, LowOFUL\(Junet al\.,[2019](https://arxiv.org/html/2605.20269#bib.bib3)\), VOFUL,222LowOFUL, VOFUL, and LowRank\-Reward are adaptations of stationary low\-rank methods to our piecewise\-low\-rank setting; see App\.[F](https://arxiv.org/html/2605.20269#A6)for details\.LinTS, SW\-LinTS, and adapted BOSS\(Duonget al\.,[2024](https://arxiv.org/html/2605.20269#bib.bib20)\)/Jedra\(Jedraet al\.,[2024](https://arxiv.org/html/2605.20269#bib.bib16)\); Oracle\-LinUCB \(true subspace\) is an optimistic reference\. Curves are means over≥10\\geq 10seeds with±1\\pm 1SE bands\.

### 5\.1Phase\-transition boundary

Theory predicts a crossover atd−r≍T1/6d\-r\\asymp T^\{1/6\}: SPSC wins above it, ambient LinUCB below\. We verify on a piecewise low\-rank LDS atT=5,000T\{=\}5\{,\}000, sweeping\(d,r\)∈\{5,10,20,30,45,60,80,100\}×\{1,3,5,10,15,20\}\(d,r\)\\in\\\{5,10,20,30,45,60,80,100\\\}\\times\\\{1,3,5,10,15,20\\\}withr<dr\{<\}d\(40 cells\),K=10K\{=\}10,σε=0\.3\\sigma\_\{\\varepsilon\}\{=\}0\.3, spectral radius0\.990\.99,4040actions, probe costc=0\.1c\{=\}0\.1\. Per\-cell mean regrets and verdicts are tabulated in App\.[G](https://arxiv.org/html/2605.20269#A7)\(Table[16](https://arxiv.org/html/2605.20269#A7.T16)\)\.

![Refer to caption](https://arxiv.org/html/2605.20269v1/figures/experiment1_synthetic_phase.png)Figure 1:Phase\-transition boundary\.\(a\)Empirical ratio=1\{=\}1contour \(solid\) closely tracks the theoretical crossoverd−r=T1/6d\-r=T^\{1/6\}\(dashed\); markers indicate SPSC wins \(blue circles\) and LinUCB wins \(red triangles\)\.\(b\)Ratio versusddfor eachrr\(log scale\): empirical ratios \(solid\) match ther/d\\sqrt\{r/d\}rate predicted by Theorem[4\.1](https://arxiv.org/html/2605.20269#S4.Thmtheorem1)\(dotted\)\.SPSC achieves1616–29%29\\%reductions wheneverd≥45d\\geq 45andr≥3r\\geq 3with everyrr\-curve trackingr/d\\sqrt\{r/d\}: use SPSC whend−r≳T1/6d\-r\\gtrsim T^\{1/6\}, and ambient LinUCB otherwise\.

### 5\.2Real\-data multi\-baseline comparison

Six real\-data benchmarks recast as piecewise low\-rank bandits on a\(d,r\)\(d,r\)\-grid: UCICovertype\(K=4K\{=\}4,T=10,000T\{=\}10\{,\}000\);Pendigits,Satimage, pixelizedMNISTandFashion\-MNIST\(random\-projection features\), andMovieLens\-100Kwith genuine user ratings \(allK=10K\{=\}10,T=5,000T\{=\}5\{,\}000, 10 seeds\)\. Segments are class or user\-subset shifts\. The first five have cluster\-induced low\-rank structure; MovieLens is only approximately low\-rank \(rank\-ddSVD features, §[F](https://arxiv.org/html/2605.20269#A6)\) and serves as a robustness stress test\. Table[1](https://arxiv.org/html/2605.20269#S5.T1)reports SPSC vs\. LinUCB and vs\. best non\-oracle competitor on representative cells; per\-cell tables in Appendix[G](https://arxiv.org/html/2605.20269#A7)\.

Table 1:SPSC/LinUCBandSPSC\-Adaptive/Best Competitorratios across six real\-data benchmarks \(10 seeds per cell\)\. Values<1\{<\}1indicate SPSC wins;boldmarks cells where an SPSC variant beats every non\-oracle baseline\. SPSC trails LinUCB atd≈rd\\approx r\(top of each block\) and gains asddgrows relative torr\. Restart\-LinUCB, the closest competitor, is subspace\-oblivious, so its regret is constant along each row\.d=55d\{=\}55d=105d\{=\}105d=200d\{=\}200bestDataset /rrS/LinS/BestS/LinS/BestS/LinS/BestcellratioCovertype,r=10r\{=\}100\.960\.990\.880\.92——\(105,20\)\(105,20\)0\.86Pendigits,r=10r\{=\}100\.760\.770\.650\.73——\(105,10\)\(105,10\)0\.65Satimage,r=10r\{=\}100\.470\.590\.400\.58——\(105,10\)\(105,10\)0\.40MNIST,r=10r\{=\}100\.840\.860\.740\.880\.73/0\.980\.98\(105,20\)\(105,20\)0\.74Fashion\-MNIST,r=10r\{=\}100\.880\.900\.730\.880\.67/0\.990\.99\(105,20\)\(105,20\)0\.71MovieLens,r=10r\{=\}101\.001\.000\.970\.970\.92/0\.930\.93\(200,5\)\(200,5\)0\.92At\(d=105,r=10\)\(d\{=\}105,r\{=\}10\), SPSC\-Adaptive beats LinUCB by−47%\-47\\%on Pendigits \(operating\-regime grid in Fig\.[2](https://arxiv.org/html/2605.20269#A7.F2), App\.[G](https://arxiv.org/html/2605.20269#A7)\) and−68%\-68\\%on Satimage \(closest competitor VOFUL is\+112%\+112\\%above SPSC\-Adaptive; per\-cell results in Table[10](https://arxiv.org/html/2605.20269#A7.T10), App\.[G](https://arxiv.org/html/2605.20269#A7)\); at\(d=105,r=20\)\(d\{=\}105,r\{=\}20\)on Covertype it beats Restart\-LinUCB by−15%\-15\\%\. Non\-low\-rank baselines are by constructionrr\-insensitive\.

### 5\.3Clinical benchmarks: Warfarin and Vancomycin dosing

#### Warfarin\.

Warfarin dosing depends on demographics, genotype \(VKORC1, CYP2C9\), and clinical indicators\(Consortium,[2009](https://arxiv.org/html/2605.20269#bib.bib1)\)\. We calibrate to the IWPC cohort \(∼5,700\{\\sim\}5\{,\}700patients,d=93d\{=\}93,K=8K\{=\}8segments,T=5,000T\{=\}5\{,\}000, 10 seeds; reward==negative deviation from therapeutic dose\)\. Table[2](https://arxiv.org/html/2605.20269#S5.T2)\(r=3r\{=\}3\): SPSC\-Adaptive cuts regret by67\.3%67\.3\\%vs\. LinUCB; full per\-rank tables in Table[14](https://arxiv.org/html/2605.20269#A7.T14)\(App\.[G](https://arxiv.org/html/2605.20269#A7)\); random\-subspace ablation in App\.[J](https://arxiv.org/html/2605.20269#A10)\.

#### Vancomycin\.

With the AUC\-targetedRybaket al\.\([2020](https://arxiv.org/html/2605.20269#bib.bib18)\)protocol \(Cockcroft–GaultCrCl→CLvanco=0\.04​CrCl\\mathrm\{CrCl\}\\to\\mathrm\{CL\}\_\{\\mathrm\{vanco\}\}=0\.04\\,\\mathrm\{CrCl\}, daily dose atAUC24=500\\mathrm\{AUC\}\_\{24\}\{=\}500;d=93d\{=\}93,K=8K\{=\}8,T=5,000T\{=\}5\{,\}000, 10 seeds\), Table[3](https://arxiv.org/html/2605.20269#S5.T3)sweepsr∈\{1,2,3,5,10\}r\\in\\\{1,2,3,5,10\\\}: SPSC\-Adaptive cuts regret by36\.4%36\.4\\%atr=1r\{=\}1and14\.514\.5–25\.7%25\.7\\%forr∈\{2,3,5,10\}r\\in\\\{2,3,5,10\\\}vs\. LinUCB, beating every non\-oracle baseline at every rank\. Per\-rank tables in Appendix[L](https://arxiv.org/html/2605.20269#A12)\.

Table 2:Warfarin\(representative cellr=3r\{=\}3, mean±\\pmSE, 10 seeds\)\. SPSC\-Adaptive cuts regret by67\.3%67\.3\\%vs\. LinUCB\. Full per\-rank tables in Appendix[G](https://arxiv.org/html/2605.20269#A7)\.MethodCosted regretvs\. LinUCBOracle LinUCB177±4177\\pm 4−91\.2%\-91\.2\\%SPSC Alg\. 1 \(ours\)1372±331372\\pm 33−31\.6%\-31\.6\\%SPSC\-Adaptive \(ours\)𝟔𝟓𝟕±𝟑𝟗\\mathbf\{657\\pm 39\}−67\.3%\\mathbf\{\-67\.3\\%\}LowOFUL683±97683\\pm 97−66\.0%\-66\.0\\%VOFUL779±93779\\pm 93−61\.2%\-61\.2\\%LowRank\-Reward1056±401056\\pm 40−47\.4%\-47\.4\\%SW\-LinUCB2096±182096\\pm 18\+4\.5%\+4\.5\\%LinUCB2006±172006\\pm 17—Table 3:Vancomycin\(mean±\\pmSE, 10 seeds\): SPSC\-Adaptive control regret across range ofrrvs\. LinUCB and the best non\-oracle baseline\. Full tables in Appendix[L](https://arxiv.org/html/2605.20269#A12)\.rrSPSC\-Adaptivevs\. LinUCBvs\. best comp\.1525\.3±45\.8\\mathbf\{525\.3\\pm 45\.8\}−36\.4%\-36\.4\\%−35\.1%\-35\.1\\%2613\.6±33\.1\\mathbf\{613\.6\\pm 33\.1\}−25\.7%\-25\.7\\%−17\.1%\-17\.1\\%3640\.3±33\.0\\mathbf\{640\.3\\pm 33\.0\}−22\.4%\-22\.4\\%−10\.1%\-10\.1\\%5665\.9±27\.2\\mathbf\{665\.9\\pm 27\.2\}−19\.3%\-19\.3\\%−12\.7%\-12\.7\\%10705\.6±19\.5\\mathbf\{705\.6\\pm 19\.5\}−14\.5%\-14\.5\\%−7\.0%\\phantom\{\-\}\-7\.0\\%

### 5\.4Small\-ddpiecewise\-stationary stress test

On the small\-ddstress test ofRussacet al\.\([2019](https://arxiv.org/html/2605.20269#bib.bib6)\)\(d=2d\{=\}2,r=1r\{=\}1,K=4K\{=\}4,T=6,000T\{=\}6\{,\}000, 50 arms, 30 seeds\), SPSC reduces regret by−46\.5%\\mathbf\{\-46\.5\\%\}vs\. D\-LinUCB,−34\.8%\\mathbf\{\-34\.8\\%\}vs\. SW\-LinUCB, and−52\.0%\\mathbf\{\-52\.0\\%\}vs\. stationary OFUL \(itself\+11\.5%\+11\.5\\%above D\-LinUCB here\)\. Full table in Appendix[I](https://arxiv.org/html/2605.20269#A9)\.

### 5\.5Real exploration logs: Open Bandit Pipeline \(ZOZO\)

The Open Bandit Dataset\(Saitoet al\.,[2021](https://arxiv.org/html/2605.20269#bib.bib17)\)ships production exploration logs \(random\-policy ZOZOTOWN slice,T=5,000T\{=\}5\{,\}000,K=10K\{=\}10, 10 seeds\); only approximately low\-rank, so this is a*robustness*stress test rather than a setting where the rank\-rrassumption holds exactly\. Atd=55d\{=\}55,r=5r\{=\}5, SPSC reaches𝟖𝟑±𝟐\\mathbf\{83\\pm 2\}vs\. LinUCB’s102±1102\\pm 1\(−18\.8%\-18\.8\\%\); SPSC\-Adaptive−10\.9%\-10\.9\\%\. SPSC neither breaks nor over\-claims on weakly\-low\-rank production data\. Per\-cell results in Table[15](https://arxiv.org/html/2605.20269#A7.T15)\(App\.[G](https://arxiv.org/html/2605.20269#A7)\)\.

### 5\.6Comparison with stationary low\-rank methods \(oracle restarts\)

For a best\-effort comparison with stationary low\-rank methods, we adapt BOSS\(Duonget al\.,[2024](https://arxiv.org/html/2605.20269#bib.bib20)\)and Jedra\(Jedraet al\.,[2024](https://arxiv.org/html/2605.20269#bib.bib16)\)by restarting at every true segment boundary, an oracle advantage we do not give SPSC \(setup in Appendix[K](https://arxiv.org/html/2605.20269#A11)\)\. Table[4](https://arxiv.org/html/2605.20269#S5.T4): SPSC wins all eight cells by5\.85\.8–19\.9%19\.9\\%, with the lead largest at smalldd\(−16\.3\-16\.3to−19\.9%\-19\.9\\%atd=55d\{=\}55\) and narrowing to5\.85\.8–8\.0%8\.0\\%atd=200d\{=\}200\. SPSC\-Adaptive \(no oracle\) also beats both on every cell\.

Table 4:Adapted stationary low\-rank methods on a\(d,r\)\(d,r\)\-grid\. Costed regret \(mean±\\pmSE, 10 seeds,T=5,000T\{=\}5\{,\}000,K=10K\{=\}10\)\. BOSS/Jedra restart at*oracle*segment boundaries; SPSC\-Adaptive detects them online\. SPSC variants win every cell\.ddrrSPSC Alg\. 1SPSC\-AdaptiveBOSS \(oracle\)Jedra \(oracle\)SPSC vs\. best comp\.555𝟑𝟐𝟑±𝟏𝟎\\mathbf\{323\\pm 10\}342±15342\\pm 15399±17399\\pm 17386±18386\\pm 18−16\.3%\-16\.3\\%5510𝟒𝟕𝟏±𝟏𝟎\\mathbf\{471\\pm 10\}507±13507\\pm 13588±27588\\pm 27602±24602\\pm 24−19\.9%\-19\.9\\%1055𝟐𝟔𝟒±𝟗\\mathbf\{264\\pm 9\}274±10274\\pm 10300±14300\\pm 14299±13299\\pm 13−11\.7%\-11\.7\\%10510𝟑𝟕𝟕±𝟏𝟓\\mathbf\{377\\pm 15\}401±14401\\pm 14423±18423\\pm 18429±14429\\pm 14−10\.9%\-10\.9\\%10520𝟓𝟕𝟖±𝟏𝟐\\mathbf\{578\\pm 12\}608±14608\\pm 14654±17654\\pm 17654±14654\\pm 14−11\.6%\-11\.6\\%2005𝟐𝟎𝟖±𝟓\\mathbf\{208\\pm 5\}218±6218\\pm 6236±9236\\pm 9226±9226\\pm 9−8\.0%\\phantom\{\-\}\-8\.0\\%20010𝟐𝟕𝟕±𝟏𝟎\\mathbf\{277\\pm 10\}292±12292\\pm 12294±11294\\pm 11305±15305\\pm 15−5\.8%\\phantom\{\-\}\-5\.8\\%20020𝟒𝟒𝟐±𝟏𝟑\\mathbf\{442\\pm 13\}452±11452\\pm 11473±16473\\pm 16489±18489\\pm 18−6\.6%\\phantom\{\-\}\-6\.6\\%#### Robustness of SPSC\-Adaptive\.

Detailed comparison under correct vs\. misspecified oracle boundaries is in Appendix[M](https://arxiv.org/html/2605.20269#A13): SPSC\-Adaptive is robust to false\-alarm boundaries, while Alg\.[1](https://arxiv.org/html/2605.20269#alg1)degrades monotonically as the oracle is corrupted\.

### 5\.7Rank misspecification, probe\-rate sensitivity, and take\-away

Rank misspecification\.The true rankr⋆r^\{\\star\}is rarely known in advance, so we evaluate SPSC’s robustness to rank mis\-specification on Covertype \(d=155d\{=\}155,r⋆=10r^\{\\star\}\{=\}10; App\.[H\.2](https://arxiv.org/html/2605.20269#A8.SS2)\): sweeping over nine grid pointsr∈\{1,3,5,10,15,20,30,50,80\}r\\in\\\{1,3,5,10,15,20,30,50,80\\\}gives a U\-shaped curve \(under:\+33%\+33\\%atr=1r\{=\}1; sweet spotr=30r\{=\}30,−10%\-10\\%\); SPSC beats LinUCB acrossr∈\[15,50\]r\\in\[15,50\], so mild overestimation is safe\.Probe rate\.The probe periodmmtrades exploration cost against subspace\-estimation accuracy, so the optimalmmdepends on segment length; we test whether the theoretical optimummk⋆∝ℓk2/3m\_\{k\}^\{\\star\}\\propto\\ell\_\{k\}^\{2/3\}holds empirically \(App\.[H\.1](https://arxiv.org/html/2605.20269#A8.SS1)\)\. On the synthetic reference setting \(d=4d\{=\}4,r=1r\{=\}1\), the probe\-period sweep\{5,10,20,30,50,100,300\}\\\{5,10,20,30,50,100,300\\\}attains its optimum near2020–3030, matching the prediction\.Additional datasets\.To verify that the per\-cell advantage generalizes beyond a single benchmark, the full\(d,r\)\(d,r\)\-grid is reported in Appendix[G](https://arxiv.org/html/2605.20269#A7): SPSC wins every cell atd≥105d\\geq 105, peaking at\(d,r\)=\(105,20\)\(d,r\)\{=\}\(105,20\)\.Sensitivity & dynamics\.To assess whether any of the four working assumptions \(known variance, exact rank, sub\-unit spectral radius, regular change points\) is critical to SPSC’s performance, we ablate each separately\. Large\-scale assumption sweeps \(App\.[H\.4](https://arxiv.org/html/2605.20269#A8.SS4)\) confirm SPSC tracks Oracle within a constant factor through variance misspecification, approximate\-rank perturbation \(ϵk⟂\\epsilon\_\{k\}^\{\\perp\}up to0\.40\.4\), and spectral radius up toρ=0\.95\\rho\{=\}0\.95; SPSC remains the best non\-Oracle method atρ=0\.99\\rho\{=\}0\.99\. Subspace error tracks the predicted1/m1/\\sqrt\{m\}rate \(App\.[H\.5](https://arxiv.org/html/2605.20269#A8.SS5)\); noise/change\-point\-frequency/drift\-speed sweeps \(App\.[H\.6](https://arxiv.org/html/2605.20269#A8.SS6)\) confirm the same trends\.Take\-away\.Across the eleven benchmarks, SPSC deliversr/d\\sqrt\{r/d\}intrinsic\-rank savings wheneverd−r≳T1/6d\-r\\gtrsim T^\{1/6\}and does not catastrophically fail outside that regime\.

## 6Conclusion

Sequential decision problems in recommendation, clinical dosing, and adaptive experimentation share two features: rewards live on a low\-rank subspace of rankr≪dr\\ll d, and that subspace shifts at unknown change points\. Stationary low\-rank, nonstationary, and cost\-aware bandits each cover one piece; none recover a changing subspace under priced single\-play scalar feedback\. We close this gap: three probe\-side conditions, known noise variance, bounded state\-noise coupling, and full\-dimensional probe support, are each individually necessary \(in the unrestricted\-second\-moment scope\) and jointly sufficient for subspace recovery from quadratic functionals of scalar rewards \(Theorem[2\.2](https://arxiv.org/html/2605.20269#S2.Thmtheorem2)\)\. Based on this, we propose SPSC, which interleaves probing with windowed projected ridge\-UCB in the learnedrr\-dimensional subspace and achieves costed dynamic regret𝒪~​\(r​T\)\+𝒪~​\(T2/3\)\+O​\(W​Vin\)\\widetilde\{\\mathcal\{O\}\}\(r\\sqrt\{T\}\)\+\\widetilde\{\\mathcal\{O\}\}\(T^\{2/3\}\)\+O\(WV\_\{\\rm in\}\), replacing the ambientd​Td\\sqrt\{T\}rate with the intrinsicrr\(Theorem[4\.1](https://arxiv.org/html/2605.20269#S4.Thmtheorem1)\); a CUSUM adaptive variant attains the same rate without oracle change points \(Proposition[4\.5](https://arxiv.org/html/2605.20269#S4.Thmtheorem5)\)\. On eleven benchmarks across synthetic, UCI, clinical, and production data, SPSC reduces regret wheneverd−r≳T1/6d\-r\\gtrsim T^\{1/6\}, a crossover consistent with theory\. Limitations and extensions are discussed in App\.[A](https://arxiv.org/html/2605.20269#A1)\.

## References

- A new look at dynamic regret for non\-stationary stochastic bandits\.Journal of Machine Learning Research24\(288\),pp\. 1–37\.Cited by:[Table 5](https://arxiv.org/html/2605.20269#A2.T5.5.5.3.1.1),[§1](https://arxiv.org/html/2605.20269#S1.SS0.SSS0.Px4.p1.2)\.
- Y\. Abbasi\-Yadkori, D\. Pál, and C\. Szepesvári \(2011\)Improved algorithms for linear stochastic bandits\.Advances in neural information processing systems24\.Cited by:[Table 7](https://arxiv.org/html/2605.20269#A2.T7.1.1.3.1.1),[Assumption C\.2](https://arxiv.org/html/2605.20269#A3.Thmtheorem2.p1.7.6),[Lemma C\.3](https://arxiv.org/html/2605.20269#A3.Thmtheorem3.p1.8.1),[Table 18](https://arxiv.org/html/2605.20269#A9.T18.18.14.4),[§5](https://arxiv.org/html/2605.20269#S5.p1.3)\.
- R\. Bhatia \(2013\)Matrix analysis\.Springer Science & Business Media\.Cited by:[§C\.2](https://arxiv.org/html/2605.20269#A3.SS2.10.p1.9)\.
- W\. C\. Cheung, D\. Simchi\-Levi, and R\. Zhu \(2019\)Learning to optimize under non\-stationarity\.InThe 22nd International Conference on Artificial Intelligence and Statistics,pp\. 1079–1087\.Cited by:[Table 18](https://arxiv.org/html/2605.20269#A9.T18.15.11.4),[§1](https://arxiv.org/html/2605.20269#S1.SS0.SSS0.Px1.p1.6),[§1](https://arxiv.org/html/2605.20269#S1.SS0.SSS0.Px4.p1.2),[§5](https://arxiv.org/html/2605.20269#S5.p1.3)\.
- I\. W\. P\. Consortium \(2009\)Estimation of the warfarin dose with clinical and pharmacogenetic data\.New England Journal of Medicine360\(8\),pp\. 753–764\.Cited by:[§1](https://arxiv.org/html/2605.20269#S1.p1.2),[§5\.3](https://arxiv.org/html/2605.20269#S5.SS3.SSS0.Px1.p1.7)\.
- T\. Duong, Z\. Wang, and C\. Zhang \(2024\)Beyond task diversity: provable representation transfer for sequential multitask linear bandits\.Advances in Neural Information Processing Systems37,pp\. 37791–37822\.Cited by:[Appendix K](https://arxiv.org/html/2605.20269#A11.p1.4),[Table 7](https://arxiv.org/html/2605.20269#A2.T7.6.6.3.1.1),[§1](https://arxiv.org/html/2605.20269#S1.SS0.SSS0.Px4.p1.2),[§5\.6](https://arxiv.org/html/2605.20269#S5.SS6.p1.9),[§5](https://arxiv.org/html/2605.20269#S5.p1.3)\.
- E\. C\. Elumar, C\. Tekin, and O\. Yağan \(2024\)Multi\-armed bandits with costly probes\.IEEE Transactions on Information Theory71\(1\),pp\. 618–643\.Cited by:[§1](https://arxiv.org/html/2605.20269#S1.SS0.SSS0.Px4.p1.2)\.
- D\. Feijer, H\. Abdollahpouri, S\. Gupta, A\. Clare, Y\. Wen, T\. Wasson, M\. Dimakopoulou, Z\. Nazari, K\. Kretschman, and M\. Lalmas \(2025\)Calibrated recommendations with contextual bandits\.arXiv preprint arXiv:2509\.05460\.Cited by:[§1](https://arxiv.org/html/2605.20269#S1.p1.2)\.
- Y\. Hou, V\. Y\. Tan, and Z\. Zhong \(2024\)Almost minimax optimal best arm identification in piecewise stationary linear bandits\.Advances in Neural Information Processing Systems37,pp\. 128967–129041\.Cited by:[Table 5](https://arxiv.org/html/2605.20269#A2.T5.5.9.1.1.1),[§1](https://arxiv.org/html/2605.20269#S1.SS0.SSS0.Px4.p1.2)\.
- K\. Jang, C\. Zhang, and K\. Jun \(2024\)Efficient low\-rank matrix estimation, experimental design, and arm\-set\-dependent low\-rank bandits\.InProceedings of the 41st International Conference on Machine Learning,pp\. 21329–21372\.Cited by:[Table 5](https://arxiv.org/html/2605.20269#A2.T5.5.7.1.1.1),[§1](https://arxiv.org/html/2605.20269#S1.SS0.SSS0.Px1.p1.6),[§1](https://arxiv.org/html/2605.20269#S1.SS0.SSS0.Px4.p1.2)\.
- Y\. Jedra, W\. Réveillard, S\. Stojanovic, and A\. Proutiere \(2024\)Low\-rank bandits via tight two\-to\-infinity singular subspace recovery\.InInternational Conference on Machine Learning,pp\. 21430–21485\.Cited by:[Appendix K](https://arxiv.org/html/2605.20269#A11.p1.4),[Table 5](https://arxiv.org/html/2605.20269#A2.T5.3.3.2.1.1),[Table 7](https://arxiv.org/html/2605.20269#A2.T7.7.7.3.1.1),[§1](https://arxiv.org/html/2605.20269#S1.SS0.SSS0.Px1.p1.6),[§1](https://arxiv.org/html/2605.20269#S1.SS0.SSS0.Px4.p1.2),[§5\.6](https://arxiv.org/html/2605.20269#S5.SS6.p1.9),[§5](https://arxiv.org/html/2605.20269#S5.p1.3)\.
- K\. Jun, R\. Willett, S\. Wright, and R\. Nowak \(2019\)Bilinear bandits with low\-rank structure\.InInternational Conference on Machine Learning,pp\. 3163–3172\.Cited by:[Table 7](https://arxiv.org/html/2605.20269#A2.T7.3.3.4.1.1),[Appendix F](https://arxiv.org/html/2605.20269#A6.SS0.SSS0.Px7.p1.10),[§1](https://arxiv.org/html/2605.20269#S1.SS0.SSS0.Px1.p1.6),[§1](https://arxiv.org/html/2605.20269#S1.SS0.SSS0.Px4.p1.2),[§5](https://arxiv.org/html/2605.20269#S5.p1.3)\.
- Y\. Kang, C\. Hsieh, and T\. C\. M\. Lee \(2022\)Efficient frameworks for generalized low\-rank matrix bandit problems\.Advances in Neural Information Processing Systems35,pp\. 19971–19983\.Cited by:[Table 5](https://arxiv.org/html/2605.20269#A2.T5.2.2.2.1.1),[§1](https://arxiv.org/html/2605.20269#S1.SS0.SSS0.Px4.p1.2)\.
- J\. Komiyama, E\. Fouché, and J\. Honda \(2024\)Finite\-time analysis of globally nonstationary multi\-armed bandits\.Journal of Machine Learning Research25\(112\),pp\. 1–56\.Cited by:[Table 5](https://arxiv.org/html/2605.20269#A2.T5.5.8.1.1.1)\.
- B\. Laurent and P\. Massart \(2000\)Adaptive estimation of a quadratic functional by model selection\.Annals of statistics,pp\. 1302–1338\.Cited by:[Appendix D](https://arxiv.org/html/2605.20269#A4.p3.12)\.
- P\. Liu, Y\. Li, and J\. Li \(2025\)Change surface regression for nonlinear subgroup identification with application to warfarin pharmacogenomics data\.Biometrics81\(1\),pp\. ujae169\.Cited by:[§1](https://arxiv.org/html/2605.20269#S1.p1.2)\.
- Y\. Lu, A\. Meisami, and A\. Tewari \(2021\)Low\-rank generalized linear bandit problems\.InInternational conference on artificial intelligence and statistics,pp\. 460–468\.Cited by:[Table 7](https://arxiv.org/html/2605.20269#A2.T7.5.5.4.1.1),[Appendix F](https://arxiv.org/html/2605.20269#A6.SS0.SSS0.Px7.p1.10),[§1](https://arxiv.org/html/2605.20269#S1.SS0.SSS0.Px4.p1.2)\.
- Y\. Russac, C\. Vernade, and O\. Cappé \(2019\)Weighted linear bandits for non\-stationary environments\.Advances in Neural Information Processing Systems32\.Cited by:[Figure 11](https://arxiv.org/html/2605.20269#A9.F11),[Figure 11](https://arxiv.org/html/2605.20269#A9.F11.10.5),[Table 18](https://arxiv.org/html/2605.20269#A9.T18),[Table 18](https://arxiv.org/html/2605.20269#A9.T18.12.8.3),[Table 18](https://arxiv.org/html/2605.20269#A9.T18.4.2),[Appendix I](https://arxiv.org/html/2605.20269#A9.p1.10),[§1](https://arxiv.org/html/2605.20269#S1.SS0.SSS0.Px1.p1.6),[§1](https://arxiv.org/html/2605.20269#S1.SS0.SSS0.Px3.p1.10),[§1](https://arxiv.org/html/2605.20269#S1.SS0.SSS0.Px4.p1.2),[§5\.4](https://arxiv.org/html/2605.20269#S5.SS4.p1.9),[§5](https://arxiv.org/html/2605.20269#S5.p1.3)\.
- M\. J\. Rybak, J\. Le, T\. P\. Lodise, D\. P\. Levine, J\. S\. Bradley, C\. Liu, B\. A\. Mueller, M\. P\. Pai, A\. Wong\-Beringer, J\. C\. Rotschafer,et al\.\(2020\)Therapeutic monitoring of vancomycin for serious methicillin\-resistant staphylococcus aureus infections: a revised consensus guideline and review by the american society of health\-system pharmacists, the infectious diseases society of america, the pediatric infectious diseases society, and the society of infectious diseases pharmacists\.American journal of health\-system pharmacy77\(11\),pp\. 835–864\.Cited by:[§5\.3](https://arxiv.org/html/2605.20269#S5.SS3.SSS0.Px2.p1.11)\.
- Y\. Saito, S\. Aihara, M\. Matsutani, and Y\. Narita \(2021\)Open bandit dataset and pipeline: towards realistic and reproducible off\-policy evaluation\.InThirty\-fifth Conference on Neural Information Processing Systems Datasets and Benchmarks Track \(Round 2\),Cited by:[§1](https://arxiv.org/html/2605.20269#S1.p1.2),[§5\.5](https://arxiv.org/html/2605.20269#S5.SS5.p1.9)\.
- Y\. Seldin, P\. Bartlett, K\. Crammer, and Y\. Abbasi\-Yadkori \(2014\)Prediction with limited advice and multiarmed bandits with paid observations\.InInternational Conference on Machine Learning,pp\. 280–287\.Cited by:[§1](https://arxiv.org/html/2605.20269#S1.SS0.SSS0.Px4.p1.2)\.
- S\. Stojanovic, Y\. Jedra, and A\. Proutiere \(2023\)Spectral entry\-wise matrix estimation for low\-rank reinforcement learning\.Advances in Neural Information Processing Systems36,pp\. 77056–77070\.Cited by:[Table 5](https://arxiv.org/html/2605.20269#A2.T5.5.6.1.1.1),[§1](https://arxiv.org/html/2605.20269#S1.SS0.SSS0.Px4.p1.2)\.
- J\. A\. Tropp \(2011\)Freedman’s inequality for matrix martingales\.Electronic Communications in Probability16,pp\. 262–270\.Cited by:[Theorem C\.8](https://arxiv.org/html/2605.20269#A3.Thmtheorem8.p1.10.10)\.
- A\. D\. Tucker, C\. Biddulph, C\. Wang, and T\. Joachims \(2023\)Bandits with costly reward observations\.InUncertainty in Artificial Intelligence,pp\. 2147–2156\.Cited by:[§1](https://arxiv.org/html/2605.20269#S1.SS0.SSS0.Px4.p1.2)\.

## Appendix: Table of Contents

A\.[Limitations and extensions](https://arxiv.org/html/2605.20269#A1)\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.[p\.A](https://arxiv.org/html/2605.20269#A1)

B\.[Comparison with prior work](https://arxiv.org/html/2605.20269#A2)\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.[p\.B](https://arxiv.org/html/2605.20269#A2)

C\.[Proofs](https://arxiv.org/html/2605.20269#A3)\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.[p\.C](https://arxiv.org/html/2605.20269#A3)

C\.1[Preliminaries and notation](https://arxiv.org/html/2605.20269#A3.SS1)\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.[p\.C\.1](https://arxiv.org/html/2605.20269#A3.SS1)

C\.2[Concentration of the lifted probe moment](https://arxiv.org/html/2605.20269#A3.SS2)\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.[p\.C\.2](https://arxiv.org/html/2605.20269#A3.SS2)

C\.3[Necessity of the probe\-side conditions](https://arxiv.org/html/2605.20269#A3.SS3)\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.[p\.C\.3](https://arxiv.org/html/2605.20269#A3.SS3)

C\.4[Lemmas for the interleaved analysis](https://arxiv.org/html/2605.20269#A3.SS4)\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.[p\.C\.4](https://arxiv.org/html/2605.20269#A3.SS4)

C\.5[Proof of Theorem4\.1\(costed dynamic regret of Alg\.1\)](https://arxiv.org/html/2605.20269#A3.SS5)\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.[p\.C\.5](https://arxiv.org/html/2605.20269#A3.SS5)

C\.6[Proof of Corollary4\.4\(rank\-adaptive\)](https://arxiv.org/html/2605.20269#A3.SS6)\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.[p\.C\.6](https://arxiv.org/html/2605.20269#A3.SS6)

C\.7[Proof of Proposition4\.5\(SPSC\-Adaptive\)](https://arxiv.org/html/2605.20269#A3.SS7)\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.[p\.C\.7](https://arxiv.org/html/2605.20269#A3.SS7)

D\.[Probe distributions: scaled sphere and Gaussian truncation](https://arxiv.org/html/2605.20269#A4)\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.[p\.D](https://arxiv.org/html/2605.20269#A4)

E\.[Algorithms: pseudocode and adaptive variant](https://arxiv.org/html/2605.20269#A5)\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.[p\.E](https://arxiv.org/html/2605.20269#A5)

F\.[Experimental setup](https://arxiv.org/html/2605.20269#A6)\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.[p\.F](https://arxiv.org/html/2605.20269#A6)

G\.[Per\-cell tables: every dataset, every cell](https://arxiv.org/html/2605.20269#A7)\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.[p\.G](https://arxiv.org/html/2605.20269#A7)

H\.[Sensitivity and robustness studies](https://arxiv.org/html/2605.20269#A8)\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.[p\.H](https://arxiv.org/html/2605.20269#A8)

I\.[Nonstationary baselines \(small\-ddstress test\)](https://arxiv.org/html/2605.20269#A9)\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.[p\.I](https://arxiv.org/html/2605.20269#A9)

J\.[Warfarin: random\-subspace ablation](https://arxiv.org/html/2605.20269#A10)\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.[p\.J](https://arxiv.org/html/2605.20269#A10)

K\.[BOSS/Jedra adaptation](https://arxiv.org/html/2605.20269#A11)\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.[p\.K](https://arxiv.org/html/2605.20269#A11)

L\.[Vancomycin: full per\-rank tables](https://arxiv.org/html/2605.20269#A12)\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.[p\.L](https://arxiv.org/html/2605.20269#A12)

M\.[When the adaptive variant wins](https://arxiv.org/html/2605.20269#A13)\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.[p\.M](https://arxiv.org/html/2605.20269#A13)

## Appendix ALimitations and extensions

Three boundaries of the present results are worth flagging\. The identification theorem is tight in the unrestricted\-second\-moment scope; restricting to specific noise families could relax one or more of the three conditions but would also forfeit the converse half\. TheO​\(W​Vin\)O\(WV\_\{\\rm in\}\)term in the regret bound is informative only when within\-segment path variation is small, and the CUSUM\-style detector in SPSC\-Adaptive trades detection delay for false\-alarm control, so very frequent change points require the sliding\-window estimator to be re\-tuned\. Two natural extensions stand out\. Bilinear or tensorized factor models with side information onwtw\_\{t\}should inherit the probe–exploit decomposition with the segment\-wise𝒪~​\(T2/3\)\\widetilde\{\\mathcal\{O\}\}\(T^\{2/3\}\)identification cost replaced by the corresponding higher\-order moment\-estimation rate\. Heterogeneous\-rank segments, whererritself shifts at change points, strictly generalize Cor\.[4\.4](https://arxiv.org/html/2605.20269#S4.Thmtheorem4), which covers a single rank\-thresholding pass and assumes a common rank across segments\.

## Appendix BComparison with prior work

This appendix positions SPSC against published work in low\-rank bandits, nonstationary bandits, and active\-query bandits via three tables: Table[5](https://arxiv.org/html/2605.20269#A2.T5)\(head\-to\-head with seven recent works on regret form, change\-point adaptation, and probing budget\), Table[6](https://arxiv.org/html/2605.20269#A2.T6)\(compact positioning of SPSC’s combined setting against the three closest*problem classes*\), and Table[7](https://arxiv.org/html/2605.20269#A2.T7)\(regret\-rate comparison with five published baselines that appear in our experiments\)\. The take\-away is that the existing literature splits along three axes \(low\-rank, nonstationary, costly probing\) and no prior method addresses all three; SPSC is the first to do so with a self\-contained identification chain that turns rank\-one scalar rewards into matrix\-valued evidence\.

Table 5:Comparison with related literature\. “Prob\.” indicates a probabilistic regret bound; “CP?” indicates change\-point adaptation\.ReferenceVenue/YearRegret / TheoryProb\.CP?Differencevs\. oursKanget al\.\[[2022](https://arxiv.org/html/2605.20269#bib.bib13)\]NeurIPS’22𝒪~​\(\(d1\+d2\)​M​r​T\)\\widetilde\{\\mathcal\{O\}\}\\\!\\left\(\\sqrt\{\(d\_\{1\}\+d\_\{2\}\)MrT\}\\right\)✓✗Stationary; probing not budgeted\.Stojanovicet al\.\[[2023](https://arxiv.org/html/2605.20269#bib.bib11)\]NeurIPS’23Entry\-wise / subspace recovery✗/✓✗Estimation focus; no probe budget\.Jedraet al\.\[[2024](https://arxiv.org/html/2605.20269#bib.bib16)\]ICML’24𝒪~​\(r5/4​\(m\+n\)3/4​T\)\\widetilde\{\\mathcal\{O\}\}\\\!\\left\(r^\{5/4\}\(m\+n\)^\{3/4\}\\sqrt\{T\}\\right\)✓✗Stationary; no re\-learning\.Janget al\.\[[2024](https://arxiv.org/html/2605.20269#bib.bib15)\]ICML’24Arm\-set\-dependent regret✓✗Stationary; no CP detection\.Abbasi\-Yadkoriet al\.\[[2023](https://arxiv.org/html/2605.20269#bib.bib7)\]JMLR’23𝒪~​\(K​N​\(S\+1\)\)\\widetilde\{\\mathcal\{O\}\}\(\\sqrt\{KN\(S\+1\)\}\)✗✓UnstructuredKK\-arm; no low\-rank\.Komiyamaet al\.\[[2024](https://arxiv.org/html/2605.20269#bib.bib14)\]JMLR’24ADR\-bandit finite\-time✗✓Unstructured; no low\-rank \+ probing\.Houet al\.\[[2024](https://arxiv.org/html/2605.20269#bib.bib12)\]NeurIPS’24Fixed\-confidence sample complexity✓✓BAI objective; no low\-rank\.Table 6:Compact positioning of SPSC’s combined setting\.Work classLow\-rankNonstationaryCostly probingMain gap vs\. oursLow\-rank bandits✓✗✗Fixed subspace; no piecewise changes; no sensing\-cost budget\.Nonstationary linear/contextual bandits✗✓✗Adapt in ambient parameter space; ignore latent low\-rank structure\.Costly\-information / active\-query bandits✗✗✓Price information acquisition; do not address subspace recovery under changing representations\.This paper✓✓✓Combines low\-rank structure, piecewise\-stationary adaptation, and explicit costly probing in a single identification\-to\-exploitation framework\.Table 7:Regret\-scaling comparison with the published baselines that appear in our experiments\.AlgorithmReferenceRegret scalingKey difference vs\. SPSCLinUCBAbbasi\-Yadkoriet al\.\[[2011](https://arxiv.org/html/2605.20269#bib.bib2)\]O​\(d​T\)O\(d\\sqrt\{T\}\)Ambient; no subspace exploitation\.LowOFULJunet al\.\[[2019](https://arxiv.org/html/2605.20269#bib.bib3)\]𝒪~​\(r​T\)\\widetilde\{\\mathcal\{O\}\}\(r\\sqrt\{T\}\)Needs oracle subspaceBB\.LowRank\-RewardLuet al\.\[[2021](https://arxiv.org/html/2605.20269#bib.bib4)\]𝒪~​\(\(d1\+d2\)3/2​r​T\)\\widetilde\{\\mathcal\{O\}\}\(\(d\_\{1\}\{\+\}d\_\{2\}\)^\{3/2\}\\sqrt\{rT\}\)Stationary; ambient prefactor in\(d1\+d2\)3/2\(d\_\{1\}\{\+\}d\_\{2\}\)^\{3/2\}\.BOSSDuonget al\.\[[2024](https://arxiv.org/html/2605.20269#bib.bib20)\]𝒪~​\(r​d​T\)\\widetilde\{\\mathcal\{O\}\}\(r\\sqrt\{dT\}\)Stationary; no online change adaptation\.JedraJedraet al\.\[[2024](https://arxiv.org/html/2605.20269#bib.bib16)\]𝒪~​\(r5/4​\(m\+n\)3/4​T\)\\widetilde\{\\mathcal\{O\}\}\(r^\{5/4\}\(m\{\+\}n\)^\{3/4\}\\sqrt\{T\}\)Stationary; no probe cost\.SPSC \(ours\)This work𝒪~​\(r​T\+T2/3\)\\widetilde\{\\mathcal\{O\}\}\(r\\sqrt\{T\}\+T^\{2/3\}\)Learns a*changing*BBvia priced probes\.
## Appendix CProofs

This section proves the statements of §[4](https://arxiv.org/html/2605.20269#S4)in dependency order:

1. 1\.§[C\.1](https://arxiv.org/html/2605.20269#A3.SS1)fixes notation and establishes the probe\-time excitation lemma that all proofs depend on\.
2. 2\.§[C\.2](https://arxiv.org/html/2605.20269#A3.SS2)derives the load\-bearing*identification chain*: closed\-form inverse of the probe operator𝒦\\mathcal\{K\}, quadratic\-measurement identity, lifted probe sample’s near\-unbiasedness, matrix Bernstein/Freedman, and the projector error via Davis–Kahan\.
3. 3\.§[C\.3](https://arxiv.org/html/2605.20269#A3.SS3)establishes the necessity half of Theorem[2\.2](https://arxiv.org/html/2605.20269#S2.Thmtheorem2)via three propositions \(Prop\.[C\.12](https://arxiv.org/html/2605.20269#A3.Thmtheorem12)–[C\.14](https://arxiv.org/html/2605.20269#A3.Thmtheorem14)\) showing each probe\-side condition is individually necessary in the unrestricted\-second\-moment problem\.
4. 4\.§[C\.4](https://arxiv.org/html/2605.20269#A3.SS4)states and proves the interleaved\-analysis lemmas: projected nonstationary UCB with time\-varying basis \(Lem\.[C\.16](https://arxiv.org/html/2605.20269#A3.Thmtheorem16)\), uniform prefix subspace concentration \(Lem\.[C\.17](https://arxiv.org/html/2605.20269#A3.Thmtheorem17)\), and cumulative interleaved subspace error \(Lem\.[C\.18](https://arxiv.org/html/2605.20269#A3.Thmtheorem18)\)\.
5. 5\.§[C\.5](https://arxiv.org/html/2605.20269#A3.SS5)proves the main costed regret bound \(Thm\.[4\.1](https://arxiv.org/html/2605.20269#S4.Thmtheorem1)\) via a five\-step decomposition: probe regret, exploitation regret via Lem\.[C\.16](https://arxiv.org/html/2605.20269#A3.Thmtheorem16), per\-segment bound, probe\-estimation tradeoff with burn\-in, and sum over segments\.
6. 6\.§[C\.6](https://arxiv.org/html/2605.20269#A3.SS6)derives the rank\-adaptive corollary \(Cor\.[4\.4](https://arxiv.org/html/2605.20269#S4.Thmtheorem4)\) via Weyl’s inequality on the matrix\-Bernstein bound\.
7. 7\.§[C\.7](https://arxiv.org/html/2605.20269#A3.SS7)lifts the guarantee to SPSC\-Adaptive \(Prop\.[4\.5](https://arxiv.org/html/2605.20269#S4.Thmtheorem5)\) by controlling the CUSUM detector\.

The windowed projected self\-normalized bound \(Lem\.[C\.3](https://arxiv.org/html/2605.20269#A3.Thmtheorem3)\), the windowed projected potential condition \(Assumption[C\.2](https://arxiv.org/html/2605.20269#A3.Thmtheorem2)\), and the projected nonstationary UCB lemma \(Lem\.[C\.16](https://arxiv.org/html/2605.20269#A3.Thmtheorem16)\) are the linear\-bandit ingredients; constants that do not affect leading order are absorbed into𝒪~​\(⋅\)\\widetilde\{\\mathcal\{O\}\}\(\\cdot\)\.

### C\.1Preliminaries and notation

Throughout,ℐk=\[τk−1,τk\)\\mathcal\{I\}\_\{k\}=\[\\tau\_\{k\-1\},\\tau\_\{k\}\)denotes segmentkkof lengthℓk:=\|ℐk\|\\ell\_\{k\}:=\|\\mathcal\{I\}\_\{k\}\|, so∑kℓk=T\\sum\_\{k\}\\ell\_\{k\}=T\. Insideℐk\\mathcal\{I\}\_\{k\}the learner performsmk=\|𝒯k\|m\_\{k\}=\|\\mathcal\{T\}\_\{k\}\|probe rounds \(𝒯k:=𝒯probe∩ℐk\\mathcal\{T\}\_\{k\}:=\\mathcal\{T\}\_\{\\mathrm\{probe\}\}\\cap\\mathcal\{I\}\_\{k\}\) andnk=ℓk−mkn\_\{k\}=\\ell\_\{k\}\-m\_\{k\}exploitation rounds \(Ek:=ℐk∖𝒯kE\_\{k\}:=\\mathcal\{I\}\_\{k\}\\setminus\\mathcal\{T\}\_\{k\}\)\. We writeP^t=U^t​U^t⊤\\widehat\{P\}\_\{t\}=\\widehat\{U\}\_\{t\}\\widehat\{U\}\_\{t\}^\{\\top\}andPk⋆=Bk⋆​Bk⋆⊤P\_\{k\}^\{\\star\}=B\_\{k\}^\{\\star\}B\_\{k\}^\{\\star\\top\}for the estimated and true rank\-rrprojectors, andεk:=‖P^k−Pk⋆‖op\\varepsilon\_\{k\}:=\\\|\\widehat\{P\}\_\{k\}\-P\_\{k\}^\{\\star\}\\\|\_\{\\mathrm\{op\}\}\. We work on the high\-probability event𝒢w:=\{maxt≤T⁡‖wt‖2≤Sw\}\\mathcal\{G\}\_\{w\}:=\\bigl\\\{\\max\_\{t\\leq T\}\\\|w\_\{t\}\\\|\_\{2\}\\leq S\_\{w\}\\bigr\\\}\. For sub\-Gaussian innovations one may takeSw=𝒪~​\(r\)S\_\{w\}=\\widetilde\{\\mathcal\{O\}\}\(\\sqrt\{r\}\)via union bound \(the failure probability is absorbed into the overallδ\\deltabudget\); for bounded innovations𝒢w\\mathcal\{G\}\_\{w\}holds deterministically\. In what follows we implicitly condition on𝒢w\\mathcal\{G\}\_\{w\}\.

The*predictable second moment*isM~t:=𝔼​\[θt​θt⊤∣ℋt−1\]=Bk⋆​𝔼​\[wt​wt⊤∣ℋt−1\]​\(Bk⋆\)⊤\\widetilde\{M\}\_\{t\}:=\\mathbb\{E\}\[\\theta\_\{t\}\\theta\_\{t\}^\{\\top\}\\mid\\mathcal\{H\}\_\{t\-1\}\]=B\_\{k\}^\{\\star\}\\mathbb\{E\}\[w\_\{t\}w\_\{t\}^\{\\top\}\\mid\\mathcal\{H\}\_\{t\-1\}\]\(B\_\{k\}^\{\\star\}\)^\{\\top\}, and the probe\-time average isM¯kprobe:=mk−1​∑t∈𝒯kM~t\\bar\{M\}\_\{k\}^\{\\mathrm\{probe\}\}:=m\_\{k\}^\{\-1\}\\sum\_\{t\\in\\mathcal\{T\}\_\{k\}\}\\widetilde\{M\}\_\{t\}\. By the non\-degenerate\-innovation assumptionΣη,k≻0\\Sigma\_\{\\eta,k\}\\succ 0of §[2](https://arxiv.org/html/2605.20269#S2),M¯kprobe\\bar\{M\}\_\{k\}^\{\\mathrm\{probe\}\}has rankrrand itsrr\-th eigenvalueλmin\>0\\lambda\_\{\\min\}\>0is uniformly bounded below inkk\(Lem\.[C\.1](https://arxiv.org/html/2605.20269#A3.Thmtheorem1)below; stability ofAkA\_\{k\}is used only to bound‖wt‖≤Sw\\\|w\_\{t\}\\\|\\leq S\_\{w\}, not for this lower bound\)\. ConstantsC,C′,…C,C^\{\\prime\},\\ldotsdepend only onσε,R𝒜,L,ρQ,Sw,λmin\\sigma\_\{\\varepsilon\},R\_\{\\mathcal\{A\}\},L,\\rho\_\{Q\},S\_\{w\},\\lambda\_\{\\min\}and may change line to line\.

###### Lemma C\.1\(Predictable probe\-time excitation\)\.

For each segmentkk,

λr​\(1mk​∑t∈𝒯k𝔼​\[wt​wt⊤∣ℋt−1\]\)≥λmin\>0almost surely\.\\lambda\_\{r\}\\\!\\left\(\\frac\{1\}\{m\_\{k\}\}\\sum\_\{t\\in\\mathcal\{T\}\_\{k\}\}\\mathbb\{E\}\[w\_\{t\}w\_\{t\}^\{\\top\}\\mid\\mathcal\{H\}\_\{t\-1\}\]\\right\)\\;\\geq\\;\\lambda\_\{\\min\}\\;\>\\;0\\qquad\\text\{almost surely\.\}

###### Proof\.

For eacht∈ℐkt\\in\\mathcal\{I\}\_\{k\}, the conditional second moment satisfies𝔼​\[wt​wt⊤∣ℋt−1\]=Ak​wt−1​wt−1⊤​Ak⊤\+Ση,k⪰Ση,k\\mathbb\{E\}\[w\_\{t\}w\_\{t\}^\{\\top\}\\mid\\mathcal\{H\}\_\{t\-1\}\]=A\_\{k\}w\_\{t\-1\}w\_\{t\-1\}^\{\\top\}A\_\{k\}^\{\\top\}\+\\Sigma\_\{\\eta,k\}\\succeq\\Sigma\_\{\\eta,k\}\(LDS recursion \+ non\-degenerate innovations\)\. Henceλr\(𝔼\[wtwt⊤∣ℋt−1\]\)≥λr\(Ση,k\)=:λmin\>0\\lambda\_\{r\}\(\\mathbb\{E\}\[w\_\{t\}w\_\{t\}^\{\\top\}\\mid\\mathcal\{H\}\_\{t\-1\}\]\)\\geq\\lambda\_\{r\}\(\\Sigma\_\{\\eta,k\}\)=:\\lambda\_\{\\min\}\>0uniformly across rounds\. Averaging over any probe subset𝒯k⊆ℐk\\mathcal\{T\}\_\{k\}\\subseteq\\mathcal\{I\}\_\{k\}preserves this PSD lower bound:λr​\(mk−1​∑t∈𝒯k𝔼​\[wt​wt⊤∣ℋt−1\]\)≥λmin\\lambda\_\{r\}\(m\_\{k\}^\{\-1\}\\sum\_\{t\\in\\mathcal\{T\}\_\{k\}\}\\mathbb\{E\}\[w\_\{t\}w\_\{t\}^\{\\top\}\\mid\\mathcal\{H\}\_\{t\-1\}\]\)\\geq\\lambda\_\{\\min\}almost surely\. Stability ofAkA\_\{k\}is therefore not needed for the lemma; the innovation covariance alone suffices\. ∎

#### Notation for the interleaved analysis\.

For each segmentℐk=\[τk−1,τk\)\\mathcal\{I\}\_\{k\}=\[\\tau\_\{k\-1\},\\tau\_\{k\}\), recallℓk=\|ℐk\|\\ell\_\{k\}=\|\\mathcal\{I\}\_\{k\}\|,𝒯k=𝒯probe∩ℐk\\mathcal\{T\}\_\{k\}=\\mathcal\{T\}\_\{\\mathrm\{probe\}\}\\cap\\mathcal\{I\}\_\{k\},mk=\|𝒯k\|m\_\{k\}=\|\\mathcal\{T\}\_\{k\}\|,Ek=ℐk∖𝒯kE\_\{k\}=\\mathcal\{I\}\_\{k\}\\setminus\\mathcal\{T\}\_\{k\},nk=\|Ek\|=ℓk−mkn\_\{k\}=\|E\_\{k\}\|=\\ell\_\{k\}\-m\_\{k\}\. Fort∈ℐkt\\in\\mathcal\{I\}\_\{k\}, letqk​\(t\):=\|𝒯k∩\[τk−1,t\)\|q\_\{k\}\(t\):=\|\\mathcal\{T\}\_\{k\}\\cap\[\\tau\_\{k\-1\},t\)\|be the number of probes collected in segmentkkstrictly before roundtt\. DenotePk⋆=Bk⋆​Bk⋆⊤P\_\{k\}^\{\\star\}=B\_\{k\}^\{\\star\}B\_\{k\}^\{\\star\\top\},P^t=U^t​U^t⊤\\widehat\{P\}\_\{t\}=\\widehat\{U\}\_\{t\}\\widehat\{U\}\_\{t\}^\{\\top\}, andεk,t:=‖P^t−Pk⋆‖op\\varepsilon\_\{k,t\}:=\\\|\\widehat\{P\}\_\{t\}\-P\_\{k\}^\{\\star\}\\\|\_\{\\mathrm\{op\}\}\. The within\-segment variation isVkin:=∑s,s\+1∈ℐk‖θs\+1−θs‖2V\_\{k\}^\{\\rm in\}:=\\sum\_\{s,s\+1\\in\\mathcal\{I\}\_\{k\}\}\\\|\\theta\_\{s\+1\}\-\\theta\_\{s\}\\\|\_\{2\},Vin:=∑kVkinV\_\{\\rm in\}:=\\sum\_\{k\}V\_\{k\}^\{\\rm in\}\. LetRQ:=supu∈supp​\(Q\)‖u‖2R\_\{Q\}:=\\sup\_\{u\\in\\mathrm\{supp\}\(Q\)\}\\\|u\\\|\_\{2\}\(RQ=dR\_\{Q\}=\\sqrt\{d\}for scaled\-sphere probes;RQ≤R𝒜R\_\{Q\}\\leq R\_\{\\mathcal\{A\}\}if probes are feasible actions covered by the action\-radius bound\)\.

#### Balanced interleaved probe schedule\.

The probe schedule is balanced: there exists an absolute constanta0a\_\{0\}such that, for every segmentkkand everyj∈\{0,1,…,mk\}j\\in\\\{0,1,\\dots,m\_\{k\}\\\},

\|\{t∈Ek:qk​\(t\)=j\}\|≤a0​⌈ℓk/mk⌉\.\\bigl\|\\\{t\\in E\_\{k\}:\\,q\_\{k\}\(t\)=j\\\}\\bigr\|\\;\\leq\\;a\_\{0\}\\bigl\\lceil\\ell\_\{k\}/m\_\{k\}\\bigr\\rceil\.\(B\)Uniformly spaced probes satisfy this condition\.

#### Windowed projected potential\.

For each exploit roundt∈Ekt\\in E\_\{k\}, Alg\.[1](https://arxiv.org/html/2605.20269#alg1)uses the*current*basisU^t−1\\widehat\{U\}\_\{t\-1\}and re\-projects the windowed history through this same basis:zt​\(x\):=U^t−1⊤​xz\_\{t\}\(x\):=\\widehat\{U\}\_\{t\-1\}^\{\\top\}x,V~t:=λ​Ir\+∑s∈𝒲tzt​\(xs\)​zt​\(xs\)⊤\\widetilde\{V\}\_\{t\}:=\\lambda I\_\{r\}\+\\sum\_\{s\\in\\mathcal\{W\}\_\{t\}\}z\_\{t\}\(x\_\{s\}\)z\_\{t\}\(x\_\{s\}\)^\{\\top\},wt​\(x\):=‖zt​\(x\)‖V~t−1w\_\{t\}\(x\):=\\\|z\_\{t\}\(x\)\\\|\_\{\\widetilde\{V\}\_\{t\}^\{\-1\}\}\.

###### Assumption C\.2\(Windowed projected potential\)\.

For each segmentℐk\\mathcal\{I\}\_\{k\},

∑t∈Ekmin⁡\{1,wt​\(xt\)2\}≤Cpot​\(nk/W\+1\)​r​log⁡\(1\+W​R𝒜2λ​r\),\\sum\_\{t\\in E\_\{k\}\}\\min\\\{1,w\_\{t\}\(x\_\{t\}\)^\{2\}\\\}\\;\\leq\\;C\_\{\\rm pot\}\\,\(n\_\{k\}/W\+1\)\\,r\\log\\\!\\Bigl\(1\+\\frac\{WR\_\{\\mathcal\{A\}\}^\{2\}\}\{\\lambda r\}\\Bigr\),\(5\)with the convention that the factor\(nk/W\+1\)\(n\_\{k\}/W\+1\)is interpreted as11andWWis replaced bynkn\_\{k\}whenW≥nkW\\geq n\_\{k\}\. For fixed basis this is the standard elliptical\-potential lemma\[Abbasi\-Yadkoriet al\.,[2011](https://arxiv.org/html/2605.20269#bib.bib2), Lem\. 11\]\(resp\. its sliding\-window form whenW<nkW<n\_\{k\}\); the moving\-basis case reduces to controlling the cumulative log\-determinant change under basis updates, which follows from prefix concentration \(Lem\.[C\.17](https://arxiv.org/html/2605.20269#A3.Thmtheorem17)\) via a routine Lipschitz bound\.

###### Lemma C\.3\(Windowed projected self\-normalized concentration\)\.

For a fixeda⋆∈ℝra^\{\\star\}\\in\\mathbb\{R\}^\{r\}andσε\\sigma\_\{\\varepsilon\}\-sub\-Gaussian noise on the projected covariateszt=U^t⊤​xt∈ℝrz\_\{t\}=\\widehat\{U\}\_\{t\}^\{\\top\}x\_\{t\}\\in\\mathbb\{R\}^\{r\}, the windowed ridge estimatora^t=V~t−1​b~t\\widehat\{a\}\_\{t\}=\\widetilde\{V\}\_\{t\}^\{\-1\}\\widetilde\{b\}\_\{t\}satisfies, with probability at least1−δ/K1\-\\delta/Kper segmentkkand simultaneously for allt∈Ekt\\in E\_\{k\},

‖a^t−a⋆‖V~t≤βt\(r,W\),βt\(r,W\):=σε​r​log⁡\(1\+W​R𝒜2/\(λ​r\)\)\+2​log⁡\(2​K/δ\)\+λ​Sw\.\\\|\\widehat\{a\}\_\{t\}\-a^\{\\star\}\\\|\_\{\\widetilde\{V\}\_\{t\}\}\\leq\\beta\_\{t\}^\{\(r,W\)\},\\qquad\\beta\_\{t\}^\{\(r,W\)\}:=\\sigma\_\{\\varepsilon\}\\sqrt\{r\\log\\bigl\(1\+WR\_\{\\mathcal\{A\}\}^\{2\}/\(\\lambda r\)\\bigr\)\+2\\log\(2K/\\delta\)\}\+\\sqrt\{\\lambda\}\\,S\_\{w\}\.This is the windowed projected specialization ofAbbasi\-Yadkoriet al\.\[[2011](https://arxiv.org/html/2605.20269#bib.bib2), Thm\. 1, 2\]\.

### C\.2Concentration of the lifted probe moment \(load\-bearing step\)

This is the non\-standard piece of the analysis; we derive it in full\. We work with scaled\-sphere probesut=d​vtu\_\{t\}=\\sqrt\{d\}\\,v\_\{t\},vt∼Unif​\(𝕊d−1\)v\_\{t\}\\sim\\mathrm\{Unif\}\(\\mathbb\{S\}^\{d\-1\}\), which satisfy‖ut‖2=d\\\|u\_\{t\}\\\|\_\{2\}=\\sqrt\{d\}*deterministically*and𝔼​\[ut​ut⊤\]=Id\\mathbb\{E\}\[u\_\{t\}u\_\{t\}^\{\\top\}\]=I\_\{d\}\. The probe moment operator𝒦:M↦𝔼​\[\(u⊤​M​u\)​u​u⊤\]\\mathcal\{K\}:M\\mapsto\\mathbb\{E\}\[\(u^\{\\top\}Mu\)uu^\{\\top\}\]is a linear bijection on the space of symmetricd×dd\\times dmatrices\.

###### Lemma C\.4\(Closed\-form inverse of𝒦\\mathcal\{K\}on symmetric matrices\)\.

For scaled\-sphere probesu=d​vu=\\sqrt\{d\}\\,v,v∼Unif​\(𝕊d−1\)v\\sim\\mathrm\{Unif\}\(\\mathbb\{S\}^\{d\-1\}\),𝒦\\mathcal\{K\}acts on symmetricd×dd\\times dmatrices as𝒦​\(M\)=dd\+2​\(tr⁡\(M\)​Id\+2​M\)\\mathcal\{K\}\(M\)=\\tfrac\{d\}\{d\+2\}\\bigl\(\\operatorname\{tr\}\(M\)\\,I\_\{d\}\+2M\\bigr\)with inverse𝒦−1​\(N\)=d\+22​d​N−tr⁡\(N\)2​d​Id\\mathcal\{K\}^\{\-1\}\(N\)=\\tfrac\{d\+2\}\{2d\}\\,N\-\\tfrac\{\\operatorname\{tr\}\(N\)\}\{2d\}\\,I\_\{d\}\. Moreover‖𝒦−1‖op→op≤1\\\|\\mathcal\{K\}^\{\-1\}\\\|\_\{\\mathrm\{op\}\\to\\mathrm\{op\}\}\\leq 1on symmetric inputs\.

###### Proof\.

Use the fourth\-moment identity for the uniform sphere𝔼​\[vi​vj​vk​vl\]=\(δi​j​δk​l\+δi​k​δj​l\+δi​l​δj​k\)/\(d​\(d\+2\)\)\\mathbb\{E\}\[v\_\{i\}v\_\{j\}v\_\{k\}v\_\{l\}\]=\(\\delta\_\{ij\}\\delta\_\{kl\}\+\\delta\_\{ik\}\\delta\_\{jl\}\+\\delta\_\{il\}\\delta\_\{jk\}\)/\(d\(d\+2\)\)and the rescalingu=d​vu=\\sqrt\{d\}\\,v:𝔼​\[\(u⊤​M​u\)​uk​ul\]=d2​𝔼​\[\(v⊤​M​v\)​vk​vl\]=d2⋅\(2​Mk​l\+tr⁡\(M\)​δk​l\)/\(d​\(d\+2\)\)=dd\+2​\(2​Mk​l\+tr⁡\(M\)​δk​l\)\\mathbb\{E\}\[\(u^\{\\top\}Mu\)u\_\{k\}u\_\{l\}\]=d^\{2\}\\mathbb\{E\}\[\(v^\{\\top\}Mv\)v\_\{k\}v\_\{l\}\]=d^\{2\}\\cdot\(2M\_\{kl\}\+\\operatorname\{tr\}\(M\)\\delta\_\{kl\}\)/\(d\(d\+2\)\)=\\tfrac\{d\}\{d\+2\}\(2M\_\{kl\}\+\\operatorname\{tr\}\(M\)\\delta\_\{kl\}\)\(usingMMsymmetric\)\. So𝒦​\(M\)=dd\+2​\(tr⁡\(M\)​Id\+2​M\)\\mathcal\{K\}\(M\)=\\tfrac\{d\}\{d\+2\}\(\\operatorname\{tr\}\(M\)I\_\{d\}\+2M\)\. Taking traces ofN=𝒦​\(M\)N=\\mathcal\{K\}\(M\)givestr⁡\(N\)=d​tr⁡\(M\)\\operatorname\{tr\}\(N\)=d\\,\\operatorname\{tr\}\(M\), sotr⁡\(M\)=tr⁡\(N\)/d\\operatorname\{tr\}\(M\)=\\operatorname\{tr\}\(N\)/dandM=d\+22​d​N−tr⁡\(N\)2​d​IdM=\\tfrac\{d\+2\}\{2d\}N\-\\tfrac\{\\operatorname\{tr\}\(N\)\}\{2d\}I\_\{d\}\.

For the operator\-norm bound:𝒦−1​\(N\)\\mathcal\{K\}^\{\-1\}\(N\)is diagonalized in the eigenbasis ofNN; ifNNhas eigenvaluesμ1,…,μd\\mu\_\{1\},\\dots,\\mu\_\{d\}, then𝒦−1​\(N\)\\mathcal\{K\}^\{\-1\}\(N\)has eigenvaluesνi=d\+22​d​μi−tr⁡\(N\)2​d\\nu\_\{i\}=\\tfrac\{d\+2\}\{2d\}\\mu\_\{i\}\-\\tfrac\{\\operatorname\{tr\}\(N\)\}\{2d\}\. Maximizing\|νi\|\|\\nu\_\{i\}\|over‖N‖op=1\\\|N\\\|\_\{\\mathrm\{op\}\}=1\(i\.e\.maxi⁡\|μi\|=1\\max\_\{i\}\|\\mu\_\{i\}\|=1\): atμ1=1,μ2=⋯=μd=−1\\mu\_\{1\}=1,\\mu\_\{2\}=\\cdots=\\mu\_\{d\}=\-1,tr⁡\(N\)=2−d\\operatorname\{tr\}\(N\)=2\-dandν1=d\+2−\(2−d\)2​d=1\\nu\_\{1\}=\\tfrac\{d\+2\-\(2\-d\)\}\{2d\}=1; atμ1=−1,μ2=⋯=μd=1\\mu\_\{1\}=\-1,\\mu\_\{2\}=\\cdots=\\mu\_\{d\}=1,ν1=−1\\nu\_\{1\}=\-1\. All other eigenvalue patterns give\|νi\|≤1\|\\nu\_\{i\}\|\\leq 1by direct case analysis\. So‖𝒦−1‖op→op=1\\\|\\mathcal\{K\}^\{\-1\}\\\|\_\{\\mathrm\{op\}\\to\\mathrm\{op\}\}=1on symmetric matrices ford≥2d\\geq 2\. ∎

###### Lemma C\.5\(Quadratic measurement identity\)\.

On every probe roundt∈𝒯probet\\in\\mathcal\{T\}\_\{\\mathrm\{probe\}\}, withδσ:=σ^2−σε2\\delta\_\{\\sigma\}:=\\widehat\{\\sigma\}^\{2\}\-\\sigma\_\{\\varepsilon\}^\{2\}andmt:=𝔼​\[εt​θt∣ℋt−1,ut\]m\_\{t\}:=\\mathbb\{E\}\[\\varepsilon\_\{t\}\\theta\_\{t\}\\mid\\mathcal\{H\}\_\{t\-1\},u\_\{t\}\],

𝔼​\[st∣σ​\(ℋt−1,ut\)\]=ut⊤​M~t​ut\+2​ut⊤​mt−δσ,‖mt‖≤ϵ×\.\\mathbb\{E\}\[s\_\{t\}\\mid\\sigma\(\\mathcal\{H\}\_\{t\-1\},u\_\{t\}\)\]=u\_\{t\}^\{\\top\}\\widetilde\{M\}\_\{t\}u\_\{t\}\+2u\_\{t\}^\{\\top\}m\_\{t\}\-\\delta\_\{\\sigma\},\\qquad\\\|m\_\{t\}\\\|\\leq\\epsilon\_\{\\times\}\.Under exact probe conditions \(δσ=ϵ×=0\\delta\_\{\\sigma\}=\\epsilon\_\{\\times\}=0\) this collapses to𝔼​\[st∣⋅\]=ut⊤​M~t​ut\\mathbb\{E\}\[s\_\{t\}\\mid\\cdot\]=u\_\{t\}^\{\\top\}\\widetilde\{M\}\_\{t\}u\_\{t\}\.

###### Proof\.

Expandyt2=\(ut⊤​θt\)2\+2​εt​ut⊤​θt\+εt2y\_\{t\}^\{2\}=\(u\_\{t\}^\{\\top\}\\theta\_\{t\}\)^\{2\}\+2\\varepsilon\_\{t\}u\_\{t\}^\{\\top\}\\theta\_\{t\}\+\\varepsilon\_\{t\}^\{2\}and condition onσ​\(ℋt−1,ut\)\\sigma\(\\mathcal\{H\}\_\{t\-1\},u\_\{t\}\); the middle term contributes2​ut⊤​mt2u\_\{t\}^\{\\top\}m\_\{t\}withmtm\_\{t\}as defined in the lemma, bounded byϵ×\\epsilon\_\{\\times\}via the bounded state\-noise coupling assumption \(§[2](https://arxiv.org/html/2605.20269#S2)\); the last term contributesσε2\\sigma\_\{\\varepsilon\}^\{2\}, and subtractingσ^2\\widehat\{\\sigma\}^\{2\}leaves−δσ\-\\delta\_\{\\sigma\}\. Independence ofutu\_\{t\}from\(θt,ℋt−1\)\(\\theta\_\{t\},\\mathcal\{H\}\_\{t\-1\}\)gives𝔼​\[\(ut⊤​θt\)2∣ℋt−1,ut\]=ut⊤​M~t​ut\\mathbb\{E\}\[\(u\_\{t\}^\{\\top\}\\theta\_\{t\}\)^\{2\}\\mid\\mathcal\{H\}\_\{t\-1\},u\_\{t\}\]=u\_\{t\}^\{\\top\}\\widetilde\{M\}\_\{t\}u\_\{t\}\. ∎

###### Lemma C\.6\(Lifted probe sample is near\-unbiased\)\.

LetGt:=𝒦−1​\(st​ut​ut⊤\)G\_\{t\}:=\\mathcal\{K\}^\{\-1\}\(s\_\{t\}u\_\{t\}u\_\{t\}^\{\\top\}\)for scaled\-sphereut=d​vtu\_\{t\}=\\sqrt\{d\}\\,v\_\{t\},vt∼Unif​\(𝕊d−1\)v\_\{t\}\\sim\\mathrm\{Unif\}\(\\mathbb\{S\}^\{d\-1\}\)\. Then𝔼​\[Gt∣ℋt−1\]=M~t\+B~t\\mathbb\{E\}\[G\_\{t\}\\mid\\mathcal\{H\}\_\{t\-1\}\]=\\widetilde\{M\}\_\{t\}\+\\widetilde\{B\}\_\{t\}with bias

B~t=−δσd​Id,‖B~t‖op=\|δσ\|d\.\\widetilde\{B\}\_\{t\}=\-\\tfrac\{\\delta\_\{\\sigma\}\}\{d\}\\,I\_\{d\},\\qquad\\\|\\widetilde\{B\}\_\{t\}\\\|\_\{\\mathrm\{op\}\}=\\tfrac\{\|\\delta\_\{\\sigma\}\|\}\{d\}\.The bias is a scaled identity, hence shifts every eigenvalue uniformly and does not rotate eigenvectors ofM~t\\widetilde\{M\}\_\{t\}\.

###### Proof\.

By linearity of𝒦−1\\mathcal\{K\}^\{\-1\}and Lemma[C\.5](https://arxiv.org/html/2605.20269#A3.Thmtheorem5),𝔼​\[Gt∣ℋt−1\]=𝒦−1​\(𝒦​\(M~t\)\)\+2​𝒦−1​\(𝔼​\[\(ut⊤​mt\)​ut​ut⊤∣ℋt−1\]\)−δσ​𝒦−1​\(𝔼​\[ut​ut⊤\]\)=M~t\+B~t\\mathbb\{E\}\[G\_\{t\}\\mid\\mathcal\{H\}\_\{t\-1\}\]=\\mathcal\{K\}^\{\-1\}\(\\mathcal\{K\}\(\\widetilde\{M\}\_\{t\}\)\)\+2\\,\\mathcal\{K\}^\{\-1\}\(\\mathbb\{E\}\[\(u\_\{t\}^\{\\top\}m\_\{t\}\)u\_\{t\}u\_\{t\}^\{\\top\}\\mid\\mathcal\{H\}\_\{t\-1\}\]\)\-\\delta\_\{\\sigma\}\\,\\mathcal\{K\}^\{\-1\}\(\\mathbb\{E\}\[u\_\{t\}u\_\{t\}^\{\\top\}\]\)=\\widetilde\{M\}\_\{t\}\+\\widetilde\{B\}\_\{t\}, withM~t=𝒦−1​𝒦​\(M~t\)\\widetilde\{M\}\_\{t\}=\\mathcal\{K\}^\{\-1\}\\mathcal\{K\}\(\\widetilde\{M\}\_\{t\}\)\.

*Variance\-bias term\.*𝔼​\[ut​ut⊤\]=Id\\mathbb\{E\}\[u\_\{t\}u\_\{t\}^\{\\top\}\]=I\_\{d\}exactly for scaled\-sphere probes, so−δσ​𝒦−1​\(Id\)=−δσ​\[d\+22​d​Id−d2​d​Id\]=−δσ⋅22​d​Id=−δσd​Id\-\\delta\_\{\\sigma\}\\mathcal\{K\}^\{\-1\}\(I\_\{d\}\)=\-\\delta\_\{\\sigma\}\\bigl\[\\tfrac\{d\+2\}\{2d\}I\_\{d\}\-\\tfrac\{d\}\{2d\}I\_\{d\}\\bigr\]=\-\\delta\_\{\\sigma\}\\cdot\\tfrac\{2\}\{2d\}I\_\{d\}=\-\\tfrac\{\\delta\_\{\\sigma\}\}\{d\}I\_\{d\}\. This is a scaled identity, hence does not rotate eigenvectors ofM~t\\widetilde\{M\}\_\{t\}\.

*State\-noise coupling term\.*The remaining contribution is2​𝒦−1​\(𝔼​\[\(ut⊤​mt\)​ut​ut⊤∣ℋt−1\]\)2\\,\\mathcal\{K\}^\{\-1\}\\bigl\(\\mathbb\{E\}\[\(u\_\{t\}^\{\\top\}m\_\{t\}\)\\,u\_\{t\}u\_\{t\}^\{\\top\}\\mid\\mathcal\{H\}\_\{t\-1\}\]\\bigr\)\. The\(a,b\)\(a,b\)\-entry of the inner expectation is∑c\(mt\)c​𝔼​\[\(ut\)a​\(ut\)b​\(ut\)c\]\\sum\_\{c\}\(m\_\{t\}\)\_\{c\}\\,\\mathbb\{E\}\[\(u\_\{t\}\)\_\{a\}\(u\_\{t\}\)\_\{b\}\(u\_\{t\}\)\_\{c\}\], a degree\-three polynomial inutu\_\{t\}\. For sphere\-symmetric probesut↦−utu\_\{t\}\\mapsto\-u\_\{t\}leaves the distribution invariant, so every odd\-degree moment vanishes and𝔼​\[\(ut⊤​mt\)​ut​ut⊤∣ℋt−1\]=0\\mathbb\{E\}\[\(u\_\{t\}^\{\\top\}m\_\{t\}\)\\,u\_\{t\}u\_\{t\}^\{\\top\}\\mid\\mathcal\{H\}\_\{t\-1\}\]=0exactly\. Hence the coupling term contributes zero, andB~t=−δσd​Id\\widetilde\{B\}\_\{t\}=\-\\tfrac\{\\delta\_\{\\sigma\}\}\{d\}\\,I\_\{d\}\. ∎

###### Lemma C\.7\(Uniform a\.s\. bound onGtG\_\{t\}\)\.

For scaled\-sphere probes‖ut‖=d\\\|u\_\{t\}\\\|=\\sqrt\{d\}deterministically; on the noise\-truncation event\|εt\|≤Lε:=σε​2​log⁡\(2​T/δ\)\|\\varepsilon\_\{t\}\|\\leq L\_\{\\varepsilon\}:=\\sigma\_\{\\varepsilon\}\\sqrt\{2\\log\(2T/\\delta\)\}\(which holds with probability≥1−δ\\geq 1\-\\deltavia union overTTrounds\),\|st\|≤Rs:=\(d​Sw\+Lε\)2\+σ^2\|s\_\{t\}\|\\leq R\_\{s\}:=\(\\sqrt\{d\}\\,S\_\{w\}\+L\_\{\\varepsilon\}\)^\{2\}\+\\widehat\{\\sigma\}^\{2\}, and the centered lifted sample satisfies‖X~t‖op≤2​RX\\\|\\tilde\{X\}\_\{t\}\\\|\_\{\\mathrm\{op\}\}\\leq 2R\_\{X\}withRX:=d⋅Rs\+Sw2R\_\{X\}:=d\\cdot R\_\{s\}\+S\_\{w\}^\{2\}\. So both the envelope and predictable variance are at most2​RX2R\_\{X\}andRX2R\_\{X\}^\{2\}respectively\.

###### Proof\.

For scaled\-sphereutu\_\{t\},‖ut‖=d\\\|u\_\{t\}\\\|=\\sqrt\{d\}exactly\.\|st\|=\|\(ut⊤​θt\+εt\)2−σ^2\|≤\(d​Sw\+Lε\)2\+σ^2=Rs\|s\_\{t\}\|=\|\(u\_\{t\}^\{\\top\}\\theta\_\{t\}\+\\varepsilon\_\{t\}\)^\{2\}\-\\widehat\{\\sigma\}^\{2\}\|\\leq\(\\sqrt\{d\}\\,S\_\{w\}\+L\_\{\\varepsilon\}\)^\{2\}\+\\widehat\{\\sigma\}^\{2\}=R\_\{s\}using\|ut⊤​θt\|≤‖ut‖​‖θt‖≤d​Sw\|u\_\{t\}^\{\\top\}\\theta\_\{t\}\|\\leq\\\|u\_\{t\}\\\|\\\|\\theta\_\{t\}\\\|\\leq\\sqrt\{d\}\\,S\_\{w\}on‖θt‖≤Sw\\\|\\theta\_\{t\}\\\|\\leq S\_\{w\}\(orthonormalBk⋆B\_\{k\}^\{\\star\},‖wt‖≤Sw\\\|w\_\{t\}\\\|\\leq S\_\{w\}\)\. Then‖Gt‖op=‖𝒦−1​\(st​ut​ut⊤\)‖op≤\|st\|​‖ut​ut⊤‖op⋅1=Rs⋅d\\\|G\_\{t\}\\\|\_\{\\mathrm\{op\}\}=\\\|\\mathcal\{K\}^\{\-1\}\(s\_\{t\}u\_\{t\}u\_\{t\}^\{\\top\}\)\\\|\_\{\\mathrm\{op\}\}\\leq\|s\_\{t\}\|\\,\\\|u\_\{t\}u\_\{t\}^\{\\top\}\\\|\_\{\\mathrm\{op\}\}\\cdot 1=R\_\{s\}\\cdot dusing‖𝒦−1‖op→op≤1\\\|\\mathcal\{K\}^\{\-1\}\\\|\_\{\\mathrm\{op\}\\to\\mathrm\{op\}\}\\leq 1and‖ut​ut⊤‖op=d\\\|u\_\{t\}u\_\{t\}^\{\\top\}\\\|\_\{\\mathrm\{op\}\}=d\. Adding the deterministicSw2=‖M~t‖opS\_\{w\}^\{2\}=\\\|\\widetilde\{M\}\_\{t\}\\\|\_\{\\mathrm\{op\}\}bound for the centering gives‖X~t‖op≤2​RX\\\|\\tilde\{X\}\_\{t\}\\\|\_\{\\mathrm\{op\}\}\\leq 2R\_\{X\}\. ∎

###### Theorem C\.8\(Matrix Bernstein forM^k\\widehat\{M\}\_\{k\}\)\.

LetM^k:=mk−1​∑t∈𝒯kGt\\widehat\{M\}\_\{k\}:=m\_\{k\}^\{\-1\}\\sum\_\{t\\in\\mathcal\{T\}\_\{k\}\}G\_\{t\}andXt:=Gt−𝔼​\[Gt∣ℋt−1\]X\_\{t\}:=G\_\{t\}\-\\mathbb\{E\}\[G\_\{t\}\\mid\\mathcal\{H\}\_\{t\-1\}\]\. Conditional on Lemma[C\.7](https://arxiv.org/html/2605.20269#A3.Thmtheorem7),\{Xt\}\\\{X\_\{t\}\\\}is a bounded matrix\-valued MDS with‖Xt‖op≤2​RX\\\|X\_\{t\}\\\|\_\{\\mathrm\{op\}\}\\leq 2R\_\{X\}a\.s\. and∥∑t∈𝒯k𝔼\[Xt2∣ℋt−1\]∥op≤mkRX2\\\|\\sum\_\{t\\in\\mathcal\{T\}\_\{k\}\}\\mathbb\{E\}\[X\_\{t\}^\{2\}\\mid\\mathcal\{H\}\_\{t\-1\}\]\\\|\_\{\\mathrm\{op\}\}\\leq m\_\{k\}R\_\{X\}^\{2\}\. HereB~\\widetilde\{B\}denotes the segment\-level bias; for scaled\-sphere probes under the standing assumptions of §[2](https://arxiv.org/html/2605.20269#S2),B~t\\widetilde\{B\}\_\{t\}from Lem\.[C\.6](https://arxiv.org/html/2605.20269#A3.Thmtheorem6)collapses to the deterministic constant−\(δσ/d\)​Id\-\(\\delta\_\{\\sigma\}/d\)I\_\{d\}, so we drop the subscript when no ambiguity arises and writeB~\\widetilde\{B\}for the common value\. Freedman’s matrix inequality\[Tropp,[2011](https://arxiv.org/html/2605.20269#bib.bib19)\]gives, with probability at least1−δ1\-\\delta,

‖M^k−M¯kprobe−B~‖op≤2​RX​log⁡\(2​d/δ\)/mk\+2​RX​log⁡\(2​d/δ\)3​mk\.\\\|\\widehat\{M\}\_\{k\}\-\\bar\{M\}\_\{k\}^\{\\mathrm\{probe\}\}\-\\widetilde\{B\}\\\|\_\{\\mathrm\{op\}\}\\leq 2R\_\{X\}\\sqrt\{\\log\(2d/\\delta\)/m\_\{k\}\}\+\\frac\{2R\_\{X\}\\log\(2d/\\delta\)\}\{3m\_\{k\}\}\.\(6\)

###### Proof\.

The MDS property is Lemma[C\.6](https://arxiv.org/html/2605.20269#A3.Thmtheorem6)\(shifted by the segment\-level biasB~\\widetilde\{B\}from Lemma[C\.6](https://arxiv.org/html/2605.20269#A3.Thmtheorem6), which is deterministic and thus enters as a constant offset\)\. The a\.s\. bound‖Xt‖op≤2​RX\\\|X\_\{t\}\\\|\_\{\\mathrm\{op\}\}\\leq 2R\_\{X\}follows from‖Gt‖op≤RX\\\|G\_\{t\}\\\|\_\{\\mathrm\{op\}\}\\leq R\_\{X\}and‖𝔼​\[Gt\]‖op≤RX\\\|\\mathbb\{E\}\[G\_\{t\}\]\\\|\_\{\\mathrm\{op\}\}\\leq R\_\{X\}\. The predictable variance bound follows from𝔼​\[Xt2\]⪯𝔼​\[Gt2\]⪯RX2​I\\mathbb\{E\}\[X\_\{t\}^\{2\}\]\\preceq\\mathbb\{E\}\[G\_\{t\}^\{2\}\]\\preceq R\_\{X\}^\{2\}I\. Applying the matrix Freedman inequality to the MDS\{Xt\}\\\{X\_\{t\}\\\}inℝsymd×d\\mathbb\{R\}^\{d\\times d\}\_\{\\mathrm\{sym\}\}with these two bounds yields \([6](https://arxiv.org/html/2605.20269#A3.E6)\); the leadinglog⁡\(2​d/δ\)/mk\\sqrt\{\\log\(2d/\\delta\)/m\_\{k\}\}rate dominates thelog⁡\(2​d/δ\)/mk\\log\(2d/\\delta\)/m\_\{k\}term formk≳log⁡\(d/δ\)m\_\{k\}\\gtrsim\\log\(d/\\delta\)\. ∎

###### Proposition C\.9\(Segment factorization\)\.

M¯kprobe=Bk⋆​S¯kprobe​\(Bk⋆\)⊤\\bar\{M\}\_\{k\}^\{\\mathrm\{probe\}\}=B\_\{k\}^\{\\star\}\\bar\{S\}\_\{k\}^\{\\mathrm\{probe\}\}\(B\_\{k\}^\{\\star\}\)^\{\\top\}whereS¯kprobe:=mk−1​∑t∈𝒯k𝔼​\[wt​wt⊤∣ℋt−1\]\\bar\{S\}\_\{k\}^\{\\mathrm\{probe\}\}:=m\_\{k\}^\{\-1\}\\sum\_\{t\\in\\mathcal\{T\}\_\{k\}\}\\mathbb\{E\}\[w\_\{t\}w\_\{t\}^\{\\top\}\\mid\\mathcal\{H\}\_\{t\-1\}\]\. In particular,range​\(M¯kprobe\)=range​\(Bk⋆\)\\mathrm\{range\}\(\\bar\{M\}\_\{k\}^\{\\mathrm\{probe\}\}\)=\\mathrm\{range\}\(B\_\{k\}^\{\\star\}\)\.

###### Proof\.

M~t=Bk⋆​𝔼​\[wt​wt⊤∣ℋt−1\]​\(Bk⋆\)⊤\\widetilde\{M\}\_\{t\}=B\_\{k\}^\{\\star\}\\mathbb\{E\}\[w\_\{t\}w\_\{t\}^\{\\top\}\\mid\\mathcal\{H\}\_\{t\-1\}\]\(B\_\{k\}^\{\\star\}\)^\{\\top\}fort∈ℐkt\\in\\mathcal\{I\}\_\{k\}; average over𝒯k\\mathcal\{T\}\_\{k\}and pullBk⋆B\_\{k\}^\{\\star\}out\. Range equality usesλr​\(S¯kprobe\)≥λmin\>0\\lambda\_\{r\}\(\\bar\{S\}\_\{k\}^\{\\mathrm\{probe\}\}\)\\geq\\lambda\_\{\\min\}\>0\(Lem\.[C\.1](https://arxiv.org/html/2605.20269#A3.Thmtheorem1)\)\. ∎

###### Corollary C\.10\(Projector concentration\)\.

Ifmkm\_\{k\}is large enough that‖M^k−M¯kprobe‖op≤λmin/2\\\|\\widehat\{M\}\_\{k\}\-\\bar\{M\}\_\{k\}^\{\\mathrm\{probe\}\}\\\|\_\{\\mathrm\{op\}\}\\leq\\lambda\_\{\\min\}/2, then with probability≥1−δ\\geq 1\-\\delta,

εk:=‖P^k−Pk⋆‖op≤Csub​log⁡\(2​d/δ\)/mk\+Δσ,Csub:=8​RXλmin,Δσ:=4​\|δσ\|/dλmin\.\\varepsilon\_\{k\}:=\\\|\\widehat\{P\}\_\{k\}\-P\_\{k\}^\{\\star\}\\\|\_\{\\mathrm\{op\}\}\\leq C\_\{\\mathrm\{sub\}\}\\sqrt\{\\log\(2d/\\delta\)/m\_\{k\}\}\+\\Delta\_\{\\sigma\},\\quad C\_\{\\mathrm\{sub\}\}:=\\frac\{8R\_\{X\}\}\{\\lambda\_\{\\min\}\},\\ \\Delta\_\{\\sigma\}:=\\frac\{4\|\\delta\_\{\\sigma\}\|/d\}\{\\lambda\_\{\\min\}\}\.\(7\)For scaled\-sphere probes, the variance\-misspecification component\|δσ\|/d\|\\delta\_\{\\sigma\}\|/dcorresponds to a scaled\-identity bias \(Lem\.[C\.6](https://arxiv.org/html/2605.20269#A3.Thmtheorem6)\) that is parallel toIdI\_\{d\}and therefore preserves the eigenvectors ofM¯kprobe\\bar\{M\}\_\{k\}^\{\\rm probe\}; applying Davis–Kahan with the biased mean as reference removes the\|δσ\|/d\|\\delta\_\{\\sigma\}\|/dcontribution toΔσ\\Delta\_\{\\sigma\}at population level \(Cor\.[4\.2](https://arxiv.org/html/2605.20269#S4.Thmtheorem2)\)\.

###### Proof\.

By Lemma[C\.6](https://arxiv.org/html/2605.20269#A3.Thmtheorem6)\(scaled\-sphere\),𝔼​\[M^k∣ℋ\]=M¯kprobe\+B~\\mathbb\{E\}\[\\widehat\{M\}\_\{k\}\\mid\\mathcal\{H\}\]=\\bar\{M\}\_\{k\}^\{\\mathrm\{probe\}\}\+\\widetilde\{B\}withB~=−\(δσ/d\)​Id\\widetilde\{B\}=\-\(\\delta\_\{\\sigma\}/d\)\\,I\_\{d\}\(a scaled identity\), so∥B~∥op=\|δσ\|/d=:bσ\\\|\\widetilde\{B\}\\\|\_\{\\mathrm\{op\}\}=\|\\delta\_\{\\sigma\}\|/d=:b\_\{\\sigma\}\. Combining with Theorem[C\.8](https://arxiv.org/html/2605.20269#A3.Thmtheorem8),‖M^k−M¯kprobe‖op≤2​RX​log⁡\(2​d/δ\)/mk\+bσ\\\|\\widehat\{M\}\_\{k\}\-\\bar\{M\}\_\{k\}^\{\\mathrm\{probe\}\}\\\|\_\{\\mathrm\{op\}\}\\leq 2R\_\{X\}\\sqrt\{\\log\(2d/\\delta\)/m\_\{k\}\}\+b\_\{\\sigma\}\.M¯kprobe\\bar\{M\}\_\{k\}^\{\\mathrm\{probe\}\}has rank exactlyrrwithrr\-th eigenvalue≥λmin\\geq\\lambda\_\{\\min\}\(Lem\.[C\.1](https://arxiv.org/html/2605.20269#A3.Thmtheorem1)via Prop\.[C\.9](https://arxiv.org/html/2605.20269#A3.Thmtheorem9)\); Davis–Kahan\[Bhatia,[2013](https://arxiv.org/html/2605.20269#bib.bib23), Thm\. VII\.3\.1\]gives‖P^k−Pk⋆‖op≤4​‖M^k−M¯kprobe‖op/λmin\\\|\\widehat\{P\}\_\{k\}\-P\_\{k\}^\{\\star\}\\\|\_\{\\mathrm\{op\}\}\\leq 4\\\|\\widehat\{M\}\_\{k\}\-\\bar\{M\}\_\{k\}^\{\\mathrm\{probe\}\}\\\|\_\{\\mathrm\{op\}\}/\\lambda\_\{\\min\}, yielding \([7](https://arxiv.org/html/2605.20269#A3.E7)\)\. ∎

###### Lemma C\.11\(Variance estimator from probe residuals\)\.

Split the firstNNprobes of segmentkkin half: formM^k\(N/2\)\\widehat\{M\}\_\{k\}^\{\(N/2\)\}from the firstN/2N/2probes \(matrix\-Bernstein estimate\), and define the residual estimator

σ^2:=2N​∑t∈𝒯k,N/2<t≤N\(yt2−ut⊤​M^k\(N/2\)​ut\)\.\\widehat\{\\sigma\}^\{2\}\\;:=\\;\\frac\{2\}\{N\}\\sum\_\{t\\in\\mathcal\{T\}\_\{k\},\\,N/2<t\\leq N\}\\bigl\(y\_\{t\}^\{2\}\-u\_\{t\}^\{\\top\}\\widehat\{M\}\_\{k\}^\{\(N/2\)\}u\_\{t\}\\bigr\)\.On the event of Theorem[C\.8](https://arxiv.org/html/2605.20269#A3.Thmtheorem8)forM^k\(N/2\)\\widehat\{M\}\_\{k\}^\{\(N/2\)\}, with probability at least1−δ1\-\\delta,

\|σ^2−σε2\|≤C​σε2​log⁡\(1/δ\)/N\.\|\\widehat\{\\sigma\}^\{2\}\-\\sigma\_\{\\varepsilon\}^\{2\}\|\\;\\leq\\;C\\,\\sigma\_\{\\varepsilon\}^\{2\}\\,\\sqrt\{\\log\(1/\\delta\)/N\}\.

###### Proof sketch\.

By Lemma[C\.5](https://arxiv.org/html/2605.20269#A3.Thmtheorem5), on probe roundtt,𝔼​\[yt2−ut⊤​M~t​ut∣ℋt−1,ut\]=σε2\+O​\(ϵ×\)\\mathbb\{E\}\[y\_\{t\}^\{2\}\-u\_\{t\}^\{\\top\}\\widetilde\{M\}\_\{t\}u\_\{t\}\\mid\\mathcal\{H\}\_\{t\-1\},u\_\{t\}\]=\\sigma\_\{\\varepsilon\}^\{2\}\+O\(\\epsilon\_\{\\times\}\)\. SubstitutingM^k\(N/2\)\\widehat\{M\}\_\{k\}^\{\(N/2\)\}forM~t\\widetilde\{M\}\_\{t\}contributes\|ut⊤​\(M^k\(N/2\)−M~t\)​ut\|=O​\(1/N\)\|u\_\{t\}^\{\\top\}\(\\widehat\{M\}\_\{k\}^\{\(N/2\)\}\-\\widetilde\{M\}\_\{t\}\)u\_\{t\}\|=O\(\\sqrt\{1/N\}\)on the matrix\-Bernstein event\. The squared noiseεt2\\varepsilon\_\{t\}^\{2\}is sub\-exponential with meanσε2\\sigma\_\{\\varepsilon\}^\{2\}; the sample mean ofN/2N/2i\.i\.d\. samples concentrates at rateσε2​log⁡\(1/δ\)/N\\sigma\_\{\\varepsilon\}^\{2\}\\sqrt\{\\log\(1/\\delta\)/N\}by Bernstein’s inequality for sub\-exponential variables\. ∎

This chain \(Lemmas[C\.4](https://arxiv.org/html/2605.20269#A3.Thmtheorem4)–[C\.7](https://arxiv.org/html/2605.20269#A3.Thmtheorem7), Theorem[C\.8](https://arxiv.org/html/2605.20269#A3.Thmtheorem8), Corollary[C\.10](https://arxiv.org/html/2605.20269#A3.Thmtheorem10), Proposition[C\.9](https://arxiv.org/html/2605.20269#A3.Thmtheorem9)\) gives a self\-contained subspace\-recovery guarantee for SPSC\.

### C\.3Necessity of the probe\-side conditions

The probe\-side conditions of §[2](https://arxiv.org/html/2605.20269#S2)\(known probe distributionQQwith full\-dimensional coverage, known noise variance, and bounded state\-noise coupling‖𝔼​\[εt​θt\]‖≤ϵ×\\\|\\mathbb\{E\}\[\\varepsilon\_\{t\}\\theta\_\{t\}\]\\\|\\leq\\epsilon\_\{\\times\}\) are each individually necessary for identifiability of the predictable second momentM~t\\widetilde\{M\}\_\{t\}from single\-play scalar rewards\. The three propositions below construct two distinct conditional second moments generating identical observation laws when the named condition is dropped\.

*Scope\.*These propositions establish identifiability obstructions in the unrestricted\-second\-moment problem and serve as necessity checks for the probe\-side modeling assumptions\. They are not lower bounds inside the rank\-rrLDS class of §[2](https://arxiv.org/html/2605.20269#S2): the counterexample second moments need not be rank\-rror compatible with a stable LDSwtw\_\{t\}\.

###### Proposition C\.12\(Non\-identification without known noise variance\)\.

Fixtt\. Supposeϵ×=0\\epsilon\_\{\\times\}=0\(exact state\-noise orthogonality\) and full probe coverage hold, but the conditional noise variancevt​\(u\):=𝔼​\[εt2∣ℋt−1,u\]v\_\{t\}\(u\):=\\mathbb\{E\}\[\\varepsilon\_\{t\}^\{2\}\\mid\\mathcal\{H\}\_\{t\-1\},u\]is completely unknown\. ThenM~t\\widetilde\{M\}\_\{t\}is not identifiable from the observablegt​\(u\):=𝔼​\[yt2∣ℋt−1,u\]g\_\{t\}\(u\):=\\mathbb\{E\}\[y\_\{t\}^\{2\}\\mid\\mathcal\{H\}\_\{t\-1\},u\]\.

###### Proof\.

gt​\(u\)=u⊤​M~t​u\+vt​\(u\)g\_\{t\}\(u\)=u^\{\\top\}\\widetilde\{M\}\_\{t\}u\+v\_\{t\}\(u\)\. For any smallδ∈\(0,σε2/L2\]\\delta\\in\(0,\\sigma\_\{\\varepsilon\}^\{2\}/L^\{2\}\], setH:=δ​IdH:=\\delta I\_\{d\}and defineM~t′:=M~t\+H\\widetilde\{M\}\_\{t\}^\{\\prime\}:=\\widetilde\{M\}\_\{t\}\+Handvt′​\(u\):=vt​\(u\)−u⊤​H​u=vt​\(u\)−δ​‖u‖2v\_\{t\}^\{\\prime\}\(u\):=v\_\{t\}\(u\)\-u^\{\\top\}Hu=v\_\{t\}\(u\)\-\\delta\\\|u\\\|^\{2\}\. On the truncation support‖u‖≤L\\\|u\\\|\\leq L,vt′​\(u\)≥σε2−δ​L2≥0v\_\{t\}^\{\\prime\}\(u\)\\geq\\sigma\_\{\\varepsilon\}^\{2\}\-\\delta L^\{2\}\\geq 0, sovt′v\_\{t\}^\{\\prime\}is a valid conditional variance\. The two pairs\(M~t,vt\)\(\\widetilde\{M\}\_\{t\},v\_\{t\}\)and\(M~t′,vt′\)\(\\widetilde\{M\}\_\{t\}^\{\\prime\},v\_\{t\}^\{\\prime\}\)produce identical observablesgtg\_\{t\}, soM~t≠M~t′\\widetilde\{M\}\_\{t\}\\neq\\widetilde\{M\}\_\{t\}^\{\\prime\}are indistinguishable\. ∎

###### Proposition C\.13\(Non\-identification without bounded state\-noise coupling\)\.

Fixtt\. Supposeσε2\\sigma\_\{\\varepsilon\}^\{2\}is known and probe coverage is full, but the cross\-momentmt​\(u\):=𝔼​\[θt​εt∣ℋt−1,u\]m\_\{t\}\(u\):=\\mathbb\{E\}\[\\theta\_\{t\}\\varepsilon\_\{t\}\\mid\\mathcal\{H\}\_\{t\-1\},u\]is arbitrary \(no boundϵ×\\epsilon\_\{\\times\}\)\. ThenM~t\\widetilde\{M\}\_\{t\}is not identifiable fromht​\(u\):=𝔼​\[yt2−σε2∣ℋt−1,u\]h\_\{t\}\(u\):=\\mathbb\{E\}\[y\_\{t\}^\{2\}\-\\sigma\_\{\\varepsilon\}^\{2\}\\mid\\mathcal\{H\}\_\{t\-1\},u\]\.

###### Proof\.

ht​\(u\)=u⊤​M~t​u\+2​u⊤​mt​\(u\)h\_\{t\}\(u\)=u^\{\\top\}\\widetilde\{M\}\_\{t\}u\+2u^\{\\top\}m\_\{t\}\(u\)\. For any nonzero symmetricHH, letM~t′:=M~t\+H\\widetilde\{M\}\_\{t\}^\{\\prime\}:=\\widetilde\{M\}\_\{t\}\+Handmt′​\(u\):=mt​\(u\)−12​H​um\_\{t\}^\{\\prime\}\(u\):=m\_\{t\}\(u\)\-\\tfrac\{1\}\{2\}Hu\. Thenu⊤​M~t′​u\+2​u⊤​mt′​\(u\)=u⊤​M~t​u\+u⊤​H​u\+2​u⊤​mt​\(u\)−u⊤​H​u=ht​\(u\)u^\{\\top\}\\widetilde\{M\}\_\{t\}^\{\\prime\}u\+2u^\{\\top\}m\_\{t\}^\{\\prime\}\(u\)=u^\{\\top\}\\widetilde\{M\}\_\{t\}u\+u^\{\\top\}Hu\+2u^\{\\top\}m\_\{t\}\(u\)\-u^\{\\top\}Hu=h\_\{t\}\(u\)for everyuu, so the two pairs are observationally equivalent\. ∎

###### Proposition C\.14\(Non\-identification without full\-dimensional coverage\)\.

Suppose probe actionsutu\_\{t\}lie in a proper subspaceS⊊ℝdS\\subsetneq\\mathbb\{R\}^\{d\}almost surely\. ThenM~t\\widetilde\{M\}\_\{t\}is not identifiable from either linear rewardsyty\_\{t\}or quadratic observationsyt2y\_\{t\}^\{2\}\.

###### Proof\.

Pick any nonzero symmetricHHsupported onS⟂S^\{\\perp\}\(i\.e\.H=PS⟂​H​PS⟂≠0H=P\_\{S^\{\\perp\}\}HP\_\{S^\{\\perp\}\}\\neq 0, possible sinceS⟂≠\{0\}S^\{\\perp\}\\neq\\\{0\\\}\)\. For everyu∈Su\\in S,H​u∈S⟂Hu\\in S^\{\\perp\}andu⊤​H​u=0u^\{\\top\}Hu=0, sou⊤​\(M~t\+H\)​u=u⊤​M~t​uu^\{\\top\}\(\\widetilde\{M\}\_\{t\}\+H\)u=u^\{\\top\}\\widetilde\{M\}\_\{t\}uandu⊤​\(θt\+H​z\)=u⊤​θtu^\{\\top\}\(\\theta\_\{t\}\+Hz\)=u^\{\\top\}\\theta\_\{t\}for anyz∈S⟂z\\in S^\{\\perp\}\. Thus the pairs\(θt,M~t\)\(\\theta\_\{t\},\\widetilde\{M\}\_\{t\}\)and\(θt\+H​z,M~t\+H\)\(\\theta\_\{t\}\+Hz,\\widetilde\{M\}\_\{t\}\+H\)generate identical observations on all probe rounds, soM~t\\widetilde\{M\}\_\{t\}is not identifiable\. ∎

### C\.4Lemmas for the interleaved analysis

###### Lemma C\.16\(Projected nonstationary UCB with time\-varying basis\)\.

Fix a segmentℐk\\mathcal\{I\}\_\{k\}\. For each exploit roundt∈Ekt\\in E\_\{k\}, defineUt:=U^t−1U\_\{t\}:=\\widehat\{U\}\_\{t\-1\},Pt:=Ut​Ut⊤P\_\{t\}:=U\_\{t\}U\_\{t\}^\{\\top\},zt​\(x\):=Ut⊤​xz\_\{t\}\(x\):=U\_\{t\}^\{\\top\}x,at⋆:=Ut⊤​θta\_\{t\}^\{\\star\}:=U\_\{t\}^\{\\top\}\\theta\_\{t\}, and \(as in Alg\.[1](https://arxiv.org/html/2605.20269#alg1)\)V~t=λ​Ir\+∑s∈𝒲tzt​\(xs\)​zt​\(xs\)⊤\\widetilde\{V\}\_\{t\}=\\lambda I\_\{r\}\+\\sum\_\{s\\in\\mathcal\{W\}\_\{t\}\}z\_\{t\}\(x\_\{s\}\)z\_\{t\}\(x\_\{s\}\)^\{\\top\},a^t=V~t−1​∑s∈𝒲tzt​\(xs\)​ys\\widehat\{a\}\_\{t\}=\\widetilde\{V\}\_\{t\}^\{\-1\}\\sum\_\{s\\in\\mathcal\{W\}\_\{t\}\}z\_\{t\}\(x\_\{s\}\)y\_\{s\}\. Assume on segmentℐk\\mathcal\{I\}\_\{k\}: \(i\) the windowed projected self\-normalized event of Lem\.[C\.3](https://arxiv.org/html/2605.20269#A3.Thmtheorem3)holds uniformly overEkE\_\{k\}; \(ii\) Assumption[C\.2](https://arxiv.org/html/2605.20269#A3.Thmtheorem2)holds; \(iii\)‖θt‖≤Sw\\\|\\theta\_\{t\}\\\|\\leq S\_\{w\},‖x‖≤R𝒜\\\|x\\\|\\leq R\_\{\\mathcal\{A\}\}forx∈𝒜tx\\in\\mathcal\{A\}\_\{t\}\. Suppose Alg\.[1](https://arxiv.org/html/2605.20269#alg1)uses an optimism correction satisfying

γt≥Cγ​Sw​\(1\+R𝒜​W/λ\)​εk,t−1\+Cγ​R𝒜​Vk,t​\(W\),\\gamma\_\{t\}\\;\\geq\\;C\_\{\\gamma\}S\_\{w\}\\Bigl\(1\+R\_\{\\mathcal\{A\}\}\\sqrt\{W/\\lambda\}\\Bigr\)\\varepsilon\_\{k,t\-1\}\\;\+\\;C\_\{\\gamma\}R\_\{\\mathcal\{A\}\}V\_\{k,t\}\(W\),\(8\)whereLW:=log⁡\(1\+W​R𝒜2/\(λ​r\)\)L\_\{W\}:=\\log\(1\+WR\_\{\\mathcal\{A\}\}^\{2\}/\(\\lambda r\)\)andVk,t​\(W\):=∑s,s\+1∈ℐk,t−W≤s<t‖θs\+1−θs‖2V\_\{k,t\}\(W\):=\\sum\_\{s,s\+1\\in\\mathcal\{I\}\_\{k\},\\,t\-W\\leq s<t\}\\\|\\theta\_\{s\+1\}\-\\theta\_\{s\}\\\|\_\{2\}\. Then on the same event,

∑t∈Ek\(maxx∈𝒜t⁡x⊤​θt−xt⊤​θt\)≤𝒪~​\(r​nk\)\+Ctv​R𝒜​Sw​\(1\+R𝒜​W/λ\)​∑t∈Ekεk,t−1\+C​R𝒜​W​Vkin\.\\sum\_\{t\\in E\_\{k\}\}\\bigl\(\\max\_\{x\\in\\mathcal\{A\}\_\{t\}\}x^\{\\top\}\\theta\_\{t\}\-x\_\{t\}^\{\\top\}\\theta\_\{t\}\\bigr\)\\;\\leq\\;\\widetilde\{\\mathcal\{O\}\}\(r\\sqrt\{n\_\{k\}\}\)\+C\_\{\\rm tv\}R\_\{\\mathcal\{A\}\}S\_\{w\}\\Bigl\(1\+R\_\{\\mathcal\{A\}\}\\sqrt\{W/\\lambda\}\\Bigr\)\\sum\_\{t\\in E\_\{k\}\}\\varepsilon\_\{k,t\-1\}\+CR\_\{\\mathcal\{A\}\}WV\_\{k\}^\{\\rm in\}\.\(9\)

###### Proof\.

Fixt∈Ekt\\in E\_\{k\}and decompose, forx∈𝒜tx\\in\\mathcal\{A\}\_\{t\},x⊤​θt=zt​\(x\)⊤​at⋆\+ζt​\(x\)x^\{\\top\}\\theta\_\{t\}=z\_\{t\}\(x\)^\{\\top\}a\_\{t\}^\{\\star\}\+\\zeta\_\{t\}\(x\)withζt​\(x\)=x⊤​\(I−Pt\)​θt\\zeta\_\{t\}\(x\)=x^\{\\top\}\(I\-P\_\{t\}\)\\theta\_\{t\}\. Sinceθt=Pk⋆​θt\\theta\_\{t\}=P\_\{k\}^\{\\star\}\\theta\_\{t\}within segmentkkand‖\(I−Pt\)​Pk⋆‖op=‖Pt−Pk⋆‖op=εk,t−1\\\|\(I\-P\_\{t\}\)P\_\{k\}^\{\\star\}\\\|\_\{\\mathrm\{op\}\}=\\\|P\_\{t\}\-P\_\{k\}^\{\\star\}\\\|\_\{\\mathrm\{op\}\}=\\varepsilon\_\{k,t\-1\}for two same\-rank orthogonal projectors,

\|ζt​\(x\)\|≤R𝒜​Sw​εk,t−1\.\|\\zeta\_\{t\}\(x\)\|\\leq R\_\{\\mathcal\{A\}\}S\_\{w\}\\,\\varepsilon\_\{k,t\-1\}\.\(10\)
Rewrite the windowed regression in basisUtU\_\{t\}\. Fors∈𝒲ts\\in\\mathcal\{W\}\_\{t\},ys=zt​\(xs\)⊤​at⋆\+bs,t\+εsy\_\{s\}=z\_\{t\}\(x\_\{s\}\)^\{\\top\}a\_\{t\}^\{\\star\}\+b\_\{s,t\}\+\\varepsilon\_\{s\}with biasbs,t=xs⊤​\(I−Pt\)​θs\+xs⊤​Pt​\(θs−θt\)b\_\{s,t\}=x\_\{s\}^\{\\top\}\(I\-P\_\{t\}\)\\theta\_\{s\}\+x\_\{s\}^\{\\top\}P\_\{t\}\(\\theta\_\{s\}\-\\theta\_\{t\}\)\. The first term has\|xs⊤​\(I−Pt\)​θs\|≤R𝒜​Sw​εk,t−1\|x\_\{s\}^\{\\top\}\(I\-P\_\{t\}\)\\theta\_\{s\}\|\\leq R\_\{\\mathcal\{A\}\}S\_\{w\}\\varepsilon\_\{k,t\-1\}\(againθs=Pk⋆​θs\\theta\_\{s\}=P\_\{k\}^\{\\star\}\\theta\_\{s\}\)\. The second is at mostR𝒜​∑u=st−1‖θu\+1−θu‖2R\_\{\\mathcal\{A\}\}\\sum\_\{u=s\}^\{t\-1\}\\\|\\theta\_\{u\+1\}\-\\theta\_\{u\}\\\|\_\{2\}\.

By definition,a^t−at⋆=V~t−1​∑s∈𝒲tzt​\(xs\)​εs\+V~t−1​∑s∈𝒲tzt​\(xs\)​bs,t−λ​V~t−1​at⋆\.\\widehat\{a\}\_\{t\}\-a\_\{t\}^\{\\star\}=\\widetilde\{V\}\_\{t\}^\{\-1\}\\sum\_\{s\\in\\mathcal\{W\}\_\{t\}\}z\_\{t\}\(x\_\{s\}\)\\varepsilon\_\{s\}\+\\widetilde\{V\}\_\{t\}^\{\-1\}\\sum\_\{s\\in\\mathcal\{W\}\_\{t\}\}z\_\{t\}\(x\_\{s\}\)b\_\{s,t\}\-\\lambda\\widetilde\{V\}\_\{t\}^\{\-1\}a\_\{t\}^\{\\star\}\.On the self\-normalized event of Lem\.[C\.3](https://arxiv.org/html/2605.20269#A3.Thmtheorem3)the noise\+ridge contribution has weighted norm≤βt\(r,W\)=𝒪~​\(r\)\\leq\\beta\_\{t\}^\{\(r,W\)\}=\\widetilde\{\\mathcal\{O\}\}\(\\sqrt\{r\}\)\.

For the deterministic subspace\-bias part, letbtsub∈ℝ\|𝒲t\|b\_\{t\}^\{\\rm sub\}\\in\\mathbb\{R\}^\{\|\\mathcal\{W\}\_\{t\}\|\}have entriesxs⊤​\(I−Pt\)​θsx\_\{s\}^\{\\top\}\(I\-P\_\{t\}\)\\theta\_\{s\}, with‖btsub‖∞≤R𝒜​Sw​εk,t−1\\\|b\_\{t\}^\{\\rm sub\}\\\|\_\{\\infty\}\\leq R\_\{\\mathcal\{A\}\}S\_\{w\}\\varepsilon\_\{k,t\-1\}\. LetZtZ\_\{t\}be the matrix with rowszt​\(xs\)⊤z\_\{t\}\(x\_\{s\}\)^\{\\top\},s∈𝒲ts\\in\\mathcal\{W\}\_\{t\}\. Since∑s∈𝒲tzt​\(xs\)​zt​\(xs\)⊤=Zt⊤​Zt⪯V~t\\sum\_\{s\\in\\mathcal\{W\}\_\{t\}\}z\_\{t\}\(x\_\{s\}\)z\_\{t\}\(x\_\{s\}\)^\{\\top\}=Z\_\{t\}^\{\\top\}Z\_\{t\}\\preceq\\widetilde\{V\}\_\{t\},‖V~t−1/2​Zt⊤‖op≤1\\\|\\widetilde\{V\}\_\{t\}^\{\-1/2\}Z\_\{t\}^\{\\top\}\\\|\_\{\\mathrm\{op\}\}\\leq 1, hence

‖∑s∈𝒲tzt​\(xs\)​bs,tsub‖V~t−12=‖V~t−1/2​Zt⊤​btsub‖22≤‖btsub‖22≤\|𝒲t\|​‖btsub‖∞2≤W​R𝒜2​Sw2​εk,t−12,\\Bigl\\\|\\sum\_\{s\\in\\mathcal\{W\}\_\{t\}\}z\_\{t\}\(x\_\{s\}\)b\_\{s,t\}^\{\\rm sub\}\\Bigr\\\|\_\{\\widetilde\{V\}\_\{t\}^\{\-1\}\}^\{2\}=\\\|\\widetilde\{V\}\_\{t\}^\{\-1/2\}Z\_\{t\}^\{\\top\}b\_\{t\}^\{\\rm sub\}\\\|\_\{2\}^\{2\}\\leq\\\|b\_\{t\}^\{\\rm sub\}\\\|\_\{2\}^\{2\}\\leq\|\\mathcal\{W\}\_\{t\}\|\\,\\\|b\_\{t\}^\{\\rm sub\}\\\|\_\{\\infty\}^\{2\}\\leq WR\_\{\\mathcal\{A\}\}^\{2\}S\_\{w\}^\{2\}\\varepsilon\_\{k,t\-1\}^\{2\},so the correspondingV~t−1\\widetilde\{V\}\_\{t\}^\{\-1\}\-norm is at mostR𝒜​Sw​W​εk,t−1R\_\{\\mathcal\{A\}\}S\_\{w\}\\sqrt\{W\}\\,\\varepsilon\_\{k,t\-1\}\. Therefore for anyxx,\|zt​\(x\)⊤​V~t−1​∑szt​\(xs\)​bs,tsub\|≤R𝒜​Sw​W​εk,t−1​wt​\(x\)\|z\_\{t\}\(x\)^\{\\top\}\\widetilde\{V\}\_\{t\}^\{\-1\}\\sum\_\{s\}z\_\{t\}\(x\_\{s\}\)b\_\{s,t\}^\{\\rm sub\}\|\\leq R\_\{\\mathcal\{A\}\}S\_\{w\}\\sqrt\{W\}\\,\\varepsilon\_\{k,t\-1\}\\,w\_\{t\}\(x\), and sincewt​\(x\)≤‖x‖/λw\_\{t\}\(x\)\\leq\\\|x\\\|/\\sqrt\{\\lambda\}, this is bounded byR𝒜​Sw​W/λ​εk,t−1​‖x‖R\_\{\\mathcal\{A\}\}S\_\{w\}\\sqrt\{W/\\lambda\}\\,\\varepsilon\_\{k,t\-1\}\\\|x\\\|, a quantity dominated by theγt​‖x‖\\gamma\_\{t\}\\\|x\\\|correction in \([8](https://arxiv.org/html/2605.20269#A3.E8)\)\. The drift\-bias part contributes≤C​R𝒜​W​Vkin\\leq CR\_\{\\mathcal\{A\}\}WV\_\{k\}^\{\\rm in\}in total by the standard windowed argument \(each increment appears in≤W\\leq Wwindows\)\.

By the optimism index in Alg\.[1](https://arxiv.org/html/2605.20269#alg1), withxt⋆=arg⁡maxx∈𝒜t⁡x⊤​θtx\_\{t\}^\{\\star\}=\\arg\\max\_\{x\\in\\mathcal\{A\}\_\{t\}\}x^\{\\top\}\\theta\_\{t\}, the instantaneous regret obeys

Δt≤2​βt\(r,W\)​wt​\(xt\)\+Ctv​R𝒜​Sw​\(1\+R𝒜​W/λ\)​εk,t−1\+dt,\\Delta\_\{t\}\\leq 2\\beta\_\{t\}^\{\(r,W\)\}w\_\{t\}\(x\_\{t\}\)\+C\_\{\\rm tv\}R\_\{\\mathcal\{A\}\}S\_\{w\}\\Bigl\(1\+R\_\{\\mathcal\{A\}\}\\sqrt\{W/\\lambda\}\\Bigr\)\\varepsilon\_\{k,t\-1\}\+d\_\{t\},where∑tdt≤C​R𝒜​W​Vkin\\sum\_\{t\}d\_\{t\}\\leq CR\_\{\\mathcal\{A\}\}WV\_\{k\}^\{\\rm in\}\. Cauchy–Schwarz together with Assumption[C\.2](https://arxiv.org/html/2605.20269#A3.Thmtheorem2)gives∑t∈Ekβt\(r,W\)​wt​\(xt\)≤\(supt∈Ekβt\(r,W\)\)​nk⋅2​Cpot​r​LW=𝒪~​\(r​nk\)\\sum\_\{t\\in E\_\{k\}\}\\beta\_\{t\}^\{\(r,W\)\}w\_\{t\}\(x\_\{t\}\)\\leq\\bigl\(\\sup\_\{t\\in E\_\{k\}\}\\beta\_\{t\}^\{\(r,W\)\}\\bigr\)\\sqrt\{n\_\{k\}\\cdot 2C\_\{\\rm pot\}rL\_\{W\}\}=\\widetilde\{\\mathcal\{O\}\}\(r\\sqrt\{n\_\{k\}\}\)\(usingβt\(r,W\)=𝒪~​\(r\)\\beta\_\{t\}^\{\(r,W\)\}=\\widetilde\{\\mathcal\{O\}\}\(\\sqrt\{r\}\)\)\. Summing yields \([9](https://arxiv.org/html/2605.20269#A3.E9)\)\. ∎

###### Lemma C\.17\(Uniform prefix subspace concentration\)\.

Under the probe\-side assumptions of §[2](https://arxiv.org/html/2605.20269#S2), scaled\-sphere probes, exact centeringσ^2=σε2\\widehat\{\\sigma\}^\{2\}=\\sigma\_\{\\varepsilon\}^\{2\}, andλmin\>0\\lambda\_\{\\min\}\>0, there exist constantsCsub,C0\>0C\_\{\\rm sub\},C\_\{0\}\>0such that, with probability at least1−δ/31\-\\delta/3, simultaneously for all segmentskkand all roundst∈ℐkt\\in\\mathcal\{I\}\_\{k\},

εk,t≤1​if​qk​\(t\)<q⋆,εk,t≤Csub​log⁡\(2​K​d​T/δ\)/qk​\(t\)​if​qk​\(t\)≥q⋆,\\varepsilon\_\{k,t\}\\leq 1\\text\{ if \}q\_\{k\}\(t\)<q^\{\\star\},\\qquad\\varepsilon\_\{k,t\}\\leq C\_\{\\rm sub\}\\sqrt\{\\log\(2KdT/\\delta\)/q\_\{k\}\(t\)\}\\text\{ if \}q\_\{k\}\(t\)\\geq q^\{\\star\},whereq⋆:=C0​log⁡\(2​K​d​T/δ\)/λmin2q^\{\\star\}:=C\_\{0\}\\log\(2KdT/\\delta\)/\\lambda\_\{\\min\}^\{2\}\.

###### Proof\.

For a fixed segmentkkand probe\-prefix sizeqq, the lifted probe estimatorq−1​∑s∈𝒯k:s<tGsq^\{\-1\}\\sum\_\{s\\in\\mathcal\{T\}\_\{k\}:s<t\}G\_\{s\}satisfies a matrix Bernstein/Freedman bound \(Thm\.[C\.8](https://arxiv.org/html/2605.20269#A3.Thmtheorem8)\) at deviationC​log⁡\(2​K​d​T/δ\)/qC\\sqrt\{\\log\(2KdT/\\delta\)/q\}with probability≥1−δ/\(3​K​T\)\\geq 1\-\\delta/\(3KT\)\. By Lem\.[C\.1](https://arxiv.org/html/2605.20269#A3.Thmtheorem1)the predictable probe\-timerrth eigenvalue is≥λmin\\geq\\lambda\_\{\\min\}\. Wheneverq≥q⋆=C0​log⁡\(2​K​d​T/δ\)/λmin2q\\geq q^\{\\star\}=C\_\{0\}\\log\(2KdT/\\delta\)/\\lambda\_\{\\min\}^\{2\}the perturbation is at most a fixed fraction of the eigengap, and Davis–Kahan \(Cor\.[C\.10](https://arxiv.org/html/2605.20269#A3.Thmtheorem10)\) gives‖P^t−Pk⋆‖op≤Csub​log⁡\(2​K​d​T/δ\)/q\\\|\\widehat\{P\}\_\{t\}\-P\_\{k\}^\{\\star\}\\\|\_\{\\mathrm\{op\}\}\\leq C\_\{\\rm sub\}\\sqrt\{\\log\(2KdT/\\delta\)/q\}\. A union bound over allKKsegments and all at mostTTprobe prefixes yields the simultaneous statement; forq<q⋆q<q^\{\\star\}we use the trivial bound‖P^t−Pk⋆‖op≤1\\\|\\widehat\{P\}\_\{t\}\-P\_\{k\}^\{\\star\}\\\|\_\{\\mathrm\{op\}\}\\leq 1\. ∎

###### Lemma C\.18\(Cumulative interleaved subspace error\)\.

On the event of Lemma[C\.17](https://arxiv.org/html/2605.20269#A3.Thmtheorem17), for every segmentkk,

∑t∈Ekεk,t−1≤C​log⁡\(2​K​d​T/δ\)​ℓkmk\+C​q⋆​ℓkmk\.\\sum\_\{t\\in E\_\{k\}\}\\varepsilon\_\{k,t\-1\}\\;\\leq\\;C\\sqrt\{\\log\(2KdT/\\delta\)\}\\,\\frac\{\\ell\_\{k\}\}\{\\sqrt\{m\_\{k\}\}\}\\;\+\\;C\\,\\frac\{q^\{\\star\}\\ell\_\{k\}\}\{m\_\{k\}\}\.\(11\)

###### Proof\.

Group exploit rounds byj=qk​\(t−1\)j=q\_\{k\}\(t\-1\)\. By the balanced\-schedule condition \([B](https://arxiv.org/html/2605.20269#A3.Ex4)\) each group has at mosta0​⌈ℓk/mk⌉a\_\{0\}\\lceil\\ell\_\{k\}/m\_\{k\}\\rceilexploit rounds\. Forj<q⋆j<q^\{\\star\}useεk,t−1≤1\\varepsilon\_\{k,t\-1\}\\leq 1, contributingC​q⋆​ℓk/mkCq^\{\\star\}\\ell\_\{k\}/m\_\{k\}\. Forj≥q⋆j\\geq q^\{\\star\}, Lemma[C\.17](https://arxiv.org/html/2605.20269#A3.Thmtheorem17)givesεk,t−1≤Csub​log⁡\(2​K​d​T/δ\)/j\\varepsilon\_\{k,t\-1\}\\leq C\_\{\\rm sub\}\\sqrt\{\\log\(2KdT/\\delta\)/j\}, so∑j=q⋆mkj−1/2≤2​mk\\sum\_\{j=q^\{\\star\}\}^\{m\_\{k\}\}j^\{\-1/2\}\\leq 2\\sqrt\{m\_\{k\}\}yields the first term\. ∎

### C\.5Proof of Theorem[4\.1](https://arxiv.org/html/2605.20269#S4.Thmtheorem1)

Fix segmentℐk\\mathcal\{I\}\_\{k\}\. We decompose the costed regret onℐk\\mathcal\{I\}\_\{k\}into probe regret and exploitation regret\.

#### Probe regret\.

On a probe roundt∈𝒯kt\\in\\mathcal\{T\}\_\{k\}, Alg\.[1](https://arxiv.org/html/2605.20269#alg1)playsxt=ut∼Qx\_\{t\}=u\_\{t\}\\sim Qrather than an action in𝒜t\\mathcal\{A\}\_\{t\}\. Since‖x‖≤R𝒜\\\|x\\\|\\leq R\_\{\\mathcal\{A\}\}forx∈𝒜tx\\in\\mathcal\{A\}\_\{t\},‖ut‖≤RQ\\\|u\_\{t\}\\\|\\leq R\_\{Q\}, and‖θt‖≤Sw\\\|\\theta\_\{t\}\\\|\\leq S\_\{w\},maxx∈𝒜t⁡x⊤​θt−ut⊤​θt≤\(R𝒜\+RQ\)​Sw\\max\_\{x\\in\\mathcal\{A\}\_\{t\}\}x^\{\\top\}\\theta\_\{t\}\-u\_\{t\}^\{\\top\}\\theta\_\{t\}\\leq\(R\_\{\\mathcal\{A\}\}\+R\_\{Q\}\)S\_\{w\}, plus probe costcc\. So each probe contributes at mostA:=\(R𝒜\+RQ\)​Sw\+cA:=\(R\_\{\\mathcal\{A\}\}\+R\_\{Q\}\)S\_\{w\}\+c, givingRegprobe​\(ℐk\)≤A​mk\\mathrm\{Reg\}\_\{\\rm probe\}\(\\mathcal\{I\}\_\{k\}\)\\leq Am\_\{k\}\.

#### Exploitation regret\.

By Lemmas[C\.16](https://arxiv.org/html/2605.20269#A3.Thmtheorem16)and[C\.18](https://arxiv.org/html/2605.20269#A3.Thmtheorem18),

Regexploit​\(ℐk\)≤𝒪~​\(r​nk\)\+B​ℓkmk\+C​R𝒜​Sw​\(1\+R𝒜​W/λ\)​q⋆​ℓkmk\+C​R𝒜​W​Vkin,\\mathrm\{Reg\}\_\{\\rm exploit\}\(\\mathcal\{I\}\_\{k\}\)\\leq\\widetilde\{\\mathcal\{O\}\}\(r\\sqrt\{n\_\{k\}\}\)\+B\\,\\frac\{\\ell\_\{k\}\}\{\\sqrt\{m\_\{k\}\}\}\+CR\_\{\\mathcal\{A\}\}S\_\{w\}\\Bigl\(1\+R\_\{\\mathcal\{A\}\}\\sqrt\{W/\\lambda\}\\Bigr\)\\frac\{q^\{\\star\}\\ell\_\{k\}\}\{m\_\{k\}\}\+CR\_\{\\mathcal\{A\}\}WV\_\{k\}^\{\\rm in\},absorbing constants and logs intoB=C​R𝒜​Sw​\(1\+R𝒜​W/λ\)​log⁡\(2​K​d​T/δ\)B=CR\_\{\\mathcal\{A\}\}S\_\{w\}\(1\+R\_\{\\mathcal\{A\}\}\\sqrt\{W/\\lambda\}\)\\sqrt\{\\log\(2KdT/\\delta\)\}\.

#### Per\-segment bound\.

Combining,

DynReg\(c\)​\(ℐk\)≤𝒪~​\(r​nk\)\+A​mk\+B​ℓkmk\+𝒪~​\(q⋆​ℓkmk\)\+C​R𝒜​W​Vkin\.\\mathrm\{DynReg\}^\{\(c\)\}\(\\mathcal\{I\}\_\{k\}\)\\leq\\widetilde\{\\mathcal\{O\}\}\(r\\sqrt\{n\_\{k\}\}\)\+Am\_\{k\}\+B\\,\\frac\{\\ell\_\{k\}\}\{\\sqrt\{m\_\{k\}\}\}\+\\widetilde\{\\mathcal\{O\}\}\\\!\\Bigl\(\\frac\{q^\{\\star\}\\ell\_\{k\}\}\{m\_\{k\}\}\\Bigr\)\+CR\_\{\\mathcal\{A\}\}WV\_\{k\}^\{\\rm in\}\.\(12\)

#### Optimizing the probe\-estimation tradeoff\.

Ignoring the lower\-order burn\-in term, minimizefk​\(m\):=A​m\+B​ℓk​m−1/2f\_\{k\}\(m\):=Am\+B\\ell\_\{k\}m^\{\-1/2\}\. Settingfk′​\(m\)=A−B​ℓk/\(2​m3/2\)=0f\_\{k\}^\{\\prime\}\(m\)=A\-B\\ell\_\{k\}/\(2m^\{3/2\}\)=0givesmk⋆=\(B​ℓk/\(2​A\)\)2/3m\_\{k\}^\{\\star\}=\(B\\ell\_\{k\}/\(2A\)\)^\{2/3\}, andA​mk⋆\+B​ℓk/mk⋆≤C​A1/3​B2/3​ℓk2/3Am\_\{k\}^\{\\star\}\+B\\ell\_\{k\}/\\sqrt\{m\_\{k\}^\{\\star\}\}\\leq C\\,A^\{1/3\}B^\{2/3\}\\ell\_\{k\}^\{2/3\}\. Atmk⋆m\_\{k\}^\{\\star\}the burn\-in contribution is𝒪~​\(ℓk1/3/λmin2\)\\widetilde\{\\mathcal\{O\}\}\(\\ell\_\{k\}^\{1/3\}/\\lambda\_\{\\min\}^\{2\}\)\(after absorbingA,BA,Bconstants\)\. Ifℓk<q⋆\\ell\_\{k\}<q^\{\\star\}, the segment is charged trivially byO​\(ℓk\)O\(\\ell\_\{k\}\), absorbed into the same burn\-in order\. Hence

DynReg\(c\)​\(ℐk\)≤𝒪~​\(r​nk\)\+𝒪~​\(A1/3​B2/3​ℓk2/3\)\+𝒪~​\(ℓk1/3/λmin2\)\+C​R𝒜​W​Vkin\.\\mathrm\{DynReg\}^\{\(c\)\}\(\\mathcal\{I\}\_\{k\}\)\\leq\\widetilde\{\\mathcal\{O\}\}\(r\\sqrt\{n\_\{k\}\}\)\+\\widetilde\{\\mathcal\{O\}\}\\\!\\bigl\(A^\{1/3\}B^\{2/3\}\\ell\_\{k\}^\{2/3\}\\bigr\)\+\\widetilde\{\\mathcal\{O\}\}\\\!\\bigl\(\\ell\_\{k\}^\{1/3\}/\\lambda\_\{\\min\}^\{2\}\\bigr\)\+CR\_\{\\mathcal\{A\}\}WV\_\{k\}^\{\\rm in\}\.\(13\)

#### Sum over segments\.

By Cauchy–Schwarz,∑kr​nk≤r​K​T\\sum\_\{k\}r\\sqrt\{n\_\{k\}\}\\leq r\\sqrt\{KT\}\. By Hölder,∑kℓk2/3≤K1/3​T2/3\\sum\_\{k\}\\ell\_\{k\}^\{2/3\}\\leq K^\{1/3\}T^\{2/3\}and∑kℓk1/3≤K2/3​T1/3\\sum\_\{k\}\\ell\_\{k\}^\{1/3\}\\leq K^\{2/3\}T^\{1/3\}, and∑kVkin=Vin\\sum\_\{k\}V\_\{k\}^\{\\rm in\}=V\_\{\\rm in\}\. Summing \([13](https://arxiv.org/html/2605.20269#A3.E13)\) overkkgives

DynRegT\(c\)≤𝒪~​\(r​K​T\)\+𝒪~​\(A1/3​B2/3​K1/3​T2/3\)\+𝒪~​\(K2/3​T1/3/λmin2\)\+O​\(R𝒜​W​Vin\)\.\\mathrm\{DynReg\}\_\{T\}^\{\(c\)\}\\leq\\widetilde\{\\mathcal\{O\}\}\(r\\sqrt\{KT\}\)\+\\widetilde\{\\mathcal\{O\}\}\\\!\\bigl\(A^\{1/3\}B^\{2/3\}K^\{1/3\}T^\{2/3\}\\bigr\)\+\\widetilde\{\\mathcal\{O\}\}\\\!\\bigl\(K^\{2/3\}T^\{1/3\}/\\lambda\_\{\\min\}^\{2\}\\bigr\)\+O\(R\_\{\\mathcal\{A\}\}WV\_\{\\rm in\}\)\.Union\-bounding the windowed self\-normalized event, the prefix subspace concentration, and the noise event at totalδ\\deltayields \([4](https://arxiv.org/html/2605.20269#S4.E4)\)\. For fixedKK, the leading term is𝒪~​\(r​T\)\\widetilde\{\\mathcal\{O\}\}\(r\\sqrt\{T\}\), the probe term is𝒪~​\(T2/3\)\\widetilde\{\\mathcal\{O\}\}\(T^\{2/3\}\), and the burn\-in term𝒪~​\(T1/3\)\\widetilde\{\\mathcal\{O\}\}\(T^\{1/3\}\)is lower order\. WhenVin=0V\_\{\\rm in\}=0, the third term vanishes and we recover Corollary[4\.3](https://arxiv.org/html/2605.20269#S4.Thmtheorem3)\.∎

### C\.6Proof of Corollary[4\.4](https://arxiv.org/html/2605.20269#S4.Thmtheorem4)

By Theorem[C\.8](https://arxiv.org/html/2605.20269#A3.Thmtheorem8), with probability≥1−δ\\geq 1\-\\deltaevery eigenvalue ofM^k\\widehat\{M\}\_\{k\}is withinτkrank:=2​RX​log⁡\(2​d/δ\)/mk\\tau\_\{k\}^\{\\rm rank\}:=2R\_\{X\}\\sqrt\{\\log\(2d/\\delta\)/m\_\{k\}\}of the corresponding eigenvalue ofM¯kprobe\+B~\\bar\{M\}\_\{k\}^\{\\mathrm\{probe\}\}\+\\widetilde\{B\}\(Weyl’s inequality applied to the matrix in \([6](https://arxiv.org/html/2605.20269#A3.E6)\)\)\. The population spectrum has exactlyrreigenvalues≥λmin\\geq\\lambda\_\{\\min\}and the remainingd−rd\-rare zero \(Prop\.[C\.9](https://arxiv.org/html/2605.20269#A3.Thmtheorem9)\)\. Under the eigengap hypothesisλmin≥4​τkrank\\lambda\_\{\\min\}\\geq 4\\tau\_\{k\}^\{\\rm rank\}, thresholding at2​τkrank2\\tau\_\{k\}^\{\\rm rank\}returns exactlyrrindices with probability≥1−δ\\geq 1\-\\delta\. Condition on this event; the regret analysis of Theorem[4\.1](https://arxiv.org/html/2605.20269#S4.Thmtheorem1)applies verbatim with the estimated rank equal to the truerr, so \([4](https://arxiv.org/html/2605.20269#S4.E4)\) holds with an extraδ\\deltain the union bound\.∎

### C\.7Proof of Proposition[4\.5](https://arxiv.org/html/2605.20269#S4.Thmtheorem5)\(SPSC\-Adaptive\)

The detector statistic of Alg\.[2](https://arxiv.org/html/2605.20269#alg2)compares two non\-overlapping rolling\-window lifted\-moment estimators of lengthWdetW\_\{\\mathrm\{det\}\},M^trecent\\widehat\{M\}\_\{t\}^\{\\mathrm\{recent\}\}andM^tpast\\widehat\{M\}\_\{t\}^\{\\mathrm\{past\}\}, viaSt:=‖M^trecent−M^tpast‖opS\_\{t\}:=\\\|\\widehat\{M\}\_\{t\}^\{\\mathrm\{recent\}\}\-\\widehat\{M\}\_\{t\}^\{\\mathrm\{past\}\}\\\|\_\{\\mathrm\{op\}\}, and triggers a reset wheneverSt\>2​ηdetS\_\{t\}\>2\\eta\_\{\\mathrm\{det\}\}, whereηdet:=Csub​log⁡\(d​T/δFA\)/Wdet\\eta\_\{\\mathrm\{det\}\}:=C\_\{\\mathrm\{sub\}\}\\sqrt\{\\log\(dT/\\delta\_\{\\mathrm\{FA\}\}\)/W\_\{\\mathrm\{det\}\}\}is the calibration radius\. The proof has two parts: bounding the false\-alarm probability underH0H\_\{0\}\(no change inside the comparison window\) and bounding the detection delay underH1H\_\{1\}\(a change of sizeΔk≥2​b\\Delta\_\{k\}\\geq 2bhas occurred\), and then propagating the resulting boundary error through Theorem[4\.1](https://arxiv.org/html/2605.20269#S4.Thmtheorem1)\.

#### \(i\) False\-alarm control underH0H\_\{0\}\.

Fix a roundttand condition onH0H\_\{0\}: the predictable second moment is constant across the past and recent windows that producedM^tpast\\widehat\{M\}\_\{t\}^\{\\mathrm\{past\}\}andM^trecent\\widehat\{M\}\_\{t\}^\{\\mathrm\{recent\}\}\. Apply Theorem[C\.8](https://arxiv.org/html/2605.20269#A3.Thmtheorem8)\(matrix Bernstein for the lifted probe estimator\) to each window separately at confidenceδFA/\(2​T\)\\delta\_\{\\mathrm\{FA\}\}/\(2T\)to get

‖M^trecent−M¯trecent‖op≤ηdet,‖M^tpast−M¯tpast‖op≤ηdet,\\bigl\\\|\\widehat\{M\}\_\{t\}^\{\\mathrm\{recent\}\}\-\\bar\{M\}\_\{t\}^\{\\mathrm\{recent\}\}\\bigr\\\|\_\{\\mathrm\{op\}\}\\leq\\eta\_\{\\mathrm\{det\}\},\\qquad\\bigl\\\|\\widehat\{M\}\_\{t\}^\{\\mathrm\{past\}\}\-\\bar\{M\}\_\{t\}^\{\\mathrm\{past\}\}\\bigr\\\|\_\{\\mathrm\{op\}\}\\leq\\eta\_\{\\mathrm\{det\}\},each with probability at least1−δFA/\(2​T\)1\-\\delta\_\{\\mathrm\{FA\}\}/\(2T\), whereM¯trecent\\bar\{M\}\_\{t\}^\{\\mathrm\{recent\}\}andM¯tpast\\bar\{M\}\_\{t\}^\{\\mathrm\{past\}\}are the predictable averages on the corresponding windows\. UnderH0H\_\{0\}they coincide, so by the triangle inequalitySt≤‖M^trecent−M¯trecent‖op\+‖M^tpast−M¯tpast‖op≤2​ηdetS\_\{t\}\\leq\\\|\\widehat\{M\}\_\{t\}^\{\\mathrm\{recent\}\}\-\\bar\{M\}\_\{t\}^\{\\mathrm\{recent\}\}\\\|\_\{\\mathrm\{op\}\}\+\\\|\\widehat\{M\}\_\{t\}^\{\\mathrm\{past\}\}\-\\bar\{M\}\_\{t\}^\{\\mathrm\{past\}\}\\\|\_\{\\mathrm\{op\}\}\\leq 2\\eta\_\{\\mathrm\{det\}\}with probability at least1−δFA/T1\-\\delta\_\{\\mathrm\{FA\}\}/T, i\.e\.Pr⁡\(St\>2​ηdet∣H0\)≤δFA/T\\Pr\(S\_\{t\}\>2\\eta\_\{\\mathrm\{det\}\}\\mid H\_\{0\}\)\\leq\\delta\_\{\\mathrm\{FA\}\}/T\. A union bound overt∈\[T\]t\\in\[T\]gives total false\-alarm probability at mostδFA\\delta\_\{\\mathrm\{FA\}\}\.

#### \(ii\) Detection delay underH1H\_\{1\}\.

Letτk\\tau\_\{k\}be a true change point with eigengapΔk:=‖Pk⋆−Pk−1⋆‖op≥2​b\\Delta\_\{k\}:=\\\|P\_\{k\}^\{\\star\}\-P\_\{k\-1\}^\{\\star\}\\\|\_\{\\mathrm\{op\}\}\\geq 2bfor the thresholdb\>2​ηdetb\>2\\eta\_\{\\mathrm\{det\}\}\. Taket=τk\+Wdett=\\tau\_\{k\}\+W\_\{\\mathrm\{det\}\}: the recent window now lies entirely in segmentkkwhile the past window lies entirely in segmentk−1k\-1\. By the segment\-factorization of the predictable probe moment \(Proposition[C\.9](https://arxiv.org/html/2605.20269#A3.Thmtheorem9)\) and probe\-time excitation \(Lemma[C\.1](https://arxiv.org/html/2605.20269#A3.Thmtheorem1)\),‖M¯trecent−M¯tpast‖op≥λmin​Δk≥2​b​λmin\\\|\\bar\{M\}\_\{t\}^\{\\mathrm\{recent\}\}\-\\bar\{M\}\_\{t\}^\{\\mathrm\{past\}\}\\\|\_\{\\mathrm\{op\}\}\\geq\\lambda\_\{\\min\}\\,\\Delta\_\{k\}\\geq 2b\\lambda\_\{\\min\}\. By the same matrix\-Bernstein concentration as in \(i\),St≥‖M¯trecent−M¯tpast‖op−2​ηdet≥2​b​λmin−2​ηdet\>2​ηdetS\_\{t\}\\geq\\\|\\bar\{M\}\_\{t\}^\{\\mathrm\{recent\}\}\-\\bar\{M\}\_\{t\}^\{\\mathrm\{past\}\}\\\|\_\{\\mathrm\{op\}\}\-2\\eta\_\{\\mathrm\{det\}\}\\geq 2b\\lambda\_\{\\min\}\-2\\eta\_\{\\mathrm\{det\}\}\>2\\eta\_\{\\mathrm\{det\}\}with probability at least1−δFA/T1\-\\delta\_\{\\mathrm\{FA\}\}/T\(usingb\>2​ηdetb\>2\\eta\_\{\\mathrm\{det\}\}after absorbingλmin\\lambda\_\{\\min\}intobb\)\. Therefore the detector triggers no later thanτ^k=τk\+Wdet\\widehat\{\\tau\}\_\{k\}=\\tau\_\{k\}\+W\_\{\\mathrm\{det\}\}, giving detection delayDk≤WdetD\_\{k\}\\leq W\_\{\\mathrm\{det\}\}\.

#### \(iii\) Boundary\-error propagation\.

On the detector good eventℰdet=\{\\mathcal\{E\}\_\{\\mathrm\{det\}\}=\\bigl\\\{no false alarm and every change detected within delayDk≤Wdet\}D\_\{k\}\\leq W\_\{\\mathrm\{det\}\}\\bigr\\\}, which holds with probability at least1−δFA1\-\\delta\_\{\\mathrm\{FA\}\}by parts \(i\)\-\(ii\), the estimated boundariesτ^k\\widehat\{\\tau\}\_\{k\}satisfy\|τ^k−τk\|≤Wdet\|\\widehat\{\\tau\}\_\{k\}\-\\tau\_\{k\}\|\\leq W\_\{\\mathrm\{det\}\}\. Splitting the horizon atτ^k\\widehat\{\\tau\}\_\{k\}and applying Theorem[4\.1](https://arxiv.org/html/2605.20269#S4.Thmtheorem1)on each estimated segment, the only difference from the oracle\-boundary analysis is the contribution of the rounds in\[τk,τ^k\)\[\\tau\_\{k\},\\widehat\{\\tau\}\_\{k\}\)where the algorithm is still using the old basisU^τk−1\\widehat\{U\}\_\{\\tau\_\{k\}\-1\}on data drawn from segmentkk\. Each such round contributes at most2​R𝒜​Sw2R\_\{\\mathcal\{A\}\}S\_\{w\}to the instantaneous regret, so∑k2​R𝒜​Sw​Dk≤2​R𝒜​Sw​K​Wdet=O​\(K​Wdet\)\\sum\_\{k\}2R\_\{\\mathcal\{A\}\}S\_\{w\}D\_\{k\}\\leq 2R\_\{\\mathcal\{A\}\}S\_\{w\}\\,K\\,W\_\{\\mathrm\{det\}\}=O\(KW\_\{\\mathrm\{det\}\}\)\. Combining,

DynRegT\(c\)​\(Alg\.[2](https://arxiv.org/html/2605.20269#alg2)\)≤DynRegT\(c\)​\(Alg\.[1](https://arxiv.org/html/2605.20269#alg1)\)\+O​\(K​Wdet\)\\mathrm\{DynReg\}\_\{T\}^\{\(c\)\}\\bigl\(\\text\{Alg\.~\\ref\{alg:spsc\_adaptive\}\}\\bigr\)\\;\\leq\\;\\mathrm\{DynReg\}\_\{T\}^\{\(c\)\}\\bigl\(\\text\{Alg\.~\\ref\{alg:spsc\}\}\\bigr\)\\;\+\\;O\(KW\_\{\\mathrm\{det\}\}\)onℰdet\\mathcal\{E\}\_\{\\mathrm\{det\}\}, which is the claim\. The total failure probability isδ\+δFA\\delta\+\\delta\_\{\\mathrm\{FA\}\}, absorbed into the overallδ\\deltabudget by re\-tuning constants\.∎

## Appendix DProbe distributions: scaled sphere and Gaussian truncation

The analysis in §[C\.2](https://arxiv.org/html/2605.20269#A3.SS2)uses scaled\-sphere probesut=d​vtu\_\{t\}=\\sqrt\{d\}\\,v\_\{t\},vt∼Unif​\(𝕊d−1\)v\_\{t\}\\sim\\mathrm\{Unif\}\(\\mathbb\{S\}^\{d\-1\}\), which satisfy‖ut‖2=d\\\|u\_\{t\}\\\|\_\{2\}=\\sqrt\{d\}exactly\. No truncation is required: the matrix\-Bernstein envelopeRX=d​Rs\+Sw2R\_\{X\}=dR\_\{s\}\+S\_\{w\}^\{2\}holds deterministically given the noise\-truncation event of Lemma[C\.7](https://arxiv.org/html/2605.20269#A3.Thmtheorem7)\.

In our implementation, probes are generated viau←d​u~/‖u~‖u\\leftarrow\\sqrt\{d\}\\,\\tilde\{u\}/\\\|\\tilde\{u\}\\\|foru~∼𝒩​\(0,Id\)\\tilde\{u\}\\sim\\mathcal\{N\}\(0,I\_\{d\}\), which is exactly the scaled\-sphere distribution\.

For isotropic\-Gaussian probes \(no rescaling\),ut∼𝒩​\(0,Id\)u\_\{t\}\\sim\\mathcal\{N\}\(0,I\_\{d\}\), the Laurent–Massartχ2\\chi^\{2\}tail\[Laurent and Massart,[2000](https://arxiv.org/html/2605.20269#bib.bib24), Lem\. 1\]givesPr⁡\(‖ut‖\>L\)≤δ/T\\Pr\(\\\|u\_\{t\}\\\|\>L\)\\leq\\delta/TatL=2​d​log⁡\(2​T/δ\)L=\\sqrt\{2d\\log\(2T/\\delta\)\}; union\-bounding over\|𝒯probe\|≤T\|\\mathcal\{T\}\_\{\\mathrm\{probe\}\}\|\\leq TgivesPr⁡\(⋂t\{‖ut‖≤L\}\)≥1−δ\\Pr\(\\bigcap\_\{t\}\\\{\\\|u\_\{t\}\\\|\\leq L\\\}\)\\geq 1\-\\delta\. On this event the results of §[C\.2](https://arxiv.org/html/2605.20269#A3.SS2)apply with‖ut‖≤L\\\|u\_\{t\}\\\|\\leq L\(replacingd\\sqrt\{d\}\), adding only alog⁡\(T/δ\)\\log\(T/\\delta\)factor toRXR\_\{X\}andCsubC\_\{\\mathrm\{sub\}\}that is absorbed in𝒪~​\(⋅\)\\widetilde\{\\mathcal\{O\}\}\(\\cdot\)\.

## Appendix EAlgorithms: pseudocode and adaptive variant

This appendix gives the full pseudocode for SPSC \(oracle boundaries, Alg\.[1](https://arxiv.org/html/2605.20269#alg1)\) and SPSC\-Adaptive \(online change\-point detection, Alg\.[2](https://arxiv.org/html/2605.20269#alg2)\), and explains the adaptive design choices \(detector form, threshold, recovery phase, burn\-in\) that tie the tuning back to the guarantee of Proposition[4\.5](https://arxiv.org/html/2605.20269#S4.Thmtheorem5)\.

### E\.1SPSC \(oracle boundaries\)

Algorithm 1SPSC: Single\-Play Subspace\-Calibrated Optimism \(oracle boundaries\)1:Input:segments

\{ℐk\}k=1K\\\{\\mathcal\{I\}\_\{k\}\\\}\_\{k=1\}^\{K\}, probe schedule

𝒯probe\\mathcal\{T\}\_\{\\mathrm\{probe\}\},

λ\>0\\lambda\>0, probe distribution

QQ, rank

rr, window

WW\.

2:Initialize

U^0∈ℝd×r\\widehat\{U\}\_\{0\}\\in\\mathbb\{R\}^\{d\\times r\}arbitrarily with orthonormal columns\.

3:for

k=1,…,Kk=1,\\dots,Kdo⊳\\trianglerightouter loop over segments

4:

Macc←0M\_\{\\mathrm\{acc\}\}\\leftarrow 0;

Nk←0N\_\{k\}\\leftarrow 0;

U^t←U^t−1\\widehat\{U\}\_\{t\}\\leftarrow\\widehat\{U\}\_\{t\-1\}\.⊳\\trianglerightreset segment\-local accumulator and probe counter

5:for

t∈ℐkt\\in\\mathcal\{I\}\_\{k\}do

6:if

t∈𝒯probet\\in\\mathcal\{T\}\_\{\\mathrm\{probe\}\}then⊳\\trianglerightprobe round

7:draw

ut∼Qu\_\{t\}\\sim Q; play

xt=utx\_\{t\}=u\_\{t\}; observe

yty\_\{t\}\.

8:

st←yt2−σ^2s\_\{t\}\\leftarrow y\_\{t\}^\{2\}\-\\widehat\{\\sigma\}^\{2\};

Gt←𝒦−1​\(st​ut​ut⊤\)G\_\{t\}\\leftarrow\\mathcal\{K\}^\{\-1\}\(s\_\{t\}\\,u\_\{t\}u\_\{t\}^\{\\top\}\)\.

9:

Macc←Macc\+GtM\_\{\\mathrm\{acc\}\}\\leftarrow M\_\{\\mathrm\{acc\}\}\+G\_\{t\};

Nk←Nk\+1N\_\{k\}\\leftarrow N\_\{k\}\+1;

U^t←TopEigr⁡\(Macc/Nk\)\\widehat\{U\}\_\{t\}\\leftarrow\\operatorname\{TopEig\}\_\{r\}\(M\_\{\\mathrm\{acc\}\}/N\_\{k\}\)\.

10:else⊳\\trianglerightexploitation round

11:

𝒲t←\{s∈ℐk∖𝒯probe:t−W≤s<t\}\\mathcal\{W\}\_\{t\}\\leftarrow\\\{s\\in\\mathcal\{I\}\_\{k\}\\setminus\\mathcal\{T\}\_\{\\mathrm\{probe\}\}:t\{\-\}W\\leq s<t\\\};

zt​\(x\)←U^t−1⊤​xz\_\{t\}\(x\)\\leftarrow\\widehat\{U\}\_\{t\-1\}^\{\\top\}x\.

12:

V~t←λ​Ir\+∑s∈𝒲tzt​\(xs\)​zt​\(xs\)⊤\\widetilde\{V\}\_\{t\}\\leftarrow\\lambda I\_\{r\}\+\\sum\_\{s\\in\\mathcal\{W\}\_\{t\}\}z\_\{t\}\(x\_\{s\}\)z\_\{t\}\(x\_\{s\}\)^\{\\top\},

b~t←∑s∈𝒲tzt​\(xs\)​ys\\widetilde\{b\}\_\{t\}\\leftarrow\\sum\_\{s\\in\\mathcal\{W\}\_\{t\}\}z\_\{t\}\(x\_\{s\}\)y\_\{s\}\.

13:

a^t←V~t−1​b~t\\widehat\{a\}\_\{t\}\\leftarrow\\widetilde\{V\}\_\{t\}^\{\-1\}\\widetilde\{b\}\_\{t\}; choose

xt=arg​maxx∈𝒜t⁡\{zt​\(x\)⊤​a^t\+βt\(r,W\)​‖zt​\(x\)‖V~t−1\+γt​‖x‖2\}x\_\{t\}=\\operatorname\*\{arg\\,max\}\_\{x\\in\\mathcal\{A\}\_\{t\}\}\\bigl\\\{z\_\{t\}\(x\)^\{\\top\}\\widehat\{a\}\_\{t\}\+\\beta\_\{t\}^\{\(r,W\)\}\\\|z\_\{t\}\(x\)\\\|\_\{\\widetilde\{V\}\_\{t\}^\{\-1\}\}\+\\gamma\_\{t\}\\\|x\\\|\_\{2\}\\bigr\\\}\.

14:observe

yty\_\{t\};

U^t←U^t−1\\widehat\{U\}\_\{t\}\\leftarrow\\widehat\{U\}\_\{t\-1\}\.

15:endif

16:endfor

17:endfor

### E\.2SPSC\-Adaptive \(unknown boundaries\)

SPSC\-Adaptive recovers segment boundaries from probe data, removing the oracle assumption of Alg\.[1](https://arxiv.org/html/2605.20269#alg1)\.

#### Detector\.

At each probe round the algorithm maintains two non\-overlapping rolling\-window estimators of the lifted second moment:M^trecent\\widehat\{M\}\_\{t\}^\{\\mathrm\{recent\}\}over the lastnnprobes andM^tpast\\widehat\{M\}\_\{t\}^\{\\mathrm\{past\}\}over the segment\-accumulated probes preceding that window\. The statistic

St:=‖M^trecent−M^tpast‖opS\_\{t\}:=\\bigl\\\|\\widehat\{M\}\_\{t\}^\{\\mathrm\{recent\}\}\-\\widehat\{M\}\_\{t\}^\{\\mathrm\{past\}\}\\bigr\\\|\_\{\\mathrm\{op\}\}\(14\)is compared to a thresholdbb; wheneverSt\>bS\_\{t\}\>bthe algorithm declares a change and enters arecoveryphase\.

#### Recovery phase\.

Recovery deploysmrelearnm\_\{\\mathrm\{relearn\}\}consecutive probe rounds with no exploitation\. The block\-probe design serves two purposes: \(i\) by Proposition[C\.9](https://arxiv.org/html/2605.20269#A3.Thmtheorem9),mrelearnm\_\{\\mathrm\{relearn\}\}back\-to\-back probes produce a subspace estimateU^\\widehat\{U\}with projector error‖P^−P⋆‖op=O​\(1/mrelearn\)\\\|\\widehat\{P\}\-P^\{\\star\}\\\|\_\{\\mathrm\{op\}\}=O\(1/\\sqrt\{m\_\{\\mathrm\{relearn\}\}\}\)on a1−δ1\-\\deltaevent; \(ii\) by zeroing out stale buffers it prevents the windowed ridge estimator from carrying information from the previous regime into the new one\. Aftermrelearnm\_\{\\mathrm\{relearn\}\}rounds the algorithm transitions back tonormalprobe–exploitation interleaving with probe rateμ\\mu\.

#### Threshold calibration and detection delay\.

UnderH0H\_\{0\}\(no change\), matrix Freedman applied to the two windows givesPr⁡\(St\>2​ηdet\)≤δFA/T\\Pr\(S\_\{t\}\>2\\eta\_\{\\mathrm\{det\}\}\)\\leq\\delta\_\{\\mathrm\{FA\}\}/Twithηdet=Csub​log⁡\(d​T/δFA\)/n\\eta\_\{\\mathrm\{det\}\}=C\_\{\\mathrm\{sub\}\}\\sqrt\{\\log\(dT/\\delta\_\{\\mathrm\{FA\}\}\)/n\}; choosingb=2​ηdetb=2\\eta\_\{\\mathrm\{det\}\}and union\-bounding gives at mostδFA\\delta\_\{\\mathrm\{FA\}\}false alarms across the horizon\. UnderH1H\_\{1\}at timeτk\\tau\_\{k\}, a separationΔk≥2​b\\Delta\_\{k\}\\geq 2bforces a fire within delayDmax=2​n/μ\+τburnD\_\{\\max\}=2n/\\mu\+\\tau\_\{\\mathrm\{burn\}\}, where the2​n/μ2n/\\muterm is the time for the recent window to refill with post\-change probes, andτburn\\tau\_\{\\mathrm\{burn\}\}is a short burn\-in period after recovery that prevents the detector from firing on its own freshly\-reset state\. The overall regret overhead is2​R𝒜​Sw​∑kDk=O​\(K​Wdet\)2R\_\{\\mathcal\{A\}\}S\_\{w\}\\sum\_\{k\}D\_\{k\}=O\(KW\_\{\\mathrm\{det\}\}\), which is lower\-order in the rate of Proposition[4\.5](https://arxiv.org/html/2605.20269#S4.Thmtheorem5)\.

Algorithm 2SPSC\-Adaptive: unknown boundaries via CUSUM\-style detection1:Input:probe rate

μ∈\(0,1\)\\mu\\in\(0,1\), detection window

nn, threshold

bb, burn\-in

τburn\\tau\_\{\\mathrm\{burn\}\}, relearning budget

mrelearnm\_\{\\mathrm\{relearn\}\},

WW,

λ\\lambda\.

2:

𝚙𝚑𝚊𝚜𝚎←recovery\\mathtt\{phase\}\\leftarrow\\textsc\{recovery\};

𝚛𝚎𝚌←0\\mathtt\{rec\}\\leftarrow 0;

M^acc←0\\widehat\{M\}\_\{\\mathrm\{acc\}\}\\leftarrow 0\.

3:for

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

4:if

𝚙𝚑𝚊𝚜𝚎=recovery\\mathtt\{phase\}=\\textsc\{recovery\}then⊳\\trianglerightblock\-probe to rebuild subspace

5:probe: draw

utu\_\{t\}, play

xt=utx\_\{t\}=u\_\{t\}, observe

yty\_\{t\}; update

M^acc\\widehat\{M\}\_\{\\mathrm\{acc\}\};

𝚛𝚎𝚌\+=1\\mathtt\{rec\}\\mathrel\{\+\}=1\.

6:if

𝚛𝚎𝚌=mrelearn\\mathtt\{rec\}=m\_\{\\mathrm\{relearn\}\}then

7:

U^←TopEigr⁡\(M^acc/mrelearn\)\\widehat\{U\}\\leftarrow\\operatorname\{TopEig\}\_\{r\}\(\\widehat\{M\}\_\{\\mathrm\{acc\}\}/m\_\{\\mathrm\{relearn\}\}\); reset buffers;

𝚙𝚑𝚊𝚜𝚎←normal\\mathtt\{phase\}\\leftarrow\\textsc\{normal\}\.

8:endif

9:else⊳\\trianglerightinterleave probes at rateμ\\mu

10:ifBernoulli\(

μ\\mu\) probe roundthen

11:update lifted estimator

M^acc\\widehat\{M\}\_\{\\mathrm\{acc\}\}and refresh rolling windows\.

12:if

St\>bS\_\{t\}\>b\(Eq\.[14](https://arxiv.org/html/2605.20269#A5.E14)\) and detector is armedthen

13:

𝚙𝚑𝚊𝚜𝚎←recovery\\mathtt\{phase\}\\leftarrow\\textsc\{recovery\};

𝚛𝚎𝚌←0\\mathtt\{rec\}\\leftarrow 0; reset\.

14:endif

15:else

16:windowed projected ridge\-UCB step as in Alg\.[1](https://arxiv.org/html/2605.20269#alg1)\(exploit branch\)\.

17:endif

18:endif

19:endfor

#### Tuning used in experiments\.

Across all experiments reported in §[5](https://arxiv.org/html/2605.20269#S5)and the appendix we useμ=0\.1\\mu=0\.1,n=Wdet=50n=W\_\{\\mathrm\{det\}\}=50,τburn=100\\tau\_\{\\mathrm\{burn\}\}=100,mrelearn=30m\_\{\\mathrm\{relearn\}\}=30, andbbset from the CUSUM threshold𝚌𝚞𝚜𝚞𝚖​\_​𝚝𝚑𝚛𝚎𝚜𝚑𝚘𝚕𝚍=3\.0\\mathtt\{cusum\\\_threshold\}=3\.0\. These are held fixed across datasets and\(d,r\)\(d,r\)cells; no per\-dataset retuning is done\. Sensitivity to the probe rateμ\\muand the detection windownnis reported in §[H](https://arxiv.org/html/2605.20269#A8)\.

## Appendix FExperimental setup

#### Synthetic phase\-transition benchmark\.

θt=Bk⋆​wt\\theta\_\{t\}=B\_\{k\}^\{\\star\}w\_\{t\}with piecewise\-constant orthonormalBk⋆∈ℝd×rB\_\{k\}^\{\\star\}\\in\\mathbb\{R\}^\{d\\times r\}\. Per segment, latent state evolves aswt=Ak​wt−1\+ηt−1w\_\{t\}=A\_\{k\}w\_\{t\-1\}\+\\eta\_\{t\-1\}with spectral radiusρ​\(Ak\)=0\.99\\rho\(A\_\{k\}\)=0\.99and Gaussian innovationηt−1∼𝒩​\(0,0\.042​Ir\)\\eta\_\{t\-1\}\\sim\\mathcal\{N\}\(0,0\.04^\{2\}I\_\{r\}\)\. Reward noiseεt∼𝒩​\(0,0\.09\)\\varepsilon\_\{t\}\\sim\\mathcal\{N\}\(0,0\.09\);4040actions per round drawn i\.i\.d\. uniformly on the unit sphere\.K=10K\{=\}10segments of equal length overT=5,000T\{=\}5\{,\}000\. Probe distributionQQisotropic Gaussian, probe costc=0\.1c\{=\}0\.1, probe period5050\.

#### UCI datasets \(Covertype, Pendigits, Satimage\)\.

Features are the raw attribute vectorsϕ​\(x\)∈ℝd0\\phi\(x\)\\in\\mathbb\{R\}^\{d\_\{0\}\}reduced to ambient dimensionddvia Gaussian random projectionR∈ℝd×d0R\\in\\mathbb\{R\}^\{d\\times d\_\{0\}\}\. For Covertype, segments correspond to disjoint size\-KKcover\-type subsets of the 7 classes; for Pendigits and Satimage, to disjoint digit/class subsets,K=10K\{=\}10\. Actions at roundttare\|𝒜t\|=40\|\\mathcal\{A\}\_\{t\}\|=40examples drawn from the active segment’s class pool\. Reward is centered target label\.λ=0\.01\\lambda\{=\}0\.01, probe period1010, windowW=400W\{=\}400,δ=0\.05\\delta\{=\}0\.05,c=0\.02c\{=\}0\.02\.

#### Pixelized MNIST / Fashion\-MNIST\.

Images flattened, pixel\-normalized, then projected toddvia random projection\. Segments are class\-subset swaps as above\. Same hyperparameters as UCI datasets\.

#### MovieLens\-100K with real ratings\.

Standard MovieLens\-100K user\-item matrix centered by per\-item mean\. Featuresϕ​\(user,item\)\\phi\(\\text\{user\},\\text\{item\}\)are item\-side latent factors from a rank\-ddSVD of the observed\-entry mask; reward is the raw user rating \(11–55\), centered\. Segments correspond to disjoint time\-bucketed user cohorts,K=10K\{=\}10\. This is a*fully real*benchmark \(we do*not*generate rewards from a low\-rank surrogate\), so the data is only approximately low\-rank and provides a stringent stress test\.T=5,000T\{=\}5\{,\}000, same hyperparameters\.

#### Warfarin clinical dosing\.

IWPC cohort statistics \(∼5,700\{\\sim\}5\{,\}700patients\);d=93d\{=\}93features \(demographics, VKORC1/CYP2C9 genotype, medications, interactions\)\. Reward is negative absolute deviation from the therapeutic dose,K=8K\{=\}8patient\-cohort segments,T=5,000T\{=\}5\{,\}000,λ=1\.0\\lambda\{=\}1\.0, probe period1010,W=200W\{=\}200,c=0\.1c\{=\}0\.1, 10 seeds\.

#### Baseline hyperparameters\.

All baselines inheritλ\\lambda,δ\\deltafrom SPSC when applicable\. D\-LinUCB uses discount factor0\.9980\.998; SW\-LinUCB uses windowWW; Restart\-LinUCB restarts everyT/KT/Krounds \(i\.e\. oracle boundaries\); LinTS/SW\-LinTS use posterior varianceσ2=δ2\\sigma^\{2\}=\\delta^\{2\}\. Oracle\-LinUCB knows the trueBk⋆B\_\{k\}^\{\\star\}and runs LinUCB in the projectedℝr\\mathbb\{R\}^\{r\}\.

#### Subspace\-aware baselines \(LowOFUL, VOFUL, LowRank\-Reward\): adaptation to the piecewise\-low\-rank setting\.

The published versions of these methods do not directly apply in our setting: LowOFUL\[Junet al\.,[2019](https://arxiv.org/html/2605.20269#bib.bib3)\]requires oracle access to the rank\-rrsubspaceB⋆B^\{\\star\}; the algorithms ofLuet al\.\[[2021](https://arxiv.org/html/2605.20269#bib.bib4)\]are either theoretically optimal but not efficiently implementable \(LowGLOC\) or rely on low\-rank matrix\-completion machinery \(LowGLOC\-LP\) that does not transfer to our action\-set bandit setup; and the variance\-aware OFUL family \(VOFUL/VOFUL2\) is a full\-ddvariance\-aware confidence\-set construction with no rank exploitation\. To obtain competitive baselines for the piecewise\-low\-rank regime, each maintains its own running estimate of the segment subspace via reward\-outer\-product PCA: LowOFUL accumulatesM=∑t\(yt​xt\)​\(yt​xt\)⊤M=\\sum\_\{t\}\(y\_\{t\}x\_\{t\}\)\(y\_\{t\}x\_\{t\}\)^\{\\top\}and re\-estimates the top\-rreigenspace every2020rounds \(after a3030\-round warm\-up\); LowRank\-Reward applies the same estimator on a sliding windowW=200W\{=\}200with oracle resets at segment boundaries; VOFUL applies a variance\-weighted variantM=∑twt​\(yt​xt\)​\(yt​xt\)⊤M=\\sum\_\{t\}w\_\{t\}\\,\(y\_\{t\}x\_\{t\}\)\(y\_\{t\}x\_\{t\}\)^\{\\top\}withwt=1/\(‖xt‖2\+σε2\)w\_\{t\}=1/\(\\\|x\_\{t\}\\\|^\{2\}\+\\sigma\_\{\\varepsilon\}^\{2\}\)\. These adaptations*strengthen*the baselines: granting them online subspace recovery removes representation quality as a confound, so any remaining gap to SPSC reflects probe\-based identification, the windowed head, and drift handling rather than failure to exploit low\-rank structure\.

#### Implementation and compute\.

All experiments use NumPy/SciPy only\. A full\(d,r\)\(d,r\)grid \(9 cells, 10 seeds, nine per\-cell baselines plus Oracle\-LinUCB and the two SPSC variants; BOSS and Jedra appear only in the §5\.6 grid\) takes 6–20 hours on a single 16\-core CPU\. Covertype is the longest \(T=10,000T\{=\}10\{,\}000\)\.

## Appendix GPer\-cell tables: every dataset, every cell

Tables[8](https://arxiv.org/html/2605.20269#A7.T8)–[15](https://arxiv.org/html/2605.20269#A7.T15)give the full per\-cell results \(mean±\\pmSE costed regret over 10 seeds\) for every method on every\(d,r\)\(d,r\)cell\. Cells where at least one SPSC variant beats every non\-oracle baseline are highlightedgreen; the best non\-oracle baseline per cell isunderlined\.

Table 8:Covertypeper\-cell results\. Mean±\\pmSE costed regret over 10 seeds\. Green = SPSC variant beats every non\-oracle baseline; underline = best non\-oracle\.T=10,000T\{=\}10\{,\}000,K=4K\{=\}4\.*Reading note \(applies to all per\-cell tables in this appendix\):*rank\-insensitive methods \(LinUCB, SW\-LinUCB, D\-LinUCB, Restart\-LinUCB, LinTS, SW\-LinTS\) act in ambient space; their regret depends onddbut not onrr, hence bit\-identical values across the rows of eachdd\-block\.ddrrOracleSPSCSPSC\-AdpLowOFULVOFULLR\-RewSW\-LinD\-LinRst\-LinLinUCBLinTSSW\-LinTS512013±1382013\{\\pm\}1382655±852655\{\\pm\}852114±442114\{\\pm\}443748±1623748\{\\pm\}1623736±1643736\{\\pm\}1642379±1362379\{\\pm\}1362651±1102651\{\\pm\}1102502±982502\{\\pm\}982661±1242661\{\\pm\}1242694±1262694\{\\pm\}1263633±1593633\{\\pm\}1593064±1133064\{\\pm\}113551718±51718\{\\pm\}511296±211296\{\\pm\}211262±321262\{\\pm\}321429±321429\{\\pm\}321436±321436\{\\pm\}321366±441366\{\\pm\}441331±201331\{\\pm\}201346±211346\{\\pm\}211329±211329\{\\pm\}211336±211336\{\\pm\}211462±251462\{\\pm\}251443±251443\{\\pm\}25102768±292768\{\\pm\}294307±624307\{\\pm\}624161±634161\{\\pm\}635067±835067\{\\pm\}835167±1305167\{\\pm\}1305122±615122\{\\pm\}614403±414403\{\\pm\}414599±574599\{\\pm\}574348±374348\{\\pm\}374465±494465\{\\pm\}495591±785591\{\\pm\}785486±735486\{\\pm\}73204004±554004\{\\pm\}555769±545769\{\\pm\}545786±845786\{\\pm\}847120±937120\{\\pm\}937001±727001\{\\pm\}727538±817538\{\\pm\}815703±345703\{\\pm\}345971±405971\{\\pm\}405669±405669\{\\pm\}405800±505800\{\\pm\}507825±417825\{\\pm\}417581±447581\{\\pm\}44305202±485202\{\\pm\}486961±956961\{\\pm\}957051±817051\{\\pm\}818890±1108890\{\\pm\}1108770±938770\{\\pm\}939527±969527\{\\pm\}966653±346653\{\\pm\}346928±306928\{\\pm\}306594±516594\{\\pm\}516743±346743\{\\pm\}349615±1059615\{\\pm\}1059345±909345\{\\pm\}901051554±30554\{\\pm\}301023±291023\{\\pm\}291010±211010\{\\pm\}211134±411134\{\\pm\}411124±441124\{\\pm\}441026±281026\{\\pm\}281075±321075\{\\pm\}321082±331082\{\\pm\}331073±311073\{\\pm\}311075±331075\{\\pm\}331109±351109\{\\pm\}351104±351104\{\\pm\}35102154±272154\{\\pm\}273452±453452\{\\pm\}453405±403405\{\\pm\}403775±343775\{\\pm\}343758±483758\{\\pm\}483869±363869\{\\pm\}363920±363920\{\\pm\}363959±363959\{\\pm\}363909±373909\{\\pm\}373943±353943\{\\pm\}354198±404198\{\\pm\}404168±374168\{\\pm\}37203233±363233\{\\pm\}364600±624600\{\\pm\}624507±464507\{\\pm\}465297±675297\{\\pm\}675325±685325\{\\pm\}685621±435621\{\\pm\}435302±405302\{\\pm\}405383±325383\{\\pm\}325313±305313\{\\pm\}305355±355355\{\\pm\}355826±425826\{\\pm\}425734±425734\{\\pm\}42304165±234165\{\\pm\}235529±715529\{\\pm\}715450±675450\{\\pm\}676476±336476\{\\pm\}336556±516556\{\\pm\}516989±546989\{\\pm\}546360±386360\{\\pm\}386473±336473\{\\pm\}336324±426324\{\\pm\}426400±376400\{\\pm\}377085±487085\{\\pm\}487029±467029\{\\pm\}46

Table 9:Pendigitsper\-cell results\.T=5,000T\{=\}5\{,\}000,K=10K\{=\}10, 10 seeds\.ddrrOracleSPSCSPSC\-AdpLowOFULVOFULLR\-RewSW\-LinD\-LinRst\-LinLinUCBLinTSSW\-LinTS5139\.0±2\.039\.0\{\\pm\}2\.02914±1592914\{\\pm\}1595480±3915480\{\\pm\}3919536±1999536\{\\pm\}1999623±1389623\{\\pm\}1386606±776606\{\\pm\}771090±91090\{\\pm\}91267±81267\{\\pm\}81022±141022\{\\pm\}141073±151073\{\\pm\}156629±426629\{\\pm\}424630±414630\{\\pm\}4155118\.0±1\.018\.0\{\\pm\}1\.04019±794019\{\\pm\}794073±2004073\{\\pm\}2005913±465913\{\\pm\}465939±645939\{\\pm\}644542±484542\{\\pm\}483863±113863\{\\pm\}114056±94056\{\\pm\}93620±73620\{\\pm\}73658±93658\{\\pm\}94343±164343\{\\pm\}164648±94648\{\\pm\}910951±5951\{\\pm\}52774±582774\{\\pm\}582682±932682\{\\pm\}933703±713703\{\\pm\}713655±673655\{\\pm\}674246±284246\{\\pm\}283863±113863\{\\pm\}114056±94056\{\\pm\}93620±73620\{\\pm\}73658±93658\{\\pm\}94343±164343\{\\pm\}164648±94648\{\\pm\}9201816±41816\{\\pm\}42803±602803\{\\pm\}602490±562490\{\\pm\}563689±543689\{\\pm\}543854±583854\{\\pm\}584271±394271\{\\pm\}393863±113863\{\\pm\}114056±94056\{\\pm\}93620±73620\{\\pm\}73658±93658\{\\pm\}94343±164343\{\\pm\}164648±94648\{\\pm\}9302534±62534\{\\pm\}63051±623051\{\\pm\}622776±452776\{\\pm\}453827±453827\{\\pm\}453818±393818\{\\pm\}394329±204329\{\\pm\}203863±113863\{\\pm\}114056±94056\{\\pm\}93620±73620\{\\pm\}73658±93658\{\\pm\}94343±164343\{\\pm\}164648±94648\{\\pm\}9105111\.0±0\.011\.0\{\\pm\}0\.03011±883011\{\\pm\}883120±1343120\{\\pm\}1344254±1144254\{\\pm\}1144277±1074277\{\\pm\}1073051±893051\{\\pm\}893297±63297\{\\pm\}63400±63400\{\\pm\}63152±63152\{\\pm\}63184±53184\{\\pm\}53117±103117\{\\pm\}103557±43557\{\\pm\}410666±3666\{\\pm\}32066±642066\{\\pm\}641693±381693\{\\pm\}382927±742927\{\\pm\}742816±552816\{\\pm\}553027±433027\{\\pm\}433297±63297\{\\pm\}63400±63400\{\\pm\}63152±63152\{\\pm\}63184±53184\{\\pm\}53117±103117\{\\pm\}103557±43557\{\\pm\}4201242±31242\{\\pm\}32067±622067\{\\pm\}621571±671571\{\\pm\}672840±412840\{\\pm\}412835±352835\{\\pm\}353123±183123\{\\pm\}183297±63297\{\\pm\}63400±63400\{\\pm\}63152±63152\{\\pm\}63184±53184\{\\pm\}53117±103117\{\\pm\}103557±43557\{\\pm\}4301745±41745\{\\pm\}42247±582247\{\\pm\}581722±581722\{\\pm\}582826±752826\{\\pm\}752839±562839\{\\pm\}563283±193283\{\\pm\}193297±63297\{\\pm\}63400±63400\{\\pm\}63152±63152\{\\pm\}63184±53184\{\\pm\}53117±103117\{\\pm\}103557±43557\{\\pm\}4

Table 10:Satimageper\-cell results\.T=5,000T\{=\}5\{,\}000,K=10K\{=\}10, 10 seeds\.ddrrOracleSPSCSPSC\-AdpLowOFULVOFULLR\-RewSW\-LinD\-LinRst\-LinLinUCBLinTSSW\-LinTS5135\.0±2\.035\.0\{\\pm\}2\.01480±881480\{\\pm\}881513±1231513\{\\pm\}1232739±172739\{\\pm\}172704±182704\{\\pm\}182660±242660\{\\pm\}24655±7655\{\\pm\}7778±6778\{\\pm\}6629±6629\{\\pm\}6680±6680\{\\pm\}62397±142397\{\\pm\}141675±161675\{\\pm\}1655118\.0±1\.018\.0\{\\pm\}1\.02439±812439\{\\pm\}812015±752015\{\\pm\}752913±112913\{\\pm\}112911±82911\{\\pm\}83450±523450\{\\pm\}523051±63051\{\\pm\}63201±93201\{\\pm\}92779±32779\{\\pm\}32848±92848\{\\pm\}93403±113403\{\\pm\}113781±103781\{\\pm\}1010597±3597\{\\pm\}31343±411343\{\\pm\}411073±491073\{\\pm\}492294±992294\{\\pm\}992288±962288\{\\pm\}962689±622689\{\\pm\}623051±63051\{\\pm\}63201±93201\{\\pm\}92779±32779\{\\pm\}32848±92848\{\\pm\}93403±113403\{\\pm\}113781±103781\{\\pm\}10201218±41218\{\\pm\}41506±341506\{\\pm\}341201±331201\{\\pm\}332455±1062455\{\\pm\}1062479±652479\{\\pm\}652879±552879\{\\pm\}553051±63051\{\\pm\}63201±93201\{\\pm\}92779±32779\{\\pm\}32848±92848\{\\pm\}93403±113403\{\\pm\}113781±103781\{\\pm\}10301725±81725\{\\pm\}81900±381900\{\\pm\}381635±401635\{\\pm\}402641±542641\{\\pm\}542772±472772\{\\pm\}473085±533085\{\\pm\}533051±63051\{\\pm\}63201±93201\{\\pm\}92779±32779\{\\pm\}32848±92848\{\\pm\}93403±113403\{\\pm\}113781±103781\{\\pm\}10105116\.0±1\.016\.0\{\\pm\}1\.02484±592484\{\\pm\}592333±1082333\{\\pm\}1083638±73638\{\\pm\}73655±123655\{\\pm\}123911±473911\{\\pm\}473572±83572\{\\pm\}83671±93671\{\\pm\}93441±63441\{\\pm\}63484±103484\{\\pm\}103600±93600\{\\pm\}93891±73891\{\\pm\}710538±3538\{\\pm\}31377±441377\{\\pm\}441112±491112\{\\pm\}492431±872431\{\\pm\}872361±782361\{\\pm\}782703±402703\{\\pm\}403572±83572\{\\pm\}83671±93671\{\\pm\}93441±63441\{\\pm\}63484±103484\{\\pm\}103600±93600\{\\pm\}93891±73891\{\\pm\}7201098±51098\{\\pm\}51454±331454\{\\pm\}331182±341182\{\\pm\}342229±572229\{\\pm\}572346±462346\{\\pm\}462697±392697\{\\pm\}393572±83572\{\\pm\}83671±93671\{\\pm\}93441±63441\{\\pm\}63484±103484\{\\pm\}103600±93600\{\\pm\}93891±73891\{\\pm\}7301569±51569\{\\pm\}51769±321769\{\\pm\}321506±331506\{\\pm\}332525±422525\{\\pm\}422587±802587\{\\pm\}802722±252722\{\\pm\}253572±83572\{\\pm\}83671±93671\{\\pm\}93441±63441\{\\pm\}63484±103484\{\\pm\}103600±93600\{\\pm\}93891±73891\{\\pm\}7

Table 11:Fashion\-MNISTper\-cell results\.T=5,000T\{=\}5\{,\}000,K=10K\{=\}10, 10 seeds\.ddrrOracleSPSCSPSC\-AdpLowOFULVOFULLR\-RewSW\-LinD\-LinRst\-LinLinUCBLinTSSW\-LinTS555539±6539\{\\pm\}63773±913773\{\\pm\}913792±583792\{\\pm\}584487±1034487\{\\pm\}1034475±1184475\{\\pm\}1184719±934719\{\\pm\}934169±94169\{\\pm\}94324±114324\{\\pm\}113801±63801\{\\pm\}63868±123868\{\\pm\}125183±115183\{\\pm\}115357±155357\{\\pm\}1510945±5945\{\\pm\}53406±733406\{\\pm\}733377±923377\{\\pm\}924425±1264425\{\\pm\}1264471±1424471\{\\pm\}1424740±594740\{\\pm\}594169±94169\{\\pm\}94324±114324\{\\pm\}113801±63801\{\\pm\}63868±123868\{\\pm\}125183±115183\{\\pm\}115357±155357\{\\pm\}15201676±61676\{\\pm\}63450±623450\{\\pm\}623162±813162\{\\pm\}814677±1194677\{\\pm\}1194708±754708\{\\pm\}754924±564924\{\\pm\}564169±94169\{\\pm\}94324±114324\{\\pm\}113801±63801\{\\pm\}63868±123868\{\\pm\}125183±115183\{\\pm\}115357±155357\{\\pm\}151055399±3399\{\\pm\}33200±883200\{\\pm\}883208±603208\{\\pm\}603365±713365\{\\pm\}713522±923522\{\\pm\}923688±813688\{\\pm\}814152±84152\{\\pm\}84236±74236\{\\pm\}74016±84016\{\\pm\}84034±104034\{\\pm\}104376±94376\{\\pm\}94496±114496\{\\pm\}1110757±6757\{\\pm\}62927±762927\{\\pm\}762623±842623\{\\pm\}843331±423331\{\\pm\}423478±513478\{\\pm\}513645±653645\{\\pm\}654152±84152\{\\pm\}84236±74236\{\\pm\}74016±84016\{\\pm\}84034±104034\{\\pm\}104376±94376\{\\pm\}94496±114496\{\\pm\}11201439±41439\{\\pm\}42855±752855\{\\pm\}752528±592528\{\\pm\}593559±803559\{\\pm\}803564±453564\{\\pm\}453797±383797\{\\pm\}384152±84152\{\\pm\}84236±74236\{\\pm\}74016±84016\{\\pm\}84034±104034\{\\pm\}104376±94376\{\\pm\}94496±114496\{\\pm\}112005393±3393\{\\pm\}32949±522949\{\\pm\}522877±892877\{\\pm\}893134±723134\{\\pm\}722869±582869\{\\pm\}582948±472948\{\\pm\}474099±74099\{\\pm\}74158±84158\{\\pm\}84059±54059\{\\pm\}54059±114059\{\\pm\}114101±114101\{\\pm\}114206±84206\{\\pm\}810730±4730\{\\pm\}42703±522703\{\\pm\}522732±1012732\{\\pm\}1012929±432929\{\\pm\}432731±632731\{\\pm\}632967±262967\{\\pm\}264099±74099\{\\pm\}74158±84158\{\\pm\}84059±54059\{\\pm\}54059±114059\{\\pm\}114101±114101\{\\pm\}114206±84206\{\\pm\}8201290±51290\{\\pm\}52654±522654\{\\pm\}522582±672582\{\\pm\}673215±563215\{\\pm\}563196±613196\{\\pm\}613341±443341\{\\pm\}444099±74099\{\\pm\}74158±84158\{\\pm\}84059±54059\{\\pm\}54059±114059\{\\pm\}114101±114101\{\\pm\}114206±84206\{\\pm\}8

Table 12:MNISTper\-cell results\.T=5,000T\{=\}5\{,\}000,K=10K\{=\}10, 10 seeds\.ddrrOracleSPSCSPSC\-AdpLowOFULVOFULLR\-RewSW\-LinD\-LinRst\-LinLinUCBLinTSSW\-LinTS555666±5666\{\\pm\}55076±885076\{\\pm\}885223±1095223\{\\pm\}1096437±1526437\{\\pm\}1526646±626646\{\\pm\}626650±1166650\{\\pm\}1165889±165889\{\\pm\}166154±126154\{\\pm\}125426±105426\{\\pm\}105533±95533\{\\pm\}96958±136958\{\\pm\}137362±207362\{\\pm\}20101149±91149\{\\pm\}94648±774648\{\\pm\}774968±934968\{\\pm\}936392±1146392\{\\pm\}1146191±1186191\{\\pm\}1186623±776623\{\\pm\}775889±165889\{\\pm\}166154±126154\{\\pm\}125426±105426\{\\pm\}105533±95533\{\\pm\}96958±136958\{\\pm\}137362±207362\{\\pm\}20202196±112196\{\\pm\}114745±764745\{\\pm\}764549±824549\{\\pm\}826420±636420\{\\pm\}636352±1206352\{\\pm\}1206745±586745\{\\pm\}585889±165889\{\\pm\}166154±126154\{\\pm\}125426±105426\{\\pm\}105533±95533\{\\pm\}96958±136958\{\\pm\}137362±207362\{\\pm\}201055582±5582\{\\pm\}54658±1044658\{\\pm\}1044844±684844\{\\pm\}685184±745184\{\\pm\}745305±565305\{\\pm\}565807±935807\{\\pm\}935992±115992\{\\pm\}116073±86073\{\\pm\}85749±115749\{\\pm\}115811±105811\{\\pm\}105892±185892\{\\pm\}186222±116222\{\\pm\}11101029±51029\{\\pm\}54298±964298\{\\pm\}964229±1574229\{\\pm\}1574867±964867\{\\pm\}964917±464917\{\\pm\}465555±585555\{\\pm\}585992±115992\{\\pm\}116073±86073\{\\pm\}85749±115749\{\\pm\}115811±105811\{\\pm\}105892±185892\{\\pm\}186222±116222\{\\pm\}11201869±111869\{\\pm\}114273±1014273\{\\pm\}1014076±1144076\{\\pm\}1145020±465020\{\\pm\}464918±784918\{\\pm\}785651±465651\{\\pm\}465992±115992\{\\pm\}116073±86073\{\\pm\}85749±115749\{\\pm\}115811±105811\{\\pm\}105892±185892\{\\pm\}186222±116222\{\\pm\}112005539±2539\{\\pm\}24377±844377\{\\pm\}844260±814260\{\\pm\}814672±624672\{\\pm\}624718±1134718\{\\pm\}1134797±524797\{\\pm\}525751±105751\{\\pm\}105786±65786\{\\pm\}65659±115659\{\\pm\}115661±85661\{\\pm\}85568±105568\{\\pm\}105774±75774\{\\pm\}710907±5907\{\\pm\}54114±664114\{\\pm\}664023±1134023\{\\pm\}1134184±634184\{\\pm\}634375±754375\{\\pm\}754818±424818\{\\pm\}425751±105751\{\\pm\}105786±65786\{\\pm\}65659±115659\{\\pm\}115661±85661\{\\pm\}85568±105568\{\\pm\}105774±75774\{\\pm\}7201675±61675\{\\pm\}64052±594052\{\\pm\}593828±693828\{\\pm\}694379±344379\{\\pm\}344413±504413\{\\pm\}505022±275022\{\\pm\}275751±105751\{\\pm\}105786±65786\{\\pm\}65659±115659\{\\pm\}115661±85661\{\\pm\}85568±105568\{\\pm\}105774±75774\{\\pm\}7

Table 13:MovieLens\(fully real ratings\) per\-cell results\.T=5,000T\{=\}5\{,\}000,K=10K\{=\}10, 10 seeds\.ddrrOracleSPSCSPSC\-AdpLowOFULVOFULLR\-RewSW\-LinD\-LinRst\-LinLinUCBLinTSSW\-LinTS5554013±334013\{\\pm\}336213±636213\{\\pm\}636060±776060\{\\pm\}777676±1647676\{\\pm\}1647504±1437504\{\\pm\}1438103±608103\{\\pm\}606313±66313\{\\pm\}66363±66363\{\\pm\}66239±106239\{\\pm\}106258±86258\{\\pm\}86396±116396\{\\pm\}116587±116587\{\\pm\}11104802±244802\{\\pm\}246250±466250\{\\pm\}466015±376015\{\\pm\}377689±777689\{\\pm\}777461±1137461\{\\pm\}1137855±477855\{\\pm\}476313±66313\{\\pm\}66363±66363\{\\pm\}66239±106239\{\\pm\}106258±86258\{\\pm\}86396±116396\{\\pm\}116587±116587\{\\pm\}11205402±215402\{\\pm\}216266±426266\{\\pm\}426216±446216\{\\pm\}447407±567407\{\\pm\}567329±1087329\{\\pm\}1087391±307391\{\\pm\}306313±66313\{\\pm\}66363±66363\{\\pm\}66239±106239\{\\pm\}106258±86258\{\\pm\}86396±116396\{\\pm\}116587±116587\{\\pm\}1110553970±333970\{\\pm\}336535±566535\{\\pm\}566350±736350\{\\pm\}738276±1268276\{\\pm\}1268292±898292\{\\pm\}898340±358340\{\\pm\}356809±56809\{\\pm\}56850±46850\{\\pm\}46783±46783\{\\pm\}46793±66793\{\\pm\}66743±136743\{\\pm\}136874±126874\{\\pm\}12104951±374951\{\\pm\}376560±436560\{\\pm\}436297±556297\{\\pm\}557801±1737801\{\\pm\}1737927±1547927\{\\pm\}1548200±618200\{\\pm\}616809±56809\{\\pm\}56850±46850\{\\pm\}46783±46783\{\\pm\}46793±66793\{\\pm\}66743±136743\{\\pm\}136874±126874\{\\pm\}12205697±235697\{\\pm\}236636±326636\{\\pm\}326566±406566\{\\pm\}407562±1037562\{\\pm\}1037688±907688\{\\pm\}907674±277674\{\\pm\}276809±56809\{\\pm\}56850±46850\{\\pm\}46783±46783\{\\pm\}46793±66793\{\\pm\}66743±136743\{\\pm\}136874±126874\{\\pm\}1220053939±273939\{\\pm\}276787±526787\{\\pm\}526516±1016516\{\\pm\}1018365±1028365\{\\pm\}1028450±1188450\{\\pm\}1188420±468420\{\\pm\}467396±67396\{\\pm\}67421±67421\{\\pm\}67404±47404\{\\pm\}47417±77417\{\\pm\}77134±127134\{\\pm\}127203±77203\{\\pm\}7104998±484998\{\\pm\}486844±576844\{\\pm\}576576±366576\{\\pm\}368383±1318383\{\\pm\}1318163±1358163\{\\pm\}1358513±508513\{\\pm\}507396±67396\{\\pm\}67421±67421\{\\pm\}67404±47404\{\\pm\}47417±77417\{\\pm\}77134±127134\{\\pm\}127203±77203\{\\pm\}7205871±255871\{\\pm\}256995±476995\{\\pm\}476844±536844\{\\pm\}537296±1187296\{\\pm\}1187605±1177605\{\\pm\}1177627±587627\{\\pm\}587396±67396\{\\pm\}67421±67421\{\\pm\}67404±47404\{\\pm\}47417±77417\{\\pm\}77134±127134\{\\pm\}127203±77203\{\\pm\}7

Table 14:Warfarin\(d=93d\{=\}93,K=8K\{=\}8,T=5,000T\{=\}5\{,\}000\) per\-rank results acrossr∈\{1,2,3,5,10\}r\\in\\\{1,2,3,5,10\\\}\. 10 seeds\.ddrrOracleSPSCSPSC\-AdpLowOFULVOFULLR\-RewSW\-LinD\-LinRst\-LinLinUCBLinTSSW\-LinTS9316\.4±0\.76\.4\{\\pm\}0\.71482±491482\{\\pm\}49626±44626\{\\pm\}441491±261491\{\\pm\}261497±231497\{\\pm\}231533±201533\{\\pm\}202096±182096\{\\pm\}182175±222175\{\\pm\}221977±151977\{\\pm\}152006±172006\{\\pm\}171949±201949\{\\pm\}202060±222060\{\\pm\}22293\.9±1\.393\.9\{\\pm\}1\.31404±351404\{\\pm\}35706±37706\{\\pm\}371076±1301076\{\\pm\}130918±127918\{\\pm\}1271140±251140\{\\pm\}252096±182096\{\\pm\}182175±222175\{\\pm\}221977±151977\{\\pm\}152006±172006\{\\pm\}171949±201949\{\\pm\}202060±222060\{\\pm\}223177±4177\{\\pm\}41372±331372\{\\pm\}33657±39657\{\\pm\}39683±97683\{\\pm\}97779±93779\{\\pm\}931056±401056\{\\pm\}402096±182096\{\\pm\}182175±222175\{\\pm\}221977±151977\{\\pm\}152006±172006\{\\pm\}171949±201949\{\\pm\}202060±222060\{\\pm\}225272±7272\{\\pm\}71369±301369\{\\pm\}30769±37769\{\\pm\}37905±110905\{\\pm\}110930±76930\{\\pm\}761178±321178\{\\pm\}322096±182096\{\\pm\}182175±222175\{\\pm\}221977±151977\{\\pm\}152006±172006\{\\pm\}171949±201949\{\\pm\}202060±222060\{\\pm\}2210569±4569\{\\pm\}41481±191481\{\\pm\}191014±351014\{\\pm\}351441±631441\{\\pm\}631680±591680\{\\pm\}592078±192078\{\\pm\}192096±182096\{\\pm\}182175±222175\{\\pm\}221977±151977\{\\pm\}152006±172006\{\\pm\}171949±201949\{\\pm\}202060±222060\{\\pm\}22

Table 15:Open Bandit \(ZOZOTOWN\)per\-cell results\.T=5,000T\{=\}5\{,\}000,K=10K\{=\}10, 10 seeds\. Mean±\\pmSE costed regret\. Green = SPSC variant beats every non\-oracle baseline; underline = best non\-oracle\. LinTS / SW\-LinTS not run on this benchmark\.ddrrOracleSPSCSPSC\-AdpLowOFULVOFULLR\-RewSW\-LinD\-LinRst\-LinLinUCB55534\.2±0\.534\.2\{\\pm\}0\.583\.0±2\.383\.0\{\\pm\}2\.391\.1±4\.091\.1\{\\pm\}4\.0126\.2±1\.8126\.2\{\\pm\}1\.8126\.7±1\.5126\.7\{\\pm\}1\.5126\.8±1\.2126\.8\{\\pm\}1\.2103\.0±0\.5103\.0\{\\pm\}0\.5106\.6±0\.5106\.6\{\\pm\}0\.5101\.9±0\.6101\.9\{\\pm\}0\.6102\.2±0\.5102\.2\{\\pm\}0\.51065\.2±0\.865\.2\{\\pm\}0\.893\.9±1\.593\.9\{\\pm\}1\.594\.1±1\.794\.1\{\\pm\}1\.7129\.3±2\.6129\.3\{\\pm\}2\.6130\.2±1\.9130\.2\{\\pm\}1\.9130\.9±1\.3130\.9\{\\pm\}1\.3103\.0±0\.5103\.0\{\\pm\}0\.5106\.6±0\.5106\.6\{\\pm\}0\.5101\.9±0\.6101\.9\{\\pm\}0\.6102\.2±0\.5102\.2\{\\pm\}0\.5105529\.7±0\.529\.7\{\\pm\}0\.5106\.6±4\.8106\.6\{\\pm\}4\.8103\.3±2\.9103\.3\{\\pm\}2\.9152\.6±2\.3152\.6\{\\pm\}2\.3150\.1±1\.9150\.1\{\\pm\}1\.9150\.9±1\.6150\.9\{\\pm\}1\.6107\.4±1\.1107\.4\{\\pm\}1\.1108\.4±0\.4108\.4\{\\pm\}0\.4106\.4±0\.5106\.4\{\\pm\}0\.5107\.7±1\.0107\.7\{\\pm\}1\.01059\.0±0\.759\.0\{\\pm\}0\.7106\.9±3\.0106\.9\{\\pm\}3\.0106\.3±3\.2106\.3\{\\pm\}3\.2153\.3±1\.0153\.3\{\\pm\}1\.0155\.4±1\.8155\.4\{\\pm\}1\.8156\.1±1\.5156\.1\{\\pm\}1\.5107\.4±1\.1107\.4\{\\pm\}1\.1108\.4±0\.4108\.4\{\\pm\}0\.4106\.4±0\.5106\.4\{\\pm\}0\.5107\.7±1\.0107\.7\{\\pm\}1\.0

![Refer to caption](https://arxiv.org/html/2605.20269v1/figures/experiment_pendigits_extended.png)Figure 2:Pendigits operating\-regime grid\.SPSC and SPSC\-Adaptive dominate every non\-oracle baseline onced≥55d\{\\geq\}55andr≥10r\{\\geq\}10\.#### Reading the tables\.

Three qualitative patterns are consistent across datasets\. \(i\)*Rank\-insensitive competitors\.*LinUCB, SW\-LinUCB, D\-LinUCB and Restart\-LinUCB operate in ambient space and therefore produce the*same*regret in every row of addblock\. When a row shows all four of these at identical values, this is by design: it reflects therr\-insensitivity of ambient\-rate baselines\. \(ii\)*Subspace\-aware competitors*\(LowOFUL, VOFUL, LowRank\-Reward\) do improve withddincreasing but they assume a fixed subspace and therefore still trail SPSC on segments where the subspace changes\. \(iii\)*Within the synthetic and UCI grids, SPSC\-Adaptive typically trails SPSC\-Alg\. 1 by a small margin*; this gap reflects the detector’s false\-alarm budget\. The ordering reverses on the clinical benchmarks \(most strikingly Vancomycin atr=1r\{=\}1, where SPSC\-Adaptive cuts regret by37%37\\%vs\. SPSC\-Alg\. 1; see Table[19](https://arxiv.org/html/2605.20269#A12.T19)\), where the oracle schedule of Alg\.[1](https://arxiv.org/html/2605.20269#alg1)is misaligned with the true cohort change points and the detector’s adaptivity wins\.

#### Synthetic\(d,r\)\(d,r\)grid\.

Table[16](https://arxiv.org/html/2605.20269#A7.T16)gives the full synthetic grid underlying Figure[1](https://arxiv.org/html/2605.20269#S5.F1)\. SPSC wins on37/4037/40cells; losses are confined tod≤10d\\leq 10orr≤1r\\leq 1\(probe\-cost dominant\)\.

Table 16:Synthetic grid \(full 40 cells\)\.Mean costed regret across 10 seeds for 10 methods over\(d,r\)∈\{5,10,20,30,45,60,80,100\}×\{1,3,5,10,15,20\}\(d,r\)\\in\\\{5,10,20,30,45,60,80,100\\\}\\times\\\{1,3,5,10,15,20\\\}withr<dr<d,T=5,000T\{=\}5\{,\}000,K=10K\{=\}10, probe period5050, windowW=400W\{=\}400,λ=0\.01\\lambda\{=\}0\.01\.Methods:SPSC \(Algorithm[1](https://arxiv.org/html/2605.20269#alg1), ours\);Adpt= SPSC\-Adaptive \(Algorithm[2](https://arxiv.org/html/2605.20269#alg2), ours\); LinUCB;Oracle= Oracle\-LinUCB \(given the true subspace\);SW\-Lin= SW\-LinUCB;D\-Lin= D\-LinUCB;Rst= Restart\-LinUCB;LR\-Rew= LowRank\-Reward; LowOFUL; VOFUL\.S/L=SPSC/LinUCB\\mathrm\{S/L\}=\\mathrm\{SPSC/LinUCB\};S/Best=SPSC/min⁡\{non\-oracle, non\-Adpt baselines\}\\mathrm\{S/Best\}=\\mathrm\{SPSC\}/\\min\\\{\\text\{non\-oracle, non\-Adpt baselines\}\\\}\.Verdict\.“SPSC” ifS/L<1\\mathrm\{S/L\}<1\(SPSC has lower regret than LinUCB\); “LinUCB” otherwise\. Bold = SPSC verdict\. Counts:37 SPSC,3 LinUCB; the 3 LinUCB cells are all in the small\-ddcornerd≤10d\\leq 10withrrclose todd, where the probe cost dominates the dimensionality savings\.ddrrSPSCAdptLinUCBOracleSW\-LinD\-LinRstLR\-RewLowOFULVOFULS/LS/Bestverdict5135534420382132342064165145531\.7421\.742LinUCB533393842211342212542176299308891\.5291\.563LinUCB101270289255242602712582543173151\.0551\.060LinUCB1033894223991303914283864566295950\.9761\.008SPSC1054655254872544825234716608008230\.9550\.988SPSC201231228251212512532481792382400\.9231\.290SPSC2033533774561344494674513444494750\.7741\.026SPSC2054204535652325555815584685755780\.7440\.898SPSC20106316998004987808407848049469750\.7890\.809SPSC20158059018997368939548831011123512220\.8950\.912SPSC301189206220242202222191541982030\.8591\.225SPSC3033073304071254094134042963553550\.7541\.038SPSC3053724215442175415535364114984920\.6830\.904SPSC30105726157754517637907606908558280\.7380\.829SPSC3015741810930663917957913956106611130\.7960\.811SPSC302089096010188381002105610091109123612590\.8740\.888SPSC451165169188251871891861301721680\.8811\.275SPSC4532712963711183713753692733122940\.7300\.992SPSC4553603895042125065105023764194310\.7150\.957SPSC45104995206753956656846685596466500\.7390\.893SPSC45156516848195778128368117368118080\.7960\.885SPSC45208118369737589549809529019889890\.8330\.900SPSC601141146165301661661651081341340\.8581\.311SPSC6032292432961172942962922222492390\.7761\.033SPSC6053153194141994124164143203663430\.7600\.985SPSC60104414796053676006086015365645850\.7290\.822SPSC60155886057435247407527387137527360\.7910\.824SPSC60207087538536638458688458388828620\.8300\.845SPSC80111012511827118118118911111060\.9311\.214SPSC8032312502901162922932902242382390\.7961\.034SPSC8052792953811873793843792933073190\.7330\.954SPSC80104194305423455395455384474934730\.7720\.937SPSC80155345766714866686716675876386550\.7960\.911SPSC80206406637675997617707616917447610\.8350\.927SPSC1001107111112281131131137986930\.9541\.359SPSC10031921942381072362382361761932010\.8091\.094SPSC10052722733461833433463442662942900\.7871\.024SPSC100103683884713174724724704034384400\.7800\.912SPSC100154664915734305715765725175305350\.8130\.902SPSC100206096347265727257337236616927020\.8390\.921SPSC

## Appendix HSensitivity and robustness studies

### H\.1Probe\-rate ablation

Sweeping the probe period over\{5,10,20,30,50,100,300\}\\\{5,10,20,30,50,100,300\\\}atd=4d\{=\}4,r=1r\{=\}1,K=4K\{=\}4,T=6,000T\{=\}6\{,\}000produces a clearly U\-shaped regret curve \(Figure[3](https://arxiv.org/html/2605.20269#A8.F3)\): sparse probing under\-recovers the subspace; over\-frequent probing sacrifices exploitation\. Optimum at probe period2020–3030, matchingmk⋆∝ℓk2/3m\_\{k\}^\{\\star\}\\propto\\ell\_\{k\}^\{2/3\}prediction\. The right panel shows a monotone relationship between late\-segment subspace error and final regret, directly linking SPSC’s gains to subspace recovery quality\.

![Refer to caption](https://arxiv.org/html/2605.20269v1/figures/experiment3_probe_ablation.png)Figure 3:Probe\-rate ablation\. Left: final regret vs\. probe frequency\. Right: final control regret vs\. late\-segment subspace error\.
### H\.2Rank misspecification

On Covertype \(d=155d\{=\}155, true effective rankr⋆=10r^\{\\star\}\{=\}10,K=4K\{=\}4,T=10,000T\{=\}10\{,\}000, 5 seeds\), sweeping specifiedrrat the grid points\{1,3,5,10,15,20,30,50,80\}\\\{1,3,5,10,15,20,30,50,80\\\}\(minr=1r\{=\}1, maxr=80r\{=\}80\) gives the U\-shaped curve in Figure[4](https://arxiv.org/html/2605.20269#A8.F4)\. Underestimation loses signal \(\+33%\+33\\%atr=1r\{=\}1\); mild overestimation captures residual structure \(sweet spot atr=30r\{=\}30,−10%\-10\\%\)\. SPSC beats LinUCB acrossr∈\[15,50\]r\\in\[15,50\], so mild overestimation is a safe default\.

![Refer to caption](https://arxiv.org/html/2605.20269v1/figures/experiment_rank_misspec.png)Figure 4:Rank misspecification robustness \(Covertype,d=155d\{=\}155,r⋆=10r^\{\\star\}\{=\}10\)\. SPSC beats LinUCB forr∈\[15,50\]r\\in\[15,50\]; sweet spot atr=30r\{=\}30\(10%10\\%improvement\)\.
### H\.3Robustness and necessity experiments \(A/B/C\)

Three ablations on the reference setting \(d=4d\{=\}4,r=1r\{=\}1,K=4K\{=\}4,T=6,000T\{=\}6\{,\}000, probe period 30,W=100W\{=\}100, 10 seeds\)\.

#### A\. Variance misspecification\.

Injecting\|δσ\|∈\{0,0\.01,0\.02,0\.05,0\.1,0\.2,0\.5\}\|\\delta\_\{\\sigma\}\|\\in\\\{0,0\.01,0\.02,0\.05,0\.1,0\.2,0\.5\\\}into the probe statisticst=yt2−\(σε2\+δσ\)s\_\{t\}=y\_\{t\}^\{2\}\-\(\\sigma\_\{\\varepsilon\}^\{2\}\+\\delta\_\{\\sigma\}\)\. Regret and subspace error are stable through\|δσ\|=0\.5\|\\delta\_\{\\sigma\}\|=0\.5\(more than5×5\\timesthe true varianceσε2=0\.09\\sigma\_\{\\varepsilon\}^\{2\}=0\.09\); at maximum misspecification, regret changes by<5%<5\\%\. For scaled\-sphere probes \(the theory probe distribution\), a constant centering error contributes the population\-level identity shiftB~=−\(δσ/d\)​Id\\widetilde\{B\}=\-\(\\delta\_\{\\sigma\}/d\)I\_\{d\}, which uniformly shifts eigenvalues without corrupting eigenvectors\.

#### B\. Bounded cross\-correlation\.

Injectingεt→εt\+ϵ×​xt⊤​θt\\varepsilon\_\{t\}\\to\\varepsilon\_\{t\}\+\\epsilon\_\{\\times\}x\_\{t\}^\{\\top\}\\theta\_\{t\}forϵ×∈\{0,0\.01,0\.05,0\.1,0\.2,0\.5,1\.0\}\\epsilon\_\{\\times\}\\in\\\{0,0\.01,0\.05,0\.1,0\.2,0\.5,1\.0\\\}\. Even atϵ×=1\.0\\epsilon\_\{\\times\}=1\.0\(cross\-correlation equal to signal\), regret increases by<1%<1\\%, indicating that moderate violations of orthogonality are practically benign\.

#### C\. Imperfect probe coverage\.

Restricting probe directions to the firstdcov∈\{1,2,3,4\}d\_\{\\mathrm\{cov\}\}\\in\\\{1,2,3,4\\\}coordinates produces a dramatic monotonic regret blow\-up: atdcov=1d\_\{\\mathrm\{cov\}\}=1, SPSC regret rises to4,2894\{,\}289, nearly matching LinUCB \(4,4634\{,\}463\); subspace error degrades to0\.750\.75\. This directly confirms the necessity results: restricted coverage destroys identifiability and forcesΩ​\(T\)\\Omega\(T\)regret within the unobserved directions\.

![Refer to caption](https://arxiv.org/html/2605.20269v1/figures/experiment_robustness_abc.png)Figure 5:Robustness and necessity experiments\. \(a\) Variance misspecification, regret stable through\|δσ\|=0\.5\|\\delta\_\{\\sigma\}\|=0\.5\. \(b\) Cross\-correlation relaxation,<1%<1\\%degradation throughϵ×=1\.0\\epsilon\_\{\\times\}=1\.0\. \(c\) Imperfect coverage, regret blow\-up with restricted probe directions\.

### H\.4Assumption\-violation master table \(large\-scale\)

We complement the small\-scale A/B/C ablations above with a large\-scale \(d=60d\{=\}60,r=5r\{=\}5,K=10K\{=\}10,T=5,000T\{=\}5\{,\}000\) assumption sweep over \(a\) variance misspecificationσ^2/σε2∈\{0\.5,1,2,4\}\\widehat\{\\sigma\}^\{2\}/\\sigma\_\{\\varepsilon\}^\{2\}\\in\\\{0\.5,1,2,4\\\}, \(b\) approximate\-rank perturbationϵk⟂∈\{0,0\.05,0\.1,0\.2,0\.4\}\\epsilon\_\{k\}^\{\\perp\}\\in\\\{0,0\.05,0\.1,0\.2,0\.4\\\}, and \(c\) spectral radiusρ​\(Ak\)∈\{0\.8,0\.95,0\.99,1\.0\}\\rho\(A\_\{k\}\)\\in\\\{0\.8,0\.95,0\.99,1\.0\\\}\(the last violates the stable\-LDS hypothesis\)\. Variance misspec is absorbed into the scaled\-identity bias \(Lemma[C\.6](https://arxiv.org/html/2605.20269#A3.Thmtheorem6)\) and the relative gap stays flat \(σ^2/σε2\\widehat\{\\sigma\}^\{2\}/\\sigma\_\{\\varepsilon\}^\{2\}ratio1\.27→1\.161\.27\\to 1\.16as the sweep goes0\.5→40\.5\\to 4\); approximate\-rank degrades regret near\-linearly inϵk⟂\\epsilon\_\{k\}^\{\\perp\}; SPSC remains well\-behaved throughρ=0\.99\\rho=0\.99and degrades gracefully atρ=1\\rho=1\(random\-walk limit, outside the stable\-LDS assumption\)\.

Table 17:Assumption\-violation master table\(d=60d\{=\}60,r=5r\{=\}5,K=10K\{=\}10,T=5,000T\{=\}5\{,\}000, 10 seeds, costed dynamic regret, mean±\\pmSE\)\. SPSC tracks Oracle through all three sweeps; bold = best non\-Oracle in row\.SweepLevelOracleSPSC\-Alg1SPSC\-AdapLinUCBSW\-LinUCBD\-LinUCBLowOFULσ^2/σε2\\widehat\{\\sigma\}^\{2\}/\\sigma\_\{\\varepsilon\}^\{2\}0\.50\.5221±5221\\pm 5𝟐𝟖𝟏±𝟏𝟎\\mathbf\{281\\pm 10\}304±11304\\pm 11397±17397\\pm 17395±16395\\pm 16401±18401\\pm 18370±19370\\pm 191\.01\.0257±6257\\pm 6𝟑𝟏𝟓±𝟏𝟎\\mathbf\{315\\pm 10\}319±10319\\pm 10413±18413\\pm 18412±18412\\pm 18415±19415\\pm 19358±17358\\pm 172\.02\.0299±10299\\pm 10357±13357\\pm 13𝟑𝟓𝟓±𝟏𝟑\\mathbf\{355\\pm 13\}421±19421\\pm 19421±18421\\pm 18423±20423\\pm 20377±14377\\pm 144\.04\.0344±12344\\pm 12398±16398\\pm 16398±16398\\pm 16426±19426\\pm 19425±19425\\pm 19427±20427\\pm 20𝟑𝟗𝟎±𝟐𝟎\\mathbf\{390\\pm 20\}ϵk⟂\\epsilon\_\{k\}^\{\\perp\}0\.000\.00257±6257\\pm 6𝟑𝟏𝟓±𝟏𝟎\\mathbf\{315\\pm 10\}319±10319\\pm 10413±18413\\pm 18412±18412\\pm 18415±19415\\pm 19358±17358\\pm 170\.050\.05255±7255\\pm 7𝟑𝟏𝟏±𝟏𝟐\\mathbf\{311\\pm 12\}331±10331\\pm 10414±18414\\pm 18414±18414\\pm 18417±19417\\pm 19379±20379\\pm 200\.100\.10261±7261\\pm 7𝟑𝟏𝟗±𝟏𝟑\\mathbf\{319\\pm 13\}331±12331\\pm 12422±19422\\pm 19422±18422\\pm 18425±19425\\pm 19376±20376\\pm 200\.200\.20286±8286\\pm 8𝟑𝟒𝟎±𝟏𝟑\\mathbf\{340\\pm 13\}348±6348\\pm 6452±19452\\pm 19453±18453\\pm 18457±20457\\pm 20399±19399\\pm 190\.400\.40358±9358\\pm 9𝟑𝟗𝟔±𝟏𝟎\\mathbf\{396\\pm 10\}410±10410\\pm 10559±21559\\pm 21561±20561\\pm 20565±22565\\pm 22497±13497\\pm 13ρ​\(Ak\)\\rho\(A\_\{k\}\)0\.800\.80713±6713\\pm 6745±7745\\pm 7747±9747\\pm 9744±8744\\pm 8743±6743\\pm 6745±8745\\pm 8𝟕𝟑𝟐±𝟗\\mathbf\{732\\pm 9\}0\.950\.951083±111083\\pm 11𝟏𝟐𝟗𝟏±𝟏𝟔\\mathbf\{1291\\pm 16\}1307±141307\\pm 141403±161403\\pm 161406±151406\\pm 151404±191404\\pm 191330±181330\\pm 180\.990\.991132±231132\\pm 232017±462017\\pm 46𝟏𝟗𝟐𝟗±𝟑𝟒\\mathbf\{1929\\pm 34\}2751±462751\\pm 462732±442732\\pm 442750±522750\\pm 522585±542585\\pm 541\.001\.00914±19914\\pm 192899±832899\\pm 83𝟐𝟖𝟏𝟑±𝟓𝟗\\mathbf\{2813\\pm 59\}4644±904644\\pm 904523±874523\\pm 874674±904674\\pm 905552±1565552\\pm 156
### H\.5Subspace recovery rate and change\-point adaptation

Figure[6](https://arxiv.org/html/2605.20269#A8.F6)plots the binned mean subspace error‖P^k−Pk⋆‖2\\\|\\widehat\{P\}\_\{k\}\-P\_\{k\}^\{\\star\}\\\|\_\{2\}vs\. probe count; the empirical rate matches the predicted1/m1/\\sqrt\{m\}on a log\-log scale\. Figure[7](https://arxiv.org/html/2605.20269#A8.F7)plots post\-change instantaneous regret and the subspace\-error trajectory: SPSC recovers substantially faster than ambient LinUCB after each boundary\.

![Refer to caption](https://arxiv.org/html/2605.20269v1/figures/experiment2_subspace_recovery.png)Figure 6:Subspace recovery\.‖P^k−Pk⋆‖2\\\|\\widehat\{P\}\_\{k\}\-P\_\{k\}^\{\\star\}\\\|\_\{2\}vs\. probe count matches the predicted1/m1/\\sqrt\{m\}rate on a log\-log scale\.![Refer to caption](https://arxiv.org/html/2605.20269v1/figures/experiment4_changepoint_recovery.png)Figure 7:Change\-point adaptation\.Instantaneous regret drops sharply after each boundary as fresh probes rebuild the subspace\.
### H\.6Noise robustness, change\-point frequency, drift speed

Three single\-parameter sweeps on the reference setting\.

#### Noise\.

Sweepingσε∈\{0\.05,0\.10,0\.20,0\.30,0\.50,0\.80\}\\sigma\_\{\\varepsilon\}\\in\\\{0\.05,0\.10,0\.20,0\.30,0\.50,0\.80\\\}: SPSC/LinUCB ratio grows mildly with noise \(from0\.5660\.566to0\.5950\.595\); SPSC/Oracle stable at≈1\.55×\\approx 1\.55\\times\. The low\-rank benefit is not a low\-noise artifact\.

#### Change\-point frequency\.

K∈\{1,2,4,6,8,12\}K\\in\\\{1,2,4,6,8,12\\\}atT=6,000T\{=\}6\{,\}000\. Ratio grows from0\.4140\.414\(long segments\) to0\.8550\.855\(very short\); SPSC retains an edge at all frequencies but the margin shrinks as the per\-segment probe budget collapses below the identifiability threshold\.

#### Drift speed\.

LDS spectral radiusρ∈\{0\.30,…,0\.99\}\\rho\\in\\\{0\.30,\\ldots,0\.99\\\}\. Sharp phase transition: SPSC/LinUCB≈1\.01\\approx 1\.01forρ≤0\.70\\rho\\leq 0\.70, drops to0\.8610\.861atρ=0\.95\\rho\{=\}0\.95, and to0\.5820\.582atρ=0\.99\\rho\{=\}0\.99\. Subspace error is nearly constant acrossρ\\rho\(0\.280\.28–0\.330\.33\), so the missing benefit at lowρ\\rhois a signal\-energy effect, not estimation failure: low\-rank structure in a signal already dominated by noise leaves little to extract\.

![Refer to caption](https://arxiv.org/html/2605.20269v1/figures/experiment6_noise_robustness.png)Figure 8:Noise robustness: SPSC advantage is noise\-monotone\.![Refer to caption](https://arxiv.org/html/2605.20269v1/figures/experiment7_changepoint_frequency.png)Figure 9:Change\-point frequency\.![Refer to caption](https://arxiv.org/html/2605.20269v1/figures/experiment8_drift_speed.png)Figure 10:Drift speed\. Benefit gated by LDS correlation timeτρ=1/\(1−ρ\)\\tau\_\{\\rho\}=1/\(1\-\\rho\)\.

## Appendix IComparison with nonstationary baselines \(small\-ddstress test\)

We adopt the small\-ddpiecewise\-stationary stress test ofRussacet al\.\[[2019](https://arxiv.org/html/2605.20269#bib.bib6)\]both to verify that SPSC’s gains do not depend on large\-ddlow\-rank regimes and to compare SPSC against the standard sliding\-window and discounted baselines on the setup used to validate D\-LinUCB\. Setup:d=2d\{=\}2,r=1r\{=\}1,K=4K\{=\}4,T=6,000T\{=\}6\{,\}000,σε=1\\sigma\_\{\\varepsilon\}\{=\}1, 50 arms, 30 seeds\. SPSC reduces control regret by46\.5%46\.5\\%vs\. D\-LinUCB and34\.8%34\.8\\%vs\. SW\-LinUCB; probe overhead is a0\.9%0\.9\\%fraction\.

Table 18:Final control and costed regret on the small\-ddpiecewise\-stationary stress test ofRussacet al\.\[[2019](https://arxiv.org/html/2605.20269#bib.bib6)\]\(mean±\\pmSE, 30 seeds\)\.AlgorithmControlCostedvs\. D\-LinUCBSPSC Alg\. 1 \(ours\)2,229±542\{,\}229\\pm 542,2492\{,\}249−46\.5%\\mathbf\{\-46\.5\\%\}Oracle LinUCB1,757±551\{,\}757\\pm 551,7571\{,\}757−57\.8%\-57\.8\\%D\-LinUCB\[Russacet al\.,[2019](https://arxiv.org/html/2605.20269#bib.bib6)\]4,167±1104\{,\}167\\pm 1104,1674\{,\}167—SW\-LinUCB\[Cheunget al\.,[2019](https://arxiv.org/html/2605.20269#bib.bib5)\]3,417±823\{,\}417\\pm 823,4173\{,\}417−18\.0%\-18\.0\\%OFUL\[Abbasi\-Yadkoriet al\.,[2011](https://arxiv.org/html/2605.20269#bib.bib2)\]4,645±1494\{,\}645\\pm 1494,6454\{,\}645\+11\.5%\+11\.5\\%Reset\-LinUCB \(oracle\)4,647±1474\{,\}647\\pm 1474,6474\{,\}647\+11\.5%\+11\.5\\%![Refer to caption](https://arxiv.org/html/2605.20269v1/figures/experiment9_sota_benchmark.png)Figure 11:Small\-ddpiecewise\-stationary stress test ofRussacet al\.\[[2019](https://arxiv.org/html/2605.20269#bib.bib6)\]\(d=2d\{=\}2,r=1r\{=\}1,K=4K\{=\}4,T=6,000T\{=\}6\{,\}000, 30 seeds\)\.\(a\)Cumulative control regret; vertical dotted lines mark the three change points\.\(b\)Final control regret per method; SPSC is the best non\-oracle baseline\.
## Appendix JWarfarin: random\-subspace ablation

The Warfarin gain reported in §[5\.3](https://arxiv.org/html/2605.20269#S5.SS3)admits two distinct explanations: projection of the9393\-dimensional regression onto anrr\-dimensional subspace, which alone reduces the effective dimension and stabilizes the ridge estimate; and identification of the*correct*rank\-rrsubspace via the probe\-based estimator\. The two cannot be separated from a single regret comparison, since SPSC performs both simultaneously\. We disentangle them by replacing the learned subspaceU^t\\widehat\{U\}\_\{t\}with a fresh random rank\-rrprojection at every segment, leaving every other component of SPSC unchanged; the remaining setup mirrors §[5\.3](https://arxiv.org/html/2605.20269#S5.SS3)\(d=93d\{=\}93,K=8K\{=\}8,T=5,000T\{=\}5\{,\}000,rrswept over\{1,2,3,5,10\}\\\{1,2,3,5,10\\\},1010seeds\)\. The random\-subspace variant captures roughly half of the SPSC\-vs\-LinUCB regret gap, so dimensionality reduction accounts for approximately half of the gain and identification of the correct subspace for the remainder\. Consistent with this decomposition, the learned subspace retains between2×2\\timesand6×6\\timesmore signal variance than a random rank\-rrprojection at everyrr, quantifying the value of the probe\-based identification\.

![Refer to caption](https://arxiv.org/html/2605.20269v1/figures/ablation_warfarin_random_subspace.png)Figure 12:Warfarin random\-subspace ablation\.SPSC’s learned subspace vs\. a fresh random rank\-rrprojection at every segment\. Half of the gap to LinUCB is dimensionality reduction; the other half is learned signal\.
## Appendix KBOSS/Jedra adaptation to the piecewise setting

Stationary low\-rank methods exploit the same rank structure as SPSC but assume the subspace is fixed, so without segment\-aware restarts they would fail trivially in the piecewise\-stationary setting\. To isolate the contribution of*online*subspace identification rather than mere low\-rank exploitation, we provide BOSS\[Duonget al\.,[2024](https://arxiv.org/html/2605.20269#bib.bib20)\]and Jedra\[Jedraet al\.,[2024](https://arxiv.org/html/2605.20269#bib.bib16)\]with the true segment boundaries \(an oracle advantage SPSC does not receive\), restart each at every boundary, and otherwise leave their hyperparameters at the authors’ recommended defaults\. The question is then whether identifying a*changing*subspace online still outperforms exploiting a*fixed*low\-rank reward offline, even under this oracle advantage\. The benchmark is piecewise LDS,K=10,T=5,000,σε=0\.3K\{=\}10,T\{=\}5\{,\}000,\\sigma\_\{\\varepsilon\}\{=\}0\.3, 40 actions, 10 seeds, probe costc=0\.1c\{=\}0\.1, on a gridd∈\{55,105,200\}×r∈\{5,10,20\}d\\in\\\{55,105,200\\\}\\times r\\in\\\{5,10,20\\\}\(eight cells:\(55,5\),\(55,10\),\(105,5\),\(105,10\),\(105,20\),\(200,5\),\(200,10\),\(200,20\)\(55,5\),\(55,10\),\(105,5\),\(105,10\),\(105,20\),\(200,5\),\(200,10\),\(200,20\)\)\.

Results \(cf\. Table[4](https://arxiv.org/html/2605.20269#S5.T4)\): SPSC Alg\. 1 wins every cell, by5\.85\.8–19\.9%19\.9\\%, with the lead largest at smalldd\(where the ambientddis closest torrand probing pays off most\) and narrowing to5\.85\.8–8\.0%8\.0\\%atd=200d\{=\}200as oracle\-restart\-plus\-PCA closes the gap\. SPSC\-Adaptive \(no oracle restarts\) also beats BOSS and Jedra on every cell, and the ranking is consistent on every seed\. The point is that “low\-rank exploitation” alone is not enough for changing\-subspace problems: the learner must*identify a changing subspace online*, which is SPSC’s core capability\.

## Appendix LVancomycin: full per\-rank tables

The body table reports Vancomycin at a single rank, but the true rank of the pharmacokinetic response is not known in advance\. We sweeprrhere to confirm that SPSC\-Adaptive’s advantage holds across rank choices\. Setup:d=93d\{=\}93,K=8K\{=\}8,T=5,000T\{=\}5\{,\}000,σε=0\.3\\sigma\_\{\\varepsilon\}\{=\}0\.3, 10 seeds, probe period 10, window 200, probe costc=0\.1c\{=\}0\.1\(per\-rank breakdown of the Table[3](https://arxiv.org/html/2605.20269#S5.T3)summary in the main body\)\. SPSC\-Adaptive beats every non\-oracle baseline at every rank\.

Table 19:Vancomycin per\-rank results\(mean±\\pmSE, 10 seeds\)\. “vs\. best comp\.” compares SPSC\-Adaptive against the strongest non\-oracle baseline in each column \(marked⋆\)\. SPSC\-Adaptive wins every rank\.Methodr=1r\{=\}1r=2r\{=\}2r=3r\{=\}3r=5r\{=\}5r=10r\{=\}10Oracle LinUCB34\.3±1\.534\.3\\pm 1\.5115\.1±2\.0115\.1\\pm 2\.0197\.2±3\.0197\.2\\pm 3\.0268\.1±3\.4268\.1\\pm 3\.4373\.2±5\.7373\.2\\pm 5\.7SPSC Alg\. 1 \(ours\)840\.3±24\.5840\.3\\pm 24\.5805\.9±15\.4805\.9\\pm 15\.4802\.3±12\.3802\.3\\pm 12\.3805\.3±9\.5805\.3\\pm 9\.5811\.0±12\.2811\.0\\pm 12\.2SPSC\-Adaptive525\.3±45\.8\\mathbf\{525\.3\\pm 45\.8\}613\.6±33\.1\\mathbf\{613\.6\\pm 33\.1\}640\.3±33\.0\\mathbf\{640\.3\\pm 33\.0\}665\.9±27\.2\\mathbf\{665\.9\\pm 27\.2\}705\.6±19\.5\\mathbf\{705\.6\\pm 19\.5\}LowOFUL1049\.9±12\.81049\.9\\pm 12\.8740\.1±36\.3⋆740\.1\\pm 36\.3^\{\\star\}734\.5±37\.8734\.5\\pm 37\.8791\.5±26\.0791\.5\\pm 26\.0801\.9±20\.1801\.9\\pm 20\.1VOFUL1063\.5±5\.51063\.5\\pm 5\.5789\.7±24\.8789\.7\\pm 24\.8712\.5±25\.5⋆712\.5\\pm 25\.5^\{\\star\}763\.0±30\.6⋆763\.0\\pm 30\.6^\{\\star\}758\.6±27\.9⋆758\.6\\pm 27\.9^\{\\star\}LowRank\-Reward1175\.6±11\.61175\.6\\pm 11\.6806\.8±11\.2806\.8\\pm 11\.2835\.1±10\.7835\.1\\pm 10\.7898\.8±6\.7898\.8\\pm 6\.7880\.5±5\.5880\.5\\pm 5\.5SW\-LinUCB875\.6±6\.7875\.6\\pm 6\.7875\.6±6\.7875\.6\\pm 6\.7875\.6±6\.7875\.6\\pm 6\.7875\.6±6\.7875\.6\\pm 6\.7875\.6±6\.7875\.6\\pm 6\.7D\-LinUCB925\.3±5\.8925\.3\\pm 5\.8925\.3±5\.8925\.3\\pm 5\.8925\.3±5\.8925\.3\\pm 5\.8925\.3±5\.8925\.3\\pm 5\.8925\.3±5\.8925\.3\\pm 5\.8Restart\-LinUCB808\.9±5\.3⋆808\.9\\pm 5\.3^\{\\star\}808\.9±5\.3808\.9\\pm 5\.3808\.9±5\.3808\.9\\pm 5\.3808\.9±5\.3808\.9\\pm 5\.3808\.9±5\.3808\.9\\pm 5\.3LinUCB825\.3±6\.1825\.3\\pm 6\.1825\.3±6\.1825\.3\\pm 6\.1825\.3±6\.1825\.3\\pm 6\.1825\.3±6\.1825\.3\\pm 6\.1825\.3±6\.1825\.3\\pm 6\.1SPSC\-Adaptive vs\. LinUCB−36\.4%\-36\.4\\%−25\.7%\-25\.7\\%−22\.4%\-22\.4\\%−19\.3%\-19\.3\\%−14\.5%\-14\.5\\%SPSC\-Adaptive vs\. best comp\.−35\.1%\-35\.1\\%−17\.1%\-17\.1\\%−10\.1%\-10\.1\\%−12\.7%\-12\.7\\%−7\.0%\\phantom\{\-\}\-7\.0\\%
## Appendix MWhen the adaptive variant wins

This appendix disentangles the two SPSC variants: Alg\.[1](https://arxiv.org/html/2605.20269#alg1)assumes oracle change points; Alg\.[2](https://arxiv.org/html/2605.20269#alg2)detects them online via the detector statistic \([14](https://arxiv.org/html/2605.20269#A5.E14)\)\. When the oracle boundaries are correct, Alg\.[1](https://arxiv.org/html/2605.20269#alg1)is slightly better because the adaptive detector pays a small statistical price for unknown change\-point localization\. When the oracle provides misspecified \(false\-alarm\) boundaries, the picture reverses sharply\.

![Refer to caption](https://arxiv.org/html/2605.20269v1/figures/experiment_oracle_quality.png)Figure 13:SPSC Alg\. 1 vs\. SPSC\-Adaptive under oracle misspecification\.Final cumulative costed regret as the oracle\-supplied number of segmentsKoracleK\_\{\\mathrm\{oracle\}\}varies, withKreal=5K\_\{\\mathrm\{real\}\}\{=\}5true subspace shifts \(d=60d\{=\}60,r=5r\{=\}5,T=5,000T\{=\}5\{,\}000,2020seeds; mean±\\pmSE\)\. Alg\.[1](https://arxiv.org/html/2605.20269#alg1)is fedKoracle∈\{5,10,20,40,80,150,200\}K\_\{\\mathrm\{oracle\}\}\\in\\\{5,10,20,40,80,150,200\\\}evenly\-spaced boundaries \(extras beyondKrealK\_\{\\mathrm\{real\}\}are false alarms\) and degrades monotonically; Alg\.[2](https://arxiv.org/html/2605.20269#alg2)runs CUSUM on the clean stream and ignores the oracle, so its regret is flat; LinUCB is an oracle\-free reference\. The two SPSC variants cross over atKoracle≈10K\_\{\\mathrm\{oracle\}\}\{\\approx\}10: at the correct oracle \(Koracle=Kreal=5K\_\{\\mathrm\{oracle\}\}\{=\}K\_\{\\mathrm\{real\}\}\{=\}5\) Alg\.[1](https://arxiv.org/html/2605.20269#alg1)is∼8%\{\\sim\}8\\%better, while atKoracle=200K\_\{\\mathrm\{oracle\}\}\{=\}200it is∼37%\{\\sim\}37\\%worse\.SPSC\-Adaptive’s regret is flat asKoracleK\_\{\\mathrm\{oracle\}\}grows from the truth \(Kreal=5K\_\{\\mathrm\{real\}\}\{=\}5\) to40×40\\timesover\-specified \(Koracle=200K\_\{\\mathrm\{oracle\}\}\{=\}200\), while Alg\.[1](https://arxiv.org/html/2605.20269#alg1)degrades monotonically and is∼37%\{\\sim\}37\\%worse than Adaptive atKoracle=200K\_\{\\mathrm\{oracle\}\}\{=\}200\(a1\.37×1\.37\\timesratio\): a detector\-based reset is strictly safer than a fixed schedule when boundaries are unknown or noisy\.