INFINITE-HORIZON MARKOV CONTROL PROCESSES WITH UNDISCOUNTED COST CRITERIA: FROM AVERAGE TO OVERTAKING OPTIMALITY

Abstract. We consider discrete-time Markov control processes on Borel spaces and infinite-horizon undiscounted cost criteria which are sensitive to the growth rate of finite-horizon costs. These criteria include, at one extreme, the grossly underselective average cost criterion and, at the other, the excessively overselective strong overtaking optimality introduced in the economics literature by Ramsey. Between these two we have the overtaking (or catching-up) optimality of Gale and von Weizsäcker, Flynn’s opportunity cost and F-strong average optimality, Dutta’s D-strong average optimality, Veinott’s bias-optimality, and Yushkevich’s canonical policies. In this paper we give conditions for the existence of optimal policies for each of these criteria, and show how they are interrelated, among other things