用几何视角重分析经典强化学习算法，发现其收敛速度可优于传统理论预期。
Geometric Re-Analysis of Classical MDP Solving Algorithms
- 基于马尔可夫决策过程的几何解释，提出改进折扣因子的变换方法
- 证明最优策略对应的马尔可夫奖励过程在不可约且非周期时，值迭代收敛率严格小于γ
- 揭示值迭代中存在旋转分量，为算法收敛性提供新理解，适合强化学习研究者
我们基于最近提出的马尔可夫决策过程（MDPs）几何解释，对经典求解算法值迭代（VI）和策略迭代（PI）进行再分析。首先，构建了一套基于几何的分析工具，包括一种改变折扣因子γ的变换方法，从而在多个场景下提升这些算法的收敛保证。特别地，我们的一个结果揭示了值迭代方法中存在旋转分量；由此表明，当由最优策略诱导的马尔可夫奖励过程（MRP）不可约且非周期时，值迭代的渐近收敛速率严格小于γ。
原文摘要 · Abstract (English)
We build on a recently introduced geometric interpretation of Markov Decision Processes (MDPs) to analyze classical MDP-solving algorithms: Value Iteration (VI) and Policy Iteration (PI). First, we develop a geometry-based analytical apparatus, including a transformation that modifies the discount factor $γ$, to improve convergence guarantees for these algorithms in several settings. In particular, one of our results identifies a rotation component in the VI method, and as a consequence shows that when a Markov Reward Process (MRP) induced by the optimal policy is irreducible and aperiodic, the asymptotic convergence rate of value iteration is strictly smaller than $γ$.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。