改进多链MDP值迭代算法，加速收敛并提升理论精度。
Faster Fixed-Point Methods for Multichain MDPs
- 设计新算法解决多链MDP中的导航难题，优化策略选择路径。
- 实现更快的收敛速度，理论复杂度比前人工作更优。
- 适用于强化学习中复杂环境下的平均奖励问题研究者。
我们研究在平均奖励准则下求解一般（即多链）马尔可夫决策过程（MDPs）的值迭代（VI）算法，这是一个基础但理论挑战性极强的问题。除所有平均奖励问题固有的非收缩性和贝尔曼算子解不唯一等困难外，多链情形下最优策略还需解决导向最佳连通分量的导航子问题，同时优化各分量内的长期性能。我们开发了能更好解决该导航子问题的算法，从而实现多链MDPs的更快收敛，获得优于以往工作的收敛速率与更精确的复杂度度量。研究中许多关键成果具有独立价值，包括平均奖励与折扣问题的新关联、可扩展至一般巴拿赫空间的折扣值迭代最优不动点方法、折扣值误差的新亚线性收敛率，以及多链MDPs的精细化次优性分解。总体而言，本工作为折扣与平均奖励问题提供了更快的收敛率，并拓展了值迭代方法的理论基础。
原文摘要 · Abstract (English)
We study value-iteration (VI) algorithms for solving general (a.k.a. multichain) Markov decision processes (MDPs) under the average-reward criterion, a fundamental but theoretically challenging setting. Beyond the difficulties inherent to all average-reward problems posed by the lack of contractivity and non-uniqueness of solutions to the Bellman operator, in the multichain setting an optimal policy must solve the navigation subproblem of steering towards the best connected component, in addition to optimizing long-run performance within each component. We develop algorithms which better solve this navigational subproblem in order to achieve faster convergence for multichain MDPs, obtaining improved rates of convergence and sharper measures of complexity relative to prior work. Many key components of our results are of potential independent interest, including novel connections between average-reward and discounted problems, optimal fixed-point methods for discounted VI which extend to general Banach spaces, new sublinear convergence rates for the discounted value error, and refined suboptimality decompositions for multichain MDPs. Overall our results yield faster convergence rates for discounted and average-reward problems and expand the theoretical foundations of VI approaches.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。