Models and algorithms for skip-free Markov decision processes on trees
E. J. Collins
We introduce a class of models for multidimensional control problems
which 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.
Some key words:
Markov decision processes on trees; multidimensional Markov decision processes;
x-revised problems