论文标题
乘以非对称仿射固定点问题和对马尔可夫决策过程的应用而乘以加速的价值迭代
Multiply Accelerated Value Iteration for Non-Symmetric Affine Fixed Point Problems and application to Markov Decision Processes
论文作者
论文摘要
我们分析了Nesterov加速梯度算法的修改版本，该算法适用于非自我伴侣矩阵的仿射固定点问题，例如在马尔可夫决策过程中出现的具有折扣或平均收益标准的决策过程中出现的矩阵。我们表征了该算法确实以加速渐近速率收敛的矩阵光谱。我们还引入了$ d $ th阶算法，并表明它在频谱上更苛刻的条件下产生了多个加速率。随后，我们应用这些方法来开发马尔可夫决策过程引起的非线性固定点问题的加速方案。数值实验说明了这一点。
We analyze a modified version of Nesterov accelerated gradient algorithm, which applies to affine fixed point problems with non self-adjoint matrices, such as the ones appearing in the theory of Markov decision processes with discounted or mean payoff criteria. We characterize the spectra of matrices for which this algorithm does converge with an accelerated asymptotic rate. We also introduce a $d$th-order algorithm, and show that it yields a multiply accelerated rate under more demanding conditions on the spectrum. We subsequently apply these methods to develop accelerated schemes for non-linear fixed point problems arising from Markov decision processes. This is illustrated by numerical experiments.
