捕捉移动子空间：超越平稳性的低秩老虎机

# 捕捉移动子空间：超越平稳性的低秩赌博机

**来源：** https://arxiv.org/html/2605.20269

**Hamed Khosravi**  
H. Milton Stewart School of Industrial and Systems Engineering  
Georgia Institute of Technology  
Atlanta, GA 30332  
[email protected]  

**和**

**Xiaoming Huo**  
H. Milton Stewart School of Industrial and Systems Engineering  
Georgia Institute of Technology  
Atlanta, GA 30332  
[email protected]  

###### 摘要

许多真实的赌博机部署（推荐系统、临床剂量、广告定向）共享两个结构性事实，但先前的工作仅孤立地处理它们：奖励存在于一个低维潜在子空间中，并且该子空间会发生漂移。静态低秩赌博机利用了秩，但在任何子空间变化下都会失效；非平稳线性赌博机适应漂移，但支付环境维度的代价 \(\widetilde{\mathcal{O}}(d\sqrt{T})\)。我们研究的是具有标量反馈的*分段平稳低秩*线性情境赌博机：\(\theta_t = B_k^\star w_t\)，其中秩为 \(r\) 的因子 \(B_k^\star \in \mathbb{R}^{d \times r}\) 在 \(K\) 个未知分段内保持恒定，并可能在边界处发生偏移。我们的结果在三个维度上是紧的。

**(i) 可辨识性边界。** 使用单次标量奖励，当且仅当三个探测侧条件成立时（已知噪声方差、有界状态-噪声耦合、全维探测支撑），移动子空间才可通过奖励的二次泛函恢复。这三个条件在无约束二阶矩问题中各自都是必要的，并且三者共同构成充分条件：这是对可解区域边界的刻画，而不仅仅是充分内点。

**(ii) 算法与动态遗憾。** SPSC（单次子空间校准乐观算法）在学习到的 \(r\) 维子空间内交替使用各向同性探测与窗口投影岭-UCB 开发；一种 CUSUM 风格的自适应变体在线发现分段边界。其有限动态遗憾为 \(\widetilde{\mathcal{O}}(r\sqrt{T}) + \widetilde{\mathcal{O}}(T^{2/3}) + O(W V_{\rm in})\)，用内在秩 \(r\) 取代了环境维度的 \(d\sqrt{T}\) 速率。

**(iii) 实证。** 在涵盖合成数据、UCI/MovieLens、半合成临床数据和 ZOZOTOWN 生产日志数据的十一个基准测试上，当 \(d - r \gtrsim T^{1/6}\) 时，SPSC 优于非平稳和低秩基线方法，与分析得出的交叉点一致。据我们所知，这是首个在此设定下刻画可辨识性边界并达到内在秩动态遗憾速率的工作。

## 1 引言

高维序贯决策（个性化推荐、临床剂量、广告分配）共享两个结构性事实，而线性赌博机文献迄今仅孤立地处理它们：奖励存在于一个低维潜在子空间，并且该子空间会发生漂移。用户偏好、临床反应和广告创意效果占据环境空间 \(\mathbb{R}^d\) 的一个薄片，其内在秩为 \(r \ll d\)；但这个薄片**并非静态的**：品味发生漂移，群体发生变化，治疗方案被修订，潜在因子本身也会跨越未知变化点移动。生产部署使这两个事实都清晰可见：Spotify 的主页情境赌博机明确针对用户意图的每日变化 (Feijer et al., 2025 (https://arxiv.org/html/2605.20269#bib.bib21))；IWPC 华法林队列 (Consortium, 2009 (https://arxiv.org/html/2605.20269#bib.bib1)) 已被重新分析，以揭示三个潜在患者亚组，其剂量-反应系数在边界处符号翻转 (Liu et al., 2025 (https://arxiv.org/html/2605.20269#bib.bib22))；公开的 Open Bandit 日志 (Saito et al., 2021 (https://arxiv.org/html/2605.20269#bib.bib17)) 包含了在 ZOZOTOWN 多个广告活动中收集的标量反馈。

####  文献的止步之处。

静态低秩赌博机 (Jun et al., 2019 (https://arxiv.org/html/2605.20269#bib.bib3); Jedra et al., 2024 (https://arxiv.org/html/2605.20269#bib.bib16); Jang et al., 2024 (https://arxiv.org/html/2605.20269#bib.bib15)) 实现了 \(\widetilde{\mathcal{O}}(r\sqrt{T})\) 的速率，但假设因子固定不变；任何非平凡的子空间变化都会使分析失效（\(\widetilde{\mathcal{O}}\) 隐藏了 \(T, d, r, 1/\delta\) 中的多对数因子）。非平稳线性赌博机 (Russac et al., 2019 (https://arxiv.org/html/2605.20269#bib.bib6); Cheung et al., 2019 (https://arxiv.org/html/2605.20269#bib.bib5)) 通过滑动窗口或折扣来吸收漂移，但在 \(\mathbb{R}^d\) 中运作，并在每个分段内支付 \(\widetilde{\mathcal{O}}(d\sqrt{T})\) 的代价，完全忽略了内在秩。朴素的组合以具有启发性的方式失败：在 \(\mathbb{R}^d\) 中的滑动窗口岭从未恢复子空间；一次性的子空间估计在变化点触发时立即失效；每段重新运行静态低秩算法需要对边界有先知般的访问。没有先前的算法能够在标量反馈下恢复变化的子空间，也没有先前的分析将此恢复过程所需付出的代价与其所带来的开发遗憾减少进行定价。

####  本文工作。

我们研究的是*分段平稳低秩*线性情境赌博机，具有标量反馈：\(\theta_t = B_k^\star w_t\)，其中秩为 \(r\) 的因子 \(B_k^\star \in \mathbb{R}^{d \times r}\) 在 \(K\) 个未知分段 \(\mathcal{I}_k = [\tau_{k-1}, \tau_k)\) 内保持不变（变化点为 \(1 = \tau_0 < \tau_1 < \dots < \tau_K = T+1\)），并可能在边界处发生偏移，学习器仅能观测到标量响应 \(y_t = x_t^\top \theta_t + \varepsilon_t\)（§[2](https://arxiv.org/html/2605.20269#S2)）。真正的困难是双重的。(a) 单个标量响应 \(y_t\) 是 \(\theta_t \theta_t^\top\) 的一个秩一二次测量，因此移动子空间只能通过*二阶*探测来恢复。(b) 每次探测都会将一个时间步从开发中分流，因此探测的获取本身必须根据其启用的遗憾来进行定价。我们的结果在三个维度上是紧的。

####  贡献。

**(i) 可辨识性边界（定理 2.2 (https://arxiv.org/html/2605.20269#S2.Thmtheorem2)）。** 三个探测侧条件（已知噪声方差、有界状态-噪声耦合、全维探测支撑）在无约束二阶矩问题中各自都是必要的，并且共同构成从标量奖励的二次泛函中恢复 \(\mathrm{range}(B_k^\star)\) 的充分条件。必要性部分，即三个匹配的不可能性结果（命题 C.12 (https://arxiv.org/html/2605.20269#A3.Thmtheorem12)–C.14 (https://arxiv.org/html/2605.20269#A3.Thmtheorem14)），是将其与一般的可辨识性陈述区分开来的关键：它刻画了可解区域的边界，而不仅仅是充分内点。

**(ii) 算法与有限动态遗憾（定理 4.1 (https://arxiv.org/html/2605.20269#S4.Thmtheorem1)）。** SPSC（算法 1 (https://arxiv.org/html/2605.20269#alg1)）通过学习到的 \(r\) 维子空间内的二次测量恒等式，交替使用各向同性探测与窗口投影岭-UCB 开发；SPSC-自适应变体（算法 2 (https://arxiv.org/html/2605.20269#alg2)）使用 CUSUM 风格的检测器在线发现分段变化。有限动态遗憾为 \(\mathrm{DynReg}_T^{(c)} \leq \widetilde{\mathcal{O}}(r\sqrt{T}) + \widetilde{\mathcal{O}}(T^{2/3}) + O(W V_{\rm in})\)，用内在秩 \(r\) 取代了环境维度的 \(d\sqrt{T}\) 速率，其中 \(W\) 是开发窗口，\(V_{\rm in}\) 是段内路径变化。

**(iii) 十一个基准测试对阵十一个基线方法。** 一个合成相变网格、五个 UCI 环境加上 MovieLens、两个半合成临床数据集、Russac et al. (2019 (https://arxiv.org/html/2605.20269#bib.bib6)) 的小 \(d\) 分段平稳压力测试，以及 Open Bandit 生产日志，对阵 LinUCB、D-LinUCB、SW-LinUCB、Restart-LinUCB、LowOFUL、VOFUL、LowRank-Reward、LinTS、SW-LinTS 以及适配的静态低秩方法 BOSS 和 Jedra。当 \(d - r \gtrsim T^{1/6}\) 时，SPSC 实现了遗憾减少，与分析得出的交叉点一致。一个直接的必要性压力测试（附录 H.3 (https://arxiv.org/html/2605.20269#A8.SS3)，C 部分）将探测覆盖限制在一个真子空间内，并重现了命题 C.14 (https://arxiv.org/html/2605.20269#A3.Thmtheorem14) 预测的 \(\Omega(T)\) 爆炸，证实了第三个可辨识性条件并非证明伪像。据我们所知，这是首个在标量反馈下的分段平稳低秩设定中刻画可辨识性边界并达到内在秩动态遗憾速率的工作。

####  相关工作。

静态低秩赌博机 (Jun et al., 2019 (https://arxiv.org/html/2605.20269#bib.bib3); Kang et al., 2022 (https://arxiv.org/html/2605.20269#bib.bib13); Jedra et al., 2024 (https://arxiv.org/html/2605.20269#bib.bib16); Jang et al., 2024 (https://arxiv.org/html/2605.20269#bib.bib15); Stojanovic et al., 2023 (https://arxiv.org/html/2605.20269#bib.bib11); Duong et al., 2024 (https://arxiv.org/html/2605.20269#bib.bib20); Lu et al., 2021 (https://arxiv.org/html/2605.20269#bib.bib4)) 达到内在秩速率，但假设 \(B^\star\) 固定；非平稳线性赌博机 (Russac et al., 2019 (https://arxiv.org/html/2605.20269#bib.bib6); Cheung et al., 2019 (https://arxiv.org/html/2605.20269#bib.bib5); Abbasi-Yadkori et al., 2023 (https://arxiv.org/html/2605.20269#bib.bib7); Hou et al., 2024 (https://arxiv.org/html/2605.20269#bib.bib12)) 在环境维度上界定动态遗憾，并忽略低秩结构；代价感知观测 (Seldin et al., 2014 (https://arxiv.org/html/2605.20269#bib.bib8); Tucker et al., 2023 (https://arxiv.org/html/2605.20269#bib.bib9); Elumar et al., 2024 (https://arxiv.org/html/2605.20269#bib.bib10)) 为固定参数的信息获取定价，而非识别变化的子空间。SPSC 位于这三者的交叉点：它 (i) 达到与内在秩 \(r\) 成比例的遗憾标度，(ii) 在没有先知边界的情况下适应变化的子空间，并且 (iii) 明确为探测获取定价。附录 B (https://arxiv.org/html/2605.20269#A2) 给出了完整的定位（表 5 (https://arxiv.org/html/2605.20269#A2.T5)–7 (https://arxiv.org/html/2605.20269#A2.T7)）。

## 2 设定与基于探测的可辨识性

####  分段低秩模型。

在每个回合 \(t\)，奖励参数可分解为 \(\theta_t = B_k^\star w_t\)，其中 \(B_k^\star \in \mathbb{R}^{d \times r}\) 具有标准正交列，并在 \(K \geq 1\) 个分段 \(\mathcal{I}_k\) 上分段恒定（变化点为 \(1 = \tau_0 < \tau_1 < \dots < \tau_K = T+1\) 未知），而潜在状态 \(w_t \in \mathbb{R}^r\) 在每个分段内遵循一个稳定的线性动力系统 \(w_t = A_k w_{t-1} + \eta_{t-1},\quad t \in \mathcal{I}_k\)，其中未知的 \(A_k\) 满足 \(\rho(A_k) \leq 1 - \alpha_0\)（\(\alpha_0 > 0\)，仅用于通过平稳协方差界确保 \(\|w_t\| \leq S_w\)），零均值创新项 \(\eta_{t-1}\) 的协方差为 \(\Sigma_{\eta,k} \succ 0\)。我们假设一致动作有界性 \(\sup_{x \in \mathcal{A}_t} \|x\| \leq R_{\mathcal{A}}\)，一个已知的探测分布 \(Q\) 满足 \(\mathbb{E}[uu^\top] \succeq \rho_Q I_d\) 且具有次高斯边际（有界 \(\|u\| \leq L\) 是一个特例；见注记 2.1 (https://arxiv.org/html/2605.20269#S2.Thmtheorem1)），条件 \(\sigma_\varepsilon\)-次高斯噪声（方差未知），有界状态-噪声耦合 \(\|\mathbb{E}[\varepsilon_t \theta_t]\|_2 \leq \epsilon_\times\)，以及全维探测覆盖。下面的定理 2.2 (https://arxiv.org/html/2605.20269#S2.Thmtheorem2) 表明，这三个探测侧条件对于从单次标量奖励中识别变化的子空间各自必要且共同充分。在整个论文中，\(\delta \in (0, 1)\) 表示全局置信参数（浓度界以概率 \(\geq 1-\delta\) 成立），\(\lambda > 0\) 表示第 3 节 (https://arxiv.org/html/2605.20269#S3) 中窗口估计器所使用的岭正则化参数。

####  二次测量恒等式。

令 \(\widehat{\sigma}^2\) 为算法对噪声方差的估计，定义每个探测回合 \(t \in \mathcal{T}_{\mathrm{probe}}\) 上的中心化探测统计量 \(s_t := y_t^2 - \widehat{\sigma}^2\)。根据第 2 节 (https://arxiv.org/html/2605.20269#S2) 的探测噪声假设，令 \(\delta_\sigma := \widehat{\sigma}^2 - \sigma_\varepsilon^2\)，则
\[
\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,
\tag{1}
\]
其中 \(\widetilde{M}_t := \mathbb{E}[\theta_t \theta_t^\top \mid \mathcal{H}_{t-1}]\) 是可预测二阶矩，其值域包含在 \(\mathrm{range}(B_k^\star)\) 中（对于 \(t \in \mathcal{I}_k\)）；在非退化创新条件 \(\Sigma_{\eta,k} \succ 0\)（第 2 节 (https://arxiv.org/html/2605.20269#S2)）下，探测时间平均值具有确切的值域 \(\mathrm{range}(B_k^\star)\)（命题 C.9 (https://arxiv.org/html/2605.20269#A3.Thmtheorem9)）。在精确探测条件下（\(\delta_\sigma = \epsilon_\times = 0\)），这简化为 \(\mathbb{E}[s_t \mid \cdot] = u_t^\top \widetilde{M}_t u_t\)：*一个标量奖励携带了对 \(\widetilde{M}_t\) 的一个二次测量*。

####  提升子空间估计器。

探测矩算子 \(\mathcal{K}: M \mapsto \mathbb{E}[(u^\top Mu) \, uu^\top]\) 对于尺度化球面探测 \(u=\sqrt{d}\, v,\, v \sim \mathrm{Unif}(\mathbb{S}^{d-1})\) 在对称矩阵上具有闭式逆：
\[
\mathcal{K}(M) = \frac{d}{d+2}\bigl(\operatorname{tr}(M)\, I_d + 2M\bigr), \quad
\mathcal{K}^{-1}(N) = \frac{d+2}{2d}\, N - \frac{\operatorname{tr}(N)}{2d}\, I_d, \quad
\|\mathcal{K}^{-1}\|_{\mathrm{op}\to\mathrm{op}} \leq 1
\tag{2}
\]
在对称子空间上（引理 C.4 (https://arxiv.org/html/2605.20269#A3.Thmtheorem4)）。定义*提升探测样本*
\[
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,
\tag{3}
\]
其中偏差项 \(\widetilde{B}_t = -(\delta_\sigma/d)\, I_d\) 在尺度化球面探测上精确成立，因此 \(\|\widetilde{B}_t\|_{\mathrm{op}} = |\delta_\sigma|/d\)（引理 C.6 (https://arxiv.org/html/2605.20269#A3.Thmtheorem6)）。对分段 \(k\) 的探测回合上的提升样本进行平均，得到 \(\widehat{M}_k := m_k^{-1} \sum_{t \in \mathcal{T}_k} G_t\)（其中 \(\mathcal{T}_k := \mathcal{T}_{\mathrm{probe}} \cap \mathcal{I}_k\)）。