An Optimality Condition for Discrete Dynamic Programming with no Discounting

Abstract

In this paper we consider the discrete time finite state Markov decision problem with Veinott's criterion of maximizing the Cesaro mean of the vector of expected returns received in a finite horizon as the horizon tends to infinity. A necessary and sufficient condition for optimality is obtained, and at the same time we verify Veinott's conjecture that there are optimal stationary policies.