arXiv:2505.06769v1 宣告类型: 新 摘要: 两类概率系统的标准模型是马尔可夫链(MCs)和马尔可夫决策过程(MDPs)。此类概率模型的经典目标是可达性和随机最短路径。这些问题的广泛研究算法方法是值迭代(VI)算法，该算法通过应用局部更新（称为贝尔曼更新）进行迭代更新。文献中有许多关于VI的实用方法，但它们在最坏情况下需要指数级的贝尔曼更新。预处理步骤是一个离散的、图论的算法，需要线性空间。一个重要但未解决的问题是在多项式时间预处理后，VI是否可以通过次指数级的贝尔曼更新来实现。在这项工作中，我们提出了一种基于猜测值的VI新方法。我们的理论贡献有两个方面。首先，对于MCs，我们提出了一种几乎线性时间的预处理算法，之后与猜测值一起，VI只需要次指数级的贝尔曼更新。其次，我们改进了VI在MDPs中收敛速度的分析。最后，我们基于新方法提出了一种实用的MDPs算法。实验结果表明，我们的方法在文献中的多个基准例子上比现有的基于VI的方法有显著的改进。