Feb, 2020

随机最短路径的近最优遗憾边界

PDF
TL;DR本文介绍了一种解决随机最短路径问题的算法，其中代理必须通过在有限次数的游戏中获得最佳策略，从而在最短期望代价下达到目标状态。通过探究悔恨最小化和最小瞬时代价的根号反比关系，本文提出了一种不依赖于最小代价的算法，并展示了任何学习算法在最坏情况下都要有至少 Omega（Bstar 根号乘以 S、A、K 的数量）的悔恨。
stochastic shortest pathplanningreinforcement learningregret minimizationlearning algorithm
发现论文，激发创造
  • 随机最短路径的最小化后悔策略

    本文研究了随机最短路问题，提出了一种基于有限阶段马尔科夫决策过程的新算法，其中最小化代理与模型之间的遗憾的上界可达到 $ \widetilde O (\sqrt { (B_\star^2 + B_\star) |S| |A| K})$。根据实验，该算法大幅改善了 Rosenberg 等人的遗憾上界，并且对于期望成本小于 1 的情况，提出了一种完全匹配的下界。

    Mar, 2021

  • 随机最短路径：极小 - 极大，无参数和无限时间后悔

    本文旨在解决随机最短路径问题中的学习问题，并设计了一种名为 EB-SSP 的基于模型的算法。该算法通过探索奖励来诱导一个乐观的 SSP 问题，其值迭代方案已被证明会收敛，并获得与下限之间的效果。同时，该算法在不使用任何先前知识的情况下获得最小化后悔率，并在如正成本或一般成本等各种情况下均有所改善。

    Apr, 2021

  • 带有对手可变成本的随机最短路径

    本文提出了对抗性 SSP 模型，包含时间上对成本的不良变化和未知转移，其开发了第一个对抗性 SSP 算法，并证明了高概率的回报上限。

    Jun, 2020

  • 改进的随机最短路径线性 MDP 无悔算法

    提出两种新的无懊悔算法解决带有线性 MDP 的随机最短路径问题，其中第一种算法能够以较低的计算成本获得较小的后悔界，并且对于有限时间情况，还获得了对数后悔界；而第二种算法则实现了无时间限制情况下的近乎最优性，但计算成本较高。

    Dec, 2021

  • 线性混合随机最短路径学习的几乎极小最优遗憾

    我们提出了一种基于扩展值迭代和细粒度方差感知置信集的新算法，用于解决具有线性混合转移内核的随机最短路径问题，其在减少限制性假设的同时实现了接近极小极大的算法性能。

    Feb, 2024

  • 使用线性函数逼近学习随机最短路径

    本论文研究了具有线性函数逼近的随机最短路径问题，提出了一种使用 Hoeffding 类型置信度集的新算法，能够实现次线性后悔保证。同时，对于在 $c_{min}=0$ 的情况，可以保证近似次立方的后悔保证。此外，通过设计改进的贝恩斯坦置信度集，改进的算法能够保证近乎最优的后悔保证。

    Oct, 2021

  • 达成目标很困难：解决随机最短路径样本复杂度问题

    本文研究计算马尔科夫决策过程中随机最短路径问题中，学习合理策略的采样复杂度，得到在有选项模型的情况下，学习合理策略的采样下界，并提出一种能够匹配界限的算法。同时，探讨在没有选项模型的情况下学习最佳策略识别问题中的高效学习可能性，并证明在一些假设下是实现可能的。

    Oct, 2022

  • 目标导向的强化学习中的无悔探索

    本研究中，我们针对没有固定假设的广义 SSP 问题，提出了第一个无悔算法 UC-SSP，并且证明了它在任意未知 SSP 上的后悔上界，该后悔上界与状态数 S、动作数 A、代价和 SSP 直径 D 有关，同时引入了一套新的停止规则，用以中断当前策略并切换到新的策略以提高效率。

    Dec, 2019

  • 使用线性函数逼近的随机最短路径问题的遗憾界限

    该研究提出了一种使用线性函数逼近算法的随机最短路径问题的算法，具有次线性 regret、计算效率高、使用平稳策略等特点，是该领域内第一种此类算法。

    May, 2021

  • 通过后验采样的随机最短路径模型在线学习

    该研究提出了一种基于后验采样的在线强化学习算法，即 PSRL-SSP，用于解决短路径问题，该算法只需要先验分布的知识，并且具有贝叶斯后悔界，是首个这样的后验采样算法，并在数值上优于之前提出的基于乐观主义的算法。

    Jun, 2021