Stochasticity in Approximate Dynamic Programming

点击翻译按钮获取中文摘要

My research focus is on patient scheduling in settings with multiple types of patients and/or multiple resources consumed. The challenge consists in juggling resources to meet different wait time targets while fitting different resource consumption into available capacity. In partnership with local organizations we have begun to examine the challenge of scheduling new and follow-up visits to an outpatient clinic - with wait time targets for new patients and time windows for follow-ups as well as the challenge of home health care visits where patients receive multiple visits on a regular schedule. While these applications form the test scenarios for our research, my primary concern is to address some of the limitations inherent in past work. Our primary methodology in solving scheduling problems has been Approximate Dynamic Programming (ADP) as scheduling problems are sequential decision problems where any realistic setting runs into the curse of dimensionality and thus requires an approximation method. Within ADP we have focused on the linear programming approach that has to main limitations - the restriction on the form of the approximation to a linear architecture and the fact that in transforming the MDP into a linear program one removes the variability. In some settings, ignoring variability is fine as the infinite horizon means that there is time to reach the expectations. We have demonstrated that assuming deterministic service times work reasonably well when the only concern is overtime at the end of the day. Part of this application extends this work to scenarios where one is also concerned with idle time and waiting time during the day. In the two settings described at the outset what is often variable is the number of visits per patient. Relying on the expected number of visits may in fact lead to unwanted periods of congestion. Thus, one long term objective of this proposal is to explore the application of robust optimization to help determine the optimal approximation in ADP. Since the LP approach to ADP transforms the MDP into a linear program, it would appear reasonable that the application of robust optimization is possible. Some work has already been done in this area suggesting that this may well be a promising direction. A second long term objective is the application of neural networks to the development of value function approximations that are capable of approximating a complicated value function but that nonetheless remain linear. We have done some work using non-linear approximation architectures that demonstrate improved performance over linear approximations but at the cost of significantly higher computational challenges. There is a possibility through machine learning of capturing some of the non-linearity while still being able to use the LP approach thus keeping the computational efficiencies of the LP approach while improving its ability to capture additional complexity.