Finite state approximation algorithms for average cost denumerable state Markov decision processes (Q1066819)

This paper describes six algorithms for finding approximate solutions to infinite state space Markov decision processes under the average cost criteria. Three of the algorithms are variants on value iteration and three are variants on policy iteration. The convergence of these algorithms is guaranteed by a scrambling-type recurrency condition, (which ensures the average cost is independent of the starting state), and ''tail'' conditions (which allows states in the tail to be ignored). Computational results on the various algorithms are given.