McGill大学等最新《不确定性决策下的上下文优化方法》综述

近来，在运筹学（OR）和机器学习（ML）领域，将预测算法和优化技术结合起来解决不确定性下的决策问题，引发了极大的兴趣。这促使上下文优化领域的兴起，在这个领域下，人们开发了数据驱动的程序，为决策者提供行动建议，以最大限度地利用最新更新的信息。在OR和ML的文献中，以各种不同的名称提出了大量的模型和方法，包括数据驱动优化，规范优化，预测性随机规划，策略优化，（智能）预测/评估-然后优化，决策为中心的学习，（基于任务的）端到端学习/预测/优化等。本综述文章聚焦于单阶段和两阶段随机规划问题，识别了从数据中学习策略的三个主要框架，并讨论了它们的优势和局限性。我们用统一的符号和术语介绍现有的模型和方法，并根据识别的三个主要框架对它们进行分类。我们通过这项调查的目的是加强对这一活跃研究领域的一般理解，并激发在整合机器学习和随机规划方面进行更多的理论和算法进步。

本文综述了单阶段和两阶段上下文优化的文献。在上下文优化中，决策者面临着一个有不确定性的决策问题，其中影响目标和约束的不确定参数的分布是未知的，尽管可以利用相关的辅助信息（协变量或特征）。在很多不同的领域，辅助信息在推断不确定参数的相关统计数据以及在决策制定中的作用是显而易见的。例如，天气和一天中的时间可以帮助解决关于道路网络拥堵的不确定性，并有助于找到穿越城市的最短路径。在投资组合优化中，股票收益可能依赖于历史价格和在Twitter上发布的情绪（Xu和Cohen，2018）。利用这些信息可以让决策者建立一个风险较低的投资组合。同样，面临夏季产品需求不确定性的零售商可以根据预测的天气情况推断需求是低还是高（Martínez-de Albeniz和Belkaid，2021）。

传统的随机优化模型忽略了上下文信息，并使用不确定参数的无条件分布来做出决策（Birge和Louveaux，2011）。这样的决策可能是次优的（Ban和Rudin，2019），在某些情况下，甚至有可能是不可行的（Rahimian和Pagnoncelli，2022）。数据的可用性和巨大的计算能力，结合机器学习（ML）和优化技术的进步，导致了向上下文优化（Mišić和Perakis，2020）的范式转变。使用辅助信息进行规定要求一个将观察到的上下文映射到行动的决策规则。我们确定了学习此映射的三种不同范式。

决策规则优化：这种方法在Ban和Rudin（2019）的文章中被介绍给运营研究社区，以“大数据”为名，尽管在强化学习中以策略梯度方法的名称已经是一种类似的常见做法（参见Sutton等人（1999）及其后的文献）。它包括使用参数化映射作为决策规则，并确定基于可用数据获得最佳经验性能的参数。决策规则可以形成为协变量的特征函数的线性组合，甚至可以使用深度神经网络（DNN）。当可用数据有限时，可能还需要某种形式的正则化。

序列学习和优化（SLO）：Bertsimas和Kallus（2020）似乎是首先将这种两阶段过程正式化的人（也称为预测/估计-然后优化或规定优化/随机规划），首先使用训练过的模型预测给定协变量的不确定参数的条件分布，然后解决相关的条件随机优化（CSO）问题以获得最优行动。通过在训练时使用适当的正则化或通过调整CSO问题的表述，可以使该过程更加稳健，以减少由模型过拟合或错误规范引起的决策后失望（Smith和Winkler，2006）。

集成学习和优化（ILO）：出于确定最佳决策规则的目的，在SLO中，人们可能会质疑在更关心所规定行动的质量时，高精度预测器的必要性。这个想法激发了一种集成的学习和优化版本，该版本搜索指导CSO问题朝向最佳性能行动的预测模型。ILO范式最早出现在Bengio（1997）中，并且最近在关于智能预测-然后优化，决策为中心的学习以及（基于任务的）端到端学习/预测/优化的活跃文献流中复苏（Donti等人，2017，Stratigakos等人，2022，Wahdany等人，2023）。

本文的大纲如下。第2节严格定义了从数据到决策的学习映射的三个框架：决策规则优化、SLO和ILO。第3节回顾了使用线性和非线性决策规则的决策规则优化的文献。第4节关注SLO，包括导致健壮决策的模型，而第5节描述了基于ILO框架的模型及用于训练它们的算法。第6节从理论和应用的角度提供了未来研究方向的概述。我们注意到，文献中还有其他与我们的调查互补的调查和教程。Mišić和Perakis（2020）调查了SLO框架在供应链、收入管理和医疗保健的运营管理问题中的应用。Kotary等人（2021）提供了一份全面的文献调研，提出使用ML方法加速解决受约束的优化模型（另请参见Bengio等人，2021）。它还回顾了一些应用于“基于期望值的模型”的较早的ILO文献（参见定义1）。Qi和Shen（2022）是一篇主要关注将ILO应用于基于期望值的模型的教程，对更一般的方法的讨论非常有限。它总结了最流行的方法及其一些理论保证。相比之下，我们对ILO的调查超出了基于期望值的决策模型，并通过将上下文决策问题视为CSO问题，更好地反映了更现代的文献，提供了这个快速发展的研究领域的全面概述。我们建立了最小化遗憾（Elmachtoub和Grigas，2022）、（基于任务的）端到端学习（Donti等人，2017）和基于模仿的模型（Kong等人，2022）之间的联系。此外，我们创建了一个基于训练过程的分类法，用于一个通用的ILO框架，包括在设计可微代理和优化器以及基于展开和隐式微分的改进训练过程方面的最新理论和算法进展。

2. 上下文优化：概述

上下文优化范式寻求在可行集 Z ⊂ Rⁿᶻ 中作出一个决策（即，一个行动）z，以最小化具有不确定参数 y ∈ Y ∈ Rⁿʸ 的成本函数 c(z; y)。在做出决策时，不确定的参数是未知的。然而，在必须选择 z 之前，会显示与不确定参数 y 相关的一组相关特征（协变量）x ∈ X ⊆ Rⁿˣ。X 中的特征和 Y 中的不确定参数的联合分布由 P 表示。

本节介绍近年来提出的解决上下文优化问题的主要流程。尽管这些流程都包含一个学习组件，但它们在具体结构和训练过程方面有很大的不同。总的来说，当处理上下文优化时，决策者需要做出几个设计选择：(i) 流程的架构，即它是否包含单一的预测组件，或者是结合学习和优化，(ii) 预测模型的类别（例如，线性、神经网络或随机森林）及其超参数，(iii) 在训练期间使用的损失函数类型，即是最小化估计误差还是策略的下游成本，这定义了一种方法是否属于顺序或集成范式。每个设计选择都有其自己的归纳偏见，并可能暗示特定的方法论挑战，特别是对于ILO。一般来说，事先不清楚哪种组合的选择会带来最佳性能，因此，必须通过实验来评估流程。

3. 决策规则优化

通过解决问题（4）中的经验风险最小化（ERM）获得的决策规则，最小化任务上的策略成本，即下游优化问题。基于策略的方法在决策时特别有效率，因为只需评估估计的策略。一旦策略被训练，就不需要解决任何优化问题。我们将决策规则方法定义为使用参数化映射 πθ(x)，例如线性策略（Ban和Rudin，2019）或神经网络（Oroojlooyjadid等人，2020）。由于使用神经网络获得的策略缺乏可解释性，线性决策规则被广泛使用。

4. 序列学习和优化

在回顾基于SLO（Sequential Learning and Optimization，顺序学习和优化）的上下文优化方法时，我们区分两种设置：(i) 一种较传统的设置，其中从数据中学习条件分布并直接用于优化模型，和 (ii) 一种试图产生对模型误差规范具有鲁棒性的决策的设置。本节介绍的方法的概述见表2。

5. 集成学习和优化

正如前面讨论的，ILO是一个端到端的框架，在训练流程中包括三个组件：(i) 一个预测模型，将协变量映射到预测分布（或可能是一个点预测），(ii) 一个优化模型，以预测为输入并返回一个决策，以及 (iii) 一个基于任务的损失函数，捕捉下游的优化问题。预测模型的参数是通过最大化策略的规定性能进行训练的，即它是根据该引发策略所产生的任务损失而不是估计损失进行训练的。接下来，我们讨论几种实现ILO方法的方法。我们首先描述在ILO中使用的不同模型（第5.1节），然后介绍用于进行训练的算法。我们将算法分为四类，即使用展开的训练方法（第5.2节），隐式微分（第5.3节），可微损失函数的代理（第5.4节）和可微优化器（第5.5节）。本节介绍的方法的概述见表3。

6. 结论和未来研究方向

现在，我们总结一下在上下文优化领域进一步研究的关键方向。

约束中的不确定性。大多数上下文优化的研究假设约束没有不确定性。如果约束也是不确定的，忽略协变量信息的SAA解可能不可行（Rahimian和Pagnoncelli，2022）。Bertsimas和Kallus（2020）强调了在约束的条件下使用ERM（经验风险最小化）的挑战。Rahimian和Pagnoncelli（2022）解决了一个条件概率约束问题，以高概率确保解在特征的条件分布下保持可行。尽管他们没有专注于上下文优化，但可以在约束学习（Fajemisin等人，2023）和反向优化（Chan等人，2021）的文献中找到有趣的联系。

风险规避。在风险厌恶的情况下，对于研究上下文优化问题越来越感兴趣。具体来说，可以考虑将（1）中的风险中性期望替换为风险度量，如风险价值（value-at-risk）。通过这样做，可以期望在很高的概率下，决策者的损失低于特定阈值。可以使用一个不确定性集合来表示这样的风险度量，该集合代表可能在未来发生的所有可能结果。所得到的不确定性集合应该经过谨慎选择。它应该捕捉到最相关的场景，以平衡避免风险和获取回报之间的权衡。

工具箱和基准测试。最近提出了几个工具箱和软件包用于训练决策流程。Agrawal等人（2019）提供了CvxpyLayer库，其中包括凸优化问题的一个子类作为PyTorch、TensorFlow和JAX中自动微分库中的可微分层。用于端到端学习的不可微分非线性优化问题的其他库包括higher（Grefenstette等人，2019）、JAXopt（Blondel等人，2022）、TorchOpt（Ren等人，2022）和Theseus（Pineda等人，2022）。Tang和Khalil（2022）介绍了PyEPO，这是一个用于线性不确定参数的ILO问题的Python开源软件包。他们实现了各种现有方法，例如SPO+、DBB、DPO和FYL。他们还包括新的基准测试和全面的实验，突出了集成学习的优势。Dalle等人（2022）提供了类似的工具用于Julia中的组合问题。在固定模拟设置下对现有方法进行比较的研究较少，特别是在真实数据方面。Buttler等人（2022）在零售和食品行业的四个数据集上对选定方法进行了元分析，对一个无约束的新闻供应商问题进行了比较。他们强调在这四个数据集上没有一种方法明显优于其他方法。内源性不确定性。虽然在研究决策影响不确定参数的问题上取得了一些进展（Basciftci等人，2021），但涉及协变量的决策依赖不确定性的文献较少（Bertsimas和Kallus，2020；Bertsimas和Koduri，2022）。一个例子是设施选址问题，其中一旦设施位于某个区域，需求就会发生变化，或者一个价格设置的新闻供应商问题，其需求取决于价格（Liu和Zhang，2023）。在这些问题中，需求和价格之间的因果关系是未知的。可以与异质处理效应的文献建立有趣的联系，例如Wager和Athey（2018），他们引入因果森林来估计处理效应，并提供了渐近一致性结果。Alley等人（2023）研究了一个价格设置问题，并提供了一种新的损失函数，用于分离价格对需求的因果效应和由其他特征引起的条件效应。

数据隐私。另一个问题是数据可能来自多个来源并包含敏感的个人信息，因此不能直接（Doshi-Velez和Kim，2017；Kaminski，2019）例如，公民有权要求银行在贷款被拒绝的情况下提供解释。虽然可解释性在预测型机器学习应用中受到了广泛关注（Rudin，2019），但在上下文优化，即规范性上下文方面，它仍然很少被探索。可解释性要求透明的决策流程，对用户来说是可以理解的，例如基于简单模型（如决策树或规则列表）构建的决策流程。相反，通过在黑盒模型或复杂模型之上添加附加算法，可以实现解释性。Serrano等人（2022）在规范性上下文中分析了特征的重要性。他们引入了一种综合方法，通过解决一个具有整数主问题的双层规划来优化（交叉）验证准确性。为了实现解释性，Forel等人（2023）将反事实解释的概念应用于通过上下文的差异来解释给定的数据驱动决策，这使得该决策是最优的，或比给定的专家决策更合适。通过识别这些差异，可以在必要时进行校正或完善上下文信息，或者提供支持不同决策的解释性元素。

公平性。基于上下文信息做出决策时，如果上下文由受保护属性组成，可能会引发公平性问题。这在定价问题中特别得到了研究，以防止不同客户或客户群体被提出差异过大的价格（Cohen等人，2021；2022）。 ILO的有限样本保证。一个未解决的问题是针对非线性问题推导出ILO模型性能的泛化界限。

多智能体决策。在交通和运营管理问题中，多智能体的视角变得必要，不同的智能体可以访问不同的信息来源（即协变量）。在这方面，Heaton等人（2022）的一些最新工作通过隐式微分的变分不等式和JFB方法，确定了上下文博弈的纳什均衡。

昂贵的标签获取。在许多应用中，获取不确定参数和协变量向量的标签是昂贵的。例如，在个性化定价中，可以向客户发送调查问卷，以获取有关对于价格的敏感性的信息。然而，创建、发送和收集调查问卷可能会产生成本。Liu等人（2023a）开发了一种主动学习方法来获取标签以解决SPO问题，而为非线性上下文优化开发主动学习方法的更一般情况是一个有趣的未来方向。Besbes等人（2023）在新闻供应商问题中提供了有关数据质量和数量之间权衡的理论结果，从而指导决策者如何投资于数据获取策略。

多阶段上下文优化。大多数关于上下文优化的研究集中在单阶段和两阶段问题上。Ban等人（2019）和Rios等人（2015）使用回归模型的残差构建多阶段情景树，并解决多阶段条件随机优化问题。Bertsimas等人（2023）将加权的SAA模型推广到多阶段问题。Qi等人（2023）提出了一个端到端学习框架来解决实际的多阶段库存补充问题。顺序决策是一个活跃的研究领域，其中通过MLE（Rust，1988）获得MDP的转移动态和奖励函数的估计。Nikishin等人（2022）引入了一种基于模型的强化学习方法，将学习和规划相结合，优化表格型和非表格型MDP的期望回报。他们使用Bellman算子的软版本（Ziebart等人，2008）进行高效的参数学习，并展示了他们的状态-动作值函数在表格型MDP中具有较低的逼近误差。另一个有趣的研究方向是挑战上下文和不确定参数的联合分布是稳态的假设。Neghab等人（2022）研究了一个具有隐藏马尔可夫模型的新闻供应商模型，该模型描述了特征和需求的分布。最后，一个需要关注的领域是在实际应用中部署模型，解决与MDP中决策集中学习相关的计算难题，例如大规模的状态-动作对和高维策略空间（Wang等人，2023）。一个例子是在非营利组织的Mate等人（2022）中，将服务呼叫调度问题建模为一个不安定多臂赌博机（RMAB）问题，以改善母婴健康。他们将每个受益人建模为一个臂，应用聚类方法学习动态，并使用Whittle指数策略来解决RMAB问题。Wang等人（2023）使用决策集中学习来解决RMAB问题，通过进行软-前k个臂的选择来缓解选择Whittle指数策略的计算难度，这是一个最优传输问题（Xie等人，2020）。