随机最短路径问题的高效约束生成
该论文提出了一种使用分层规划展开的基于成本约束的随机最短路径问题(HC-SSP)的框架,通过分支和剪枝算法来迭代地分配成本预算,从而在真实时间和风险敏感的应用中找到一个可行解。
May, 2022
本文介绍了一个基于约束的随机规划问题,其中利用整数线性规划方法确保了确定性决策,同时为安全性关键的应用提供了约束违规概率的上界。同时还介绍了确定性策略和随机策略的随机舍入过程,并探讨了如何在考虑不同时间步的约束情况下进行 CC-SSP 的推广。
Feb, 2023
提出了 k-SP 约束条件,这是一种新颖的约束条件,可以提高稀疏奖励 MDP 中的样本效率。在数值实验中,通过减少策略的轨迹空间,实现了抑制冗余探索和利用,提高了样本效率,并展示了优于传统算法的成果。
Jul, 2021
本文提出了一种利用关系型特征抽象学习广义策略自动机(Generalized Policy Automata,GPA)来解决随机最短路径(Stochastic Shortest Path Problems,SSPs)问题的方法,该方法通过少量数据训练便能学到适用于各种相关问题的泛化的非确定性部分策略(partial policy),并在针对数量超过训练数据的问题上显著优于现有的 SSP 求解器。
Apr, 2022
本文研究了离线情况下有限状态和动作空间下的目标导向强化学习,提出基于简单值迭代的算法来解决离线策略评估和学习任务,并分析了这些算法的强实例相关界限。
Jun, 2022
本文介绍了一种解决随机最短路径问题的算法,其中代理必须通过在有限次数的游戏中获得最佳策略,从而在最短期望代价下达到目标状态。通过探究悔恨最小化和最小瞬时代价的根号反比关系,本文提出了一种不依赖于最小代价的算法,并展示了任何学习算法在最坏情况下都要有至少 Omega(Bstar 根号乘以 S、A、K 的数量)的悔恨。
Feb, 2020
本文提出了一个在局部转换下的全多项式近似方案,可用于计算最优确定性策略,以解决 (C) C-SSP 问题,其中固定阈值限制随机最短路径问题是在一定操作限制下的规划形式,当限制违反时,这种 CC-SSP 变体允许边界概率,而 SSP 问题的状态可达性呈现出一定的局部性,并且在此情况下,只有一定数量的状态可以共享一些后续状态。
Apr, 2022
本文研究计算马尔科夫决策过程中随机最短路径问题中,学习合理策略的采样复杂度,得到在有选项模型的情况下,学习合理策略的采样下界,并提出一种能够匹配界限的算法。同时,探讨在没有选项模型的情况下学习最佳策略识别问题中的高效学习可能性,并证明在一些假设下是实现可能的。
Oct, 2022
该研究提出了一种基于后验采样的在线强化学习算法,即 PSRL-SSP,用于解决短路径问题,该算法只需要先验分布的知识,并且具有贝叶斯后悔界,是首个这样的后验采样算法,并在数值上优于之前提出的基于乐观主义的算法。
Jun, 2021