This paper considers undiscounted Markov decision problems. With no restriction (on either the periodicity or chain structure of the problem) we show that the value iteration method for finding maximal gain policies exhibits a geometric rate of convergence, whenever convergence occurs. In addition, we study the behaviour of the value-iteration operator; we give bounds for the number of steps needed for contraction, describe the ultimate behaviour of the convergence factor and give conditions for the existence of a uniform convergence rate.

In a preceding paper [2] we have introduced a new approach for solving a wide class of Markov decision problems in which the state-space may be general and the system may be continuously controlled. The criterion is the average cost. This paper discusses two applications of this approach. The first application concerns a house-selling problem in which a constructor builds houses which may be sold at any stage of the construction and potential customers make offers depending on the stage of the construction. The second application considers an M/M/c queueing problem in which the number of operating servers can be controlled by turning servers on or off.