数字技术的出现改变了航空、在线零售和互联网广告等商业领域的决策方式。如今，需要在高度不确定和快速变化的环境中反复做出实时决策。此外，组织的资源通常有限，需要在决策之间进行有效分配。这类问题被称为资源受限的在线分配问题，应用比比皆是。一些示例包括：
预算约束下的竞价：广告商越来越多地使用基于拍卖的市场（例如搜索引擎和广告交易平台）购买广告位。典型的广告商可以在一个月内参与大量拍卖。由于这些市场的供应不确定，广告商会设定预算来控制其总支出。因此，广告商需要确定如何在限制总支出和最大化转化的同时以最佳方式进行竞价。
动态广告分配：发布商可以通过与广告商签订协议保证一定数量的展示量或在公开市场上拍卖广告位来将其网站货币化。要做出这一选择，发布商需要实时权衡在公开市场上出售广告位的短期收入和向预订广告提供优质广告位的长期利益。
航空收入管理：飞机座位数量有限，需要在航班起飞前尽可能地填满座位。但航班需求会随着时间而变化，航空公司希望将机票卖给愿意支付最高价格的客户。因此，航空公司越来越多地采用复杂的自动化系统来管理机票的定价和可用性。
库存有限的情况下的个性化零售：在线零售商可以使用实时数据为到访的顾客提供个性化产品。由于产品库存有限且无法轻松补货，零售商需要动态决定提供哪些产品以及以什么价格提供，以在满足库存限制的同时实现收入最大化。
这些问题的共同特点是存在资源约束（在上述例子中分别为预算、合同义务、席位或库存），并且需要在不确定的环境中做出动态决策。资源约束具有挑战性，因为它们将决策与时间联系起来——例如，在竞价问题中，早期出价过高可能会导致广告商没有预算，从而错失以后的机会。相反，出价过于保守可能会导致转化次数或点击次数较少。
互联网广告市场中广告商和发布商面临的两个核心资源配置问题。
在本文中，我们将讨论最先进的算法，这些算法可以帮助在动态、资源受限的环境中实现目标最大化。特别是，我们最近开发了一类用于在线分配问题的新型算法，称为双镜像下降，这种算法简单、稳健且灵活。我们的论文发表在《运筹学》、《ICML'20》和《ICML'21》上，我们正在持续努力继续推进这一领域的发展。与现有方法相比，双镜像下降速度更快，因为它不需要解决辅助优化问题；更灵活，因为它只需进行最少的修改就可以处理不同部门的许多应用程序；更稳健，因为它在不同环境下都具有出色的性能。
在线分配问题
在线分配问题中，决策者拥有的总资源量 ( B ) 是有限的，并且会随时间 ( T )收到一定数量的请求。在任意时间点 ( t )，决策者都会收到奖励函数 ( f t ) 和资源消耗函数 ( b t )，并采取行动 ( x t )。奖励和资源消耗函数会随时间变化，目标是在资源约束内最大化总奖励。如果所有请求都是预先知道的，则可以通过解决离线优化问题来获得最佳分配，该问题旨在确定如何在资源约束1内随时间最大化奖励函数。
最优离线分配在实践中无法实现，因为它需要知道未来的请求。然而，这对于确定在线分配问题的目标仍然有用：在不知道未来请求的情况下，设计一种性能尽可能接近最优的算法。
利用双镜下降实现多个领域的最佳效果
处理资源限制的一个简单但有效的方法是引入资源的“价格”，这样在做决策时就可以考虑消耗资源的机会成本。例如，今天卖掉一张飞机座位意味着明天就卖不出去。这些价格可用作算法的内部核算系统。它们的作用是协调不同时刻的决策，并允许将具有资源限制的复杂问题分解为更简单的子问题：每个时间段一个，没有资源限制。例如，在竞价问题中，价格反映了广告商消耗一个单位预算的机会成本，并允许广告商将每次拍卖作为独立的竞价问题来处理。
这将在线分配问题重新定义为资源定价问题，以便做出最佳决策。我们算法的关键创新是使用机器学习以在线方式预测最佳价格：我们使用镜像下降法动态选择价格，这是一种用于训练机器学习预测模型的流行优化算法。由于资源价格在优化领域被称为“对偶变量”，因此我们将结果算法称为对偶镜像下降法。
该算法按顺序工作，假设一段时间内的均匀资源消耗是最佳的，并在每次操作后更新对偶变量。它从某个时刻 (t) 开始，采取一个操作 ( xt )，使奖励减去消耗资源的机会成本 (如下方顶部灰色框所示) 最大化。如果有足够的资源可用，则执行该操作 (例如，出价多少或显示哪个广告)。然后，该算法计算资源消耗中的误差 ( gt )，即一段时间内的均匀消耗与实际资源消耗之间的差值 (下面第三个灰色框中)。根据误差，使用镜像下降法计算下一个时间段的新对偶变量，然后通知下一个操作。镜像下降法力求使误差尽可能接近零，从而提高对偶变量估计的准确性，从而使得资源随时间均匀消耗。虽然均匀资源消耗的假设可能令人惊讶，但它有助于避免错过好机会，并且通常与商业目标一致，因此是有效的。镜像下降还允许多种更新规则；更多详细信息请参阅论文。
双镜像下降算法概述。
根据设计，双镜像下降具有自我修正功能，可防止过早耗尽资源或等待太长时间才消耗资源而错失良机。当请求消耗的资源多于或少于目标时，相应的对偶变量会增加或减少。当资源定价更高或更低时，未来的行动将选择更保守或更积极地消耗资源。
该算法易于实现，速度快，在不同环境下均具有出色的性能。以下是我们的算法的一些显著特点：
现有方法需要定期使用过去数据解决大型辅助优化问题。相比之下，该算法不需要解决任何辅助优化问题，并且更新对偶变量的规则非常简单，在许多情况下可以以线性时间复杂度运行。因此，它对于许多需要快速决策的实时应用很有吸引力。
对问题结构的要求极低。这种灵活性使双镜像下降能够以最小的修改处理不同部门的许多应用。此外，我们的算法非常灵活，因为它们可以适应不同的目标、约束或正则化器。通过加入正则化器，决策者可以将经济效率以外的重要目标纳入其中，例如公平性。
现有的在线分配问题算法是针对对抗性或随机输入数据量身定制的。对抗性输入的算法是鲁棒的，因为它们几乎不对数据结构做任何假设，但反过来，它们获得的性能保证在实践中过于悲观。另一方面，随机输入的算法通过利用数据中的统计模式享有更好的性能保证，但在模型指定错误时性能会很差。然而，双镜像下降在随机和对抗性输入模型中都达到了接近最优的性能，同时忽略了输入模型的结构。与现有的同时近似算法相比，我们的方法更通用，适用于广泛的问题，并且不需要预测。下面是我们的算法与其他最先进方法的比较。结果基于广告分配问题的合成数据。
双镜像下降法、基于训练的方法和对抗法相对于最佳离线解决方案的性能。值越低，表示性能越接近最佳离线分配。结果是使用基于广告分配问题的公开数据的综合实验生成的。
结论
在这篇文章中，我们介绍了双镜像下降法，这是一种用于解决在线分配问题的算法，简单、稳健且灵活。特别值得注意的是，经过在线分配算法的长期研究，双镜像下降法提供了一种分析更广泛算法的方法，与以前的技术相比，其稳健性优先级更高。双镜像下降法在多个商业领域有着广泛的应用，并已在 Google 中长期使用，以帮助广告商通过更好的算法决策来获取更多价值。我们还在探索与镜像下降法及其与PI 控制器的连接相关的进一步工作。
致谢
我们要感谢我们的合著者 Haihao Lu 和 Balu Sivan 以及 Kshipra Bhawalkar 的大力支持和贡献。我们还要感谢广告质量团队和市场算法研究的合作者。
评论