MMJul, 2022

已知和未知环境下随机最短路径问题的凸对偶

PDF
TL;DR本文从凸优化的角度研究了已知和未知环境中的随机最短路径问题，回顾了已知参数情况下的结果，并通过不同的证明发展了理解。其后专注于未知参数情况，在此基础上研究了扩展值迭代算子，包括现有算子和定义了其他算子。本文表明了 EVI 算子与凸规划的关系及其对偶形式，同时提出了一些进一步研究的问题。
stochastic shortest pathconvex optimizationextended value iterationdualopen questions
发现论文，激发创造
  • 随机鞍点问题的泛化界

    本文研究了随机鞍点问题的经验鞍点解的泛化界，证明了在具有 Lipschitz 连续和强凸强凹的目标函数的情况下，可以使用统一稳定性论证来建立一个 O（1/n）的泛化界，并在没有强凸性和没有有界域的情况下提供了泛化界。在马尔可夫决策过程中的批量策略学习和用于随机博弈的混合策略纳什均衡估计的两个示例中，我们展示了正则化 ESP 解具有接近最优样本复杂度。

    Jun, 2020

  • 用于自主车辆行为规划的概率约束随机最短路径双重描述

    本文介绍了一个基于约束的随机规划问题，其中利用整数线性规划方法确保了确定性决策，同时为安全性关键的应用提供了约束违规概率的上界。同时还介绍了确定性策略和随机策略的随机舍入过程，并探讨了如何在考虑不同时间步的约束情况下进行 CC-SSP 的推广。

    Feb, 2023

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

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

    Jun, 2020

  • 基于风险的随机最短路径

    本研究针对马尔科夫决策过程中随机最短路径问题提出了一种基于条件风险价值优化的风险感知控制方法，并通过线性规划和价值迭代两种算法实现了精确而可靠的解决方案。实验结果表明该方法在多个中等规模的问题实例上是可行的。

    Mar, 2022

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

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

    Apr, 2021

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

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

    Feb, 2024

  • 离线随机最短路径：学习、评估与优化

    本文研究了离线情况下有限状态和动作空间下的目标导向强化学习，提出基于简单值迭代的算法来解决离线策略评估和学习任务，并分析了这些算法的强实例相关界限。

    Jun, 2022

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

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

    Feb, 2020

  • 使用随机镜像下降算法求解变分不等式

    本文提出了一种新的随机镜子代理（SMP）算法，通过便捷的步长策略优化收敛率，应用于解决了随机组合最小化和特定应用于随机半定可行性问题和最小化特征值的随机变分不等式问题

    Sep, 2008

  • 面向目标的 MDP 模型中的死路理论

    本文提出了三种新的 MDP 类，允许无法到达的目标，并呈现了具有理论基础的算法，探讨了这些类之间的理论关系，并进行了初步的实证研究。

    Oct, 2012