Technical Note—Accelerated Computation of the Expected Discounted Return in a Markov Chain

Abstract

This note investigates the use of extrapolations with certain iterative methods to accelerate the computation of the expected discounted return in a finite Markov chain. An easily administered algorithm for reordering the equations allows an attractive stopping rule to be used with Gauss-Seidel iteration. Lower bound and norm reducing extrapolations are introduced. Certain of these extrapolations that are optimal are easily computed. From the results of a small numerical example, it appears that the effects of reordering can be dramatic. Some form of extrapolation with Gauss-Seidel iteration after reordering may turn out to be more efficient in practice than successive over-relaxation.