摘要

我们研究了随机输入模型下的在线线性规划 (OLP) 问题，其中约束矩阵的列以及目标函数中的相应系数是 i.i.d. 来自未知分布，并随着时间的推移依次显示。 几乎现有的在线算法是基于学习线性程序 (LP) 的对偶最优解/价格，他们的分析集中在总目标值和求解约束矩阵和目标中所有系数均为非负的打包 LP。 然而，两个主要的开放性问题是：（i）在现有算法中学习的 LP 最优对偶价格集合是否收敛到“离线”LP 的集合，以及（ii）结果是否可以扩展到一般 LP 问题，其中系数 可以是正面的也可以是负面的。 我们通过在一般 LP 问题的中等正则条件下建立对偶价格的收敛结果来解决这两个问题。 具体来说，我们确定了对偶问题的等效形式，它将对偶 LP 与样本平均近似值与随机程序相关联。 此外，我们提出了一种新型的 OLP 算法，即动作历史依赖学习算法，它通过考虑过去的输入数据以及过去的决策/动作来提高以前的算法性能。 我们为所提出的算法推导出了 O(log n log log n) 遗憾界限（在局部强凸性和 √ 平滑条件下），与典型的双价格学习算法的 O(n) 界限相反，其中 n 是 决策变量。 数值实验证明了所提出的算法和动作历史相关设计的有效性。

1 引言

随着信息技术的进步和新的在线市场的出现，顺序决策已经成为一个越来越有吸引力的研究课题。 作为广泛出现在运筹学、管理科学和人工智能领域的一个关键概念，顺序决策涉及在动态环境中寻找最优决策/策略的问题，其中系统的知识以数据的形式和 随着时间的推移，样本、积累和演变。 在本文中，我们研究了在顺序设置中求解线性规划的问题，通常称为在线线性规划 (OLP)（参见例如 (Agrawal et al., 2014)）。 OLP 的制定已广泛应用于在线 Adwords/广告 (Mehta et al., 2005)、在线拍卖市场 (Buchbinder et al., 2007)、资源分配 (Asadpour et al., 2019)、包装和 路由（Buchbinder 和 Naor，2009 年）和收入管理（Talluri 和 Van Ryzin，2006 年）。 这些应用程序上下文中的一个共同特征是客户、订单或查询以前向顺序方式到达，并且需要即时做出决策，而在决策/行动点没有可用的未来数据/信息。
OLP问题以标准线性规划为基础形式（具有n个决策变量和m个约束），而约束矩阵与线性目标函数中的相应系数逐列显示。 在本文中，我们考虑了标准随机输入模型（参见（Goel 和 Mehta，2008 年；Devanur 等人，2019 年）），其中由约束矩阵的列和相应的目标系数表示的阶数是独立采样的 并且同样来自未知分布P。在每个时间戳，决策变量的值需要根据过去的观察确定，并且以后不能更改。 目标是最小化以这种在线方式解决的目标值与完全了解线性程序数据的“离线”最佳目标值之间的差距（正式定义为遗憾）。
由于OLP的广泛应用，在过去的十年中，OLP的算法和研究成果非常多。 几乎所有现有的在线算法都基于学习 LP 对偶最优解/价格，并且他们对 OLP 的分析集中在总目标值和求解约束矩阵和目标中的所有系数均为非负的打包 LP。 文献中的两个主要开放问题是：（1）OLP 的 LP 最优对偶价格集合是否收敛到离线 LP 的价格，以及（2）结果能否扩展到系数可以为正的一般 LP 问题 或否定的。 作为我们结果的一部分，我们在本文中解决了这两个问题。
此外，我们提出了一种新型的OLP算法，并开发了分析OLP算法遗憾的工具。 我们的主要成果和主要贡献总结如下。
1.1 主要结果和主要贡献
在线线性程序的双重收敛。 我们在第 3 节中建立了一系列线性程序的对偶最优解的收敛结果。我们首先推导出对偶 LP 的等价形式，发现在随机输入模型下采样的对偶 LP 可以看作是样本平均值 约束随机规划问题的近似 (SAA) (Kleywegt et al., 2002; Shapiro et al., 2009)。 随机程序由 LP 约束容量和生成 LP 输入的分布 P 定义。 我们的主要结果表明，在适度的正则性条件下，随着（原始 LP）决策的数量趋于无穷大，采样对偶 LP 的最优解将收敛到随机程序的最优解。 具体来说，我们在随机输入模型下 √ 变量 m √ 建立两个解之间的 L 2 距离为 Õ n m 是约束的数量，n 是决策变量的数量。 此外，收敛结果不仅适用于在线打包 LP，也适用于输入数据系数可以为正或负的一般 LP。
动作历史相关的学习算法。 我们在 4.5 节开发了一种新型的 OLP 算法——动作历史依赖学习算法。 这种新算法是一种基于对偶的算法（如 (Devanur et al., 2011; Agrawal et al., 2014; Gupta and Molinaro, 2014) 等中的算法），它利用了我们对采样收敛的结果 双最优解。 大多数现有 OLP 算法设计中的一种常见模式是，在时间 t 的决策变量的选择仅取决于过去的输入数据，即约束中的系数和揭示的目标函数，而不是已经做出的决策（ 直到时间 t-1)。 我们的新动作历史相关算法考虑了过去的输入数据和过去的决策变量选择。 在网络收益管理、在线拍卖等一些具体问题中也考虑了类似的思路。 与现有的OLP算法相比，我们的新算法更加意识到过去决策所消耗的约束/资源，因此可以以更加动态、闭环和非平稳的方式做出决策。 我们在理论和数值实验中都证明，与没有这种机制的现有 OLP 算法相比，这种依赖于动作历史的机制显着提高了在线性能。
OLP 的遗憾界限。 我们分析了预期在线目标值和“离线”最佳目标值之间的最坏情况差距（遗憾）。 具体来说，我们研究了渐近状态下的遗憾，其中约束的数量 m 固定为常数，LP 右侧输入与决策变量的数量 n 成线性比例。 据我们所知，这是通用OLP公式中的第一个遗憾分析结果。 我们为所提出的依赖于动作历史的学习算法推导出了一个 O(log n log log n) 遗憾上限（在局部强凸性和平滑度假设下），其数量级与可实现的最佳下限 Ω( log n) 即使对底层分布有确切的了解（Bray，2019）。 我们的遗憾分析为受约束的在线优化问题提供了算法洞察：一个成功的算法应该能够很好地控制绑定约束（资源）消耗——不要过早耗尽这些约束或最后剩余太多，这是通常被忽略的一个方面 OLP文献中典型的双重价格学习算法。 该分析将网络收益管理文献中的发现（例如，（Jasin 和 Kumar，2012 年；Jasin，2015 年）中的自适应资源控制）扩展到更一般的非参数环境。 此外，结果和方法（如定理 2）可能适用于其他在线学习和在线决策问题。
1.2 文献回顾
在线优化/学习/决策问题已经在运筹学和理论计算机科学界进行了长期研究。 我们向读者推荐论文（Borodin 和 El-Yaniv，2005；Buchbinder 等人，2009；Hazan 等人，2016），以了解该主题和最新发展的一般概述。 OLP 问题主要在两种模型下进行研究：随机输入模型（Goel 和 Mehta，2008；Devanur 等，2019）和随机排列模型（Molinaro 和 Ravi，2013；Agrawal 等，2014；Gupta 和 莫利纳罗，2014）。 在本文中，我们考虑随机输入模型（也称为随机输入模型），其中约束矩阵的列生成 i.i.d。 来自未知分布 P。相比之下，随机排列模型假设列以随机顺序到达，并且到达顺序均匀分布在所有排列上。 从技术上讲，i.i.d. 随机输入模型中的假设比随机置换假设更强，因为随机输入模型可以被视为随机置换模型的特例（（Mehta，2013））。 实际上，随机输入模型可以从在线广告问题、航班和酒店预订中的网络收入管理问题或在线拍卖问题中得到激发。 在这些应用环境中，约束矩阵中的每一列与目标函数中的相应系数一起代表一个单独的订单/投标/查询。 从这个意义上说，随机输入模型可以解释为跨不同客户的独立假设。
我们的论文与现有的 OLP 文献的不同之处在于右侧假设，即约束容量。 一系列 OLP 论文（Devanur 和 Hayes，2009；Molinaro 和 Ravi，2013；Agrawal 等，2014；Kesselheim 等，2014；Gupta 和 Molinaro，2014）研究了算法竞争力和约束之间的权衡 容量。
他们研究了 LP 右侧的充分必要条件以及存在 (1 - ) 竞争 OLP 算法的约束数量 m。 具体来说，Agrawal 等人。 (2014) 建立了构建最坏情况示例的必要部分，指出右侧不应小于 Ω log 2 m 。 凯塞尔海姆等人。 （2014）； Gupta 和 Molinaro (2014) 开发了在此必要条件下实现 (1−) 竞争力的算法，从而完成了充分部分。 在本文中，我们研究了一个替代问题，当右手边随着决策变量的数量n线性增长时，该算法是否可以实现比（1-）-竞争力更好的性能。 一般来说，这种线性增长机制将使最优目标值也随着 n 线性增长。
因此，（1 - ）-竞争力性能保证可能会导致线性差距在 n 在线目标值和离线最优值之间。 因此，我们将遗憾而不是竞争力比率作为性能衡量标准，并将分析在线性增长机制下实现亚线性遗憾的三种算法。 此外，OLP 文献中的一个典型假设要求约束矩阵中的数据条目和目标是非负的。 我们没有在我们的模型中做出这个假设，因此我们的模型和分析可以捕捉到一个具有买卖订单的双面市场。
另一类研究源自收益管理文献，研究了OLP问题的参数化类型。 它对网络收益管理问题进行建模，其中异构客户按顺序到达系统，客户可以根据他们的请求和价格分为有限的多个类别。 在 OLP 语言中，约束矩阵的列与目标中的相应系数遵循良好的参数化分布，并且具有有限且已知的支持。 雷曼和王（2008）； Jasin 和 Kumar（2012 年，2013 年）； Bumpensanti 和 Wang (2018) 等人在模型参数已知的情况下研究了该问题，并讨论了根据系统当前状态动态解决确定性等价问题的重新求解技术的性能。 这一系列工作强调了在已知参数的环境中重新求解技术的有效性，并研究了所需的重新求解频率。 本着类似的精神，Jasin (2015) 分析了基于重新求解的算法在未知参数设置中的性能，而 Ferreira 等人。 （2018 年）研究了一个略有不同的基于定价的收入管理问题。 OLP 模型概括了网络收益管理问题，因为它不对分配施加任何参数结构。对于OLP问题，客户请求和价格的分布可能有无限支持（如秘书问题/Adwords问题），允许负值（如双边拍卖市场）。 相比之下，收益管理文献侧重于基础分布具有参数结构和有限支持的情况。 例如，Jasin (2015) 研究了一个未知设置，但该论文仍然假设知道分布的支持。 因此，(Jasin, 2015) 中的参数学习被简化为齐次泊松过程的简单强度估计问题，其中的算法依赖于估计和重新求解技术。 事实上，沿着这条文献线开发的算法对于更一般的 OLP 问题是失败的，因为当分布完全是非参数且未知时，没有办法首先估计分布参数，然后解决确定性等价优化问题 基于估计的参数。 因此，我们论文中开发的基于对偶的算法可以被视为将这种先估计后优化过程组合成一个步骤。 特别是，我们的动作历史相关算法在非参数设置中实现了重新求解技术的思想，我们的算法分析加强了自适应和重新求解设计（主要在收益管理文献中讨论）的有效性 更一般的在线优化上下文。
另一项研究调查了多秘书问题（(Kleinberg, 2005; Arlotto and Gurvich, 2019; Bray, 2019) 等）。 多秘书问题是OLP问题的一种特殊形式，它只有一个约束，约束矩阵中的所有系数都是一个。 Arlotto 和 Gurvich (2019) 表明，当奖励分布未知且不对分布施加额外假设 √ 时，多秘书问题的遗憾下限为 Ω(n)。 随后的工作 (Bray, 2019) 进一步指出，即使分布已知，遗憾的下限也是 Ω(log n)。 Balseiro 和 Gur (2019) 研究了一种类似的单约束但多智能体在线学习公式，其动机来自重复拍卖问题。 我们论文中的结果定位在更一般的背景下，并且与这一系列工作一致。 我们确定了一组假设，这些假设承认更一般的 OLP 问题的 Õ(log n) 遗憾上限。 我们的动作历史相关算法也可以看作是（Arlotto 和 Gurvich，2019；Balseiro 和 Gur，2019）中开发的优雅自适应算法的概括。 连同 (Bray, 2019)，我们的结果表明，即使与使用分布知识开发的最佳动态算法相比，动作历史相关算法也可以为多秘书问题实现近乎最佳的后悔性能。
OLP问题也与一般的在线优化问题有关。 与标准的在线优化问题相比，我们的 OLP 问题在两个方面是特殊的：（i）约束的存在和（ii）作为遗憾基准的动态预言。 对于带约束的在线优化的文献（Mahdavi 等，2012；Agrawal 和 Devanur，2014b；Yu 等，2017；Yuan 和 Lamperski，2018），常用的方法是采用双目标性能测量和报告 遗憾和约束违反分别。 我们通过开发一种分析可行在线算法的遗憾的机制来为这一研究方向做出贡献。 对于第二个方面，动态预言机允许不同时间步长的决策变量（在OLP中）取不同的值。 这是一个比静态预言更强大的预言（Mahdavi et al., 2012; Agrawal and Devanur, 2014b; Yu et al., 2017; Yuan and Lamperski, 2018），它要求不同时间步的决策变量采取相同的（ 静态）值。 换句话说，OLP 遗憾是根据更强的基准计算的。 这就解释了为什么 OLP 文献主要考虑随机输入模型和随机排列模型，而不是对抗性设置。

2 问题描述

在本节中，我们制定 OLP 问题并定义目标。 考虑一个通用的 LP 问题
(1)
其中 r j ∈ R，a j = (a 1j , …, a mj ) > ∈ R m ，并且 b = (b 1 , …, b m ) > ∈ R m 。 不失一般性，我们假设 i = 1, …, m 时 b i > 0。 在整篇论文中，我们使用粗体符号来表示向量/矩阵和标量的正常符号。
在在线设置中，线性程序的参数以在线方式显示，需要顺序确定决策变量的值。 具体来说，在每个时间 t，系数 (r t , a t ) 被揭示，我们需要立即确定 x t 的值。 与离线设置不同的是，在时间 t，我们没有以下系数的信息需要透露。 给定历史 H t−1 = {r j , a j , x j } t−1 j=1 ，x t 的决策可以表示为历史和当前时间段内观察到的系数的策略函数。 那是，
(2)
策略函数 π t 可以是时间相关的，我们表示策略 π = (π 1 , …, π n )。 决策变量 x t 必须符合约束
()
目标是最大化目标 P n j=1 r j x j 。
我们通过下面的实际例子来说明问题设置。 假设一家做市商同时收到买卖订单，订单按顺序到达。 在每一个时间 t，我们观察到一个新的订单，我们需要决定是接受还是拒绝这个订单。 订单是资源的买卖请求，也可以是混合请求，例如，以 1 个单位出售第一个资源，以 2 个单位购买第二个资源，总订单价格为 1 美元。 一旦我们做出决定，订单将离开系统，它要么被履行，要么被拒绝。 在这个例子中，术语 b i 可以解释为资源 i 的总可用库存，决策变量 x t 可以解释为订单的接受和拒绝。 特别是，我们不允许在流程中出现资源短缺。 我们的目标是最大化总收入。
我们假设 LP 参数 (r j , a j ) 是 i.i.d 生成的。 来自未知分布 P。我们将线性规划 (1) 的离线最优解表示为 x ∗ = (x ∗ 1 , …, x ∗ n ) > ，将离线（在线）目标值表示为 R n ∗ ( Rn)。 具体来说，
()
其中在线目标值取决于策略 π。 数量 R n * 假设完全了解实现（随机性），它也被称为在线学习和鲁棒优化文献中的后见之明。 在本文中，我们考虑了一个固定的 m 和大 n 机制，并关注在线和离线目标之间的最坏情况差距。 我们定义遗憾
()
和最坏的遗憾
()
其中 Ξ 表示满足某些规律性条件的分布族（稍后会指定）。
在本文中，当没有歧义时，我们省略了期望符号中的下标 P。
最坏情况后悔对一个分布族取最高后悔，因此当分布 P 未知时，它适合作为性能保证。 我们注意到离线最优解 Rn* 可以被解释为一个动态预言机，它允许最优决策变量在不同的时间步长取不同的值。 这是 OLP 问题和带约束的在线凸优化问题之间的重要区别（Mahdavi 等人，2012；Agrawal 和 Devanur，2014b；Yu 等人，2017；Yuan 和 Lamperski，2018）。
2.1 符号
在本文中，我们使用标准的大O 符号，其中O(·) 和Ω(·) 分别代表上限和√ 下限。 符号Õ(·) 进一步省略了对数因子，例如Õ( n) = √ O( n log n) 和Õ(log n) = O(log n log log n)。 以下列表总结了本文中使用的符号：
• m：约束数； n：决策变量的数量
• i：约束指数； j, t：决策变量的索引
• r j：目标函数中的第 j 个系数
• a j ：约束矩阵中的第 j 列
• r̄, ā：|r j | 和 ka j k 2 的上限
• P：(r j , a j ) 的分布； P ∈ Ξ：将在下一节中定义的分布族
• λ, µ：传达强凸性和平滑度含义的参数； 它们与下一节中定义的 r|a 的条件分布有关
• x ∗ = (x ∗ 1 , …, x ∗ n ) > ：离线原始最优解
• x = (x 1 , . …, x n ) > : 在线解
• p ∗ n : （随机）离线对偶最优解
• p ∗ : 随机程序 (7) 的（确定性）最优解
• R n ∗ : 离线最优目标值
• R n (π)（有时在政策明确时为 R n）：政策 π 下的在线回报/收益 • b = (b 1 , …, b m ) > ：右手边，约束能力
• d：平均约束能力，即 d = b/n ¯ d
• d 的上下界，d：N m¯ • Ω d ： d 的区域，定义为 i=1 (d, d)
• I B 和 I N : 分别由随机程序 (7) 定义的约束和非约束约束的索引集
• b t : 第 t 期结束时的剩余约束能力, t = 1, …, n • d t ：第t期末剩余的平均约束能力，即d t = b t /(n - t), t = 1, …, n − 1
• ∧：最小值运算符，y ∧ z := min{y, z} for y, z ∈ R
• ∨：最大值运算符，y ∨ z := max{ y, z} for y, z ∈ R • I(·)：指示函数； 当 E 为真时 I(E) = 1，否则 I(E) = 0

3 对偶收敛

许多​​ OLP 算法依赖于解决线性规划 (1) 的对偶问题。 然而，对对偶最优解的性质仍然缺乏理论理解。 在本节中，我们建立了OLP对偶解的收敛结果，为OLP算法的分析奠定了基础。
首先，线性规划 (1) 的对偶是
(3)
这里的决策变量是 p = (p 1 , …, p m ) > 和 y = (y 1 , …, y n ) > 。
令 (p * n , y n * ) 为对偶 LP (3) 的最优解。 从互补松弛条件，我们知道原始最优解满足
(4)
当 r j = a > j p n 时，最优解 x j 可能取非整数值。 这告诉我们，原始最优解很大程度上取决于对偶最优解 p* n 因此激发了我们对最优对偶解的研究。 通过将约束插入目标函数 (3) 可以获得对偶 LP 的等效形式：
(5)
其中 (·) + 为正部分函数，​​也称为 ReLu 函数。 优化问题 (5) 尽管不是线性程序，但具有凸目标函数。 它的优点是只涉及与最优原始解密切相关的 p。 更重要的是，目标函数（5）的第二部分中的随机和是相互独立的，因此和（归一化后）将收敛到某个确定性函数。 为了更好地说明这一点，令 d i = b i /n 并将 (5) 中的目标函数除以 n。 那么优化问题可以改写为
(6)
目标函数 (6) 中的第二项是 n i.i.d 的总和。 随机函数。
考虑以下随机程序
(7)
其中期望是关于 (r, a) 的。 在本文的其余部分，除非另有说明，否则总是对 (r, a) 进行期望。 显然，
()
对于所有 p。 这种观察将双重收敛问题转换为随机规划问题的形式。 (6) 中的函数 f n § 可以看作函数 f § 的样本平均逼近 (SAA)（参见 (Kleywegt et al., 2002; Shapiro et al., 2009)）。 具体而言，与具有 n 个决策变量的原始线性程序相关联的对偶程序是随机程序 (7) 的 n 个样本近似值。 我们分别用 p * n 和 p * 表示 n 样本逼近问题 (6) 和随机程序 (7) 的最优解。 在本节中，我们为 p * n 到 p * 的收敛提供了有限样本分析。 我们首先引入假设，然后正式建立收敛。
3.1 假设和基础
第一组假设涉及约束的有界性和线性增长。
假设 1（有界性和线性增长能力）。 我们假设 n (a) {(r j , a j )} j=1 是 i.i.d 生成的。 来自分布 P。
(b) 存在常数 r̄, ā > 0 使得 |r j | ≤ r̄ 和 ka j k 2 ≤ ā 几乎可以肯定。
¯ 对于 d, d¯ > 0, i = 1, …, m。 表示Ω d = N m (d, d)。
¯ © d i = b i /n ∈ (d, d) i=1 (d) n > m。
在整篇论文中，k · k 2 表示向量的 L 2 范数。
假设 1 (a) 表明线性规划 (1) 的参数（目标函数中的系数和约束矩阵中的列）是 i.i.d 生成的。 来自未知分布 P。向量 {(r j , a j ), j = 1, …, n} 彼此独立，但它们的分量可能相互依赖。
假设 1 (b) 要求参数是有界的。 限制参数ā和r̄仅用于分析目的，不会用于算法实现。 假设 1 © 要求 LP 约束的右手边随 n 线性增长。 这保证对于（最佳）解决方案，x j 的恒定比例可以是 1。这意味着可以完成的订单/请求的数量约为 n，从而确保了恒定的服务水平（百分比 订单满意）。
相反，如果这不是真的并且所有的请求都是采购订单（a ij > 0），那么当业务运行周期n趋于无穷时，服务水平可能会变为零。 参数 d i = b i /n 具有每个周期可用约束/资源的解释。 此外，我们要求决策变量的数量 n 大于约束的数量 m。 在讨论对偶收敛性时，对偶变量 p 的维数等于约束数量 m，原始决策变量 n 的数量可以看作是用于逼近 p * 的样本数量。 n > m 的假设将我们的注意力限制在低维设置上。
命题 1 总结了与对偶 LP (3) 和随机程序 (7) 相关的几个基本性质。 它指出 SAA 问题和随机程序中的目标函数都是凸的。 此外，这两个问题的最优解是有界的。
命题 1。在假设 1 下，我们对 f n 和 f 有以下结果（概率为 1）。
(a) 问题 (5) 的最优解集与问题 (3) 的最优解集相同。
(b) f n § 和 f § 都是凸的。
© 最优解 p ∗ n 和 p ∗ 满足
()
给定最优解的有界性，我们定义
()
其中 e ∈ R m 是一个全一向量。 我们知道 Ω p 涵盖了 (6) 和 (7) 的所有可能的最优解。
接下来，我们介绍关于分布 P 的第二组假设。这里和以后，I(·) 表示指标函数。
假设 2（非退化）。 我们假设 (a) 二阶矩矩阵 M := E (r,a)∼P [aa > ] 是正定的。 用 λ min 表示其最小特征值。
(b) 存在常数 λ 和 µ 使得如果 (r, a) ∼ P,
()
适用于任何 p ∈ Ω p 。
© 随机优化问题 (7) 的最优解 p ∗ 满足 p ∗ i = 0 当且仅当 d i − E (r,a)∼P [a i I(r > a > p ∗ )] > 0 .
假设 2 (a) 是温和的，因为矩阵 E[aa > ] 根据定义是半正定的； 只要 LP 的约束矩阵 A 始终具有满行秩，正定性就成立，这是求解线性规划的典型假设。 假设 2 (b) 表明 r|a 的累积分布函数不应增长过快或过慢。 假设 2 © 对随机程序强加了严格的互补性。 本质上，假设 2 对原始 LP 和对偶 LP 都施加了非退化条件。 它可以被视为 (Jasin and Kumar, 2012; Jasin, 2015) 中的非退化条件的概括，以及 (Devanur and Hayes, 2009; Agrawal et al., 2014) 中的一般位置条件的随机版本 .
我们注意到假设 2 的所有三个部分对于本文其余部分的分析都是至关重要的。
虽然假设 2 (a) 和 © 不一定对所有随机程序都成立，但对分布 P 的轻微扰动（例如，通过向 r j 和 a ij 添加小的随机噪声）将导致它们得到满足。 此外，我们提供了三个满足假设 2 (b) 的示例。 在示例 1 中，我们可以简单地选择 λ = α 和 µ = ᾱ，然后满足假设 2 (b)。 示例 2 和示例 3 的分析推迟到 A3 部分。
示例 1. 考虑一个多秘书问题，其中 m = 1 并且所有约束系数 a 1j = 1 对于 j = 1, …, n。 奖励 r j 是一个连续随机变量，其分布 P r 具有密度函数 f r (x) s.t。 对于 x ∈ [0, 1]，α ≤ f r (x) ≤ ᾱ。 这里 ᾱ ≥ α ≥ 0。
示例 2. 考虑 (r, a) ∼ P 使得 r = a > p * + 其中是一个连续随机变量，独立于 a 且有界支持。 此外， 的分布 P 有一个密度函数 f (x) 使得存在 ᾱ, α, c > 0 使得 f (x) ≥ α 对于 x ∈ [−c , c ] 和 f (x) ≤ ᾱ 对于所有 x。
示例 3. 考虑 (r, a) ∼ P 使得条件分布 r|a 具有密度函数 f r|a (x) 并且密度函数满足 α ≤ f r|a (x) ≤ ᾱ 对于 x ∈ [−r̄ , r̄] 与 α, ᾱ > 0 和 f r|a (x) = 0 对于 x ∈ / [−r̄, r̄]。 此外，存在 δ r > 0 使得 a > p ∗ ∈ [−r̄ + δ r , r̄ - δ r ] 几乎肯定。
根据假设 2 ©，我们定义了两个索引集
()
其中下标“B”和“N”分别是绑定和非绑定的缩写。 假设 2 © 意味着 I B ∩ I N = ∅ 和 I B ∪ I N = {1, …, m}。 在整篇论文中，OLP 问题的绑定和非绑定约束总是根据随机程序 (7) 定义。
现在，我们根据假设 2 推导出随机程序 (7) 的更多基本性质。首先，定义一个函数 h : R m × R m+1 → R，
()
和函数 φ : R m × R m+1 → R m ,
()
其中 u = (u 0 , u 1 , …, um ) > 和 p = (p 1 , …, p m ) > 。 函数 φ 是 P m 函数 h 关于 p 的部分子梯度； 特别是，当 u 0 = i=1 u i p i 时，φ(p, u) = d。 我们知道
()
我们定义
(8)
其中两个期望都是关于 u = (r, a) ∼ P。需要注意的是，在我们当前的假设下，函数 f 不一定是可微的。 正如我们将在引理 1 和命题 2 中看到的，∇f § 的定义构成函数 f 的次梯度的含义。
引理 1 表示 f § 和 f (p * ) 之间的差，具有次梯度函数 φ。 请注意，恒等式 (9) 与分布 P 无关。它的推导与 (Knight, 1998) 中的 Knight 恒等式具有相同的想法。 直观地说，引理可以看作是函数 f 的二阶泰勒展开。 恒等式右边的第一项和第二项可以解释为泰勒展开式中的一阶和二阶项。 由于原点正部分函数的不可微性，它们被伪装成这种特殊形式。
引理 1. 对于任何 p ≥ 0，我们有以下恒等式，
(9)
其中期望是关于 (r, a) ∼ P。
命题 2 将假设 2 应用于恒等式 (9)，它导致函数 f § 在 p ∗ 周围的局部属性。 我们提出这个命题的动机是从技术角度为假设 2 提供更多的直觉。 此外，该命题断言了 p * 的唯一性，这使得我们对 p * 收敛的概念定义明确。
命题 2（f § 的增长和平滑）。 在假设 1 和 2 下，对于 p ∈ Ω p ，
(10)
此外，随机程序 (7) 的最优解 p * 是唯一的。
该命题对假设 2 中的分配条件给出了技术解释。
本质上，假设对分布 P 的作用是在 p ∗ 周围施加局部强凸性和平滑性。 这比强凸性和平滑度的经典概念弱要求不等式 (10) 全局成立的凸函数。 假设 2 (b) 和命题 2 都涉及最优解 p ∗ 的局部性质。 正如我们将在后面的章节中看到的那样，f § 上的这个局部属性对于确保 pn 的快速收敛速度和 OLP 算法的锐利界限至关重要且足以确保。
我们使用符号 Ξ 来表示满足假设 1 和 2 的分布族。在本文的其余部分中，除了第 4.5 节，所有关于对偶收敛的理论结果和 OLP 算法的分析都是在假设 1 和 2 下建立的 . 在 4.5 节中，我们将展示假设 2 的一个更强大的版本，并相应地分析动作历史相关算法。
3.2 双重收敛
现在，我们讨论p n 到p * 的收敛。 首先，SAA 函数 f n § 可以表示为
()
其中 u j = (r j , a j ) 且函数 h 如前所述。 引理 2 是引理 1 的样本平均版本，它用次梯度函数 φ 表示 f n § 和 f n (p * ) 之间的差异。
引理 2. 对于任何 p ∈ R m ，我们有以下恒等式，
(11)
在下文中，我们将基于对恒等式 (11) 的分析建立 p * n 的收敛性。 这个想法是为了表明（11）的右手边集中在它的期望周围，就像在（9）的右手边一样。 以下两个命题分别分析一阶项和二阶项。
P n 命题 3 表明样本平均子梯度 n 1 j=1 φ(p ∗ , u j ) 以高概率保持接近其在 p ∗ 处评估的期望 ∇f § (8)。 命题 4 指出，二阶项——式（11）右边的积分，是由一个具有高概率的强凸二次函数统一下界的。 直观地说，分析只涉及函数 f n 在 p ∗ 附近的局部性质。 这就解释了为什么我们在假设 2 中只对函数 f 施加局部（而不是全局）条件。具体来说，假设 2 (a) 和 (b) 涉及 Hessian，而假设 2 © 涉及梯度，两者都被评估 在 p*。
命题 3. 我们有
()
对于任何 > 0、所有 n > m 和 P ∈ Ξ 都成立。
命题 3 是通过直接应用集中不等式得到的。 值得注意的是，右侧的概率界限不依赖于分布 P，并且不等式适用于任何 > 0。
从随机程序的最优性条件，我们知道 (∇f (p ∗ )) i = 0 对于 i ∈ I B 和 (∇f (p ∗ )) i > 0 对于 i ∈ I N 。 因此，该命题意味着样本平均次梯度（（11）中的一阶项）对于绑定维度集中在零附近，对于非绑定维度集中在正值附近。 如前所述，绑定和非绑定维度由随机程序 (7) 定义。
命题 4. 我们有
()
命题 4 讨论了 (11) 中的二阶项。 不等式 (12) 告诉我们，二阶项是一致的下界，具有高概率的二次函数。 证明固定 p 的不等式可以很容易地通过命题 3 中的集中论证来完成。具有挑战性的部分是证明不等式 (12) 对所有 p ∈ Ω p 均成立。 这里的想法是找到一组覆盖 Ω p 的集合，然后分别分析每个覆盖集。 我们使用与 (Huber et al., 1967) 中相同的覆盖方案，该方案最初是为了分析非标准最大似然估计量的一致性而开发的。 这种覆盖方案的优点是它提供了比传统的覆盖方案更严格的概率界限。 命题中涉及的参数取决于假设 1 和 2 中的参数：ā、r̄ 和 d 在假设 1 中指定； λ min 、 λ 和 µ 在假设 2 中指定。对于新引入的参数，q 可以看作是一个常数参数 √，N 的数量级为 m log m。 所有这些参数都不依赖于特定的分布P，因此结果为我们以后对OLP算法的遗憾分析提供了便利。 重要的是，命题 3 和 4 中的两个概率界限都有一个指数项 n，我们利用这个事实来确定 p * n 的收敛速度如下。
对于命题 3 和 4，恒等式 (11) 可以启发式地写为
(13)
以高概率，即（13）被违反，概率在 中呈指数下降。 请注意，上面的右侧是 p 的二次函数。 从 p * n 的最优性，
(14)
将 (13) 与 (14) 放在一起，然后对 积分，我们可以得到以下定理。
定理 1. 在假设 1 和 2 下，存在一个常数 C 使得
()
适用于所有 n ≥ max{m, 3}、m ≥ 2 和分布 P ∈ Ξ。 此外，
()
对于 m = 1 的情况，如果右侧没有 log m 项，两个结果仍然成立。
定理 1 以 L 2 距离表示收敛速度。 定理中的第二个不等式可以直接从第一个不等式中推导出来，这里我们给出两个不等式供以后使用。
此外，为了简化本文其余部分的符号，我们对两个不等式采用相同的常数而不失一般性。 该定理通过表征两个问题的最优解之间的距离，正式连接了对偶 LP 和随机程序。 如前所述，它解决了 OLP 问题中对偶最优解收敛的开放性问题。 定理的结论和证明都基于有限样本论证，与派生渐近结果的经典随机规划文献并行（Shapiro，1993；Shapiro 等人，2009）。 有限样本属性在 OLP 算法的遗憾分析中至关重要。 在下一节的定理 2 中，我们将展示 OLP 算法的遗憾如何以 p* 的 L 2 近似误差为上限。 这解释了为什么我们关注 p * n 的收敛性和近似误差而不是函数值 f (p * n )。 至于收敛速度，回想一下假设 2 (a) 和 (b) 在最优解 p ∗ 周围施加曲率条件。 它们对命题 4 中的二次型 (12) 和因此定理 1 中的收敛速度至关重要。定理 1 中收敛结果的替代证明也可以通过使用局部 Rademacher 复杂度的概念来获得。 巴特利特等人。 (2005) 提出了这种局部和经验版本的 Rademacher 复杂度，并采用该概念来推导估计器收敛的快速速率。 我们注意到，这种可能的替代处理还需要围绕最优解 p 的某些增长和平滑条件作为假设 2 (a) 和 (b)。
现在，我们讨论定理 1 对 OLP 问题的一些影响。 该定理告诉 p ∗ n 的序列将收敛到 p ∗ ，并且当 n 变大时， p ∗ n 会更接近 p ∗ 。 从算法的角度来看，OLP 算法可以基于在每个时间 t 观察到的 t 个输入形成 p ∗ 的近似值。 如果 t 足够大，近似对偶价格 p* t 应该非常接近 p * 和 p * n 。
然后，该算法可以使用 p * t（作为最优 p * n 的近似值）来决定当前决策变量的值。 这解释了为什么文献中的 OLP 算法总是解决离线 LP 的缩放版本（基于时间 t 可用的观察结果）。 然而，在文献中，由于缺乏对偶最优解的收敛知识，论文设计了其他方法来分析在线目标值。 我们的收敛结果明确地描述了收敛速度，从而为在线算法的理论分析提供了一个强大而自然的工具。
双重收敛结果也有助于大规模 LP 的近似算法的文献。 具体来说，我们可以使用前 t 个输入执行一次性学习，然后使用 p * t 作为 p * n 的近似值。 通过这种方式，我们通过仅访问前 t 列 {(r j , a j )} tj=1 来获得解决原始 LP 问题的近似算法。 近似算法可以被视为对偶 LP 的约束采样过程（De Farias 和 Van Roy，2004；Lakshminarayanan 等，2017）。 它还补充了最近的工作（Vu 等人，2018 年），其中在对 LP 问题的系数的某些统计假设下开发了大规模 LP 的近似算法。

4 LOP的学习算法

4.1 双基策略、约束过程和停止时间
在本节中，我们提出了几种基于对偶收敛结果的在线算法。 我们首先重新审视在线政策的定义，并将我们的范围缩小到一类依赖双重解决方案的双重政策。 具体来说，在每个时间 t，根据历史数据计算一个向量 p t
()
其中 H t−1 = {r j , a j , x j } t−1 j=1 。 受离线/静态 LP 最优条件的启发，我们尝试设置
()
换言之，阈值由对偶价格向量 p t 设置。 如果奖励 r t 大于阈值，我们打算接受订单。 然后，我们检查约束满足并分配
()
我们正式将具有这种结构的政策定义为双重政策。 我们强调，在这种基于对偶的策略类中，首先根据历史计算 p t （直到时间 t - 1），然后观察到 (r t , a t )。
这创造了一个自然的条件独立性
()
这与在线凸优化中的设置相匹配，其中在每个时间 t，在线玩家在我们观察函数 f t 之前做出决定（参见 (Hazan et al., 2016)）。 在遗憾分析中，我们会经常诉诸这种有条件的独立性。 在这个策略类中，在线策略 π 可以完全由映射序列 h t 指定，即 π = (h 1 , …, h n )。 为了方便我们的分析，我们引入 n 约束过程 {b t } t=1 ，
()
这样，b t = (b 1t , …, b mt ) 表示第 t 个周期结束时剩余资源的向量。
特别是， b n = (b 1n , …, b mn ) > 表示在地平线结束时的剩余资源。 根据 OLP 的 n 定义，对于 t = 1, …, n，b t ≥ 0。 此外，{b t } t=0 的过程与策略 π 有关。 基于约束过程，我们定义
()
对于 s > 0。这样，τ s 表示第一次对于某种类型的约束有少于 s 个单位。
n 准确地说，τ s 是适应过程{b t } t=1 的停止时间。 与过程 b t 类似，停止时间 τ s 也与策略 π 相关。 在执行在线政策时，我们不会在违反某些约束的第一次关闭业务。 这是因为我们正在考虑包括买卖订单在内的双面问题。 如果某种类型的资源耗尽，我们可能会接受包含该资源的销售订单作为补充方式。 我们将看到算法的精心设计将确保约束违反/资源耗尽仅在最后发生。 因此，之后的决策不会显着影响累计收入。
在本节的其余部分，我们首先推导 OLP 算法遗憾的通用上限，然后介绍三种 OLP 算法。 这三种算法都属于对偶策略类，它们的遗憾分析都依赖于对偶收敛和通用上界。 我们将注意力限制在 large-n 和 small-m 设置上，遗憾界限将使用 big-O 表示法表示，它将 m 以及假设 1 和 2 中的参数视为常数。
4.2 上界和OLP Regret
我们首先为离线最优目标值构建一个上限。 考虑优化问题
(15)
其中期望是关于 (r, a) ∼ P。有两种方法可以解释这个优化问题。 一方面，我们可以将此问题解释为原始 LP (1) 的“确定性”松弛。 我们用对偶变量 p 表示的期望形式代替 (1) 的目标和约束。 另一方面，我们可以将此优化问题视为随机程序 (7) 的原始问题。 在网络收益管理（Talluri 和 Van Ryzin，1998；Jasin 和 Kumar，2013；Bumpensanti 和 Wang，2018）、动态定价（Besbes 和 Zeevi， 2009; Wang et al., 2014; Lei et al., 2014; Chen and Gallego, 2018)，以及土匪问题 (Wu et al., 2015)。
这个想法是，在分析此类问题中在线算法的遗憾时，离线最优值通常没有易于处理的形式（例如原始 LP 问题（1））。 确定性公式作为离线最优值的易处理上界，然后确定性最优值与在线目标值之间的差距是在线算法遗憾的上限。 与文献不同，我们考虑确定性公式的拉格朗日来消除约束。 具体来说，定义
()
其中期望是关于 (r, a) ∼ P 和 p * 是随机程序 (7) 的最优解。 我们可以将 g§ 视为优化问题 (15) 的拉格朗日函数，乘数由 p * 指定。 引理 3 确定确定性公式确实为离线最优值提供了上限，并且优化问题 (7) 和 (15) 共享相同的最优解。
引理 3. 在假设 1 和 2 下，我们有
()
对于任何 p ≥ 0。这里 p * 是随机程序 (7) 的最优解。 此外，
(16)
适用于所有 p ∈ Ω p 和所有分布 P ∈ Ξ。
约束的存在使遗憾分析具有挑战性，因为约束影响在线环境中目标值的方式是难以捉摸的并且取决于问题。 拉格朗日形式 g§ 通过将约束合并到目标中来解决该问题。 直观地说，它为约束消费分配了一个成本，从而统一了两个看似冲突的方面——收入最大化和约束满足。 引理 3 的重要性是双重的。 首先，它为预期的离线最优目标值提供了一个确定的上限。 上界不依赖于具体OLP实例的实现，因此比原来的离线最优分析更方便客观价值。 其次，基于对偶的在线算法在时间 t 采用对偶价格 p t ，其在时间 t 的即时奖励可以近似为 g(p t )。 那么算法在时间 t 的单步遗憾可以用 (16) 限定。 定理 2 建立在引理 3 的基础上，并将在线目标值 ER n (π) 与 ng(p * ) 进行比较。 为基于双重的在线策略开发了一个通用上限。 上限由三个部分组成：(i) 累积“近似”误差，(ii) 约束几乎耗尽后的剩余时间段，以及 (iii) 时间段 n 结束时的剩余资源。 第一个组成部分将遗憾与上一节中研究的 E kp t − p ∗ k 22 联系起来。 它证明了为什么在最后一节中研究了对偶收敛（定理 1）。 第二个组成部分涉及 τ ā ，其中 ā 在假设 1 中定义，它是每个时期的最大可能约束消耗。 对 τ ā 的直觉是，如果需要，当 t ≤ τ ā 时，总能满足一个命令 (r t , a t )。
尽管在 τ ā 之后仍然可以接受卖单（a ij 为负），但从导出后悔上限的角度来看，我们只是忽略了 τ ā 之后的所有订单。 第三个组件考虑绑定约束的剩余约束。 直观地说，约束性约束是产生收入的瓶颈，因此在期末浪费这些资源会产生成本。
定理 2。在假设 1 和 2 下，存在一个常数 K，使得策略 π 下的最坏情况后悔，
()
对所有 n > 0 成立。这里 I B 是由随机程序 (7) 指定的绑定约束集合，p t 由策略 π 指定，p * 是随机程序 (7) 的最优解。
定理 2 为在线策略的设计提供了重要的见解。 首先，基于对偶的策略应该学习 p * 。 同时，在线策略应该对资源/约束消耗有稳定的控制。 过早地用尽约束可能会导致项 n - τ ā 的值很大，而 P 剩余资源在地平线末端也可能通过项 i∈IB b in 引起遗憾。
本质上，这两个组成部分都源于约束消费的波动。 理想的情况，虽然由于随机性而不可能，但第 i 个约束在每个时间段内被恰好 d i 个单位消耗。 以下推论表明，定理 2 中的结果适用于一般类别的停止时间。
推论 1. 对于任何给定的 b t 自适应停止时间 τ，如果 P(τ ≤ τ ā ) = 1，
()
对于所有 n > 0 且具有与定理 2 中相同的常数 K 均成立。这里 I B 是绑定约束的集合，p t 由策略 π 指定，p * 是随机程序 (7) 的最优解。
评论 定理2和推论1将遗憾上限的推导简化为近似误差分析和约束过程分析。 为了强调这种减少的有用性，我们简要讨论了为分析存在约束的在线学习问题而开发的现有技术。 最简单的方法是提出一个双目标性能度量：一个用于目标值，一个用于约束违反。 在带约束的在线凸优化问题中采用了双目标性能度量（Mahdavi 等，2012；Agrawal 和 Devanur，2014b；Yu 等，2017；Yuan 和 Lamperski，2018）。 在这些作品中，对目标值的遗憾和违反约束是分开报告的。 我们的结果提供了一种将双目标结果转换为一个性能度量的方法。 当约束系数 ā 的上限已知时，组合双目标性能度量的一种方法是惩罚约束的过度使用，例如 (Ferreira et al., 2018) 中的遗憾分析。 然而，这种方法仅适用于非自适应算法（如算法 2），但在约束过程影响决策时会失败（如算法 3 和其他重新求解算法）。 有鉴于此，定理 2 和推论 1 为非自适应和自适应算法提供了统一的处理方法。 另一种处理约束的方法是使用“收缩”技巧。 这个想法是执行在线学习，就好像约束被缩小了 1 - 因子一样，然后输出的在线解决方案对于原始问题很有可能是可行的。 这种收缩技巧用于 OLP 文献 (Agrawal et al., 2014; Kesselheim et al., 2014) 以及带背包的土匪问题 (Agrawal and Devanur, 2014a)。 收缩的不利之处在于它可能会导致过度保守的决定，并且可能在地平线结束时剩余资源过多。 最接近我们方法的遗憾分析是（Jasin 和 Kumar，2012；Jasin，2015；Balseiro 和 Gur，2019）中的分析。 其中的遗憾推导还涉及分析与约束耗尽相关的停止时间。
当没有关于 (r j , a j ) 的支持的先验知识可用时，我们的通用上限可以看作是他们对这种情况的分析的概括。 对于网络收益管理问题，假设客户订单 (r j , a j ) 的支持是有限且已知的。 在这种情况下，离线最优解可以明确地由应该接受的每种客户订单的最优数量来指定。 然后可以通过与最优量的偏差来分析在线算法的性能。 在一般的 OLP 问题中，没有离线最优解的明确表示。 定理 2 和推论 1 通过将 p ∗ 的近似误差识别为网络收益管理上下文中与最优数量的偏差的非参数概括来解决该问题。 随后的工作（Lu 等人，2020 年）也将定理 2 和推论 1 中的类似想法应用于对 (r j , a j ) 的有限支持的在线分配问题的遗憾分析。
4.3 当分布已知时
我们首先提出一种算法，用于当我们知道生成 LP 系数的分布 P 时的情况。 有了 P 的知识，随机规划问题 (7) 就得到了很好的说明。 我们研究该算法主要是为了进行基准测试，所以我们不讨论知道分布 P 的实用性。此外，我们假设随机规划问题 (7) 可以精确解决。 在算法 1 中，最优解 p ∗ 在在线过程之前计算，可以看作是先验知识。 因此，在整个过程中“无需学习”对偶价格，预先计算的 p * 可用于阈值规则。
Alogrithm 1
定理 3 告诉我们，在具有完全分布知识的在线策略下，最坏情况的后悔是 O(n)。 回想一下定理 2 中的通用后悔上限，算法 1 没有近似误差，因为 p * 被用作对偶价格。 所以算法1的遗憾只源于√约束过程的波动。 直观地说，当它接近地平线的尽头时，波动在 O(n) 的数量级上。 我们的下一个算法及其相应的后悔分析表明，p*（当分布未知时）的近似误差的贡献确实由约束过程的波动引起的后悔支配。
4.4 简化的动态学习算法
算法2 通过根据过去的观察为随机程序求解 SAA 来近似算法 1 中的对偶价格 p *。 从 OLP 的角度来看，它可以看作是 (Agrawal et al., 2014) 中动态学习算法的简化版本。 在算法 2 中，对偶价格向量 p t 仅以几何时间间隔更新，它是基于求解 t 样本近似值来计算的，即最小化 f t §。 这种简化算法与 (Agrawal et al., 2014) 中的 q 动态学习算法之间的主要区别在于，我们摆脱了 q 约束中的收缩项 1 - t n k。 具体来说，该论文中的算法在算法 2 的第 6 步中的约束右侧考虑了 1 - t n k t k d i。在随机输入模型中，收缩因子导致对偶价格 p t 的高估，因此将是 在接受订单时更加保守。 在 (Agrawal et al., 2014) 中研究的随机置换模型下，保守性可能会有所帮助，但在随机输入模型下，可能会导致剩余资源在 n 中呈线性关系。
定理 4. 使用算法 2 指定的在线策略 π 2，
()
定理 4 表明该策略会导致 O(n log n) 的最坏情况后悔。 它的证明依赖于对定理 2 中后悔界中三个分量的分析 P τ ā。总和 t=1 kp t − p ∗ k 22 可以通过对偶收敛结果进行分析。 具体来说，算法 2 中的对偶价格 p t k 是基于随机程序 (7) 的 t k 样本近似值计算的，因此可以使用定理 1 来确定距离 kp t k − p ∗ k 22 的上限。 它重申了研究对偶收敛性和表达 L 2 距离的近似误差的重要性。 基于对过程 b t 的仔细分析，研究了与停止时间和剩余资源相关的两个组件。 详细证明见C2节。
4.5 动作历史依赖学习算法
现在，我们介​​绍我们的动作历史依赖学习算法。 在算法 2 中，对偶价格 p t 是过去输入 {(r j , a j )} t−1 j=1 的函数，但它不考虑过去的动作 (x 1 , …, x t−1 )。 相反，算法 3 将过去的动作整合到 p t 的优化问题的约束中。
在周期 t + 1 开始时，观察到前 t 个输入 {(x j , r j , a j )} tj=1。 算法 2 将 LP 右侧的 b i 归一化为 n t b i = td i ，而算法 3 将 LP 右侧的剩余资源 b it 归一化（算法 3 的步骤 6）。 直觉是，如果我们碰巧
Alogrithm 2
在过去的一段时间内消耗过多的资源，剩余的资源 b 它会收缩，算法 3 会相应地推高对偶价格，更倾向于拒绝订单。 反之，如果我们一开始碰巧拒绝了很多订单，导致剩余资源过多，算法会降低对偶价格，以便在未来接受更多订单。 算法 3 中的这种钟摆式设计结合了过去通过剩余资源间接计算双重价格的行为。
从算法的角度来看，算法 3 在学习环境中实现了重新求解技术，而该想法是由（Reiman 和 Wang，2008；Jasin 和 Kumar，2012；Bumpensanti 和 Wang，2018）在已知参数环境中实现的。 与明确估计到达强度并将估计馈送到确定性等价问题的工作（Jasin，2015）不同，算法 3 的学习部分是隐式的，并集成到优化部分中。 对于算法3第6步的优化问题，左边由历史指定，右边由实时约束容量指定。 如果我们将 d it = b it n-t 定义为平均剩余资源容量，那么时间 t 的优化问题可以看作是 d t = (d 1t , …, d mt) > . 重要的是，每个时间段的目标随机程序是根据约束过程动态变化的，而算法 2 和本文前面的所有分析都集中在由固定初始 d 指定的静态随机程序上。
为了在不断变化的 d 设置中应用对偶收敛结果，我们需要一个统一版本的假设
Alogrithm 3
2. 具体来说，对于 d 0 = (d 0 1 , …, d 0 m ) > ∈ Ω d ，定义
()
并表示 p ∗ (d 0 ) 表示其最优解。 假设 3 与假设 2 共享相同的部分 (a)，并将假设 2 的部分 (b) 和 © 扩展到所有 d 0 ∈ Ω d 的统一条件。 因此，我们更新了 Ξ 的定义以表示满足假设 1 和 3 的分布族； 对于本小节，我们考虑这个更新的Ξ 内的分布 P。
假设 3（假设 2 的统一版本）。 我们假设 (a) 二阶矩矩阵 M := E (r,a)∼P [aa > ] 是正定的。 用 λ min 表示其最小特征值。
(b) 存在常数 λ 和 µ 使得如果 (r, a) ∼ P,
()
适用于任何 p ∈ Ω p 和 d 0 ∈ Ω d 。
© 最优解 p ∗ (d 0 ) 满足 p ∗ i (d 0 ) = 0 当且仅当 d 0 i − E (r,a)∼P [a i I(r > a > p ∗ (d 0 ))] > 0 对于任何 d 0 ∈ Ω d 。
定理 5 指出算法 3 导致 O(log n log log n) 的最坏情况遗憾。 从技术上讲，证明建立在对定理 2 中通用上限的三个组成部分的分析之上。需要注意的是，算法 3 中的 SAA 问题和基础随机程序随时间动态变化。 为了分析算法，我们在初始 d = b/n 周围确定了一个子集 D ⊂ Ω d 并表明 (i) 当 d t = d 0 ∈ D 时，假设 1 和 3 都满足，更重要的是，所有随机程序 由 d 0 指定的共享相同的绑定和非绑定维度； (ii) 过程 d t 仅在视界的尽头退出区域 D。 由于约束过程 b t 和 d t 更复杂，我们采用不同于定理 4 证明的方法。定理的证明和更多讨论推迟到 C3 节。
定理 5. 使用算法 3 指定的在线策略 π 3，Δ n (π 3 ) ≤ O(log n log log n)。
Fifure 1
图 1 可视化了算法 2 和算法 3 下的约束消耗。我们为每个算法运行 10 次模拟试验，并绘制每个随机试验的绑定约束的约束消耗。 前两个数字表明两种算法似乎在平衡资源消耗方面表现良好：不要过早耗尽约束或最后有太多剩余。 但是，如果我们将最后 250 个周期放大为底部两个数字，算法 √ 3 的优势就变得显着。 对于算法 2，一些试验在结束，而有些试验最后剩下 O(n)。 有趣的是，对于图 1c 中的某些曲线（如灰色 √ 和绿色曲线），剩余资源水平在结束前停止减少 O(n) 个周期，尽管剩余资源水平严格为正。 这是因为当时其他一些约束已经用尽，从那时起，即使绘制的约束仍有剩余资源，我们也不能接受更多订单。 相比之下，算法3的约束消耗要稳定得多。

5 实验和讨论

5.1 数值实验
我们在三个不同的模型上实现了三个提出的算法，模型细节如表 1 所示。在第一个模型（随机输入 I）中，约束系数 a j 和目标系数 r j 是独立同分布的。 生成为有界随机变量。 所有 d i 都设置为 0.25。 在第二个模型（随机输入 II）中，约束系数 a ij 是从正态分布生成的，这违反了有界假设。 r j 的赋值是 a j 的确定性条件，因此违反了假设 2 (b)。 a ij 和 r j 都以正概率取负值。 在随机输入 II 中，我们将 d i 交替设置为 0.2 和 0.3。 在第三个模型中，我们考虑一个随机排列模型，与 (Agrawal et al., 2014) 中的最坏情况示例相同。 决策变量的个数 n 在这个置换模型中本身就是一个随机变量，所以我们在实验中指定它的期望为 100 和 300。
Table 1
表 2 报告了三种算法在 m 和 n 的不同组合下的估计后悔值。 该估计基于 200 次模拟试验，并且在每个模拟试验中，从相应的模型中生成一个问题实例（a ij 和 r j ）。 在求解算法 1 中的随机程序时，我们使用具有 10 6 个样本的 SAA 方案。 根据实验结果，我们有以下观察结果。 首先，表 2 显示算法 3 的性能一致优于算法 1 和算法 2。重要的是，算法 3 在违反理论分析假设的随机输入 II 和排列模型中也表现出色。 特别是，随机排列问题实例用于 Agrawal 等人。 （2014）建立约束能力的必要条件，因此可以被视为最具挑战性的OLP问题之一。 据我们所知，算法 3 是第一个在通用 OLP 设置中采用动作历史相关机制的算法。 在这方面，算法 1 和算法 2 代表 OLP 文献中的典型算法（Molinaro 和 Ravi，2013；Agrawal 等，2014；Gupta 和 Molinaro，2014；Devanur 等，2019），实验证明了其有效性 与这些作品相比，依赖于动作历史的设计。 此外，算法 3 的优势随着比率 m/n 的增加而变小。 这可以通过 p m/n 来解释，因此基于对偶的算法（如算法事实，即对偶收敛速度为 3 阶）在大 n 和小 m 方案中会更有效。
为了说明遗憾如何随 n 变化，我们固定 m = 4 并针对不同的 n (= 25, 50, 100, 250, 500, 1000, 2000) 运行实验。 结果如图 2 所示，其中曲线是通过连接样本点绘制的。 对于左图，曲线验证了定理 3、4 和 5 中的遗憾结果。同时，右图看起来很有趣，因为算法 1 和 2 的遗憾是线性缩放的与 n 而算法 3 的遗憾是 O(1) （可以拟合一条水平线）。 这种现象可能是由随机输入 II 模型中 r j 的确定性分配引起的。

Table 2
Figure 2
在数值实验中（图 2 (a)），我们凭经验观察到算法 1 √ 和算法 2 的遗憾都是 n 阶。 这表明几何间隔对于算法 2 已经足够了。换句话说，算法 2 的性能不能通过简单地增加学习频率来进一步提高。 此外，这意味着如果我们想将遗憾减少到 O(log n)，则需要考虑过去的行为。 对网络收益管理问题也进行了同样的观察，从而激发了对重新求解技术的研究。
表 3 报告了基于网络收益管理问题的数值实验（Jasin，2015）。 通过将每个到达的客户与表示接受或拒绝决定的二元决策变量相关联，可以将其中的网络收益管理问题表述为 OLP 问题。 我们实验中的参数与 (Jasin, 2015) 中的数值实验相同：需求率、确定性价格、行程结构和航班容量。 我们在 (Jasin, 2015) 中实现了 PAC（概率分配控制）算法，在 (Jasin and Kumar, 2012) 中实现了重新求解算法。 实现了两种版本的重新求解算法，一种具有真实参数的知识（重新求解（I）），另一种具有不精确的参数估计（重新求解（II））。 具体来说，我们将每种客户类型的到达概率估计扰动 0.005 的幅度，并重新标准化扰动概率。 不精确估计旨在捕捉决策者无法获得真实参数，只能通过历史数据校准到达概率的场景。 对所有四种算法都测试了不同的解析频率和不同的视野，并根据平均超过 200 次模拟试验报告了性能。 具体来说，对于 PAC 算法，我们设置初始学习周期 t 0 = 15，这意味着接受所有客户
Table 3
我们的动作历史相关算法（算法 3）比其他三种算法具有更好的经验性能。 结果有点令人惊讶，因为 PAC 算法可以被视为我们的动作历史相关算法的原始版本，并且它还具有通过重新求解和重新优化的自适应设计。 此外，Re-solving (I) 算法甚至利用了真实参数值的知识。 我们相信，当 n 足够大时，我们算法的优势仅达到一个常数因子，并且我们为观察提供了两种解释。 首先，本实验共有 41 条不同的行程路线和 14 个中转航班（m = 14）。 这意味着PAC算法需要估计41个参数，而算法3只需要估计14个参数。
此外，在估计最优对偶价格时，问题的性质可能会导致较小的方差。 具体来说，PAC算法中的41个参数都是概率，平均值约为0.02。 因此，估计受到罕见事件模拟中的效率问题的影响（Asmussen 和 Glynn，2007 年）。 此外，PAC 算法的两步过程将估计作为优化问题的输入，优化过程可能会进一步放大估计误差。 其次，所有三种重新求解算法都是基于原始的，而我们的算法 3 是基于对偶的。 请注意，基于原始的算法从优化过程中输出一个随机分配规则，因此该随机规则在决定原始变量的值时会产生更多的随机性。 额外的随机性可能会导致约束过程的更大波动。
相比之下，我们的算法 3 是基于对偶的，因此可以被视为三种基于原始算法的更平滑版本。
5.2 下限和开放式问题
现在，我们提出了基于双重政策的OLP 问题的下限结果。 Bray (2019) 确定，即使在了解基础分布的情况下，多秘书问题的最坏情况遗憾也是 Ω(log n)。 我们为两个目标的下限提供了另一种证明。 首先，证明模仿了（Keskin 和 Zeevi，2014；Besbes 和 Muharremoglu，2013）中下界的推导，核心部分基于 van Trees 不等式（Gill 和 Levit，1995）——Cramer- 的贝叶斯版本 饶界。 因此，它将先前的下限分析从无约束设置扩展到约束设置。 其次，回想一下，我们在定理 2 中开发了一个通用的后悔上限。下限证明表明，在某些条件下，通用的后悔上限是相当严格的。
直观地说，这表明对 p ∗ 的有效学习和对约束过程的稳定控制不仅足以保证明显的后悔界限，而且可能是必要的。
定理 6. 存在常数 C 和 n 0 > 0 使得
()
适用于所有 n ≥ n 0 和任何基于对偶的策略 π。
基于本文的实验和理论结果，我们提出了几个开放性问题供未来研究。 首先，遗憾如何取决于 m？ 在随机输入 I 的实验中，我们观察到遗憾增加，但不会随着 m 增加太多。 这显然不是随机输入 II 的情况，其中遗憾随着 m 的增大而显着增加（有关更多实验，请参见第 D6 节）。 一种可能的解释是，随机输入 II 中 r j 的生成导致 r j 随 m 缩放，因此离线最优目标值随 mn 线性缩放。 那么一个自然的问题是什么条件使遗憾依赖于 m，以及遗憾以何种方式依赖于 m。 其次，对于更一般的随机输入模型和置换模型，是否可以放宽假设并扩展理论结果？ 当假设被违反时，甚至在置换模型中，我们观察到算法 3 的良好性能。 例如，我们在随机输入 II 下的实验中观察到算法 3 的 O(1) 遗憾（图 2）。 由于违反了假设，因此下限在随机输入 II 中不成立。 此外，在随机排列模型下，对偶收敛和遗憾结果是否仍然成立是一个有趣的问题。 这个问题需要在置换上下文中正确定义随机程序（7）。
第三，在假设 1 © 中，我们要求约束随 n 线性缩放。 我们还没有回答这个线性增长率对于建立双重收敛结果是否必要的问题。
换句话说，如何将双重收敛和遗憾界限扩展到资源有限的制度？ 此外，算法 3 更新每个周期的对偶价格。 这就提出了一个问题，即是否有可能采用不那么频繁的更新/学习方案，但仍能达到相同的遗憾顺序。
在分布已知的网络收益管理环境中，Bumpensanti 和 Wang (2018) 展示了不频繁更新方案的有效性。 其中的分析高度依赖于分布支持的有限性以及分布的知识。 我们认为，对于一般 OLP 问题，使用不频繁的更新方案得出类似的低遗憾结果既有趣又具有挑战性。 最后一个问题是关于遗憾界限的类型：我们在本文中提供的所有算法界限都是关于遗憾期望的。 一个有趣的问题是如何为 OLP 问题推导出高概率后悔界（可能使用额外的对数项）。 事实上，我们论文中对偶收敛的结果是概率性的（如命题 3 和命题 4），这可以作为推导高概率遗憾界的良好起点。