Models and algorithms for skip-free Markov decision processes on trees

Models and algorithms for skip-free Markov decision processes on trees

0.00 Avg rating0 Votes
Article ID: iaor201527353
Volume: 66
Issue: 10
Start Page Number: 1595
End Page Number: 1604
Publication Date: Oct 2015
Journal: Journal of the Operational Research Society
Authors:
Keywords: control, programming: markov decision
Abstract:

We introduce a class of models for multidimensional control problems that we call skip‐free Markov decision processes on trees. We describe and analyse an algorithm applicable to Markov decision processes of this type that are skip‐free in the negative direction. Starting with the finite average cost case, we show that the algorithm combines the advantages of both value iteration and policy iteration–it is guaranteed to converge to an optimal policy and optimal value function after a finite number of iterations but the computational effort required for each iteration step is comparable with that for value iteration. We show that the algorithm can also be used to solve discounted cost models and continuous‐time models, and that a suitably modified algorithm can be used to solve communicating models.

Reviews

Required fields are marked *. Your email address will not be published.