Novel Algorithms to Approximate the Future Consequence of Sequential Decisions

商业、医疗和交通中出现的许多复杂问题可以建模为不确定情况下的连续决策问题，这意味着决策者必须定期做出决策，而一些随机事件会随着时间的推移而展开。例如，一家航空公司在不知道未来实际需求的情况下，动态改变城市网络上不同航班的票价，试图最大化收入，同时管理未售出座位的风险。这些问题可以方便地用动态规划的形式建模，动态规划是一种通过最大化当前回报和预期未来回报的总和来寻找最佳决策的方法。不幸的是，对于许多实际问题，为了计算预期的未来回报函数，人们应该考虑的未来情景的数量是指数级的，这使得准确计算这个函数变得困难。为了克服这一问题，人们发展了近似动态规划(ADP)方法来寻找近似最优解。 许多ADP算法的基石是定义一组基函数(或近似体系结构)，用于近似当前决策的未来结果(预期未来回报函数)。目前，基函数的选择需要有关问题的事先专家知识，通常被认为是一门艺术而不是一门科学。我的研究计划旨在开发、研究和应用新的算法，这些算法通过从大量潜在的基函数中有效地选择函数的子集，并随着有关问题的更多信息变得已知而更新该子集，从而自动生成基函数。这种算法的好处有两个：第一，它减少了提出一组信息充足的基函数集的负担，这些基函数集需要关于问题的大量先验知识；第二，由于许多潜在的候选基函数被考虑，预计近似的质量将得到改善。我的短期目标包括评估提出的算法在各种应用领域的性能，例如易腐烂库存管理、患者调度和收入管理。 ADP是一种通用方法，通常用于解决各种应用中的许多不同问题。由于由这些算法生成的策略的质量取决于所选择的基函数的质量，因此，如果能够自动生成和选择基函数的过程，在理论上和实践上都将是非常有意义的。因此，即使我的研究成果取得了很小的改进，也将在多个应用领域产生重大的实际意义。

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.