Bounds and Transformations in the Computational Theory for Finite State and Action Markov Decision Processes

New improved bounds on the optimal return function infinite state and action, infinite horizon, stationary Markov decision processes are developed. They require solving a single constraint, bounded variable linear program, which can be done using marginal analysis. The bounds can be used to obtain improved tests for suboptimal decisions, using MacQueen’s [28] criterion. Actually, the test resulting from the existing bounds of [30] has not appeared before. We show how to implement these tests so that little additional computational effort is required. We consider transformations which can be used to convert a process into an equivalent one which may be easier to solve. We present six general transformations (some of which are new) which can be used. Our main consideration here is to reduce the discount factor, since the bounds depend so crucially on it. The new bounds presented require the process to have equal row sums (such as in Blackwell [4]). We show how to transform processes which do not satisfy this condition, such as semi-Markov decision processes, into ones which do. It may be worthwhile to make this transformation even when the new bounds are not to be used. Given a process which has the equal row sum property, we specify some special cases (of the general transformations) which will reduce the discount factor and retain the equal raw sum property. One of these called the diagonal reduction, reduces all diagonal elements by the smallest such element, and increases the off diagonal elements. When the same general transformation is used to reduce all diagonal elements to zero, we obtain Jacobi iteration but may lose the equal row sum property. Another special case, called the scalar fixed matrix reduction, preserves this property and reduces the discount factor, but may deteriorate the sparsity of the process. Another case, called the column reduction, not only retains the equal row sum property and preserves sparsity, but can make a dramatic reduction in the discount factor. For each column, it reduces each element in that column by the smallest such element. If one abandons the equal row sum property, then other approaches become possible. For example, Gauss-Seidel iteration is seen to be a special case implied by one of our general transformations. We show how to extrapolate, compute bounds, and apply suboptimality tests for this case. Several possible computational approaches are applied to a small numerical example.