线性混合随机最短路径学习的几乎极小最优遗憾
内容提要
本文综述随机最短路径问题的强化学习算法研究，涵盖线性函数逼近、Hoeffding与Bernstein置信集、次线性后悔保证、EB-SSP模型算法、对抗性SSP、稀疏线性MDP及PSRL-SSP后验采样，并探讨采样复杂度与下界。
延伸解读
线性函数逼近下的算法进展
文章梳理了随机最短路径问题中线性函数逼近的强化学习算法。2021年10月提出的算法使用Hoeffding置信集，在c_min=0时保证近似次立方后悔；改进的Bernstein置信集则实现近乎最优后悔。同年12月，两种无懊悔算法分别以低计算成本获得较小后悔界（有限时间下对数后悔）和高计算成本实现无时间限制的近乎最优性。这些工作共同推进了线性MDP下SSP的理论保证。
后悔下界与算法匹配
文章强调了后悔下界对算法设计的指导意义。2020年2月的工作证明任何学习算法在最坏情况下至少有Omega(B_star√(|S||A|K))的后悔，并提出了匹配该下界的算法，同时改进了Rosenberg等人的上界。2021年3月的EB-SSP算法通过探索奖励诱导乐观SSP问题，无需先验知识即达到最小化后悔率，并在正成本或一般成本等情况下均有改善。这些结果体现了下界与算法之间的紧密匹配。
模型变体与采样复杂度
文章还涵盖了对抗性SSP、稀疏线性MDP和PSRL-SSP等变体。2020年6月提出对抗性SSP模型，包含成本的不良变化和未知转移，并开发了首个对抗性SSP算法。2023年10月的PSRL-SSP是首个基于后验采样的在线算法，具有贝叶斯后悔界，数值上优于乐观主义算法。2022年10月的工作则研究了学习合理策略的采样复杂度，在有选项模型下得到下界并匹配算法，并探讨了无选项模型下高效学习的可能性。
Q&A
随机最短路径问题中，使用线性函数逼近的算法能实现什么样的后悔保证？
使用Hoeffding类型置信集的新算法能实现次线性后悔保证；当c_min=0时，可保证近似次立方的后悔保证；通过改进的Bernstein置信集，算法能保证近乎最优的后悔保证。
EB-SSP算法是如何工作的？它有什么优势？
EB-SSP是一种基于模型的算法，通过探索奖励诱导一个乐观的SSP问题，其值迭代方案已被证明会收敛。该算法在不使用任何先验知识的情况下获得最小化后悔率，并在正成本或一般成本等各种情况下均有所改善。
对抗性SSP模型是什么？针对它有什么算法？
对抗性SSP模型包含时间上对成本的不良变化和未知转移。针对该模型，开发了第一个对抗性SSP算法，并证明了高概率的回报上限。
PSRL-SSP算法有什么特点？它和基于乐观主义的算法相比如何？
PSRL-SSP是一种基于后验采样的在线强化学习算法，用于解决短路径问题，只需要先验分布的知识，并且具有贝叶斯后悔界，是首个这样的后验采样算法，并在数值上优于之前提出的基于乐观主义的算法。
在随机最短路径问题中，学习合理策略的采样复杂度下界是什么？
在有选项模型的情况下，学习合理策略的采样下界已被得到，并提出一种能够匹配界限的算法。在没有选项模型的情况下，探讨了学习最佳策略识别问题中的高效学习可能性，并证明在一些假设下是实现可能的。
稀疏线性MDP下的随机最短路径问题有什么新的遗憾最小化算法？
提出了一种新的遗憾最小化算法，用于具有稀疏线性马尔可夫决策过程（SMDP）的情节性问题，其中状态转移分布是观察特征的线性函数。
