Novel Algorithms to Approximate the Future Consequence of Sequential Decisions

近似连续决策的未来后果的新算法

• 批准号: RGPIN-2017-04877
• 负责人: SabouriBaghAbbas, Alireza
• 金额: $ 2.91万
• 依托单位: University of Calgary
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2022
• 资助国家: 加拿大
• 起止时间: 2022-01-01 至 2023-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=755185
• 关键词: Novel; Algorithms; Approximate; Future; Consequence

Many complex problems arising in business, health care, and transportation can be modelled as sequential decision making problems under uncertainty, meaning that a decision maker has to make decisions periodically while some random events unfold over time. For instance, an airline dynamically changes the fare for different flights over a network of cities without knowing the actual future demand, trying to maximize its revenue while managing the risk of unsold seats. These problems can be conveniently modelled in the form of dynamic programs, a method that finds the best decision by maximizing the sum of immediate reward and the expected future reward. Unfortunately, for many practical problems, the number of future scenarios that one should consider in order to calculate the expected future reward function is exponentially large, making exact calculation of this function intractable. In order to overcome this issue, approximate dynamic programming (ADP) methods have been developed to find an approximate optimal solution. A cornerstone of many ADP algorithms is defining a set of basis functions (or an approximation architecture) for approximating the future consequence of present decisions (the expected future reward function). Currently, the choice of basis functions requires prior expert knowledge about the problem, and is usually considered as more of an art than a science. My research program aims to develop, study, and apply novel algorithms that automate generation of basis functions by efficiently selecting a subset of functions from a large pool of potential basis functions, and updating this set as more information becomes known about the problem. The benefit of such algorithms is twofold: first, it reduces the burden to come up with a well-informed set of basis functions that requires significant prior knowledge about the problem; second, since many potential candidates are considered for basis functions, it is expected that the quality of the approximation is improved. My short-term objective includes evaluating the performance of the proposed algorithms in a variety of application areas, such as perishable inventory management, patient scheduling, and revenue management.ADP is a general method that is commonly used for solving many different problems in a variety of applications. As the quality of the policies generated by these algorithms is dependent on the quality of the basis functions chosen, it would be of great interest, both theoretically and practically, if the process of generating and selecting basis functions can be automated. Therefore, even a small improvement achieved by the findings of my research would have significant practical implications in multiple application areas.

在业务，医疗保健和运输中产生的许多复杂问题可以建模为在不确定性下的连续决策问题，这意味着决策者必须定期做出决策，而某些随机事件随着时间的推移而不断发展。例如，一家航空公司在不知道实际未来需求的情况下动态改变了不同航班的票价，试图最大化其收入，同时管理未售座位的风险。这些问题可以方便地以动态程序的形式进行建模，该方法通过最大化即时奖励和预期的未来奖励来找到最佳决定。不幸的是，对于许多实际问题，为了计算预期的未来奖励函数，应考虑的未来情况的数量成倍地大大，从而确切地计算了此功能可靠的。为了克服此问题，已经开发了近似动态编程（ADP）方法来找到近似的最佳解决方案。许多ADP算法的基石正在定义一组基础函数（或近似结构），以近似目前的决策（预期的未来奖励函数）。当前，基础功能的选择需要先前关于该问题的专家知识，通常被认为是艺术而不是科学。我的研究计划旨在开发，研究和应用新颖的算法，通过有效从大量潜在基础函数中选择一个功能的子集来使基础功能的生成自动化，并随着更多信息而更新该集合。这种算法的好处是双重的：首先，它减少了提出一组知名的基础功能的负担，这些功能需要有关该问题的重要先验知识；其次，由于考虑了许多潜在候选者的基础功能，因此预计近似的质量会提高。我的短期目标包括评估拟议算法在各种应用领域的性能，例如可腐烂的库存管理，患者调度和收入管理。ADP是一种通用方法，通常用于解决各种应用中的许多不同问题。由于这些算法产生的策略的质量取决于所选择的基本函数的质量，因此，如果可以自动化生成和选择基础函数的过程，则在理论上和实际上都非常感兴趣。因此，即使我的研究发现也有一个很小的改进，在多个应用领域都会产生重大的实际含义。