Generalized Second Order Value Iteration in Markov Decision Processes
This work addresses convergence speed issues in MDPs for researchers and practitioners, but it is incremental as it builds on existing successive relaxation techniques.
The authors tackled the slow convergence of first-order value iteration in Markov Decision Processes by proposing a second-order method based on Newton-Raphson applied to successive relaxation, proving global asymptotic convergence and demonstrating effectiveness through experiments.
Value iteration is a fixed point iteration technique utilized to obtain the optimal value function and policy in a discounted reward Markov Decision Process (MDP). Here, a contraction operator is constructed and applied repeatedly to arrive at the optimal solution. Value iteration is a first order method and therefore it may take a large number of iterations to converge to the optimal solution. Successive relaxation is a popular technique that can be applied to solve a fixed point equation. It has been shown in the literature that, under a special structure of the MDP, successive over-relaxation technique computes the optimal value function faster than standard value iteration. In this work, we propose a second order value iteration procedure that is obtained by applying the Newton-Raphson method to the successive relaxation value iteration scheme. We prove the global convergence of our algorithm to the optimal solution asymptotically and show the second order convergence. Through experiments, we demonstrate the effectiveness of our proposed approach.