Stochasticity in Approximate Dynamic Programming

近似动态规划中的随机性

• 批准号: RGPIN-2020-04301
• 负责人: Patrick, Jonathan
• 金额: $ 2.26万
• 依托单位: University of Ottawa
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2022
• 资助国家: 加拿大
• 起止时间: 2022-01-01 至 2023-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=765946
• 关键词: Stochasticity; 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.

我的研究重点是在多种类型的患者和/或多种资源消耗的设置患者调度。所面临的挑战在于，在将不同的资源消耗适应于可用容量的同时，还要兼顾资源以满足不同的等待时间目标。我们与当地组织合作，开始研究安排门诊诊所的新患者和随访访视的挑战-新患者的等待时间目标和随访时间窗口，以及患者定期接受多次访视的家庭医疗保健访视的挑战。虽然这些应用程序形成了我们研究的测试场景，但我主要关心的是解决过去工作中固有的一些局限性。我们在解决调度问题的主要方法是近似动态规划（ADP）的调度问题是连续的决策问题，任何现实的设置运行到灾难的维度，因此需要一个近似的方法。在ADP中，我们重点讨论了线性规划方法的主要局限性-对线性架构近似形式的限制以及将MDP转换为线性规划时消除可变性的事实。在某些情况下，忽略可变性是好的，因为无限的地平线意味着有时间达到预期。我们已经证明，当唯一关心的是一天结束时的加班时，假设确定性的服务时间工作得相当好。这个应用程序的一部分将这项工作扩展到了一天中还关注空闲时间和等待时间的场景。在开头所述的两种情况下，经常变化的是每个病人的就诊次数。依赖预期的访问次数实际上可能会导致不必要的拥堵时间。因此，本提案的一个长期目标是探索鲁棒优化的应用，以帮助确定ADP中的最佳近似。由于ADP的LP方法将MDP转换为线性规划，因此可以合理地应用鲁棒优化。在这方面已经做了一些工作，表明这可能是一个有希望的方向。 第二个长期目标是将神经网络应用于开发能够近似复杂值函数但仍然保持线性的值函数近似。我们已经做了一些工作，使用非线性近似架构，表现出提高性能的线性近似，但在成本显着更高的计算挑战。通过机器学习，有可能捕获一些非线性，同时仍然能够使用LP方法，从而保持LP方法的计算效率，同时提高其捕获额外复杂性的能力。