Block Optimism for Nonstationary Bandits with Latent Linear Dynamics¶

会议: NeurIPS 2026
arXiv: 2610.00911
领域: 学习理论
关键词: 内生非平稳多臂老虎机, 隐线性动力学, 双线性奖励, 循环近似, 块乐观探索

一句话总结¶

针对动作同时驱动未观测隐状态与双线性即时奖励的内生非平稳老虎机问题，提出基于指数稳定衰减的块循环近似方法与块级乐观探索算法 Block-OFUL，在开环动作序列基准下首次将遗憾上界从 $\widetilde{\mathcal{O}}(T^{2/3})$ 降低至 $\widetilde{\mathcal{O}}(\sqrt{T})$。

研究背景与动机¶

在推荐系统、在线定向广告以及个性化健康干预等诸多序贯决策场景中，环境往往表现出显著的内生非平稳性（endogenous nonstationarity）：智能体采取的动作不仅产生即时收益，还会不可逆地改变环境的潜在状态或用户偏好，从而持续影响未来收益的演化。传统的非平稳老虎机研究多聚焦于外生漂移（例如变异预算、突变点或参数漂移），或是针对独立单臂的衰退（rotting）、充能（recharging）与阻塞（blocking）机制；这些设定无法捕捉多维动作空间中，单次动作通过潜在隐状态对相关后续动作产生的系统性交叉影响。

为建模这种复杂的交叉动作内生效应，近期学术界提出了隐线性动力学老虎机模型（latent linear-dynamics bandits），其中动作驱动一个未观测的线性动力系统，奖励则由当前动作与隐状态的双线性内积给出。该结构导致了长时程规划与部分可观测学习的深度耦合：学习者只能从带有时间相关性的标量奖励反推隐式输入-输出动力学，而动作的历史影响在时间轴上无限延伸。先前的探索-承诺（Explore-Then-Commit, ETC）方法采取两阶段割裂策略，先通过均匀随机探索估计马尔可夫参数，再永久锁定至一个近似开环最优序列，其探索-利用权衡较差，仅能取得 $\widetilde{\mathcal{O}}(T^{2/3})$ 的次优伪遗憾上界。

这种次优性的根本症结在于：探索阶段收集的数据未能用于最大化累积奖励，而承诺阶段的大量样本又完全被废弃、无法用于修正对动力学模型的估计。本文的核心 idea 是：利用隐状态动力系统的指数稳定性将无限记忆截断为有限记忆块，通过块级循环近似将长程非平稳开环规划转化为平稳块级线性老虎机问题，并设计在块间交替更新置信集与执行块级乐观决策的 Block-OFUL 算法，首次实现 $\widetilde{\mathcal{O}}(\sqrt{T})$ 级实际期望遗憾。

方法详解¶

整体框架¶

算法将整个决策时域 $T$ 划分为 $N = T/(m+L)$ 个长度为 $m+L$ 的执行块（block）。每个块分为前 $m$ 步的“预热阶段”（warm-up segment）与后 $L$ 步的“信息采集阶段”（informative suffix）。预热阶段的作用是建立块内动作记忆，使得在后 $L$ 步中，任意截断长度为 $m$ 的历史动作均完整落在当前块内部，从而解耦相邻块之间的非平稳动力学耦合。在每个块开始前，算法基于历史信息步累积的数据更新对截断马尔可夫参数的岭回归估计与椭球置信集，并在复合动作空间（整块动作序列）上求解 UCB 乐观最大化问题，选出最优块后直接开环顺序执行整块动作。

%%{init: {'flowchart': {'rankSpacing': 24, 'nodeSpacing': 28, 'padding': 6, 'wrappingWidth': 400}}}%%
flowchart TD
    A["环境输入：时域 T, 截断记忆 m, 信息步长 L, 正则化参数 λ"] --> B["块级循环近似<br/>将无限记忆奖励截断至有限阶 m 步并建立块级代理奖励"]
    B --> C["块级 UCB 乐观选择<br/>基于当前 Gram 矩阵在复合块动作空间求解上置信界最大化"]
    C --> D["顺序执行块序列<br/>前 m 步充当预热历史，后 L 步采集带噪声线性观测"]
    D --> E["非鞅残差解耦与置信集更新<br/>分离过程噪声尾部偏差与块内鞅噪声并更新岭回归估计"]
    E -->|进入下一决策块 τ+1| C

关键设计¶

1. 块级循环近似：将无限记忆非平稳规划降阶为块级平稳代理奖励

在隐线性动力学中，系统状态遵循 $\mathbf{x}_{t+1} = \mathbf{A}\mathbf{x}_t + \mathbf{B}\mathbf{u}_t + \mathbf{w}_t$，奖励为 $r_t = \mathbf{u}_t^\top \mathbf{C}\mathbf{x}_t + z_t$。展开后可知确定性开环动作序列在时刻 $t$ 的期望奖励由无限阶马尔可夫参数表示：$\mu_t(\mathbf{u}_{1:t}) = \sum_{s=1}^\infty \mathbf{u}_t^\top \mathbf{G}_{s-1} \mathbf{u}_{t-s}$，其中 $\mathbf{G}_h = \mathbf{C}\mathbf{A}^h\mathbf{B}$。由于矩阵 $\mathbf{A}$ 满足指数谱稳定性 $\|\mathbf{A}^h\|_2 \le M_\rho \rho^h$（$\rho \in (0,1)$），远距离历史动作的影响呈几何级数快速衰减。算法设定截断窗口 $m \ge 1$，截断截断误差满足： $$ \Delta_m = \sum_{h=m}^\infty |\mathbf{G}_h|_2 \le \frac{|\mathbf{C}|_2|\mathbf{B}|2 M\rho}{1-\rho} \rho^m $$ 在此基础上，定义长度为 $m+L$ 的块 $\mathbf{U} = (\mathbf{v}_1, \dots, \mathbf{v}_{m+L})$ 上的代理奖励（proxy reward）为后 $L$ 步截断收益之和：$\bar{r}_m(\mathbf{U}) := \sum_{j=m+1}^{m+L} \sum_{s=1}^m \mathbf{v}_j^\top \mathbf{G}_{s-1} \mathbf{v}_{j-s}$。由于 $j \ge m+1$，这 $L$ 个位置所需的 $m$ 步历史完全落在同一块内。将参数与动作对向量化：$\boldsymbol{\theta}_m^* := [\text{vec}(\mathbf{G}_0)^\top, \dots, \text{vec}(\mathbf{G}_{m-1})^\top]^\top \in \mathbb{R}^{p^2 m}$，提升特征 $\boldsymbol{\phi}_j(\mathbf{U}) := [(\mathbf{v}_{j-1} \otimes \mathbf{v}_j)^\top, \dots, (\mathbf{v}_{j-m} \otimes \mathbf{v}_j)^\top]^\top \in \mathbb{R}^{p^2 m}$，代理奖励严谨转化为关于未知参数 $\boldsymbol{\theta}_m^*$ 的线性函数 $\bar{r}_m(\mathbf{U}) = \sum_{j=m+1}^{m+L} \langle \boldsymbol{\phi}_j(\mathbf{U}), \boldsymbol{\theta}_m^* \rangle$。论文证明若对单块最优解 $\mathbf{U}^* \in \text{argmax} \bar{r}_m(\mathbf{U})$ 进行全时程周期重复（cyclic sequence $\mathbf{U}^*_{\text{cyc}}$），其对全局开环最优基准 $\text{OPT}_T$ 的逼近差距仅为 $2T\Delta_m + \frac{2Tm}{m+L}R_m$，从而确立了在块级层面利用线性老虎机机制的理论基石。

2. 块级 UCB 乐观选择：块间交替学习与消除纯探索阶段

不同于 ETC 割裂的“前阶段探索、后阶段利用”，Block-OFUL 算法维持一个动态更新的椭球置信集，并在块粒度上实施乐观选择。在第 $\tau$ 块开始时，历史累积的信息步设计矩阵定义为 $\mathbf{V}_{\tau-1} = \lambda \mathbf{I}_d + \sum_{s=1}^{\tau-1} \boldsymbol{\Phi}_s \boldsymbol{\Phi}_s^\top$（其中 $d = p^2 m$，$\boldsymbol{\Phi}_s$ 为第 $s$ 块后 $L$ 步特征堆叠形成的 $d \times L$ 矩阵）。算法通过求解如下 UCB 优化问题直接选择下一块动作序列 $\mathbf{U}_\tau \in \mathcal{U}^{m+L}$： $$ \mathbf{U}\tau \in \mathop{\mathrm{argmax}}} \in \mathcal{U}^{m+L}} \sum_{j=m+1}^{m+L} \left( \langle \boldsymbol{\phij(\mathbf{U}), \hat{\boldsymbol{\theta}}} \rangle + \gamma_{\tau-1} |\boldsymbol{\phij(\mathbf{U})| \right) $$ 选定 }_{\tau-1}^{-1}$\mathbf{U}_\tau$ 后，智能体在环境中依次执行这 $m+L$ 个动作，前 $m$ 步仅作为状态热身，后 $L$ 步观测到的标量奖励 $r_{\tau, j}$ 则用于将最小二乘估计修正为 $\hat{\boldsymbol{\theta}}_\tau = \mathbf{V}_\tau^{-1} \sum_{s=1}^\tau \sum_{j=m+1}^{m+L} \boldsymbol{\phi}_{s,j} r_{s,j}$。这使得每一个块既在贪婪地利用当前最佳知识获取高额收益，又通过不确定性奖励（exploration bonus）主动探索参数空间，彻底消除了纯探索造成的 $T^{2/3}$ 阶遗憾损失。

3. 非鞅残差解耦与置信集构建：克服自适应决策与历史噪声相关性

在理论分析中最棘手的核心障碍在于：观测奖励 $r_{\tau,j}$ 中包含的非平稳残差无法直接视作标准鞅差噪声。展开后第 $\tau$ 块第 $j$ 步的真实奖励为： $$ r_{\tau,j} = \langle \boldsymbol{\phi}j(\mathbf{U}\tau), \boldsymbol{\theta}m^* \rangle + \epsilon $$ 其中 } + \eta_{\tau,j} + \zeta_{\tau,j$\epsilon_{\tau,j}$ 为当前块内部产生的亚高斯噪声，构成块级向量鞅差；$\eta_{\tau,j}$ 为截断 $m$ 步以外的动作历史残差，满足几何衰减 $|\eta_{\tau,j}| \le \Delta_m$；而 $\zeta_{\tau,j} = \sum_{h=j-1}^\infty \mathbf{u}_{\tau,j}^\top \mathbf{C} \mathbf{A}^h \mathbf{w}_{t_{\tau,j}-1-h}$ 则是进入当前块前历史过程噪声的残留。由于当前块动作 $\mathbf{U}_\tau$ 是根据过往奖励自适应选出的，其与块前的过程噪声必然存在相关性，破坏了条件零均值鞅性质。为此，关键设计将 $\zeta_{\tau,j}$ 拆解为动作向量与外生随机向量 $\mathbf{y}_{\tau,j} = \mathbf{C} \sum_{h=j-1}^\infty \mathbf{A}^h \mathbf{w}_{t_{\tau,j}-1-h} \in \mathbb{R}^p$ 的内积。通过对单位球面 $\mathbb{S}^{p-1}$ 建立 $1/2$-网格，结合一致集中不等式证明了无论选择何种动作，以至少 $1-\delta$ 的概率一致成立 $\|\mathbf{y}_{\tau,j}\|_2 \le \bar{\Delta}_m(\delta) = \mathcal{O}(T^{-1/2})$。该均匀边界使得算法能够将偏差项纳入置信半径 $\gamma_\tau = \alpha_\tau + \beta_\tau$，确保了置信集的有效覆盖。

4. 块更新失配解耦：避免置信半径被块长度乘性放大

传统的块级置信界分析在处理延迟或批量更新时，通常直接用预热块开始前的 Gram 矩阵放缩整个块内的不确定性，这会导致块长度 $L$ 以乘法因子直接乘在主导估计误差项上，从而恶化遗憾阶数。本文通过精细的矩阵伸缩技术（telescoping argument）将不确定性差值解耦为： $$ |\boldsymbol{\phi}j(\mathbf{U}\tau)|{\mathbf{V}}^{-1}} = |\boldsymbol{\phij(\mathbf{U}\tau)|{\mathbf{V}}^{-1}} + \left( |\boldsymbol{\phij(\mathbf{U}\tau)|{\mathbf{V}}^{-1}} - |\boldsymbol{\phij(\mathbf{U}\tau)|{\mathbf{V} \right) $$ 第一项利用标准椭球势能引理积分出标准的 }^{-1}$\sqrt{2Td \log(\dots)}$，第二项则通过特征值逆平方根差分求和 $\sum_{k=1}^d (\lambda_{0,k}^{-1/2} - \lambda_{N,k}^{-1/2})$ 严格控制在加性常数项 $\frac{2LL_\phi d}{\sqrt{\lambda}}$。这种处理使得块长度 $L$ 仅作为加性项出现，进而通过联立平衡截断误差 $T \rho^m$、块边界损失 $Tm/(m+L)$ 与统计估计项，解出最优超参 $m = \frac{\log T}{2\log(1/\rho)}$ 及 $L \asymp \frac{\sqrt{mT}}{d^{3/4}} - m$，最终严格证明出 $\widetilde{\mathcal{O}}(\sqrt{T})$ 的伪遗憾与实际期望遗憾界。

损失函数 / 训练策略¶

在算法实现与理论界中，超参数配置设定为： - 截断记忆窗口：$m = -\frac{1}{2}\log_\rho T = \frac{\log T}{2\log(1/\rho)}$； - 信息步长：$L = \frac{\sqrt{mT}}{d^{3/4}} - m$，其中 $d = p^2 m$； - 岭回归正则化系数：$\lambda = L_\phi^2 \le m$； - 置信半径 $\gamma_\tau = \alpha_\tau + \beta_\tau$： $$ \alpha_\tau = \sigma_{\mathcal{B}} \sqrt{d\log\left(1 + \frac{\tau L L_\phi^2}{d\lambda}\right) + 2\log\frac{1}{\delta}} + \sqrt{\lambda}S_m, \quad \beta_\tau = \bar{\Delta}m(\delta)\sqrt{2\tau L d\log\left(1 + \frac{\tau L L\phi^2}{d\lambda}\right)} $$ 在实际离线块动作选择优化时，由于超立方顶点集合 $\mathcal{U} = \{-1, +1\}^p$ 上的组合空间大小为 $2^{p(m+L)}$，算法采用多起点随机坐标翻转贪婪局部搜索（multi-start local search with coordinate sign flips），从多个均匀采样的初始候选块出发，贪心迭代翻转坐标直到目标函数不再提升，最终选取 UCB 目标值最高的局部极值块。

实验关键数据¶

主实验¶

论文在具有不同隐动力学谱半径的合成环境上进行了对比验证，状态维度 $n=4$，动作维度 $p=3$，动作集 $\mathcal{U} = \{-1,+1\}^p$。对比基线包括先前代表性算法 Explore-Then-Commit（ETC，探索长度 $H=120$）与均匀随机动作策略。噪声均为方差代理为 $0.01$ 的高斯噪声。时域 $T=1000$ 步下不同算法的平均累积奖励表现如下：

动力学稳定性	谱半径 $\rho(\mathbf{A})$	算法配置 $(m, L)$	Block-OFUL (本文)	ETC 基线 [Choi et al., 2026]	随机探索基线	相对 ETC 提升
高度持久/慢衰减	$\rho=0.95$	$(m=8, L=36)$	~1280	~720	~0	+77.8%
快速衰减/短记忆	$\rho=0.30$	$(m=2, L=24)$	~1450	~1120	~0	+29.5%

消融实验¶

论文在附录 D.2 设计了结构化延迟隐状态动力系统（Structured Delayed Latent Dynamics），隐状态由 $D$ 个 $p$ 维块构成（$n=pD, p=2$），动作注入第 1 块后以衰减率 $\rho$ 逐级传递，直至延迟 $D$ 步后到达第 $D$ 块才对奖励产生贡献。该实验深入分析了系统在不同延迟阶数 $D$ 与记忆持久度 $\rho$ 下在 $T=1000$ 步结束时的累积收益表现：

实验配置 $(D, \rho)$	延迟步数 $D$	稳定性 $\rho$	Block-OFUL (本文)	ETC 基线	相对增益机制分析
短延迟 + 快衰减	$D=3$	$\rho=0.30$	~850	~710	动作影响迅速消退，两算法差距适中 (+19.7%)
短延迟 + 慢衰减	$D=3$	$\rho=0.95$	~980	~650	持续的自适应更新明显优于固定承诺 (+50.8%)
长延迟 + 快衰减	$D=6$	$\rho=0.30$	~620	~480	高延迟下初始探索估计精度不足，自适应学习保持优势 (+29.2%)
长延迟 + 慢衰减	$D=6$	$\rho=0.95$	~820	~360	强记忆与长延迟叠加，ETC 崩溃，本文优势达到峰值 (+127.8%)

关键发现¶

慢衰减高持久场景优势更显著：当动力系统谱半径由 $\rho=0.30$ 增至 $\rho=0.95$ 时，过往动作对未来的影响持续长久，ETC 依赖初期有限探索得到的粗糙参数在后续全时程发生严重性能锁定，而 Block-OFUL 凭借块间不间断的自适应反馈与乐观决策，累积收益优势扩大至 77.8% 以上。
延迟抗性表现卓越：在长延迟结构化测试中，当有效动作影响被推迟 $D=6$ 步才显现时，ETC 的开环动作设计由于前期探索信息利用率低而发生退化，Block-OFUL 则始终能追踪并收敛到最优周期循环模式。
多起点局部搜索的经验有效性：尽管块级动作空间维度达到 $p(m+L)$，离散坐标翻转局部搜索配合多点随机重启在实验中足以稳定避开较差局部极小，有效支持了 UCB 机制的实施。

亮点与洞察¶

将无限记忆降阶为有限块循环：巧妙结合动力系统的李雅普诺夫指数稳定性与有限记忆块构造，从理论上证明了全局非平稳开环最优基准可由有限长度单块的周期重复序列高精度逼近，打通了控制论动力学与非平稳老虎机之间的理论壁垒。
非鞅残差的球面网格一致界处理：针对自适应决策与历史噪声耦合导致的鞅性失效问题，没有盲目放大假设，而是利用几何网格技术在整个参数空间建立关于过程噪声尾部向量的均匀浓度不等式，技巧严密自洽。
加性块更新失配分解法：通过代数伸缩巧妙拆解预热块与块内更新 Gram 矩阵之间的失配，规避了以往文献中块长度对 $\sqrt{T}$ 主导项的乘性惩罚，展现出高水平的矩阵分析功力。

局限与展望¶

依赖离线 UCB 优化 Oracle：算法在每块开始前需要求解一个在 $\mathcal{U}^{m+L}$ 上的离散/非凸全局 UCB 最大化问题，虽然多起点坐标翻转局部搜索经验表现良好，但目前缺乏多项式时间计算复杂度的可计算理论保证。
依赖已知动力学稳定性参数：超参数 $m$ 与 $L$ 的最优设置显式依赖于系统的谱半径上界 $\rho$ 及相关系统范数，如何设计能够全自适应未知衰减速率的无参（parameter-free）算法仍有待探索。
基准局限于开环序列：理论比较的基准为最优开环动作序列（open-loop action sequence），尚未覆盖闭环全状态反馈策略（closed-loop state-feedback policy）。

评分¶

新颖性: ⭐⭐⭐⭐⭐ 首次建立隐线性动力学双线性奖励老虎机中的块级乐观理论，打破 $T^{2/3}$ 理论壁垒。
实验充分度: ⭐⭐⭐⭐☆ 合成环境与结构化延迟环境验证扎实，若能补充真实系统仿真或大规模连续优化实验则更佳。
写作质量: ⭐⭐⭐⭐⭐ 数学推导严丝合缝，技术细节展开清晰，理论动机与背景衔接流畅。
价值: ⭐⭐⭐⭐⭐ 为解决推荐系统与个性化干预中带有内生延迟演化的序贯决策问题提供了奠基性的理论工具。

动力学稳定性	谱半径 \(\rho(\mathbf{A})\)	算法配置 \((m, L)\)	Block-OFUL (本文)	ETC 基线 [Choi et al., 2026]	随机探索基线	相对 ETC 提升
高度持久/慢衰减	\(\rho=0.95\)	\((m=8, L=36)\)	~1280	~720	~0	+77.8%
快速衰减/短记忆	\(\rho=0.30\)	\((m=2, L=24)\)	~1450	~1120	~0	+29.5%

实验配置 \((D, \rho)\)	延迟步数 \(D\)	稳定性 \(\rho\)	Block-OFUL (本文)	ETC 基线	相对增益机制分析
短延迟 + 快衰减	\(D=3\)	\(\rho=0.30\)	~850	~710	动作影响迅速消退，两算法差距适中 (+19.7%)
短延迟 + 慢衰减	\(D=3\)	\(\rho=0.95\)	~980	~650	持续的自适应更新明显优于固定承诺 (+50.8%)
长延迟 + 快衰减	\(D=6\)	\(\rho=0.30\)	~620	~480	高延迟下初始探索估计精度不足，自适应学习保持优势 (+29.2%)
长延迟 + 慢衰减	\(D=6\)	\(\rho=0.95\)	~820	~360	强记忆与长延迟叠加，ETC 崩溃，本文优势达到峰值 (+127.8%)