Accelerating Procedures of the Value Iteration Algorithm for Discounted Markov Decision Processes, Based on a One-Step Lookahead Analysis

Accelerating procedures for solving discounted Markov decision processes problems are developed based on a one-step lookahead analysis of the value iteration algorithm. We apply the criteria of minimum difference and minimum variance to obtain good adaptive relaxation factors that speed up the convergence of the algorithm. Several problems (including Howard's automobile replacement) are tested and a preliminary numerical evaluation reveals considerable reductions in computation time when compared to existing value iteration schemes.