非可观测状态与受限决策周期的马尔可夫强盗学习

近日，一篇题为《Learning in Markovian bandits with non-observable states and constrained decision epochs》的论文在arXiv上发布，由Thomas Hira等四位作者共同完成。该论文深入研究了在状态不可观测且决策周期可能受限的马尔可夫强盗（Markovian bandits）问题中的遗憾最小化。传统强盗算法通常假设决策者能直接观察每个臂的状态，或决策时机不受限制，但现实应用中这两者往往难以满足。论文聚焦于一种“纯”遗憾基准，即比较学习算法与最优纯策略的性能差异。纯策略类似于随机强盗中的最优策略，从头到尾始终选择同一最佳臂，从不切换。

作者首先引入了一种新的强盗模型——自退化马尔可夫强盗（self-degrading Markovian bandits），这是对经典静止马尔可夫强盗（rested Markovian bandits）的一种推广。在该模型中，每个臂的状态随选择而退化，且纯策略始终是渐近最优的。这一发现为后续理论分析奠定了基础。

论文的核心理论贡献在于证明了在缺乏任何先验知识的情况下，任何不频繁切换臂的算法都必然面临超对数遗憾增长，即遗憾下界为ω(log T)，其中T是学习周期。这意味着传统的对数遗憾界在这种环境中是不可实现的。然而，作者并未止步于此，他们设计了一种基于UCB（上置信界）的乐观算法UCB-NOM，其遗憾接近对数水平，从而弥合了理论与实际之间的差距。

更令人振奋的是，当算法预先知道一个关于臂偏差函数（bias functions）的界时，UCB-NOM可以严格实现O(log T)的遗憾，并且最坏情况下的遗憾界为O(√(T log T))。这些界与底层马尔可夫链的状态数无关，充分体现了算法的鲁棒性和可扩展性。论文的结论表明，在自退化马尔可夫强盗中，状态非可观测性只是一个轻微的不便，通过精心设计的算法和适当的先验信息，仍能获得接近最优的性能。该研究为推荐系统、动态定价和临床实验等应用提供了重要的理论指导。