📊 statistics

Weighted Sequential Bayesian Inference for Non-Stationary Linear Contextual Bandits

本文为非平稳线性上下文老虎机引入了加权序列贝叶斯（WSB）推断框架，该框架通过用动态后验取代点估计来减少过度保守，并通过新的基于 WSB 的算法和简化的鞅集中性证明，实现了最先进的遗憾保证。

原作者： Nicklas Werge, Yi-Shan Wu, Abdullah Akgül, Melih Kandemir

发布于 2026-08-12

📖 1 分钟阅读☕ 轻松阅读

原作者： Nicklas Werge, Yi-Shan Wu, Abdullah Akgül, Melih Kandemir

原始论文采用 CC BY 4.0 许可（http://creativecommons.org/licenses/by/4.0/）。 ✨ 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。阅读完整免责声明

想象一下，你是一位飞船舰长，正在一个物理规则每隔几小时就会改变的星系中航行。有时重力向上拉，有时向下，有时甚至完全消失。为了生存，你需要一台能够从过去的跳跃中学习、但又不会陷入旧习惯的导航计算机。这就是**上下文多臂老虎机（Contextual Bandits）**的世界，它是人工智能的一个分支，旨在帮助计算机在“最佳”选择不断变化的场景下做出明智的决策。这就像一个机器人试图猜测顾客想要哪种口味的冰淇淋。如果顾客的口味每天都在变，机器人就不能只记住上周他们喜欢什么；它必须看重近期的历史，并淡忘遥远的过去。

为了实现这一点，机器人通常依赖两种主要策略。第一种是**频率派（Frequentist）方法，它像一个严谨的会计师。它通过计算数字来为当前情况找到唯一的“最佳猜测”。第二种是贝叶斯（Bayesian）**方法，它更像是一个充满好奇心的探险家。它不仅仅有一个猜测，而是维护着一整张可能性地图，理解自己可能会出错，并且清楚地知道自己的不确定性程度。问题在于，在一个变化的星系中，严谨的会计师虽然快速却对自己的不确定性视而不见，而探险家虽然聪明却往往计算地图的速度太慢。本文切入了这个间隙，试图赋予探险家会计师般的效率，同时又不失其好奇心。

问题所在：“遗忘型”机器人

在现实世界中，事物很少保持不变。电影推荐系统、新药临床试验或自动驾驶汽车都会面临非平稳性（non-stationarity）——这是一个高级词汇，意指游戏的规则正在发生偏移。如果机器人试图从十年前的数据中学习，它可能会犯错，因为世界已经变了。

为了处理这个问题，科学家们尝试了三种主要技巧：

重启（Restarting）： 每隔一段时间，机器人就会擦除记忆并重新开始。这很安全但很浪费；它仅仅因为时间流逝就丢弃了有价值的教训。
滑动窗口（Sliding Windows）： 机器人只观察最近几天的数据。这更好一些，但就像通过狭窄的隧道观察世界；你可能会错过缓慢但重要的趋势。
加权学习（Weighted Learning）： 机器人记住一切，但给“较旧”的记忆分配较小的权重，就像逐渐消逝的回声。这是最平滑的方法，但要使其与“探险家”式的学习风格完美结合一直很难。

旧方法： “伪装型”探险家

长期以来，处理这些变化世界的流行方法是一种被称为**加权正则化最小二乘法（WRLS）**的技术。它是那个“严谨的会计师”。它为当前情况计算出一个单一的最佳猜测，然后继续前进。它既快速又高效。

但问题在于：WRLS 本质上并不了解自己有多“不确定”。为了让机器人进行探索（尝试新事物以学习更多），研究人员不得不对系统进行“黑客式”修改。他们提取会计师的单一最佳猜测，并人为地为其添加“伪噪声”，以此假装它是一个探险家。这就像拿着一张精确的地图并摇晃它，仅仅是为了看看会发生什么。这效果尚可，但并不是对机器人应如何学习的真实反映。

新方法： “真正的”探险家 (WSB)

本文的作者 Nicklas Werge 及其团队决定不再“伪装”。他们引入了一种名为**加权序列贝叶斯（WSB）**推理的新方法。

他们不再强迫一个单一猜测去扮演探险家，而是构建了一个从底层逻辑上就是探险家的系统。

工作原理： 想象机器人对世界有一种“信念”。每当获得新数据时，它就会更新这种信念。在变化的世界中，旧的信念会逐渐淡化（权重降低），但机器人永远拥有一张完整的“可能性地图”。
神奇之处： 作者发现，这种“真实的”贝叶斯地图在计算速度上与旧的“伪装型”会计师方法一样快。他们成功地在保持会计师速度的同时，保留了探险家天然的不确定性。
动态惩罚（The Dynamic Penalty）： 在这些问题中，最大的障碍之一是处理机器人的初始猜测（其“先验”）。如果机器人从一个错误的猜测开始，纠正错误的过程会很慢。旧方法将这个初始错误视为一个固定的、不可改变的惩罚。新的 WSB 方法将其视为动态惩罚。随着机器人收集更多数据且地图变得更加清晰，针对初始错误的惩罚会自动缩小。这就像是在你学到了足够多的知识并意识到自己错了之后，原谅了最初那个错误的自己。

他们的发现

团队不仅发明了一个新想法，还通过数学证明并进行了模拟测试。

更好的数学： 他们证明了新方法 WSB 提供了与现有最佳方法同等的安全性（数学保证）。事实上，他们显著提高了“随机化”探索（机器人通过随机尝试来学习）的数学水平，降低了与问题复杂度相关的误差率。
三种新算法： 他们基于这一理念构建了三种具体的工具：
- WSB-LinUCB： 一个确定性探险家，根据其置信度选择最佳选项。
- WSB-RandLinUCB： 一个随机化探险家，在选择中加入了一点运气。
- WSB-LinTS： 一个“汤普森采样（Thompson Sampling）”探险家，从其信念图中随机抽取一个情景并据此行动。
结果： 当他们在 4,000 轮决策（类似于一场长局游戏）的模拟运行中，新方法始终优于旧方法。
- 在世界发生突变（突然跳跃）的情景下，新的随机化方法显著降低了“遗憾值”（Regret，即错误得分）。例如，在一次 32 维（复杂问题）的测试中，旧方法产生了约 503 次错误，而新的 WSB-RandLinUCB 仅产生了 474 次错误。
- 在世界发生缓慢漂移的情景下，改进更为显著。旧方法产生了 435 次错误，而新方法仅有 405 次。
- 最重要的是，新方法没那么保守。因为它不依赖于针对初始猜测的固定“最坏情况”惩罚，所以它在早期阶段更愿意进行聪明的冒险，从而学得更快。

“消融实验”检查

作者还测试了如果机器人从一个非常糟糕的猜测（“误设先验”）开始会发生什么。他们发现，如果初始猜测只是稍有偏差，系统能处理得很好。但如果猜测极其离谱（比如认为重力是实际的 100 倍），机器人起初会表现挣扎。这证实了虽然新方法具有鲁棒性，但它仍然需要一个合理的起点才能发挥魔力。

为什么这很重要

本文提供的不仅仅是一个微小的改进，它为如何教导机器人在变化的世界中学习提供了一种更简洁、更诚实的方式。通过摒弃“伪噪声”并使用与旧方法同样快速的真正贝叶斯方法，他们证明了你不需要在“快速”和“聪明”之间做选择。机器人可以两者兼得。

作者还为许多研究人员使用的复杂数学工具提供了一个简化的证明，使整个领域变得更容易理解。虽然目前的方法仍需要知道世界可能变化的程度（一个“预算”），但该框架足够灵活，未来的版本可以自动学习这个预算。目前来看，这是迈向 AI 在无需按下“重启键”的情况下适应我们混乱、多变现实的坚实一步。

技术摘要：用于非平稳线性上下文多臂老虎机的加权顺序贝叶斯推断

问题定义

本文探讨了**非平稳线性上下文老虎机（non-stationary linear contextual bandit）**问题。在此设定下，学习者在 $T$ 轮交互中与环境进行交互。在每一轮 $t$ ，学习者观察到一组依赖于上下文的动作集合 $X_t \subseteq \mathbb{R}^d$ ，选择一个动作 $x_t$ ，并接收到一个带有噪声的奖励 $r_t = \langle x_t, \theta^*_t \rangle + \epsilon_t$ 。核心挑战在于奖励参数 $\theta^*_t \in \mathbb{R}^d$ 是未知且随时间变化的。非平稳程度通过总变分预算 $B_T = \sum_{t=1}^{T-1} \|\theta^*_t - \theta^*_{t+1}\|_2$ 来量化。目标是最小化动态遗憾（dynamic regret），即最优动作的奖励与所选动作奖励之间的累积差值。

现有的高效解决方案通常依赖于**加权正则最小二乘（WRLS）**估计器。虽然 WRLS 通过递归更新提供了 $O(d^2)$ 的计算复杂度，但它仅提供点估计。为了进行随机探索（例如 Thompson Sampling 或 Randomized UCB），以往的方法必须通过注入以频繁派协方差矩阵为比例的人造高斯噪声来构建“代理”后验分布。这种方法缺乏原生的贝叶斯理论基础，并且往往依赖于复杂的分析构造，如局部范数（local norms）。

方法论：加权顺序贝叶斯（WSB）推断

作者提出了**加权顺序贝叶斯（WSB）**推断，旨在为非平稳线性老虎机建立一个原则性的贝叶斯框架，同时保留 WRLS 的计算效率。

广义后验构造：
WSB 不仅仅维护一个点估计，而是维护一系列关于时变参数的高斯后验分布 $\rho_t(\theta) = \mathcal{N}(\theta | \mu_t, \Sigma_t)$ 。该方法使用一系列权重 $\{w_{s,t}\}$ （通常为指数衰减 $w_{s,t} = \gamma^{t-s}$ ）来降低过去观测值的权重。后验均值 $\mu_t$ 和逆协方差 $\Sigma_t^{-1}$ 通过以下方式递归更新：
$\Sigma_t^{-1} = \gamma \Sigma_{t-1}^{-1} + \sigma^{-2} x_t x_t^\top + (1-\gamma)\Sigma_0^{-1}$
$\mu_t = \Sigma_t \left( \gamma \Sigma_{t-1}^{-1} \mu_{t-1} + \sigma^{-2} x_t r_t + (1-\gamma)\Sigma_0^{-1} \mu_0 \right)$
在无信息先验下，WSB 均值 $\mu_t$ 在代数上与 WRLS 点估计 $\hat{\theta}_t$ 一致，但 WSB 原生提供了进行不确定性量化所需的完整后验协方差 $\Sigma_t$ 。
收敛分析与动态先验惩罚：
作者推导了 WSB 后验的一个一致性置信界（time-uniform confidence bound）。估计误差 $\|\mu_{t-1} - \theta^*_t\|$ 被分解为三个部分：
- 漂移项 ( $\alpha^{WSB}_t$ )： 捕捉由参数变化引起的偏差。
- 噪声项 ( $\beta^{WSB}_t$ )： 捕捉来自奖励的随机噪声。
- 动态先验项 ( $\Pi_t$ )： 一个代表初始先验影响的新颖项。不同于 WRLS 分析中初始化惩罚被固定为常数上限（ $\sqrt{\lambda}S$ ），WSB 惩罚 $\Pi_t$ 是通过随时间变化的后验协方差 $\Sigma_t$ 进行评估的。随着 $\Sigma_t$ 随时间收缩， $\Pi_t$ 也随之衰减，从而实现了一种数据驱动的、更紧凑的界限。
简化的鞅证明：
为了建立收敛界，论文提供了一个关于向量值鞅（vector-valued martingales）一致收敛性的简化证明。通过利用非负超鞅的 Ville 不等式，作者绕过了传统老虎机文献中使用的复杂停时（stopping-time）构造，为自归一化界限（self-normalized bounds）提供了更简洁的推导。

核心贡献

本文做出了三个主要贡献：

WSB 框架： 引入了一种针对非平稳线性老虎机的参数化贝叶斯推断方法，该方法在提供用于随机探索的原生后验分布的同时，保持了与 WRLS 相同的 $O(d^2)$ 效率。
精细化的遗憾保证： 为三种基于 WSB 的算法建立了频率派遗憾界：WSB-LinUCB、WSB-RandLinUCB 和 WSB-LinTS。通过将精细化的漂移分析（此前仅应用于 UCB）扩展到随机策略，作者实现了 $\tilde{O}(d^{3/4} B_T^{1/4} T^{3/4})$ 的遗憾界。这改进了早期随机基准模型（如 D-RandLinUCB, D-LinTS）中存在的 $d^{7/8}$ 依赖关系。
动态先验惩罚： 证明了贝叶斯公式将先验影响隔离为一个随后验协方差收缩而减小的动态项 $\Pi_t$ 。这减少了与使用固定初始化惩罚的方法相比的过度保守性。

实验结果

作者在涉及突发变化和渐进漂移的合成非平稳场景下对所提算法进行了评估。

确定性 vs. 随机性： 随机探索策略（WSB-RandLinUCB 和 WSB-LinTS）在所有维度和场景下均一致优于确定性的 UCB 类方法。
与基准对比：
- WSB-RandLinUCB 在所有测试维度（ $d=2$ 到 $32$）下均实现了比其频率派对应算法 D-RandLinUCB 更低的累积遗憾。
- WSB-LinTS 显著优于 D-LinTS。
- 在确定性设置下，WSB-LinUCB 的表现与 LB-WeightUCB（最先进的 WRLS UCB）相当，但在高维情况下并未一致超越 D-LinUCB（后者使用了更复杂的局部范数）。
消融研究： 关于先验误设（prior misspecification）的实验表明，虽然算法对中度先验误差具有鲁棒性，但严重的误设（即先验均值远离真实参数规模）会导致性能下降，这凸显了选择与参数界限相容的先验规模的重要性。

意义与主张

本文声称 WSB 为非平稳老虎机中的不确定性量化提供了更具原则性的基础。通过避免使用人工代理分布和局部范数，基于 WSB 的算法实现了：

理论最优性： 其遗憾界与平滑加权策略的最先进水平（ $\tilde{O}(d^{3/4} B_T^{1/4} T^{3/4})$ ）相匹配，改善了之前随机方法的维度依赖性。
实际效率： 保留了 $O(d^2)$ 的计算复杂度，避免了非参数高斯过程（Gaussian Process）方法带来的 $O(t^3)$ 开销。
降低保守性： 动态先验惩罚允许随着数据的积累减少探索的保守性，从而在随机设置中带来更优的实证表现。

作者指出，尽管其界限具有竞争力，但仍略高于 $\Omega(d^{2/3} B_T^{1/3} T^{2/3})$ 的理论下界，这一差距归因于仅使用平滑连续适应而不进行周期性重置来实现极小极大最优性（minimax optimality）的挑战。然而，WSB 框架被呈现为一个高度实用的替代方案，它在理论严谨性与连续适应能力之间取得了平衡。