×

Algorithms for countable state Markov decision models with an absorbing set. (English) Zbl 1097.90067

Summary: We consider a countable state Markov decision process with bounded reward function and an absorbing set. At first we generalize known properties and derive new properties of the critical discount factor, which is roughly defined as the maximal discount factor under which for \(V\), the maximal expected infinite-stage discounted reward, there is guaranteed existence, boundedness, and computability by the successive approximation method. The emphasis of the paper is on algorithms for computing \(V\) exactly (recursion in state space and policy iteration) or approximately (value iteration combined with an extrapolation and finite state approximation). Our extrapolation method is motivated by and based on the Perron-Frobenius theory for nonlinear operators. As a by-product we obtain an efficient algorithm for determining the distribution of the entrance time of a Markov chain into an absorbing set. Further results concern asymptotically \(\varepsilon\)-optimal policies and a new turnpike theorem. Some of the results need tightness of the transition law, which turns out to be equivalent to compactness of a nonlinear operator, which is crucial for our study.

MSC:

90C40 Markov and semi-Markov decision processes
90C59 Approximation methods and heuristics in mathematical programming
PDFBibTeX XMLCite
Full Text: DOI