title: Scalable approximate policies for Markov decision process models of hospital elective admissions.
abstract: OBJECTIVE
  To demonstrate the feasibility of using stochastic simulation methods for the solution of a large-scale Markov decision process model of on-line patient admissions scheduling.
  
  
  METHODS
  The problem of admissions scheduling is modeled as a Markov decision process in which the states represent numbers of patients using each of a number of resources. We investigate current state-of-the-art real time planning methods to compute solutions to this Markov decision process. Due to the complexity of the model, traditional model-based planners are limited in scalability since they require an explicit enumeration of the model dynamics. To overcome this challenge, we apply sample-based planners along with efficient simulation techniques that given an initial start state, generate an action on-demand while avoiding portions of the model that are irrelevant to the start state. We also propose a novel variant of a popular sample-based planner that is particularly well suited to the elective admissions problem.
  
  
  RESULTS
  Results show that the stochastic simulation methods allow for the problem size to be scaled by a factor of almost 10 in the action space, and exponentially in the state space. We have demonstrated our approach on a problem with 81 actions, four specialities and four treatment patterns, and shown that we can generate solutions that are near-optimal in about 100s.
  
  
  CONCLUSIONS
  Sample-based planners are a viable alternative to state-based planners for large Markov decision process models of elective admissions scheduling.
authors.affiliation: School of Computer Science, University of Waterloo, 200 University Avenue W., Waterloo, Ontario, Canada N2L 1Z2.
authors.forename: George
authors.initials: G
authors.lastname: Zhu
authors.affiliation: School of Computer Science, University of Waterloo, 200 University Avenue W., Waterloo, Ontario, Canada N2L 1Z2.
authors.forename: Dan
authors.initials: D
authors.lastname: Lizotte
authors.affiliation: School of Computer Science, University of Waterloo, 200 University Avenue W., Waterloo, Ontario, Canada N2L 1Z2. Electronic address: jhoey@cs.uwaterloo.ca.
authors.forename: Jesse
authors.initials: J
authors.lastname: Hoey
mesh_terms: D000465:Algorithms; D003657:Decision Making; D005240:Feasibility Studies; D006801:Humans; D008390:Markov Chains; D010343:Patient Admission; D013269:Stochastic Processes
keywords: Elective admissions planning; Markov decision process; Monte-Carlo tree search; Patient flow modelling