用秩一近似加速马尔可夫决策过程求解，效果优于传统方法。
Rank-One Modified Value Iteration
- 用幂法近似转移矩阵的平稳分布，实现秩一近似更新。
- 理论证明收敛速度与值迭代、Q-learning相同，计算复杂度相当。
- 实验表明在规划与学习任务中均显著优于一阶算法及其加速版本。
本文提出一种新算法，用于求解马尔可夫决策过程的规划与学习问题。该算法采用策略迭代式更新，在策略评估步骤中使用转移概率矩阵的秩一近似。该秩一近似与对应转移矩阵的平稳分布密切相关，通过幂法进行近似。理论上，该算法在规划问题中收敛到最优（动作）值函数的速度和计算复杂度与值迭代算法相同；在学习问题中则与Q-learning算法相当。通过大量数值仿真，我们发现该算法在规划与学习任务中始终优于一阶算法及其加速版本。
原文摘要 · Abstract (English)
In this paper, we provide a novel algorithm for solving planning and learning problems of Markov decision processes. The proposed algorithm follows a policy iteration-type update by using a rank-one approximation of the transition probability matrix in the policy evaluation step. This rank-one approximation is closely related to the stationary distribution of the corresponding transition probability matrix, which is approximated using the power method. We provide theoretical guarantees for the convergence of the proposed algorithm to optimal (action-)value function with the same rate and computational complexity as the value iteration algorithm in the planning problem and as the Q-learning algorithm in the learning problem. Through our extensive numerical simulations, however, we show that the proposed algorithm consistently outperforms first-order algorithms and their accelerated versions for both planning and learning problems.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。