Solving Markovian decision processes by successive elimination of variables (Q1105497)

Semi-Markov decision processes are solved by some algorithms which are interesting mainly for formal analytical reasons and only in very special cases for computational purposes, too. The core of the algorithms consists in eliminating one component of the (relative) value function whereas the set of actions increases in dimensionality, finally arriving at optimization over the whole set of stationary policies. The discounted case is treated only to show this main feature. In the undiscounted case the first algorithm shows that the optimality equations (with gain rate independent of the state) has a solution if the underlying problem has a constant maximal gain rate (without any structural condition). The second algorithm constructs such a solution, possibly with some free parameters, whenever a solution exists.