🤖 machine learning

Adaptive Exploration for Latent-State Bandits

本文提出了用于潜状态多臂老虎机（latent-state bandits）的自适应探索算法，该算法通过引入滞后的动作-奖励对和动态探测指纹来增强 LinUCB，从而有效地追踪未观测到的马尔可夫状态，并在状态摘要足够独特且更新频繁时，实现比标准基准更低的动态遗憾。

原作者： Jikai Jin, Kenneth Hung, Sanath Kumar Krishnamurthy, Baoyi Shi, Congshan Zhang

发布于 2026-06-02

📖 1 分钟阅读☕ 轻松阅读

CC BY 4.0

原作者： Jikai Jin, Kenneth Hung, Sanath Kumar Krishnamurthy, Baoyi Shi, Congshan Zhang

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

想象一下，你是一位试图为顾客烹饪完美佳肴的大厨，但你看不见顾客，只能看到他们吃完后递回给你的盘子。

在正常的烹饪场景中，如果顾客说：“这汤太咸了，”你就知道该如何改进。但在本文所述的场景中，顾客的味觉正在根据一个你看不见的隐藏因素发生变化——也许他们刚刚吃了一份非常辛辣的小吃，或者也许他们身体不适，又或者可能是外面的天气让他们产生了不同的渴望。

这就是**潜在状态多臂老虎机（Latent-State Bandits）**问题。这里的“老虎机”是做出选择（动作）的大厨，而“潜在状态”是隐藏的状况（顾客的心情或健康状况），它会改变食物的味道。大厨看不见状态，只能看到反馈（奖励）。

以下是本文如何解决这个谜题的拆解，通过简单的概念进行说明：

1. 问题所在：“机器中的幽灵”

标准的烹饪算法（如基础的多臂老虎机算法）假设顾客的口味是恒定的。它们认为：“如果我端上了汤且他们很喜欢，那我就再次端上汤。”
但如果顾客的口味在秘密变化（例如，他们在没告诉你的情况下，从“渴望汤”切换到了“渴望披萨”），大厨就会不断做出错误的决策。本文称之为混淆（Confounding）。大厨之所以猜错了食谱，是因为他们缺失了隐藏的上下文信息。

2. 第一个线索：观察上一口（滞后上下文）

作者的第一个想法很简单：观察刚才发生了什么。
如果顾客刚吃了一个辣塔可，然后递回一个写着“太辣了”的盘子，这能告诉你关于他们当前状态的一些信息。即使你看不见他们，但由于他们刚刚吃了塔可并感到辛辣，这表明他们目前处于“对热量敏感”的状态。

本文将此称为 LC-UCB（滞后上下文置信上限）。它将上一次的动作和上一次的奖励视为当前隐藏状态的一个“提示”。这就像是在说：“既然他们刚才抱怨了辛辣，那么我现在应该避免提供辛辣的食物。”

缺陷： 有时，提示并不足够。想象有两种不同的隐藏状态（例如，“饥饿”和“无聊”），两者都让顾客觉得“汤还可以”。如果你只看上一口，你无法分辨他们处于哪种状态，因此可能会选错下一道菜。

3. 第二个线索：“状态指纹”（探测）

为了解决这种混乱，本文提出了一个名为**探测（Probing）**的“品鉴菜单”方法。
大厨不再仅仅供应一道菜，而是同时（或快速连续地）提供两份不同菜肴的微量样本，以获取顾客当前状态的“指纹”。

场景 A（随机化探测）： 如果有两个顾客并排坐着，你可以同时给一个送去塔可，给另一个送去沙拉。他们的共同反应会给你一个独特的“指纹”，让你准确识别出他们处于什么状态。
场景 B（序列化探测）： 如果只有一个顾客，你先给他们一个塔可，等一秒钟，然后再给他们一个沙拉。如果顾客的口味变化不是特别快，那么这两次反应的组合仍然可以作为一个指纹。

这个“指纹”有助于大厨区分那些在之前看起来完全相同的状态。

4. 聪明的厨师：自适应探索

本文意识到，不断尝试所有食物是浪费的。你不需要每一秒钟都在测试新菜单。只有当你感到困惑或距离上次检查已经有一段时间时，才需要进行测试。

他们创建了自适应算法（AdaRP-UCB 和 AdaSP-UCB），利用三个“闸门”来决定何时进行探测：

“惊喜”闸门（残差）： 如果顾客的反应与大厨的预测完全不同（例如：“我以为你会喜欢这碗汤，但你竟然讨厌它！”），那么是时候再次进行探测，以弄清楚到底发生了什么变化。
“犹豫”闸门（不确定性）： 如果大厨在两道菜之间难以抉择（分数持平），他们应该进行探测，以便在做出最终决定前获得更清晰的信号。
“陈旧”闸门（风险）： 如果大厨很久没有进行探测了，那么之前的“指纹”可能已经过时且不再有用。算法会强制进行一次刷新，以防万一顾客的状态已经发生了漂移。

5. 结果：什么时候有效？

作者在包含数千次模拟的“数字厨房”中测试了这些方法。

效果最好时： 当隐藏状态足够独特，能够通过指纹被识别出来，且状态在采样到使用采样之间不会发生过于剧烈的变化时。
失效时： 当噪声太大（顾客过于难以捉摸），或者如果状态变化得太快，以至于当你完成“品鉴菜单”时，顾客的心意已经变了。

总结

本文教导我们如何在世界以我们无法直接观察到的方式发生变化时，做出更好的决策。我们不是在盲目猜测或不断测试一切，而是利用过去的线索和智能的、按需的测试来构建一个隐藏情况的“指纹”。这使我们能够走在变化的前面，即使这些变化是隐形的。

技术摘要：针对潜在状态老虎机的自适应探索

1. 问题定义

本文研究了一种非平稳多臂老虎机问题，其奖励分布取决于一个随时间自主演化的不可观测（潜在）马尔可夫状态。与标准的上下文老虎机不同，学习者无法直接观测到状态 $s_t$ ，只能观测到所选动作 $a_t$ 以及由此产生的随机奖励 $r_t$ 。

核心挑战在于，随着隐藏状态的转换，最优臂也会发生变化，但学习者必须仅根据动作和奖励的历史记录来推断当前状态。这种设定引入了三个特定的技术难点：

受混淆的奖励估计： 标准算法会对状态分布进行奖励平均，当最优臂在不同状态下发生变化时，这会导致系统性偏差。
时间上的奖励归因： 很难区分奖励性能的变化是由于学习进展还是由于隐藏状态的转换引起的。
有限的状态信息： 算法无法直接以状态特征进行条件化，必须依赖间接信号，而这一任务会随着状态空间的增大而变得更加困难。

目标是最小化相对于“状态感知预言机”（state-aware oracle）的动态遗憾（dynamic regret），该遗憾定义为当前隐藏状态下的最优臂奖励与实际选择的臂之间的累积差值。

2. 方法论

作者提出了一系列将**滞后上下文（Lagged Context）与探测策略（Probing Strategies）**集成到 LinUCB 框架中的算法。该方法避免了对潜在马尔可夫转移模型的显式估计，而是依赖于低维统计量来分离状态。

2.1 滞后上下文 (LC-UCB)

第一个组件是滞后上下文 UCB (LC-UCB)，它将前一个动作-奖励对 $(a_{t-1}, r_{t-1})$ 处理为上下文特征向量 $\phi_t$ 。

直觉： 在缓慢的马尔可夫状态动力学下，前一个奖励提供了关于前一个状态 $s_{t-1}$ 的信息，而 $s_{t-1}$ 与当前状态 $s_t$ 高度相关。
机制： 该算法学习从 $(a_{t-1}, r_{t-1})$ 到当前奖励 $r_t$ 的映射。这使得学习者能够隐式地追踪状态，并选择适用于推断出的近期状态的最优臂，而不是针对所有状态的平均值进行选择。
局限性： 如果多个状态对同一动作产生相似的奖励，则会导致 LC-UCB 失效（不可辨识性），从而导致状态推断的歧义。

2.2 探测状态指纹

为了解决歧义，作者引入了探测策略来生成“状态指纹”——即通过多个臂的联合观测结果来唯一识别隐藏状态。文中提出了两种范式：

随机化探测 UCB (RP-UCB)： 适用于可以同时为多个实验单元（例如用户）分配不同臂的情景。它收集来自同一时间步的真实联合观测值 $(r_0, r_1)$ 。
顺序探测 UCB (SP-UCB)： 适用于单单元设置。它连续采样臂（例如在 $t$ 时刻采样臂 0，在 $t+1$ 时刻采样臂 1），并将这对组合 $(r_t, r_{t+1})$ 视为合成指纹。这依赖于状态是“粘性”的（具有高自转移概率）这一假设，即状态在两次探测之间不会发生改变。

2.3 自适应探索 (AdaRP-UCB / AdaSP-UCB)

固定计划的探测即使在模型具有置信度时也会产生遗憾。作者提出了自适应探测变体，仅在必要时刷新指纹，并使用了三种门控机制：

残差门 (Residual Gate)： 如果预测误差（学生化残差）超过阈值，则触发探测，这表明发生了模型漂移或状态转换。
不确定性门 (Uncertainty Gate)： 如果前两个 UCB 分数之间的差距很小，则触发探测，这表明在臂选择方面存在高度不确定性。
陈旧性（危险）门 (Staleness/Hazard Gate)： 如果指纹在由指数危险函数定义的持续时间内未更新，则触发探测，以防止使用过时的信息。

这些门控受到最小探测间隔（ $\tau_{min}$ ）的限制，以防止振荡行为。

3. 核心贡献

算法框架： 开发了 LC-UCB、RP-UCB、SP-UCB 及其自适应变体（AdaRP-UCB、AdaSP-UCB），这些算法结合了滞后上下文与协调探测，用以处理无需显式估计马尔可夫模型的潜在状态老虎机。
理论分析： 将动态遗憾分解为三个部分：表示歧义（近似误差）、探测成本以及指纹陈旧后的漂移。论文提供的界限表明，自适应探测通过平衡这些因素来最小化遗憾。
实证验证： 在不同的隐藏状态数量 ( $S$ )、转移速率（自转移概率 $p_{stay}$ ）、奖励噪声 ( $\sigma$ ) 和时间跨度 ( $T$ ) 下进行了系统评估。

4. 实验结果

算法针对经典的基准算法（UCB1、汤姆森采样）、对抗性方法（EXP3）以及非平稳方法（滑动窗口 UCB、折扣 UCB）进行了评估。

性能： 在摘要（指纹）能够区分状态并能足够频繁更新的环境中，自适应探测方法（特别是 AdaRP-UCB 和 AdaSP-UCB）一致优于所有基准算法。
- AdaRP-UCB 在 13 个随机配置中的 12 个中取得了最低遗憾，显示出在剧烈波动环境中的显著优势。
- AdaSP-UCB 在低噪声、慢混合或大状态空间的单单元设置中表现最佳。
失效模式： 论文指出了这些方法性能下降的具体条件：
- 高噪声： 当噪声 ( $\sigma$ ) 相对于臂间隙较大时，指纹变得微弱，此时非平稳基准方法（如 D-UCB）可能表现更好。
- 弱指纹分离度： 如果不同的状态产生相似的联合奖励分布，探测策略将无法消除歧义。
- 快速切换： 当状态在探测窗口内频繁变化（低 $p_{stay}$ ）时，顺序探测 (SP-UCB) 会失效，因为合成指纹变得无效。
消融研究： 在粘性状态环境下，移除指纹特征 ( $\phi_{fp}$ ) 会显著增加遗憾。移除滞后上下文 ( $\phi_{lag}$ ) 在某些随机化设置中的影响较小，这表明自适应定时是那里的主要驱动因素。

5. 重要性与主张

本文声称其主要贡献在于提供了一种处理结构化非平稳性的实用方法，在这种情况下，环境通过自主的马尔可夫过程进行演化。不同于将变化视为任意漂移的标准非平稳老虎机，也不同于需要完全可观测性或复杂解码的 POMDP，本文的方法利用轻量级的历史摘要和探测来维持当前最优臂的估计。

作者强调，其方法在以下情形下最为有效：

潜在状态在短期内是可预测的（慢混合）。
探测策略能够生成足以分离相关状态的统计量（指纹）。
自适应门控机制能够在保持这些摘要实时性的同时，不会产生过多的探测遗憾。

这项工作通过提供一种基于 LinUCB 的计算高效解决方案，弥合了上下文老虎机与潜在状态强化学习之间的鸿沟，且无需学习隐藏状态的完整转移动力学。