arXiv:2505.00795v1 宣告类型: 新 摘要: Howard的策略迭代（HPI）是解决马尔可夫决策过程（MDPs）的经典算法。HPI 使用一种“贪婪” 的切换规则，从任意非最优策略更新到一个支配的策略，直到找到最优策略为止。尽管该算法在六十年前被提出，HPI 的运行时间的最佳已知上界仍然呈指数级增长，甚至在只包含确定性转换的 MDP 类（DMDPs）中也是如此。与此同时，对于每状态只有固定数量动作的 MDPs，HPI 的最紧低界仅为线性。在本文中，我们报告了一个显著的改进：对于 DMDPs 的 HPI，存在一个次指数级的上界，该上界依赖于奖励的位数，而与折扣因子无关。同样的上界也适用于只有两种可能奖励（其大小可任意）的 DMDPs。