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 HighWire Citing Articles via Google Scholar Google Scholar Articles by Leizarowitz, A. Search for Related Content

An Algorithm to Identify and Compute Average Optimal Policies in Multichain Markov Decision Processes

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

This paper concerns discrete-time, finite state multichain MDPs with compact action sets. The optimality criterion is long-run average cost. Simple examples illustrate that optimal stationary Markov policies do not always exist. We establish the existence of -optimal policies that are stationary Markovian, and develop an algorithm that computes these approximate optimal policies. We establish a necessary and sufficient condition for the existence of an optimal policy that is stationary Markovian, and in case that such an optimal policy exists the algorithm computes it.

Key Words: Markov decision process; long-run average cost; multichain MDP; communication classes; finite state space; computation algorithm; approximate optimal policies; optimal policies; compact action sets
History: Received: September 6, 1998; revision received: August 10, 1999;revision received: July 13, 2000;revision received: September 26, 2001;revision received: May 19, 2002;revision received: January 28, 2003;

This article has been cited by other articles:

				A. Leizarowitz and A. J. Zaslavski Uniqueness and Stability of Optimal Policies of Finite State Markov Decision Processes Mathematics of Operations Research, February 1, 2007; 32(1): 156 - 167. [Abstract] [PDF]