MSPA-MCS: Collaborative Research: Algorithms for Near-Optimal Multistage Decision-Making under Uncertainty: Online Learning from Historical Samples

摘要信息技术的最新进展使企业能够收集和维护大量关于需求、销售历史和运营其他方面的原始数据。然而，在他们的决策过程中有效和高效地使用这些数据知之甚少，这些决策过程通常可以建模为多阶段随机优化问题。在许多应用领域中，例如供应链管理和收入管理，这些都会产生复杂的问题，其中每个阶段的决策都必须在潜在随机过程的未来演变的不确定性下做出。解决这些问题的传统方法假设不确定性是通过明确指定的先验已知概率分布来定义的；了解这些分布对于开发相应的优化算法至关重要。然而，在大多数实际情况下，确切的分布是未知的，只有历史数据可用。本研究项目旨在为这些模型开发一种通用的基于采样的算法框架，与传统方法不同，它使用原始历史数据作为样本来源。首先，我们计划开发基于抽样的算法方法来近似解决复杂的随机动态规划公式，这是用于这些问题的主要范式。其次，我们将重点放在同时结合优化和学习的基于采样的模型算法上。这两个研究重点之间的一个共同主题，也是我们研究项目的一个中心特征，是对我们算法性能的明确定量分析的发展，这些算法提供了保证所需的样本量，以确保与真正的潜在概率分布的最优解相关的特定误差范围。想想亚马逊这样的公司，它为美国各地的顾客提供数百万种不同的商品。显然，对于公司来说，拥有客户想要的库存是很重要的，因为如果一件商品缺货，那么客户可能会从其他地方购买该商品。另一方面，为不需要的物品维持额外库存的缺点是，在获取这些物品时占用资金，在储存这些物品时占用大量资源，而且由于易腐烂和过时的风险，情况进一步恶化。如果一个人有一个可以预测未来的水晶球，那么公司就可以知道它销售的每种商品每天会有多少请求，从而知道每个仓库中应该有多少库存。相反,一个可以模型未来的概率(类似于当什么天气预报员说明天有40%的机会淋浴),然后可以把这些库存水平的最优决策问题的问题可以获得平均利润最大化(或最小化平均费用),平均的概念是对用于模型的随机性我们无法准确预测未来。这个项目的目标是使用过去的历史数据作为对未来数据进行建模预测的手段，然后设计算法，根据这种近似产生可证明的接近最优决策。在面对不确定性时，这种类型的决策出现在广泛的应用领域，从为一组航班销售不同类别的机票到制造依赖于重叠组件集的一套产品。这个项目的重点是有多个决策阶段的设置，这些决策阶段必须面对未来需求预测的不断发展的观点。其目的是提供工具，使这些决策自动化，并保证快速产生可靠的解决方案。

Collaborative Research: Algorithms for Near-Optimal Multistage Decision-Making under Uncertainty: Online Learning from Historical SamplesAbstractRecent advances in information technologies enable firms to collect and maintain huge amounts of raw data regarding demand, sales history and other aspects of their operations. However, little is known about using this data effectively and efficiently within their decision-making processes, which can often be modeled as multi-stage stochastic optimization problems. In many application domains, such as supply chain management and revenue management, these give rise to complex problems, where the decision in each stage must be made under uncertainty about the future evolution of an underlying stochastic process. Traditional approaches to these problems assume that the uncertainty is defined through explicitly specified probability distributions that are known a priori; the knowledge of these distributions is crucial to the development of the corresponding optimization algorithms. However, in most practical situations the exact distributions are not known, and only historical data is available. This research project aims to develop a general-purpose sampling-based algorithmic framework for these models that, unlike traditional approaches, uses the raw historical data as the source of samples. First, we plan to develop sampling-based algorithmic approaches to approximately solve complex stochastic dynamic programming formulations, the dominant paradigm used for these problems. Second, we focus on sampling-based algorithms for models that combine optimization and learning simultaneously. A common theme between these two research thrusts, and a central feature of our research project, is the development of explicit quantitative analysis of the performance of our algorithms that provide guarantees on the sample-size needed to assure a specified error bound with respect to optimal solution for the true underlying probability distribution.Consider a firm like Amazon that provides millions of different items to customers throughout the US. Clearly, it is important for the company to have the inventory that its customers want, since if an item is out of stock, then the customer is likely to purchase the item from elsewhere. On the other hand, maintaining extra inventory for undesired items has the disadvantage of tying up capital in obtaining them, using significant resources in warehousing this supply, which is further compounded by the risk of perishability and obsolesce. If one had a crystal ball with which one could predict the future, then the company could know how many requests there will be, day by day, for each of the items it sells, and therefore know how much of what should be on hand in each of its warehouses. Instead, one can model the future probabilistically (similar to what a weather forecaster does when saying that there is a 40% chance of showers tomorrow), and then one can cast the problem of making the optimal decisions for these inventory levels as a problem of maximizing the average profit that can be obtained (or minimizing the average costs incurred), where the notion of average is with respect to the randomness used to model our inability to exactly predict the future. This project has the goal of using past historical data as a means for modeling the predictions for future data, and then designing algorithms that produce provably near-optimal decisions based on this approximation. This type of decision-making in the face of uncertainty arises in a wide range of application domains, from selling different classes of airlinetickets for a portfolio of flight legs to manufacturing a suite of products that rely on overlapping sets of components. This project focuses on settings in which there are multiple stages of decision-making that must be made in the face of an evolving view of the predictions of futurerequirements. The aim is to provide tools to automate such decision-making with algorithms that are guaranteed to quickly produce reliable solutions.