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

MSPA-MCS：协作研究：不确定性下近乎最优的多阶段决策算法：历史样本在线学习

• 批准号: 0732175
• 负责人: Retsef Levi
• 金额: $ 17.23万
• 依托单位: Massachusetts Institute of Technology
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2007
• 资助国家: 美国
• 起止时间: 2007-09-01 至 2010-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0732175&HistoricalAwards=false
• 关键词: MSPA; MCS; Collaborative; Research; Algorithms

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.

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