This Article Full Text (PDF) References Alert me when this article is cited Alert me if a correction is posted Services Email this article to a friend Similar articles in this journal Alert me to new issues of the journal Download to citation manager Citing Articles Citing Articles via Google Scholar Google Scholar Articles by Leizarowitz, A. Articles by Zaslavski, A. J. Search for Related Content

Uniqueness and Stability of Optimal Policies of Finite State Markov Decision Processes

Department of Mathematics, Technion, Haifa 32000, Israel
Department of Mathematics, Technion, Haifa 32000, Israel
la{at}tx.technion.ac.il
ajzasl{at}tx.technion.ac.il

In this paper we consider infinite horizon discrete-time optimal control of Markov decision processes (MDPs) with finite state spaces and compact action sets. We restrict attention to unicost MDPs, which form a class that contains all the weakly communicating MDPs. The unicost MDPs are characterized as those MDPs for which there exists a solution to the single optimality equation. We address the problem of uniqueness and stability of minimizing Markov actions. Our main result asserts that when we endow the set of unicost MDPs with a certain natural metric, under which it is complete, then the class of MDPs with essentially unique and stable minimizing Markov actions contains the intersection of countably many open dense sets (hence is itself dense). Thus, the property of having essentially unique and stable minimizing Markov actions is generic for unicost MDPs.

Key Words: Markov decision process; single optimality equation; stability of Markov policies; genericity; overtaking optimality
History: Received: September 14, 2004; revision received: January 23, 2006;