解决动态低秩强化学习中子空间漂移的难题，实现更优的推荐与决策。
Catching a Moving Subspace: Low-Rank Bandits Beyond Stationarity
- 设计分段平稳的低秩带通算法，通过探针与投影策略联合识别漂移子空间。
- 动态误差达 $ ilde{O}(r oot{2}{T}) + ilde{O}(T^{2/3})$，摆脱 $d oot{2}{T}$ 的维度诅咒。
- 在11个真实与合成数据集上验证优势，尤其当 $d-r o T^{1/6}$ 时显著领先。
许多强化学习部署（如推荐、临床给药、广告投放）面临两个共性：回报位于低维潜在子空间，且该子空间会随时间漂移。现有方法要么假设子空间不变，要么适应漂移但代价为环境维度 $d$ 的率 $ ilde{O}(d oot{2}{T})$。本文研究具有标量反馈的分段平稳低秩线性上下文强化学习：$θ_t = B_k^ ext{⋆}w_t$，其中每个 $K$ 个未知时间段内 $B_k^ ext{⋆}∈ℝ^{d×r}$ 为常数秩 $r$ 矩阵。核心成果有三：(i) 识别边界——仅当噪声方差已知、状态-噪声耦合有界、探针支持满维时，可通过奖励的二次泛函恢复移动子空间，三条件缺一不可；(ii) 算法与动态误差——SPSC 算法在学习到的 $r$ 维子空间内结合各向同性探针与窗口投影岭-UCB，CUSUM 变体在线探测段界，动态误差为 $ ilde{O}(r oot{2}{T})+ ilde{O}(T^{2/3})+O(W ext{ }V_{ ext{in}})$，实现内在秩率；(iii) 实验验证——在十一组基准数据（含合成、UCI/MovieLens、半合成临床及 ZOZOTOWN 生产日志）上，当 $d-r\gtrsim T^{1/6}$ 时，性能超越非平稳与低秩基线，与理论交叉点一致。据我们所知，这是首个刻画该问题识别边界并达到内在秩动态误差率的工作。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。