Bounds for the quality and the number of steps in Bellman’s value iteration algorithm

The paper considers a discounted Markovian decision process with finite state space and infinite horizon. For an arbitrary action space, it derives estimates for the (finite stage) value functions and suboptimality bounds for policies consisting of sub-optimal decisions on every stage. From this, using a slightly generalized result obtained by Holzbaur and Meister, the paper gives a bound for the number of steps taken to determine an optimal or an •-optimal policy. This improves the results given in Holzbaur and Meister.