不可观测状态与受限决策时点下的马尔可夫赌博机学习
研究背景与问题定义
在在线学习领域，马尔可夫赌博机（Markovian bandits） 是一类重要的模型，其特点是每个臂（arm）的状态按马尔可夫链演化。然而，现有工作通常假设状态可观测且决策时点无约束。本文《Learning in Markovian bandits with non-observable states and constrained decision epochs》首次系统研究了状态不可观测且决策时点受限的场景下的遗憾最小化问题。
作者聚焦于纯遗憾基准（pure regret benchmark），即比较学习算法的性能与最优纯策略（pure policy）——该策略类似经典随机赌博机的最优策略，从头到尾选择同一个最优臂，绝不切换。这一设定简化了分析，但已能揭示核心挑战。
核心贡献：自退化马尔可夫赌博机与遗憾下界
论文提出了自退化马尔可夫赌博机（self-degrading Markovian bandits） 这一新概念，它是经典休憩型（rested）马尔可夫赌博机的推广。在该模型中，纯策略总是渐近最优的，这为后续理论分析提供了基础。
一个重要发现是：若算法极少切换臂，则其遗憾必然超对数增长，即 $\omega(\log(T))$（$T$ 为学习时域）。这意味着在状态不可观测且决策受限时，对数遗憾（如经典 UCB 算法）在无先验知识的情况下是不可达的。
算法设计与遗憾上界
面对这一下界，作者设计了 UCB-NOM（Upper Confidence Bound for Non-Observable Markovian bandits），一种基于乐观原则的算法。其遗憾接近对数形式，具体表现为：
- 无先验知识时：遗憾为 $O(\log(T) \cdot \text{某个因子})$，略高于对数但未达超对数下界。
- 给定先验知识时：若已知臂的偏差函数（bias function）的界，则 UCB-NOM 可实现 $O(\log(T))$ 的遗憾，且最坏情况遗憾为 $O(\sqrt{T \log(T)})$。
值得注意的是，遗憾界不依赖于马尔可夫链的状态数，这大大增强了算法的实用性。
行业意义与展望
该工作揭示了状态不可观测性在自退化马尔可夫赌博机中仅是“轻微不便”，而非根本性障碍。对于实际应用——如推荐系统、临床试验、通信网络中的资源分配——这意味着即使无法观测用户状态或系统内部状态，仍可通过精心设计的算法获得接近最优的性能。
未来方向包括：扩展到更一般的纯策略不一定最优的模型，以及考虑有限切换次数下的遗憾分析。
一句话总结：本文证明了在不可观测状态和受限决策时点的马尔可夫赌博机中，超对数遗憾下界不可避免，但 UCB-NOM 算法可达到近乎对数的遗憾，且不依赖状态数。