带有对手可变成本的随机最短路径
本文介绍了一种解决随机最短路径问题的算法,其中代理必须通过在有限次数的游戏中获得最佳策略,从而在最短期望代价下达到目标状态。通过探究悔恨最小化和最小瞬时代价的根号反比关系,本文提出了一种不依赖于最小代价的算法,并展示了任何学习算法在最坏情况下都要有至少 Omega(Bstar 根号乘以 S、A、K 的数量)的悔恨。
Feb, 2020
本文研究了随机最短路问题,提出了一种基于有限阶段马尔科夫决策过程的新算法,其中最小化代理与模型之间的遗憾的上界可达到 $ \widetilde O (\sqrt { (B_\star^2 + B_\star) |S| |A| K})$。根据实验,该算法大幅改善了 Rosenberg 等人的遗憾上界,并且对于期望成本小于 1 的情况,提出了一种完全匹配的下界。
Mar, 2021
本文旨在解决随机最短路径问题中的学习问题,并设计了一种名为 EB-SSP 的基于模型的算法。该算法通过探索奖励来诱导一个乐观的 SSP 问题,其值迭代方案已被证明会收敛,并获得与下限之间的效果。同时,该算法在不使用任何先前知识的情况下获得最小化后悔率,并在如正成本或一般成本等各种情况下均有所改善。
Apr, 2021
本文主要研究随机最短路径问题中的对手成本和未知转移,并提出了一种新的算法,可以在有限的次数内找到最优解,此外,我们还提出了一种新的算法,可以在特定情景下近似达到最优解。
Feb, 2021
本文介绍了一个基于约束的随机规划问题,其中利用整数线性规划方法确保了确定性决策,同时为安全性关键的应用提供了约束违规概率的上界。同时还介绍了确定性策略和随机策略的随机舍入过程,并探讨了如何在考虑不同时间步的约束情况下进行 CC-SSP 的推广。
Feb, 2023
我们提出了一种基于扩展值迭代和细粒度方差感知置信集的新算法,用于解决具有线性混合转移内核的随机最短路径问题,其在减少限制性假设的同时实现了接近极小极大的算法性能。
Feb, 2024
本文研究计算马尔科夫决策过程中随机最短路径问题中,学习合理策略的采样复杂度,得到在有选项模型的情况下,学习合理策略的采样下界,并提出一种能够匹配界限的算法。同时,探讨在没有选项模型的情况下学习最佳策略识别问题中的高效学习可能性,并证明在一些假设下是实现可能的。
Oct, 2022
研究用 Online Mirror Descent 框架的各种新技术,包括改进的多尺度专家算法、从一般随机最短路径到特殊无环情况的降低、倾斜的占用度量空间以及添加到成本估计器的新校正项等,以解决带对手成本的随机最短路径问题并同时减小学习者方差和最优策略的偏差。
Dec, 2020
本论文研究了具有线性函数逼近的随机最短路径问题,提出了一种使用 Hoeffding 类型置信度集的新算法,能够实现次线性后悔保证。同时,对于在 $c_{min}=0$ 的情况,可以保证近似次立方的后悔保证。此外,通过设计改进的贝恩斯坦置信度集,改进的算法能够保证近乎最优的后悔保证。
Oct, 2021
提出两种新的无懊悔算法解决带有线性 MDP 的随机最短路径问题,其中第一种算法能够以较低的计算成本获得较小的后悔界,并且对于有限时间情况,还获得了对数后悔界;而第二种算法则实现了无时间限制情况下的近乎最优性,但计算成本较高。
Dec, 2021