Generalized Value Bounds and Column Reduction in Finite Markov Decision Problems

Generalized value-function bounds are developed for a class of value-iteration methods in finite state and action Markov decision problems. The bounds are applicable to either discounted total value problems, or to undiscounted total value problems for absorbed processes which are multistage contracting. Some effects of Porteus' column reduction transformation on value-function bounds are studied. It is shown that column reduction tightens the bounds but does not accelerate their asymptotic rate of convergence. Explicit formulas are given for the value bounds obtained through column reduction, thus eliminating the need for performing the transformation.