具有不可观察状态和受限决策时期的马尔可夫老虎机的学习

arXiv:2606.27448v1 公告类型：新 摘要：本文研究了具有 \emph{不可观察状态} 和可能 \emph{约束} 决策时期的马尔可夫老虎机的遗憾最小化问题。重点仅限于“纯粹”遗憾基准，它将学习算法的性能与最佳\emph{纯策略}进行比较，后者（类似于随机强盗的最优策略）从头到尾选择最佳手臂，而无需切换。我们引入了休息马尔可夫强盗的泛化，\emph{自降级马尔可夫强盗}，对于这种强盗，纯策略总是渐近最优的。我们表明，如果没有关于潜在强盗的先验知识，切换臂的算法的遗憾很少必然对每个强盗进行超对数缩放，即 $\omega(\log(T))$，其中 $T$ 是学习范围。尽管对数机制无法达到，我们还是设计了UCB-NOM，这是一种受UCB启发的乐观算法，其遗憾几乎是对数的。最后，我们证明，鉴于马尔可夫老虎机的先验知识（以其臂的偏置函数的界限的形式），UCB-NOM 的正确实例化实现了 $O(\log(T))$ 遗憾。我们进一步表明，这种先验知识允许 UCB-NOM 的最坏情况后悔界限为 $O(\sqrt{T \log(T)})$。值得注意的是，我们的遗憾界限并不取决于底层马尔可夫链的状态数量。我们的研究结果表明，状态的不可观察性对于自降马尔可夫强盗来说是一个轻微的不便。