通过误指定缩减实现非平稳线性赌博机的动态遗憾

# 1 引言

许多在线决策问题既涉及回合特定的可行动作，也涉及漂移的奖励模型：符合条件的广告展示、可行价格和可用治疗会随时间变化，而用户偏好、需求曲线和患者反应也可能演变。受这些应用启发，我们研究具有回合特定可行决策集的非平稳线性赌博机。现有方法在获得最优的 \( \widetilde{O}(T^{2/3}P_T^{1/3}) \) 依赖关系（其中 \( P_T \) 是奖励参数序列的路径长度）时，对回合特定决策集施加了正交结构假设，这在上下文应用中可能有限制。我们通过统一的误设定缩减视角来弥补这一差距：将时间轴划分为块后，我们将每个块的动态遗憾与针对固定参数线性赌博机基准的遗憾联系起来，其中块内参数漂移作为有界误设定出现。重启具有误设定依赖的遗憾保证的算法，即可获得线性赌博机（具有一般紧致决策集）和 \( K \) 臂上下文线性赌博机的最优 \( T^{2/3}P_T^{1/3} \) 动态遗憾依赖关系。

**关键词**：非平稳在线学习，线性赌博机，动态遗憾

许多在线决策问题，如在线广告展示和上下文治疗分配，涉及选择由特征向量表示的动作，这些特征向量可以同时包含当前上下文和动作特定信息。在这些应用中，可行动作自然是回合特定的：它们取决于当前用户或患者，并且在广告展示中取决于当前可用的广告展示。线性赌博机（Abbasi-Yadkori 等，2011；Chu 等，2011）为这类问题提供了标准模型：每个可行决策由一个特征向量表示，其期望奖励被建模为该特征向量与未知参数向量的内积。策略的标准性能度量是遗憾，它将策略的累积奖励与基准的累积奖励进行比较。在经典的平稳模型中，未知参数是固定的，该基准在每个回合选择固定参数下的最佳可行决策。

然而，在许多应用中，动作与期望奖励之间的关系可能随时间漂移：用户偏好可能演变，市场条件可能变化，患者对治疗的反应也可能改变。这一关注点催生了关于非平稳随机优化和非平稳赌博机学习的广泛文献（Besbes 和 Zeevi，2011；Besbes 等，2015；Keskin 和 Zeevi，2017；Chen 等，2019；Cheung 等，2022；Wang，2025）。非平稳线性赌博机模型通过允许奖励参数跨回合变化来捕捉这种漂移。形式上，考虑一个在 \( T \) 个回合上的在线决策问题：在每个回合 \( t \)，学习器观察到一个可行决策集 \( \mathcal{A}_t \subseteq \mathbb{R}^d \)，选择一个动作 \( a_t \in \mathcal{A}_t \)，并接收条件均值为 \( \langle a_t, \theta_t \rangle \) 的奖励，其中 \( \theta_t \) 是当前奖励参数。遵循 Cheung 等（2022），问题实例的非平稳性由奖励参数序列的路径长度衡量：\( P_T := \sum_{t=1}^{T-1} \| \theta_{t+1} - \theta_t \|_2 \)。对于策略 \( \pi \)，用 \( a_t \) 表示其第 \( t \) 回合的动作，定义动态遗憾

\[
\operatorname{Reg}_T(\pi) := \mathbb{E} \sum_{t=1}^T \left[ \max_{a \in \mathcal{A}_t} \langle a, \theta_t \rangle - \langle a_t, \theta_t \rangle \right],
\]

它将学习器在每个回合的期望奖励与当前参数下最佳可行动作的期望奖励进行比较。目标是在 \( P_T \) 适中时实现小的动态遗憾。

几项工作研究了路径长度约束下的非平稳线性赌博机（Russac 等，2019；Cheung 等，2022；Zhao 等，2021；Wang 等，2025）。然而，现有的非平稳线性赌博机最优方法并未完全覆盖回合特定可行决策集的情况。Cheung 等（2022）在该情形下获得了 \( \widetilde{O}(T^{2/3}P_T^{1/3}) \) 的上界，前提是所有可行动作都位于一组固定的正交方向上，并建立了相应的 \( \Omega(T^{2/3}P_T^{1/3}) \) 下界。正交方向假设在上下文应用中可能有限制，因为用户、广告机会和患者-治疗配对通常由上下文相关的属性描述，导致特征向量具有共享结构而非固定正交基方向的标量倍数。这一限制留下了在具有一般回合特定可行决策集的非平稳线性赌博机中实现最优 \( T^{2/3}P_T^{1/3} \) 动态遗憾依赖关系的开放问题（Zhao 等，2021；Wang 等，2025）。

**我们的贡献。** 我们表明，在无需正交方向假设的情况下，对于回合特定决策集，可以实现最优的 \( T^{2/3}P_T^{1/3} \) 动态遗憾依赖关系。我们在两种设置中证明了这一点：一般紧致决策集和 \( K \) 臂上下文线性赌博机。

关键思想是局部误设定缩减：每个块内的参数漂移被视为模型误设定，因此所需的动态遗憾率遵循块级遗憾保证，这些保证*自适应*于误设定水平。该缩减基于以下块级界。在一个块 \( \mathcal{I} = \{\tau, \ldots, \tau+n-1\} \) 上，使用 \( \theta_\tau \) 作为块比较器给出

\[
\sup_{t \in \mathcal{I}} \sup_{a \in \mathcal{A}_t} |\langle a, \theta_t - \theta_\tau \rangle| \leq L P_{\mathcal{I}},
\]

其中 \( L \) 上界了可行动作的范数，\( P_{\mathcal{I}} \) 表示限制在块 \( \mathcal{I} \) 上的参数序列的路径长度。一般来说，如果块比较器 \( \bar{\theta} \) 在 \( \mathcal{I} \) 上的均匀误差最多为 \( \varepsilon \)，则块上的动态遗憾由两项界定：由 \( \bar{\theta} \) 诱导的块级固定参数基准的遗憾，以及一个近似项 \( O(n\varepsilon) \)。第一项正是块上具有误设定水平 \( \varepsilon \) 的误设定线性赌博机的遗憾。因此，一个 \( \widetilde{O}(\sqrt{n} + n\varepsilon) \) 量级的保证在取 \( \varepsilon = L P_{\mathcal{I}} \) 后得到块动态遗憾界 \( \widetilde{O}(\sqrt{n} + n L P_{\mathcal{I}}) \)。在长度为 \( \Delta \) 的块上重启并对所有块求和，得到权衡 \( \widetilde{O}(T/\sqrt{\Delta} + \Delta P_T) \)。选择最优的 \( \Delta \) 即可得到 \( \widetilde{O}(T^{2/3}P_T^{1/3}) \) 依赖关系。

我们在两种设置中获得以下保证：

- **一般紧致决策集。** 对于具有一般紧致自适应非预期决策集和遗忘参数路径的线性赌博机，定理 3.4 表明，重启 SquareCB.Lin+ 基础算法（Foster 等，2020）的 CORRAL 聚合方法达到了期望的动态遗憾界 \( \widetilde{O}\!\left(d\sqrt{T} + L^{1/3}d^{5/6}T^{2/3}P_T^{1/3}\right) \)。因此，该方法达到了最优的 \( T^{2/3}P_T^{1/3} \) 动态遗憾依赖关系，匹配了 Cheung 等（2022）的下界依赖关系，同时允许超出正交方向结构的一般回合特定紧致动作集。
- **\( K \) 臂上下文线性赌博机。** 对于遗忘对手下的 \( K \) 臂上下文线性赌博机，令 \( \Lambda_K := 1 + \log K \)，定理 4.3 表明，重启 SupLinUCB（Chu 等，2011）达到了期望的动态遗憾界 \( \widetilde{O}\!\left(\sqrt{dT}\,\Lambda_K + \sqrt{d}\,\Lambda_K^{5/6}T^{2/3}P_T^{1/3}\right) \)。这同样匹配了关于 \( T \) 和 \( P_T \) 的最优依赖关系，如命题 4.5 所证实。

与 Foster 等（2020）最初的 SquareCB.Lin+ 误设定保证（考虑遗忘序列）不同，我们的设置允许自适应非预期决策集。这需要一个额外的条件论证。在每个块上，比较器和误设定半径在块内随机化之前是固定的。因此，误设定相关项保持可预测，并且可以条件性地调用 SquareCB.Lin+ 基础算法和 CORRAL 主算法的保证。如果 \( P_T \) 未知，可以使用 Bandit-over-Bandit 层来消除这种调参，代价是通常的无参数成本（Cheung 等，2022；Zhao 等，2021）。

**相关工作与定位。** 重启、滑动窗口和加权估计方法是非平稳赌博机的常用工具（Besbes 等，2015；Russac 等，2019；Cheung 等，2022；Zhao 等，2021；Wang 等，2025）。对于非平稳线性赌博机，最近的工作发现，当可行集是回合特定时，简单的遗忘分析与 \( T^{2/3}P_T^{1/3} \) 下界之间存在差距（Zhao 等，2021）。我们的工作填补了这一差距：通过将块内参数漂移归约为有界线性误设定，可以直接处理回合特定可行集。证明建立在非平稳线性赌博机与误设定线性赌博机之间的这种联系之上，利用误设定自适应的线性赌博机保证（Foster 等，2020；Takemura 等，2021）来移除回合特定动作集上的正交结构假设。

**组织结构。** 本文的其余部分组织如下。第 2 节介绍模型和块符号。第 3 节证明具有自适应非预期决策集的一般线性赌博机的动态遗憾保证。第 4 节开发重启 SupLinUCB 及其对 \( K \) 臂上下文线性赌博机的动态遗憾保证。第 5 节总结本文。

## 2 问题设置

我们考虑一个在 \( T \) 个回合上的非平稳上下文线性赌博机。在每个回合 \( t \)，学习器观察到一个非空可行决策集 \( \mathcal{A}_t \subseteq \mathbb{R}^d \)。我们将每个可行动作与其特征向量等同起来。学习器选择一个动作 \( a_t \in \mathcal{A}_t \) 并观察一个标量奖励 \( r_t = r_t(a_t) \)。存在一个未知参数序列 \( \theta_1, \ldots, \theta_T \in \mathbb{R}^d \)，且条件均值奖励是线性的：对于 \( a \in \mathcal{A}_t \)，有 \( \mu_t(a) = \langle a, \theta_t \rangle \)。当对参数施加范数界 \( S \) 时，我们记 \( \Theta := \{\theta \in \mathbb{R}^d : \|\theta\|_2 \leq S\} \)；在下面的 \( K \) 臂设置中，我们使用相同的符号，取 \( S = 1 \)。

*历史。* 令 \( \mathcal{H}_{t-1} \) 表示截至第 \( t-1 \) 回合结束的交互历史。当允许自适应决策集时，我们还将 \( \mathcal{G}_t \) 记为第 \( t \) 回合的 \( \sigma \)-域，该域在当前决策集和学习者的动作分布确定之后、动作采样和奖励噪声实现之前。

**假设 1（次高斯奖励噪声）** 对于被选择的动作 \( a_t \)，记 \( \xi_t := r_t(a_t) - \mu_t(a_t) \)。在给定奖励前信息（包括 \( a_t \)）的条件下，噪声是均值为零且 \( R \)-次高斯的，其中 \( R \) 是通用常数。

**假设 2（路径长度）** 参数序列的路径长度为 \( P_T := \sum_{t=1}^{T-1} \|\theta_{t+1} - \theta_t\|_2 \)。

*动态遗憾。* 对于策略 \( \pi \)，令 \( a_t \) 为 \( \pi \) 在第 \( t \) 回合选择的动作，令 \( a_t^\star \) 为第 \( t \) 回合的最优动作，即 \( a_t^\star \in \arg\max_{a \in \mathcal{A}_t} \mu_t(a) = \arg\max_{a \in \mathcal{A}_t} \langle a, \theta_t \rangle \)。策略 \( \pi \) 的期望动态遗憾为

\[
\operatorname{Reg}_T(\pi) := \mathbb{E}\left[ \sum_{t=1}^T \left( \langle a_t^\star, \theta_t \rangle - \langle a_t, \theta_t \rangle \right) \right].
\]

当策略或算法从上下文中明确时，我们简记 \( \operatorname{Reg}_T \) 为 \( \operatorname{Reg}_T(\pi) \)。

*\( K \) 臂上下文特例。* Chu 等（2011）考虑的 \( K \) 臂上下文线性赌博机设置是特例 \( \mathcal{A}_t = \{x_t(i) : i \in [K]\} \)。学习器选择 \( i_t \in [K] \)，等价于 \( a_t = x_t(i_t) \)，且 \( \mu_t(i) := \mu_t(x_t(i)) \)。

*块符号。* 对于一个区间 \( \mathcal{I} = \{\tau, \ldots, \tau+n-1\} \)，记 \( \mathbb{E}_\tau[\cdot] := \mathbb{E}[\cdot \mid \mathcal{H}_{\tau-1}] \)。