Catching a Moving Subspace: Low-Rank Bandits Beyond Stationarity

Many real bandit deployments (recommendation, 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 assume a fixed subspace. Nonstationary linear bandits adapt to drift but their rates grow with the ambient dimension $d$. We study *piecewise-stationary low-rank* linear contextual bandits with scalar rewards whose parameter factors as ${\theta }_t=B_k^{\star }{w}_t$, where $B_k^{\star }\in {\mathbb{R}}^{d\times r}$ is an orthonormal basis for the rank-$r$ latent reward subspace in segment $k$ and $w_t\in {\mathbb{R}}^r$ is the time-varying latent state. The subspace is constant within each of $K$ unknown segments and may shift at the boundaries. The learner is a bandit with a sensing channel. Besides choosing actions, it may spend a round on a *probe*, a query drawn from a known exploration law that need not be a feasible action, and it pays for each probe its forgone reward plus a fee $c$. We give three results. **(i) The identification boundary** (when the moving subspace can be recovered). With one scalar reward per round, isotropic probes drawn independently of the noise recover the moving subspace, or the part of it that the latent state excites, through quadratic functionals of rewards. The noise variance need not be known. Probes that miss a direction cannot recover the subspace. If the noise may depend on the probe direction, identification can fail even with full coverage. **(ii) Algorithm and dynamic regret.** **SPSC** (Single-Play Subspace-Calibrated Optimism) interleaves isotropic probes with optimistic windowed ridge regression inside the learned $r$-dimensional subspace, given the segment boundaries. An adaptive variant detects them online. Measured against the best action for the mean reward vector, with probe costs charged, the dynamic regret over $T$ rounds is $\tilde{O}(r\sqrt{KT}+(rd{)}^{1/3}{K}^{1/3}{T}^{2/3})$ when the mean reward vector is constant within segments. The $\sqrt{T}$ term depends on the rank $r$, and the ambient dimension enters only the additive cost of learning the subspace. Drift within segments adds the usual window tradeoff. **(iii) Empirics.** Against eleven baselines on nine benchmarks, including UCI datasets, images, MovieLens and production logs, an SPSC variant has the lowest regret in 51 of 58 real-data (dataset, $d$, $r$) cells. On a 40-cell synthetic grid, a rule of thumb suggested by the theory, that SPSC wins once $d-r>T^{1/6}$, picks the winner in 39 cells.