- ICML线性混合随机最短路径学习的几乎极小最优遗憾
我们提出了一种基于扩展值迭代和细粒度方差感知置信集的新算法,用于解决具有线性混合转移内核的随机最短路径问题,其在减少限制性假设的同时实现了接近极小极大的算法性能。
- AAAI多目标概率规划的启发式搜索
本篇论文旨在将启发式搜索算法应用于多目标随机最短路径 (MOSSPs) 问题,提出了基于相对快速的 MOLAO* 和 MOLRTDP 两种算法,以及一系列能够应对随机、多目标特点的启发式函数,通过实验证明了新算法及函数的有效性。
- Forward-PECVaR 算法:CVaR SSPs 的精确评估
本文提出了一种新的算法 Forward-PECVaR,用于确切评估具有非均匀成本的 CVaR-SSPs 的稳态策略,并通过实证评估 CVaR Value Iteration 算法的质量以及算法参数对解决方案的质量和可伸缩性的影响。
- 达成目标很困难:解决随机最短路径样本复杂度问题
本文研究计算马尔科夫决策过程中随机最短路径问题中,学习合理策略的采样复杂度,得到在有选项模型的情况下,学习合理策略的采样下界,并提出一种能够匹配界限的算法。同时,探讨在没有选项模型的情况下学习最佳策略识别问题中的高效学习可能性,并证明在一些 - MM已知和未知环境下随机最短路径问题的凸对偶
本文从凸优化的角度研究了已知和未知环境中的随机最短路径问题,回顾了已知参数情况下的结果,并通过不同的证明发展了理解。其后专注于未知参数情况,在此基础上研究了扩展值迭代算子,包括现有算子和定义了其他算子。本文表明了 EVI 算子与凸规划的关系 - 离线随机最短路径:学习、评估与优化
本文研究了离线情况下有限状态和动作空间下的目标导向强化学习,提出基于简单值迭代的算法来解决离线策略评估和学习任务,并分析了这些算法的强实例相关界限。
- 基于风险的随机最短路径
本研究针对马尔科夫决策过程中随机最短路径问题提出了一种基于条件风险价值优化的风险感知控制方法,并通过线性规划和价值迭代两种算法实现了精确而可靠的解决方案。实验结果表明该方法在多个中等规模的问题实例上是可行的。
- 改进的随机最短路径线性 MDP 无悔算法
提出两种新的无懊悔算法解决带有线性 MDP 的随机最短路径问题,其中第一种算法能够以较低的计算成本获得较小的后悔界,并且对于有限时间情况,还获得了对数后悔界;而第二种算法则实现了无时间限制情况下的近乎最优性,但计算成本较高。
- ICML使用线性函数逼近学习随机最短路径
本论文研究了具有线性函数逼近的随机最短路径问题,提出了一种使用 Hoeffding 类型置信度集的新算法,能够实现次线性后悔保证。同时,对于在 $c_{min}=0$ 的情况,可以保证近似次立方的后悔保证。此外,通过设计改进的贝恩斯坦置信度 - 通过后验采样的随机最短路径模型在线学习
该研究提出了一种基于后验采样的在线强化学习算法,即 PSRL-SSP,用于解决短路径问题,该算法只需要先验分布的知识,并且具有贝叶斯后悔界,是首个这样的后验采样算法,并在数值上优于之前提出的基于乐观主义的算法。
- 使用线性函数逼近的随机最短路径问题的遗憾界限
该研究提出了一种使用线性函数逼近算法的随机最短路径问题的算法,具有次线性 regret、计算效率高、使用平稳策略等特点,是该领域内第一种此类算法。
- 随机最短路径:极小 - 极大,无参数和无限时间后悔
本文旨在解决随机最短路径问题中的学习问题,并设计了一种名为 EB-SSP 的基于模型的算法。该算法通过探索奖励来诱导一个乐观的 SSP 问题,其值迭代方案已被证明会收敛,并获得与下限之间的效果。同时,该算法在不使用任何先前知识的情况下获得最 - 随机最短路径的最小化后悔策略
本文研究了随机最短路问题,提出了一种基于有限阶段马尔科夫决策过程的新算法,其中最小化代理与模型之间的遗憾的上界可达到 $ \widetilde O (\sqrt { (B_\star^2 + B_\star) |S| |A| K})$。根据 - AAAI基于极小化遗憾优化的不确定马尔可夫决策过程鲁棒规划
本文旨在通过引入一种 Bellman 方程式来计算政策的懊悔,提出了一种基于动态规划算法的方法,以便为具有不确定成本和转移函数的 SSP UMDPs 规划,该方法精确地优化了具有独立不确定性的 UMDPs 的最小化极大遗憾,并通过选项扩展了 - 具备对抗成本和已知转移的随机最短路径最小化遗憾
研究用 Online Mirror Descent 框架的各种新技术,包括改进的多尺度专家算法、从一般随机最短路径到特殊无环情况的降低、倾斜的占用度量空间以及添加到成本估计器的新校正项等,以解决带对手成本的随机最短路径问题并同时减小学习者方 - 带有对手可变成本的随机最短路径
本文提出了对抗性 SSP 模型,包含时间上对成本的不良变化和未知转移,其开发了第一个对抗性 SSP 算法,并证明了高概率的回报上限。
- 随机最短路径的近最优遗憾边界
本文介绍了一种解决随机最短路径问题的算法,其中代理必须通过在有限次数的游戏中获得最佳策略,从而在最短期望代价下达到目标状态。通过探究悔恨最小化和最小瞬时代价的根号反比关系,本文提出了一种不依赖于最小代价的算法,并展示了任何学习算法在最坏情况 - 目标导向的强化学习中的无悔探索
本研究中,我们针对没有固定假设的广义 SSP 问题,提出了第一个无悔算法 UC-SSP,并且证明了它在任意未知 SSP 上的后悔上界,该后悔上界与状态数 S、动作数 A、代价和 SSP 直径 D 有关,同时引入了一套新的停止规则,用以中断当 - CVaR 约束 MDPs 的政策梯度
本文研究了风险受限随机最短路径问题中的条件风险价值,提出了两种基于随机逼近、小批量、策略梯度和重要性采样的本地风险最优策略算法,并将条件风险价值估计过程纳入算法中进行梯度和方差的估计和降低。
- 随机最短路径问题的次优解界
通过计算动态规划算子的 Bellman 残差,我们可以计算出随机最短路径问题解的次优性界限。在考虑到过渡成本为正的情况下,即使不是所有的策略都是正确的,我们也可以轻松地计算次优性界限。