This Article Full Text (PDF) Alert me when this article is cited Alert me if a correction is posted Services Email this article to a friend Similar articles in this journal Alert me to new issues of the journal Download to citation manager Google Scholar Articles by Shlakhter, O. Articles by Jaber, N.

Acceleration Operators in the Value Iteration Algorithms for Markov Decision Processes

Department of Mechanical and Industrial Engineering, University of Toronto, Toronto, Ontario M5S 3G8, Canada
Department of Mechanical and Industrial Engineering, University of Toronto, Toronto, Ontario M5S 3G8, Canada
Formerly with Department of Mathematics, University of Toronto, Toronto, Ontario, Canada
Department of Mechanical and Industrial Engineering, University of Toronto, Toronto, Ontario M5S 3G8, Canada
shlakht{at}mie.utoronto.ca
cglee{at}mie.utoronto.ca
jaber{at}mie.utoronto.ca

We study the general approach to accelerating the convergence of the most widely used solution method of Markov decision processes (MDPs) with the total expected discounted reward. Inspired by the monotone behavior of the contraction mappings in the feasible set of the linear programming problem equivalent to the MDP, we establish a class of operators that can be used in combination with a contraction mapping operator in the standard value iteration algorithm and its variants. We then propose two such operators, which can be easily implemented as part of the value iteration algorithm and its variants. Numerical studies show that the computational savings can be significant especially when the discount factor approaches one and the transition probability matrix becomes dense, in which the standard value iteration algorithm and its variants suffer from slow convergence.

Subject classifications: Markov decision processes; value iteration; accelerated convergence; linear programming.
History: Received April 2008; revision received June 2008; accepted July 2008.