An expected average reward criterion

In the present paper the expected average reward criterion is considered instead of the average expected reward criterion commonly used in stochastic dynamic programming. This new criterion seems to be more natural and yields stronger results. In addition to the theory of Markov chains, the theory of martingales will be used. This paper is concerned with Markov decision models with finite state space, arbitrary action space and bounded reward functions. In such a model there is always available a Markov policy which almost maximizes the average reward over a unit of time for different criteria. If the action space is a compact metric space there is even a stationary policy with the same property; further if a stationary policy is optimal for one criterion then this policy is optimal for all average reward criteria. Thus the paper solves some problems posed by Demko and Hill (1984).