Acceleration Operators in the Value Iteration Algorithms for Markov Decision Processes

Details Acceleration Operators in the Value Iteration Algorithms for Markov Decision Processes Acceleration Operators in the Value Iteration Algorithms for Markov Decision Processes

2005-06-23

arxiv.org/abs/math/0506489v2

Mathematics

Optimization and Control

32 pages, 2 figures, 2 table

Scientific paper

We study the general approach to accelerating the convergence of the most widely used solution method of Markov decision processes 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 1 and the transition probability matrix becomes dense, in which the standard value iteration algorithm and its variants suffer from slow convergence.

Affiliated with

Also associated with

No associations

Rating

Acceleration Operators in the Value Iteration Algorithms for Markov Decision Processes does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Acceleration Operators in the Value Iteration Algorithms for Markov Decision Processes, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Acceleration Operators in the Value Iteration Algorithms for Markov Decision Processes will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-581565