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.