提出霍华德策略迭代算法在确定性MDP中的新下界，揭示其最坏情况复杂度与输入规模线性相关。
Lower Bound on Howard Policy Iteration for Deterministic Markov Decision Processes
- 通过构造特定图结构，证明算法需至少Ω˜(I)次迭代
- 将原有亚线性下界提升至与输入规模线性相关的下界
- 对算法理论性能提供更严格评估，适合算法分析研究者
确定性马尔可夫决策过程（DMDP）是决策制定的数学框架，其结果和未来动作由当前选择的动作唯一决定。DMDP可视为有向加权图，控制器每一步选择一条出边。目标是定义在无限轨迹上的可测函数，价值为控制器能保证的最大累积奖励。本文考虑经典的平均收益（又称极限平均）目标，这是基本且重要的目标。霍华德策略迭代算法是求解具有平均收益目标的DMDP的常用方法。尽管该算法在实践中表现良好，但已知最佳上界为指数级，而此前最低下界仅为˜Ω(√I)，其中˜Ω隐藏了多项式对数因子，即迭代次数为输入规模I的亚线性量级。本文主要成果是改进该基础算法的下界：我们证明对于输入规模I，算法需要˜Ω(I)次迭代。
原文摘要 · Abstract (English)
Deterministic Markov Decision Processes (DMDPs) are a mathematical framework for decision-making where the outcomes and future possible actions are deterministically determined by the current action taken. DMDPs can be viewed as a finite directed weighted graph, where in each step, the controller chooses an outgoing edge. An objective is a measurable function on runs (or infinite trajectories) of the DMDP, and the value for an objective is the maximal cumulative reward (or weight) that the controller can guarantee. We consider the classical mean-payoff (aka limit-average) objective, which is a basic and fundamental objective. Howard's policy iteration algorithm is a popular method for solving DMDPs with mean-payoff objectives. Although Howard's algorithm performs well in practice, as experimental studies suggested, the best known upper bound is exponential and the current known lower bound is as follows: For the input size $I$, the algorithm requires $\tildeΩ(\sqrt{I})$ iterations, where $\tildeΩ$ hides the poly-logarithmic factors, i.e., the current lower bound on iterations is sub-linear with respect to the input size. Our main result is an improved lower bound for this fundamental algorithm where we show that for the input size $I$, the algorithm requires $\tildeΩ(I)$ iterations.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。