🤖 machine learning

Learning in Markovian bandits with non-observable states and constrained decision epochs

本文介绍了具有不可观测状态和受限决策时刻的自降级马尔可夫多臂老虎机问题，证明了虽然纯策略在渐近意义上是最优的，且在缺乏先验知识的情况下通常无法实现对数级遗憾，但所提出的 UCB-NOM 算法能够实现近对数级遗憾以及带有偏差界的 $O(\log T)$ 遗憾，且这些结果均与底层状态的数量无关。

原作者： Thomas Hira, Victor Boone, Urtzi Ayesta, Ina Maria Verloop

发布于 2026-06-29

📖 1 分钟阅读☕ 轻松阅读

CC BY 4.0

原作者： Thomas Hira, Victor Boone, Urtzi Ayesta, Ina Maria Verloop

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

想象一下，你是一位试图管理一个拥有多台机器（称为“臂”，arms）的工厂的经理。你想挑选出那台能产生最多利润的机器。然而，这个游戏有两个棘手的规则：

机器是黑箱： 你看不见机器内部的齿轮或当前状态。你只能在它们完成一项工作时看到最终产品（奖励）。你不知道一台机器内部是“磨损了”还是“崭新的”；你只知道它上次给了你什么。
“锁定”规则： 一旦你启动了一台机器，你就不能随心所欲地停掉它并切换到另一台。你必须让那台特定的机器持续运行，直到它产生一个特定的“成功信号”（比如绿灯或完成的一批次）。只有在那时，你才能决定是否切换到另一台机器。

这篇论文探讨了在这些严格的条件下，如何学习哪台机器才是最好的。

核心问题：为什么“切换”很难

在标准的“猜谜游戏”（比如挑选最好的老虎机）中，你可以尝试一台机器，得到一个结果，然后立即尝试另一台。但在这种情况下，由于“锁定”规则，切换的成本很高且速度很慢。

作者引入了一个概念，叫做**“自我退化”（Self-Degrading）**机器。把这些想象成那些如果你不使用它们，它们就会变得稍微变差的机器。如果你让一台机器闲置，它就会生锈或失去锋芒。如果你使用它，它就能保持锋利。

重大洞察： 在这种特定的“自我退化”世界里，最好的策略其实非常简单：选定一台机器，然后永远坚持使用它。 你不需要成为一个在频繁切换中寻找最优解的天才。论文证明了对于这类特定机器，这种“纯粹”的策略（永不切换）实际上是长期获胜的最优方式。

挑战：你看不见状态

尽管坚持使用一台机器是最好的策略，但你仍然需要弄清楚哪一台才是最好的。由于你看不见机器的内部状态，你必须根据你获得的奖励来猜测。

作者展示了一个令人惊讶的结果：你无法实现“完美”的学习速度。
在普通的猜谜游戏中，你可以非常快地学习到最佳选项（在数学上，你的错误增长得非常缓慢，呈对数级增长）。但因为你看不见机器，且被迫等待信号才能切换，你不可避免地会犯更多的错误。你的学习速度会比“完美”的速度稍慢一些。这就像是在尝试寻找城市里的最佳路线，但你只能看到交通灯，看不到地图，而且在撞到特定的路口之前，你无法转弯。

解决方案：UCB-NOM

为了解决这个问题，作者创建了一种名为 UCB-NOM 的算法（针对非观测马尔可夫型多臂老虎机的置信区间上界算法）。

它是如何工作的： 想象你在对这些机器进行投注。你开始先稍微尝试一下它们。每当你拉动一次杠杆，你就会更新你的“置信度分数”。
“乐观主义”技巧： 该算法带有一定的乐观色彩。如果它不能百分之百确定一台机器很差，它会给它一个获益的机会，并再次尝试它。
“倍增”规则： 为了避免过于频繁地切换（这会浪费时间），该算法使用了一个“倍增技巧”。一旦它选中了一台机器，它就会一直运行这台机器，直到它使用该机器的次数达到上次选择时的两倍。这迫使算法在做出明智决策之前，必须坚持选择一段时间以收集足够的数据。

结果：它有多好？

论文证明了两件事：

在没有任何额外帮助的情况下： 如果你对机器一无所知（甚至不知道它们闲置时会变得多“生锈”），该算法虽然可以学习，但速度会比理论上的最佳速度稍慢。它“接近”完美，但并不完全是。
在有一点帮助的情况下： 如果你得到了一个“提示”——具体来说，是关于机器在闲置时退化程度的大致估计——该算法可以实现“完美”的学习速度。它可以像你能清晰看见机器内部一样快地进行学习。

总结

论文得出结论，无法看到机器的内部状态并不是灾难。只要机器在被忽视时会变差（即“自我退化”规则），你仍然可以有效地学习到最佳策略。主要的障碍仅仅在于你无法即时切换档位；你必须承诺选择一段时间，以便从中学习。

简而言之： 这篇论文教我们如何在面对无法看到机器内部、且无法轻易关闭机器的工厂时，做一个聪明的经理。它表明，如果机器在闲置时会生锈，那么最好的做法就是选定一个并坚持下去，同时也提供了一个用来弄清“选哪一个”的数学配方。

技术摘要：具有非观测状态与约束决策时刻的马尔可夫多臂老虎机学习

1. 问题定义

本文研究了在两种特定约束下的**马尔可夫老虎机（Markovian bandits）**遗憾值最小化问题：

非观测状态： 控制器无法观测臂（马尔可夫链）的内部状态。唯一可用的反馈是激活臂产生的奖励。这对应于一种“全老虎机反馈（full bandit feedback）”设定，其中状态空间是隐藏的。
约束决策时刻： 控制器不能在每个时间步任意切换臂。相反，只有在特定的决策时刻（ $\tau_i$ ）才允许切换。这些决策时刻是由奖励流决定的停时（stopping times）。具体而言，控制器必须在收到特定信号（例如非零奖励）之前，一直保持对某一臂的投入状态。

臂被建模为马尔可夫决策过程（MDP），其转移动力学取决于该臂是激活状态还是被动状态。系统的演化方式是：未激活的臂根据其被动核（ $p^0_a$ ）进行转移，而激活的臂则根据其活跃核（ $p^1_a$ ）进行转移。

2. 学习框架与基准

作者将分析限制在**“纯遗憾（pure regret）”**基准下。

纯策略（Pure Policies）： 如果一个策略在从开始到学习时程结束期间仅选择单一的臂且从未切换，则称该策略为“纯策略”。
遗憾值定义： 遗憾值是学习算法的累积奖励与最佳纯策略（具有最高渐近增益的臂）的累积奖励之差。

纯策略的动机：
虽然对于“闲置型（restless）”老虎机（其中非激活臂仍在演化），纯策略通常是次优的），但作者引入了一类被称为**自降级闲置型老虎机（self-degrading restless bandits）**的老虎机。在这种情况下，如果一个臂处于非激活状态，其期望偏差（衡量偏差函数相对于控制器观测值的偏离程度的一个度量）会趋于减少或保持不变。论文证明，对于自降级老虎机，纯策略是渐近最优的。这一类模型泛化了“静止型（rested）”老虎机（其中非激活臂冻结），并包含了非平凡的闲置型例子，如非抢占式 Gilbert-Elliott 信道和 Nerlove-Arrow 模型。

3. 方法论：UCB-NOM

论文提出了 UCB-NOM（针对非观测马尔可夫老虎机的置信上限算法），这是一种受 UCB 原则启发的乐观算法。

UCB-NOM 的核心组成部分：

经验增益估计器： 算法通过计算该臂激活时的平均收集奖励来估计其增益（ $g_a$ ）。
乐观指数构建： 为了处理不可观测性和约束，算法构建了一个关于真实增益的乐观上界 $\tilde{g}_a(t)$ $\tilde{g}_{a} (t)$ 。该指数包含：
- 经验平均奖励。
- 考虑以下因素的探索奖励（置信区间）：
  - 拉动次数（ $N_a(t)$ ）。
  - 算法切换到臂 $a$ 的次数（切换成本）。
  - 该臂马尔可夫链的偏差跨度（bias span, $sp(b_a)$ ），它量化了偏差函数的最大偏差。
倍增技巧（Doubling Trick）： 为了满足实现理论保证所需的“稀疏切换”属性，算法采用了倍增技巧。一旦选中某臂，该臂将被持续执行，直到其访问次数翻倍。这确保了切换次数随拉动次数呈对数增长。

解决的理论挑战：

非观测性： 不同于以往依赖于观察状态来触发再生周期的研究（如 Tekin & Liu 的 RCA），UCB-NOM 无法使用再生。相反，它利用偏差跨度和切换次数来界定误差。
约束时刻： 算法必须考虑决策时刻之间的延迟。分析假设了直到下一个决策时刻的预期时间存在一个界限（ $C_\tau$ ）。

4. 关键结果与理论保证

A. 下界（对数遗憾的不可能性）

论文指出，在没有先验知识的情况下，对于一致且稀疏切换的算法，对数遗憾（ $O(\log T)$ ）是无法实现的。

定理 4： 对于任何一致且稀疏切换的算法，期望遗憾值的规模为 $\omega(\log T)$ （超对数级）。这是通过构造替代模型来证明的，这些模型在仅通过奖励进行观测时与真实模型无法区分，但具有不同的最优臂，从而迫使算法过度拉动次优臂以进行区分。

B. UCB-NOM 的性能（一般情况）

定理 6： UCB-NOM 实现的遗憾界为 $O(f(T)^2 \log T)$ ，其中 $f(T)$ 是一个趋于无穷大的“跨度代理（span proxy）”函数。
意义： 通过选择以任意缓慢的速度趋于无穷大的 $f(T)$ ，UCB-NOM 可以无限接近理想的对数区间，从而有效地匹配超对数级的下界。

C. 带有先验知识时的性能（有界偏差跨度）

如果算法已知所有臂的偏差跨度的上界 $D$ （以及决策时刻的延迟），性能将显著提升。

定理 8（实例相关）： 在固定跨度代理 $f \equiv D$ 的情况下，UCB-NOM 实现 $O(\log T)$ 的实例相关遗憾值。
定理 9（最坏情况）： 在相同的有界跨度假设下，该算法实现 $O(\sqrt{T \log T})$ 的最坏情况遗憾值。

D. 调优与置信参数

论文分析了置信参数 $\delta(t)$ 的选择。它建议在马尔可夫设置中，选择“欠乐观（under-optimistic）”（即选择较小的 $\delta(t)$ 以扩大置信区间）比在随机老虎机中更为理想。这是因为由于偏差跨度的存在，马尔可夫估计器的噪声可能比奖励方差所暗示的更大，因此需要更大的探索奖励来维持乐观属性。

5. 意义与贡献

论文声称其贡献如下：

问题形式化： 它形式化了一个结合了非观测状态和内生约束决策时刻的学习环境，其动机源于通信网络（例如非抢占式信道调度）。
自降级老虎机： 它识别并定义了一类纯策略是最优的闲置型老虎机，从而证明了使用纯遗憾作为基准的合理性。
基本极限： 它证明了状态的不可观测性结合约束决策时刻，本质上阻碍了在一般情况下的对数遗憾，从而确立了一个超对数的下界。
算法设计： 它引入了 UCB-NOM，这是一种无需观测状态即可实现近优遗憾值的算法。至关重要的是，其遗憾界不依赖于底层马尔可夫链的状态数（ $|S_a|$ ），而是取决于偏差跨度。
结构性洞察： 它表明，通过简单的先验知识（即偏差跨度的界限），可以恢复经典随机老虎机的对数遗憾保证，这表明在自降级设置中，状态不可观测性是一个“轻微的干扰”，只要已知结构性界限即可。

作者总结道，尽管该设置比标准随机老虎机更复杂，但所提出的框架和算法在遵循纯遗憾基准的前提下，无需使用通常与部分可观测马尔可夫决策过程（POMDPs）相关的复杂技术，即可提供稳健的理论保证。