Skip to main content
Article
A computationally efficient algorithm for undiscounted Markov decision processes with restricted observations
Naval Research Logistics (2009)
  • Lauren B Davis
  • Thom J Hodgson, North Carolina State University
  • Russell E King, North Carolina State University at Raleigh
  • Wenbin Wei
Abstract
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.
Keywords
  • Markov Decision process,
  • heuristics,
  • optimal control
Publication Date
February, 2009
Citation Information
Lauren B Davis, Thom J Hodgson, Russell E King and Wenbin Wei. "A computationally efficient algorithm for undiscounted Markov decision processes with restricted observations" Naval Research Logistics Vol. 56 Iss. 1 (2009)
Available at: http://works.bepress.com/lauren_b_davis/1/