Catching a Moving Subspace: Low-Rank Bandits Beyond Stationarity

• URL: http://arxiv.org/abs/2605.20269v1
• Date: Mon, 18 May 2026 22:01:48 GMT
• Title: Catching a Moving Subspace: Low-Rank Bandits Beyond Stationarity
• Abstract summary: We study piecewise-stationary low-rank linear contextual bandits with scalar feedback.<n>With single-play scalar rewards, the moving subspace is recoverable through quadratic functionals of rewards.<n>This is the first work to characterize the identification boundary and attain the intrinsic-rank dynamic-regret rate.
• Score: 13.385373310554327
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Many bandit deployments (recommendation, clinical dosing, ad targeting) share two facts prior work handles only in isolation: rewards live on a low-dimensional latent subspace, and that subspace drifts. Stationary low-rank bandits exploit rank but break under subspace change; non-stationary linear bandits adapt to drift but pay ambient rate $\widetilde{O}(d\sqrt{T})$. We study piecewise-stationary low-rank linear contextual bandits with scalar feedback: $θ_t = B_k^\star w_t$ with rank-$r$ factor $B_k^\star\in\mathbb{R}^{d\times r}$ constant within each of $K$ unknown segments and able to shift at 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 iff three probe-side conditions hold: known noise variance, bounded state-noise coupling, and full-dimensional probe support. Each is necessary in the unrestricted-second-moment problem, and jointly they are sufficient, characterizing the boundary of the solvable region. (ii) Algorithm and dynamic regret. SPSC interleaves isotropic probes with windowed projected ridge-UCB exploitation inside the learned $r$-dimensional subspace; a CUSUM-style variant discovers segment boundaries online. The costed dynamic regret is $\widetilde{O}(r\sqrt{T})+\widetilde{O}(T^{2/3})+O(W\,V_{\mathrm{in}})$, replacing the ambient $d\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 whenever $d-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.

Related papers

• Constrained Online Learning with Noisy Constraint Values [55.29259818039367]
  Under common feasibility, our LEDGER algorithm attains $O(sqrt T)$ expected regret and $O(sqrtTlog(eT))$ expected budget violation.<n>Neither a Slater condition, independence between feedback channels, nor an absolute constraint-value bound is needed.
  arXiv  Detail & Related papers  (2026-09-07T01:38:41Z)
• Breaking the Total Variance Barrier: Sharp Sample Complexity for Linear Heteroscedastic Bandits with Fixed Action Set [93.03556214432615]
  In this paper, we revisit the linear bandit problem with heteroscedastic noise, where the action set is prefixed throughout the learning process.<n>We propose a novel variance-adaptive algorithm textttVAEE for large action set, which actively explores actions that maximize the information gain.<n>We establish a nearly matching lower bound for the fixed action set setting indicating that emphharmonic-mean dependent rate is unavoidable.
  arXiv  Detail & Related papers  (2026-07-26T14:24:34Z)
• The Lie We Tell: Correcting the Euclidean Fallacy in Vision Language Action Policies via Score Matching on Tangent Space [19.950575615573978]
  We introduce a diffusion framework operating intrinsically on SE(3).<n>Our method injects noise through left-invariant SDEs, predicts scores in the space tangent, and retracts samples via the exponential map.<n>On CALVIN ABC$rightarrow$D, LDA improves average task length from $3.27$ to $3.51$ ($+7.3%$)
  arXiv  Detail & Related papers  (2026-06-01T07:59:29Z)
• Dynamic Mode Decomposition along Depth in Vision Transformers [2.899294572150795]
  We ask whether ViT depth implements approximately textitautonomous linear dynamics.<n>We test this using Dynamic Mode Decomposition (DMD), which fits $K$ from selected, consecutive hidden-state pairs.<n>On four pretrained DINO ViTs, we study the regularization, rank, and calibration budget required for stable fitting.
  arXiv  Detail & Related papers  (2026-05-08T10:33:03Z)
• Subspace Geometry Governs Catastrophic Forgetting in Low-Rank Adaptation [0.0]
  Low-Rank Adaptation (LoRA) has emerged as a parameter-efficient approach for adapting large pre-trained models.<n>We present a geometric theory characterizing catastrophic forgetting in LoRA through the lens of gradient subspace interactions.
  arXiv  Detail & Related papers  (2026-02-10T22:45:47Z)
• Improved Algorithm for Adversarial Linear Mixture MDPs with Bandit Feedback and Unknown Transition [71.33787410075577]
  We study reinforcement learning with linear function approximation, unknown transition, and adversarial losses. We propose a new algorithm that attains an $widetildeO(dsqrtHS3K + sqrtHSAK)$ regret with high probability.
  arXiv  Detail & Related papers  (2024-03-07T15:03:50Z)
• Horizon-free Reinforcement Learning in Adversarial Linear Mixture MDPs [72.40181882916089]
  We show that our algorithm achieves an $tildeObig((d+log (|mathcalS|2 |mathcalA|))sqrtKbig)$ regret with full-information feedback, where $d$ is the dimension of a known feature mapping linearly parametrizing the unknown transition kernel of the MDP, $K$ is the number of episodes, $|mathcalS|$ and $|mathcalA|$ are the cardinalities of the state and action spaces
  arXiv  Detail & Related papers  (2023-05-15T05:37:32Z)
• Borda Regret Minimization for Generalized Linear Dueling Bandits [65.09919504862496]
  We study the Borda regret minimization problem for dueling bandits, which aims to identify the item with the highest Borda score. We propose a rich class of generalized linear dueling bandit models, which cover many existing models. Our algorithm achieves an $tildeO(d2/3 T2/3)$ regret, which is also optimal.
  arXiv  Detail & Related papers  (2023-03-15T17:59:27Z)
• Bilinear Exponential Family of MDPs: Frequentist Regret Bound with Tractable Exploration and Planning [0.0]
  We study the problem of episodic reinforcement learning in continuous state-action spaces with unknown rewards and transitions. We propose an algorithm, BEF-RLSVI, that uses penalized maximum likelihood estimators to learn the unknown parameters.
  arXiv  Detail & Related papers  (2022-10-05T08:26:49Z)
• Stochastic Linear Bandits with Protected Subspace [51.43660657268171]
  We study a variant of the linear bandit problem wherein we optimize a linear objective function but rewards are accrued only to an unknown subspace. In particular, at each round, the learner must choose whether to query the objective or the protected subspace alongside choosing an action. Our algorithm, derived from the OFUL principle, uses some of the queries to get an estimate of the protected space.
  arXiv  Detail & Related papers  (2020-11-02T14:59:39Z)
• Nearly Dimension-Independent Sparse Linear Bandit over Small Action Spaces via Best Subset Selection [71.9765117768556]
  We consider the contextual bandit problem under the high dimensional linear model. This setting finds essential applications such as personalized recommendation, online advertisement, and personalized medicine. We propose doubly growing epochs and estimating the parameter using the best subset selection method.
  arXiv  Detail & Related papers  (2020-09-04T04:10:39Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.