证明了确定性马尔可夫决策问题中，霍华德策略迭代的运行时间是次指数级的。
Howard's Policy Iteration is Subexponential for Deterministic Markov Decision Problems with Rewards of Fixed Bit-size and Arbitrary Discount Factor
- 基于奖励位宽构建新分析框架，突破传统指数上界
- 首次给出不依赖折扣因子的次指数时间上界
- 适用于任意折扣因子且奖励位宽固定的确定性MDP
霍华德策略迭代（HPI）是求解马尔可夫决策问题（MDPs）的经典算法。尽管该算法问世超过60年，其最优时间复杂度的已知上界仍为状态数的指数级——即使在仅含确定性转移的确定性MDP（DMDPs）这一受限类别中亦然。而针对每状态动作数恒定的MDP，HPI的最紧下界仅为线性。本文报告了一项重要进展：对奖励位宽固定、任意折扣因子的确定性MDP，HPI首次获得次指数时间上界，该上界仅依赖于奖励的位宽，与折扣因子无关。该上界同样适用于仅有两种可能奖励值（可任意大小）的DMDPs。
原文摘要 · Abstract (English)
Howard's Policy Iteration (HPI) is a classic algorithm for solving Markov Decision Problems (MDPs). HPI uses a "greedy" switching rule to update from any non-optimal policy to a dominating one, iterating until an optimal policy is found. Despite its introduction over 60 years ago, the best-known upper bounds on HPI's running time remain exponential in the number of states -- indeed even on the restricted class of MDPs with only deterministic transitions (DMDPs). Meanwhile, the tightest lower bound for HPI for MDPs with a constant number of actions per state is only linear. In this paper, we report a significant improvement: a subexponential upper bound for HPI on DMDPs, which is parameterised by the bit-size of the rewards, while independent of the discount factor. The same upper bound also applies to DMDPs with only two possible rewards (which may be of arbitrary size).
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。