Premium
Technical note: A computationally efficient algorithm for undiscounted Markov decision processes with restricted observations
Author(s) -
Davis Lauren B.,
Hodgson Thom J.,
King Russell E.,
Wei Wenbin
Publication year - 2009
Publication title -
naval research logistics (nrl)
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.665
H-Index - 68
eISSN - 1520-6750
pISSN - 0894-069X
DOI - 10.1002/nav.20329
Subject(s) - markov decision process , unobservable , dynamic programming , mathematical optimization , computer science , algorithm , state space , partially observable markov decision process , function (biology) , markov process , state (computer science) , markov chain , process (computing) , mathematics , statistics , evolutionary biology , machine learning , econometrics , biology , operating system
We present a computationally efficient procedure to determine control policies for an infinite horizon Markov Decision process with restricted observations. The optimal policy for the system with restricted observations is a function of the observation process and not the unobservable states of the system. Thus, the policy is stationary with respect to the partitioned state space. The algorithm we propose addresses the undiscounted average cost case. The algorithm combines a local search with a modified version of Howard's (Dynamic programming and Markov processes, MIT Press, Cambridge, MA, 1960) policy iteration method. We demonstrate empirically that the algorithm finds the optimal deterministic policy for over 96% of the problem instances generated. For large scale problem instances, we demonstrate that the average cost associated with the local optimal policy is lower than the average cost associated with an integer rounded policy produced by the algorithm of Serin and Kulkarni Math Methods Oper Res 61 (2005) 311–328. © 2008 Wiley Periodicals, Inc. Naval Research Logistics 2009