基于猜测的马尔可夫链和马尔可夫决策过程的价值迭代

本研究解决了现有价值迭代算法在马尔可夫链（MC）中需要指数级贝尔曼更新的瓶颈问题。通过引入基于猜测值的新方法，研究展示了一种几乎线性时间的预处理算法，使得价值迭代能够在子指数级的贝尔曼更新下完成。此外，研究还改善了对马尔可夫决策过程（MDP）中收敛速度的分析，实验结果显示此方法在多个基准测试上的表现显著优于现有方法。