联合在线学习和资源分配是许多应用程序固有的基本问题。 在一般情况下，异构客户按顺序到达，每个客户都可以在线方式分配给一个资源。 客户随机消耗资源，分配产生随机奖励，系统延迟接收反馈结果。 我们引入了一个通用框架，该框架明智地将在线学习与广泛的在线资源分配机制相结合，其中客户上下文的顺序是对抗性的，客户奖励和资源消耗是随机且未知的。
首先，我们提出了一种针对一般资源分配问题的在线算法，称为延迟学习时的个性化资源分配 (PRA-LD)，该算法在探索、利用和对冲对抗性到达序列之间取得了三向平衡。 我们在贝叶斯后悔方面为这个在线算法提供了性能保证。 接下来，我们针对提前调度问题开发了第二个在线算法，称为延迟学习时的个性化提前调度 (PAS-LD)，并评估其理论性能。 PAS-LD 算法具有更精细的结构，并提供多天调度，同时考虑到客户的未出现行为。 我们使用来自合作伙伴卫生系统的临床数据证明了 PAS-LD 算法的实用性和有效性。 我们的结果表明，与几个基准策略相比，所提出的算法提供了有希望的结果。
信息的快速增长和大数据的可访问性为转向个性化决策提供了独特的机会。 通常，可以通过从过去的数据和决策结果中学习并根据新用户的上下文信息（例如人口统计和临床/网络历史）为新用户做出个性化决策来实现个性化（例如，参见 Bertsimas 和 Kallus 2020、Bertsimas 等人 2020 , 和 Chen et al. 2021)。 个性化健康信息的可访问性的增长可以彻底改变医疗保健行业的个性化。 例如，在线预约平台有可能增加获得高质量护理的机会通过将患者与他们所在地区最好的医生配对并根据患者的状况和偏好提供预约，为所有患者提供服务。 这推广到营销等其他领域，个性化可以通过根据用户人口统计和兴趣提供个性化广告和促销来帮助公司实现更高的点击率。
开发用于个性化资源分配的实时系统有两个核心要素，包括 (i) 学习一个模型，该模型可以预测可能的决策/行动的用户特定结果，以及 (ii) 利用这种预测模型来制作个性化资源 后续用户的分配决策。 这种带有学习过程的顺序决策受到强盗反馈的影响，其中人们只能获得所选决策的用户反应/结果（通常称为反馈），而无法观察可能已经做出的其他决策的反事实。 这一障碍激发了一种更有效的数据学习方法来学习模型，而不是离线统计模型。
离线和在线统计方法都依赖历史数据来提供估计； 然而，在线方法提供了自适应学习的优势。 在自适应学习中，自适应地收集新信息，以便尽快收集最有用的信息，而不是简单地使用潜在的大量历史数据。 自适应学习的关键是探索利用权衡（Auer 2002）。 决策者通常希望利用当前估计来做出最大化奖励的决策（利用），同时更多地探索估计不佳的决策以在后续决策中获得更高的回报（探索）。 这里的挑战是仔细平衡这种探索-开发的权衡。
除了学习之外，我们经常必须在资源有限和未知的未来到来的情况下优化个性化决策。 在这种情况下，具有随机资源消耗的异构用户随着时间的推移顺序到达，应该为他们分配有限的资源以对冲未来的到达顺序。 例如，预约安排平台需要在提供者有限的情况下以在线方式为到达的患者安排预先预约（提供者日期）。 在这里，不仅决策者经常不确定患者的奖励和服务时间，而且还缺乏有关未来患者类型顺序的信息。 因此，应安排患者，以便为将来可能出现的高回报/紧急患者提供可用容量（Truong 2015）。
我们考虑了个性化学习的在线资源分配问题，并设计了一个实时的个性化资源分配系统。 客户通常以包含其上下文信息的上下文向量为特征。 在这种类型的许多现实世界问题中，应考虑两个重要特征：（i）未来客户到达的数量及其上下文向量是未知的，以及（ii）通常存在未知的模型参数，对于做出决策至关重要 每个到达的客户。 这个问题的各种版本已经在文献中进行了广泛的研究，但大多是分开的（即在线资源分配或在线学习资源有限）。 在典型的在线资源分配问题（对抗性或随机性）中，每个到达客户的奖励和资源消耗都是已知的，难点在于进行资源分配以对冲未来到达顺序的不确定性。 在资源有限的在线学习问题中，典型的假设是客户上下文是独立同分布（IID）的，这导致存在底层（固定）最优随机分配策略。 因此，困难在于平衡探索和利用的权衡以收敛到最优分配策略。
然而，为上述问题开发的模型都没有解决具有特征（i）和（ii）的资源分配问题。
在线学习问题中另一个重要但经常被忽视的问题是延迟反馈，这是学习过程中的一个关键因素。 大多数在线学习环境中的一个常见假设是，一旦做出决定，就会立即收到反馈； 然而，在许多应用程序中，它通常是延迟实现的。 例如，预约调度平台可能每天安排数百名患者，而接收患者反馈的最快时间是在预约的预约日期之后。 此外，在某些情况下，已实现的反馈可能不会在收到后立即处理（Chapelle 和 Li 2011），这可能是延迟反馈的另一个原因。
上述讨论和挑战提出了我们在本文中回答的以下两个重要研究问题：（i）如何提供一个通用的个性化资源分配框架，在探索、利用和对冲对抗性到来之间取得三向平衡 延迟反馈下的序列，以及（ii）如何针对具有多天调度和未出现行为的提前调度问题定制该框架。
1.1 Contributions and Main Results
我们引入了一个通用框架，该框架将在线上下文学习与广泛的在线资源分配机制相结合。 首先，我们考虑一个一般的资源分配问题。
接下来，我们考虑一个提前调度问题，它是我们通用框架的一个应用，但具有更精细的结构。 对于每个问题，我们开发了一个具有理论性能保证的在线算法。 下面，我们将总结我们的主要成果和贡献。
(a) 我们针对具有个性化学习的在线资源分配算法开发了一种新的通用贝叶斯后悔分析，其中 (i) 客户上下文序列是对抗性的（不需要 IID 假设），(ii) 客户奖励是随机的，以及 (iii) 资源消耗是随机的。 我们的分析允许无缝集成在线资源分配算法的竞争比率界限和上下文学习算法的贝叶斯后悔界限。
特别是，限制我们算法的贝叶斯遗憾需要定义一个辅助问题并提出一组桥接技术（见定理 1 的证明）。 请注意，Cheung 等人也定义了一个辅助问题。 2022 年通过学习得出资源分配的下限。 然而，它们的辅助问题与我们分析所需的问题不同（详见第 4.1 节）。 通过引入一个未知模型参数已知但不知道客户上下文序列的辅助问题，我们可以将主要遗憾项分解为两部分：（i）与奖励和资源消耗值的不确定性对应的损失，以及（ii ) 与解决辅助问题的在线资源分配机制的最优差距相关的损失。 然后，我们得出以下一般性能保证：
()
其中 BayesReg(L) 是算法在长度为 L 的规划范围内的贝叶斯遗憾（参见定义 2）。 CLS-Loss 项包括上下文学习损失和与资源消耗的随机性相关的损失； 它在计划范围内的到达数量是次线性的。 此外，α 是算法中包含的任何可能的资源分配机制的竞争比率，V BM 是给定模型参数和客户上下文序列的基准测试获得的总预期回报，E[V BM ] 是预期值 V BM 在模型参数的先验分布上。
(b) 我们的框架可以处理延迟的老虎机反馈。 当没有延迟时，估计器的更新过程可以使用同步策略完成，其中需要上下文向量和实现的反馈来更新估计器。 如果没有立即的反馈，这种策略是行不通的。 因此，我们在延迟反馈下引入了异步策略，这需要开发新的置信区间。 作为我们遗憾分析的副产品，我们使用普通最小二乘法 (OLS) 方法在线性模型中为未知参数开发了延迟反馈下的置信区间。
假设 D max 作为延迟的上限，对于 Zhou 等人研究的标准上下文老虎机问题，我们的置信界产生了 √ Õ d T + dD max 的遗憾界。 2019 年，奖励模型是线性的。 这是一个比该研究中提供的更严格的界限（详细比较参见第 4.3 节），并且它在本文之外具有独立的兴趣。
© 除了不确定的回报外，异构客户的资源消耗也存在不确定性。 我们的在线算法仅在预期中强制执行容量限制。 因此，在某些情况下可能会超出资源容量。 我们对超过资源容量的分配容量施加惩罚，并将其从忽略可能性获得的算法的总预期奖励中减去超出资源容量。 我们推导出惩罚项的高概率界限，它在规划范围内的到达数量是次线性的（命题 3 和 4）。 在费雷拉等人的研究中。 2018年，提出了一种在线算法来自适应地学习容量约束中的未知参数。 对于从已知分布中采样 IID 的有限上下文信息的设置，他们施加了一个惩罚项来限制分配的超过资源容量的容量数量，并得出 Õ |X | 的上限 p KT ，其中 K 是操作数，|X | 是可能的上下文的数量。
当可能的上下文数量增加时，这个界限就会爆炸。 作为我们 √ 算法设计和后悔分析技术的副产品，我们推导出瞬时反馈设置中惩罚项的上限 Õ (d + K) T，这取决于特征空间 d 的维度 p + K 而不是 |X | K。
(d) 我们的提前调度算法不仅提供了多天调度，而且还捕获了未出现的行为。 我们对此设置的大部分额外分析与在未出现的未知概率时推导出预期奖励的置信界限有关。
复杂性的主要来源在于，当客户被分配到服务器日期时，无法立即观察到未出现的反馈，如果客户没有出现在服务上，则根本无法观察到客户反馈结果 日期。 这种用于观察反馈结果的复杂结构需要推导出一个新的置信区间，该置信区间也可能对其他应用程序具有独立的兴趣（命题 5）。 据我们所知，我们的算法是第一个基于学习的提前调度算法，具有捕获未出现行为的性能保证。
1.2 文献综述
我们讨论了与我们的工作相关的两个主要研究领域和文献流：（i）多臂强盗和（ii）在线资源分配。
多臂强盗 多臂老虎机 (MAB) 是一个在线框架，用于在每个动作（臂）对结果的影响存在不确定性时随时间做出顺序决策。
在这个框架中，智能体从一组可能的动作中选择一个动作，然后揭示一个强盗反馈，帮助智能体随着时间的推移做出更好的决策。 上下文 MAB 是 MAB 的概括，其中每个动作的奖励取决于在每一轮观察到的上下文信息。 上下文设置解决了许多现实世界的应用程序，例如在线推荐系统、在线广告和个性化医疗保健。 有关近期 MAB 研究的全面回顾，我们参考 Slivkins 2019。
具有资源约束的 MAB 具有资源约束的 MAB 是最新的一类 MAB，其中每个操作都会消耗一定数量的资源。 巴达尼迪尤鲁等人。 2013 年和阿格拉瓦尔Devanur 2014 研究了具有资源约束的标准 MAB，并提出了具有性能保证的在线算法。 在收益管理领域，Ferreira 等人。 2018年研究了一个定价问题，可以被视为具有资源限制的MAB； 他们提出了一种算法，可以在有限库存的情况下最大化总收入。 巴达尼迪尤鲁等人。 2014，阿格拉瓦尔等人。
2016 年，Agrawal 和 Devanur 2016 年研究了具有资源约束和 IID 上下文向量的 MAB。 巴达尼迪尤鲁等人。 2014 年将一般上下文 MAB 扩展到允许预算约束的资源丰富的上下文强盗。 阿格拉瓦尔等人。 2016 年通过推广 Agarwal 等人的方法，提出了一种用于带背包的上下文老虎机的有效算法。 2014 专门针对这个问题的无约束版本。 Agrawal 和 Devanur 2016 开发了一个带背包的线性上下文强盗，并构建了置信椭球来估计未知参数。 在上述研究中，上下文向量的 IID 假设导致存在潜在的最优随机分配策略。 然而，在我们的问题设置中没有（固定的）最优随机分配策略，其中上下文向量被对手挑选（没有 IID 假设）。
具有延迟反馈的 MAB Chapelle 和 Li 2011 年的突出实证研究已经确定并讨论了延迟反馈的问题。Joulani 等人。 2013 年研究了一个没有侧面（上下文）信息的随机 MAB 和一个带有侧面信息的对抗性 MAB。 他们表明，延迟反馈设置会导致随机模型中的加法惩罚和对抗模型中的乘法惩罚。 派克-伯克等人。 2017 年研究了另一个具有汇总和匿名反馈的 MAB，其中在每轮结束时只能观察到先前产生的奖励的总和； 他们匹配了与 Joulani 等人相同的遗憾界限。 2013. 维纳德等人。 2017 年分析了 MAB，如果延迟时间超过阈值，则会审查用户反馈。 比斯特里茨等人。 2019 年研究了对抗性延迟（任意延迟序列）下的对抗性强盗。 他们为具有延迟的 Exp3 算法提供了一个有限样本延迟自适应后悔界。 文献中很少探索具有延迟的上下文强盗。 杜迪克等人。 2011 年研究了具有固定延迟的随机上下文老虎机。 对于有限的 p √ 类策略，他们提供了 O ( K log(N )(τ c + T )) 的遗憾界限，其中 N 是策略数量，τ c 是固定延迟。 最近，周等人。 2019 年研究了具有延迟的上下文广义线性模型（GLM）老虎机，并提出了置信上限（UCB）算法。
√ √ 当延迟有界时，他们建立了 Õ (d + dD max ) T 的遗憾界，其中 D max 是延迟的上限，d 是特征维度。 对于 IID 设置，他们建立了 Õ ( µd + σd + d) T 的 √ √ √ 遗憾界，其中 µ 和 σ 分别是延迟的平均值和表征延迟尾部的参数。 他们的证明建立在 Li 等人提供的分析之上。 2017 年用于 GLM-UCB 算法，其预热期使用最大似然估计器，无需正则化。 他们的算法设计和证明思路很显着与本文中的不同，我们有一个线性模型，并在有界延迟反馈下使用具有正则化的 OLS 估计器。
在线资源分配。 竞争比是评估在线资源分配算法性能最广泛使用的方法。 特别是，它通常被定义为在最坏情况输入实例下在线算法和基准（透视策略）之间的相对性能。 由于我们的框架包含在线资源分配机制，我们还简要回顾了两个相关的文献流，包括在线匹配和在线提前调度。
在线匹配 该领域的研究通常分为两种主要设置，包括随机和对抗。 在随机设置中，算法要么严重依赖于使用历史数据预测到达模式，要么考虑对到达模式的假设。 在对抗性设置中，算法不需要对到达模式进行假设，并且具有对到达模式的可能变化具有鲁棒性的关键优势。 梅塔等人。 2005 年研究了 Adwords 问题并开发了一种基于权衡揭示线性规划 (LP) 技术的在线算法，实现了 1-1/e 的竞争比。 布赫宾德等人。 2007 开发了一个优雅的原始对偶范式，以相同的竞争比率解决相同的问题。 文献中已经研究了这个问题的几个变体。 我们参考 Devanur 和 Jain 2012 以及 Kell 和 Panigrahi 2016 来了解这个问题的最新概括。 我们在线算法的贝叶斯遗憾部分取决于我们算法中使用的资源分配机制的竞争比率。 我们介绍了 Buchbinder 等人提出的原始对偶范式的两种变体。
2007 并将它们用作我们在线算法中的资源分配机制。 第一个允许客户拥有不同的异构奖励和资源消耗价值。 第二个版本扩展了第一个版本，以应对多天的客户安排。
在线提前安排。 提前调度的文献集中于两种类型的等待，包括直接和间接。 正如 Gupta 和 Denton 2008 所指出的，直接等待是指客户/患者在预约当天到达系统/诊所直到服务时间的时间； 而间接等待是指从收到请求到实际预约日期之间的时间。 大多数关于提前调度的文献都集中在日内调度上，以减少直接等待。 我们的工作重点是多日调度，以减少间接等待。
帕特里克等人。 2008 年，古普塔和王 2008 年，以及费尔德曼等人。 2014 年针对这个问题提出了几种启发式方法，并研究了最优策略的结构特性。 Truong 2015 研究了一个二分类提前调度模型，并针对这个问题提出了分析结果。 在异质患者的随机环境中，Wang 等人。 2018 年和斯坦等人。 2020 年提出了有界竞争比率的在线算法。 对于异质患者的对抗环境，Keyvanshokooh 等人。 2021 开发了一种在线提前调度算法，其中供应商的能力可以以加班费为代价来扩大。 他们使用 Buchbinder 等人开发的原始对偶分析提供了竞争比率。 2007. 未出现行为是提前调度的另一个特征，可以在建模这个问题时捕捉到。
刘等人。 2010 年是第一项在预约安排问题中明确模拟患者未出现的研究。 费尔德曼等人。 2014 年还研究了患者未出现的预约安排问题。 他们描述了静态最优策略的结构，并为随机设置中的最优差距提供了一个界限。 据我们所知，之前没有任何论文研究过模拟未出现行为的学习调度问题。 但是，我们在第二个模型（提前调度）中明确建模了未出现的情况。 值得注意的是，过去的研究在未出现概率对服务/预约延迟的依赖性方面存在分歧（例如，参见 Wang 和 Gupta 2011 和 Liu 等人 2010）。 当未出现概率与服务延迟无关时，我们对 PAS-LD 算法的理论性能保证成立。
最后，与我们最接近的作品包括 Pan 等人。 2020 年和 Cheung 等人。 2022.潘等人。
2020 研究了一个带有学习的在线匹配问题，其中几种类型的患者必须与易腐资源匹配，奖励分配未知，每个患者分配消耗一个单位的容量。 通过患者到达的非平稳泊松过程，他们提出了一种两阶段算法，该算法具有不同的探索和利用阶段。 他们证明了该算法实现了一个遗憾界限，该界限随着规划周期的数量呈次线性增加。 张等人。 2022 研究了随着时间的推移向异构客户分配有限资源的问题，其中奖励是已知的，并且随着时间的推移应该了解与每种客户类型和行为相关的资源消耗分布。 他们提供了一个没有 IID 假设的信息论下限。 我们为我们的框架提供了贝叶斯遗憾，其中（i）我们没有关于上下文的 IID 假设，因此没有固定的最优分配策略，（ii）奖励和资源消耗都是随机的，（iii）没有 -在我们的第二个模型（提前调度）中应该考虑表演行为，并且（iv）学习过程是在有界延迟反馈下完成的。
1.3.论文组织和一般符号
本文的其余部分安排如下。 我们在第 2 节中阐述了我们的问题，并在第 3 节中提出了两种在线算法。我们在第 4 节中进行了非渐近性能分析。在第 5 节中，我们使用来自合作伙伴健康系统的临床数据提供了一个案例研究。 最后，我们在第 6 节结束我们的论文。
所有向量都是列向量。 对于任何列向量 x ∈ R n ，x 0 表示它的转置。 方阵 M 的行列式和迹分别由 det(M ) 和 tr(M ) 表示。 x 的 √ √ 欧几里得范数和加权范数分别表示为 k x k = x 0 x 和 k x k M = x 0 M x。 此外，I 表示单位矩阵。 对于对称正定矩阵 V ，我们将 λ min 定义为 V 的最小特征值。 我们使用 1 (·) 作为指标函数。
在本节中，我们首先为一般在线资源分配问题正式定义我们的框架。 然后，我们针对在线提前调度问题定制我们的框架，这是我们针对多天调度的通用框架的应用，并且具有更精细的结构。
我们在我们的模型中做了三个假设：（i）客户上下文的序列是未知的（上下文向量不一定来自固定分布）并且被一个不经意的对手挑选，这是一个选择客户序列的非自适应对手 预先设置上下文，(ii) 与线性模型的客户-资源 (customer-server) 匹配质量随时间推移是随机且固定的，并且它具有应自适应学习的未知模型参数，以及 (iii) 资源消耗（服务 time) 是随机的并且遵循未知分布，其平均值可能取决于客户的上下文。 为了简化表示并减少繁琐的符号，我们假设客户的平均资源消耗在到达时是已知的。 请注意，这个假设不是必需的，可以通过推论 2 删除。
2.1 一般在线资源分配
考虑一个长度为 L 的有限规划范围。我们定义 L = { 1, . . . , L } 作为天的集合，K = { 1, . . . , K } 作为资源集。 对于每个资源 k，在所考虑的计划范围内，有 C k 个不可补充的可用产能单位。 令 M = { 1, . . . , M } 是在 ∈ L 天顺序到达的顾客集合。 每个客户都与一个包含客户信息的上下文 d 向量相关联。 设 φ X i () ∈ R 为第 i 个客户在第 天的上下文向量，φ A k () 为对应于 0 0 0 0 A 资源 k 的选择的 K 维动作向量，即 , φ k () = ( 1 k=1 , . . . . , 1 k=K ) 。 我们定义 φ ik () = φ i X (), φ k A () 为特征向量，A 将上下文向量 φ X i () 和动作向量 φ k () 连接起来。 请注意，我们的模型可以轻松扩展到使用已知特征映射将任何动作-上下文对映射到 d 维特征向量的设置。
动力学 分配决策以在线方式做出，这样客户在到达时就得到处理，而无需知道客户上下文的未来顺序。 在第 i 个客户在第 天到达时，系统会显示上下文 φ X i ()。 然后，必须将客户分配给可用资源 k ∈ K，或者根据显示的上下文 φ X i () 和截至当前时间的可用观察结果拒绝客户。 如果此客户被分配到资源 k，它将消耗 C k 中的 S ik () 单位容量。 对的依赖仅用于将客户i与到达日配对，资源消耗量不依赖于到达日（匹配质量类似，如下）。 最后，系统观察奖励取决于客户资源匹配质量 Q ik () 和资源消耗 S ik ()。 匹配质量反馈的接收延迟可以是任意时间量。 我们的表现分析只需要存在反馈延迟的上限。 我们假设，当客户被分配到资源时，如果没有足够的容量，客户仍然得到充分的服务，但系统只收到与资源消耗成比例的一小部分奖励，不超过可用资源容量。
建模奖励和资源消耗 鉴于客户被分配到资源，奖励取决于两个组成部分：（i）客户资源匹配质量（每单位资源消耗）和（ii）资源消耗。 下面对两个主要组件进行建模。
客户-资源匹配质量：第 i 个客户在第 天选择资源 k ∈ K 会产生以下随机匹配质量：
()
其中 w ∈ R d+K 是未知模型参数，Q ik () ∈ [0, c Q ]。 噪声值 ξ ik () 是独立的 σ ξ -sub-Gaussian 随机变量，均值为零（参见定义 1）。
2 2 定义 1. 如果 E[e tξ ] ≤ e σ ξ t /2 , ∀ t ∈ R，则实值随机变量 ξ 为 σ ξ -sub-Gaussian。
这个定义意味着 E[ξ] = 0 和 Var[ξ] ≤ σ ξ 2 。 许多分布是亚高斯分布，包括任何有界和中心分布，以及高斯分布。
资源消耗：我们的系统模型还考虑了随机资源消耗值。
如果在日为第 i 个客户选择资源 k ∈ K，则客户使用该资源的 S ik () 单位，而不管。 我们假设 S ik () 是一个随机资源消耗，已知期望值 s ik () = E[ S ik ()] ≤ c s 。 噪声值 η ik () = S ik () − s ik () 是独立的 σ η -sub-Gaussian 随机变量，均值为零。 请注意，为了减少繁琐的符号，我们假设已知的预期资源消耗（到达时）。 这个假设是不必要的，可以通过推论 2 删除。
因此，分配给资源 k 的第 i 个客户在第 天的期望奖励为
()
我们假设客户-资源匹配质量与资源消耗无关。 尽管有人可以争辩说匹配质量可能会影响服务时间，但这种独立性假设在许多应用中是合理的。 例如，在实践中，医院和诊所通常以不依赖于提供者的方式设置程序的预约时长，我们的奖励模型可以捕捉到这一点。
我们一般在线资源分配问题的目标是在 L 天内最大化总预期奖励。 这可以被视为最大化由预期资源加权的预期匹配质量（例如，参见 Morton 和 Wood 1998 以及 Van Slyke 和 Young 2000）消费（例如，参见 Stein 等人 2019 和 Mehta 等人 2005）。 出于技术原因，让 H i 表示第 i 个客户在第 1 天到达时可用的历史记录，包括上下文向量、操作和已实现的反馈结果。 令 M̄ 为每天最大到达次数的上限，Δ 为实现比赛质量反馈所需的最大天数。 为了简化符号，我们让 q ik () 和 r ik () 分别表示 h φ ik ()、wi 和 h φ ik ()、wi s ik ()。 令 k(i, ) 为第 i 个客户在第 天选择的资源，当索引 (i, ) 很明显时，我们通常将其写为 k ∗。 不失一般性，我们假设 k w k ≤ 1 和 k φ ik () k ≤ c φ 。
2.2 在线提前排班：更精细的模式
在线提前调度可以看作是我们通用框架的应用。 我们的一般资源分配和提前调度问题之间的主要区别在于后者提供多天调度并捕获客户的未出现行为。 在多天调度的提前调度问题中，关于资源的易腐性，还有一层额外的复杂性。 特别是剩余容量可以存储起来，以后在一般的资源分配问题中使用； 但是，容量（即服务器的可用性）在提前调度问题中是易损的，并且当天剩余的服务器可用性不能转移到第二天。
考虑一个长度为 L 的调度范围。我们定义 L = { 1, . . . , L } 作为天的集合，并且 K = { 1, . . . , K } 作为服务器集。 令 M = { 1, . . . , M } 是在 ∈ L 天顺序到达的顾客集合。 每个客户都与到达时向系统显示的上下文向量（例如，紧急程度、请求类型和人口统计）相关联。 设 φ X i () ∈ R 是第 i 个客户在第 天的上下文向量。 如果接受客户，则必须将客户分配到 (i) 服务器 k ∈ K 和 (ii) 未来服务日期 t ∈ L{ 1 } 。 我们使用两个索引 ∈ L 和 t ∈ L{ 1 } 来指代调度范围内的一天，但索引 指的是客户到达日，索引 t 指的是计划日期。 我们定义一个服务器-日期对 (k, t) 来指代服务器 k 和为客户选择的服务日期 t。 对于每一天 t ∈ L{ 1 } ，每个服务器 k ∈ K 都有一个有限的容量 C kt ，它明确地允许容量每天变化。 设 φ A kt () 是对应于服务器 k 的选择和服务延迟 t - 的 A 维动作向量，其中还可能包含有关所选服务器的上下文 0 0 0 信息。 我们定义 φ ikt () = φ i X (), φ kt A () 为特征向量，A 将上下文向量 φ X i () 和动作向量 φ kt () 连接起来。
动力学在第 i 个客户在第天到达时，系统会显示上下文 φ X i ()。
然后，必须将客户分配给一个可用的服务器日期 (k, t)，使得 t ≥ + 1 或根据显示的上下文向量 φ X i () 和截至当前时间的观察结果被拒绝。
我们假设客户不会取消预定的服务，但他们可能不会出现在服务日期。 如果客户出现，C kt 中服务器可用性的 S ikt () 单位被占用，系统会延迟观察两个反馈结果（即未出现结果和匹配质量）。 如果客户没有出现，系统将无法观察匹配质量反馈。
反馈延迟可以等于服务延迟，但我们的方法允许额外的反馈处理时间。 为了保持建模的通用性，我们假设反馈结果的延迟可能大于服务延迟，但它有一个上限。 我们假设，如果客户出现在预定的服务中时没有足够的容量，客户仍然可以得到充分的服务，但系统只会收到与服务时间成比例的一小部分奖励，不超过服务器的可用性。
建模奖励和服务时间 假设客户被分配到服务器日期 (k, t)，奖励取决于三个组成部分：(i) 未出现结果，(ii) 客户-服务器匹配质量（每单位服务时间），以及（ iii) 服务时间。 下面对三个主要组件进行建模。
未出现：我们使用二进制变量 SU i () 考虑未出现，其中 SU i () = 1 表示第 i 个客户在当天出现在服务日期。 我们假设 E[ SU i ()] = p 是未知的，其中 p 表示客户在服务日期出现的概率。 噪声值 i () = SU i () − p 是均值为零的独立伯努利随机变量。
请注意，我们的模型和算法适用于没有取消或取消率低的系统。 但是，当取消概率已知时，它们可以很容易地扩展以捕获取消行为。
客户-服务器匹配质量：如果系统在第 天将第 i 个客户分配给服务器 k ∈ K 并且该客户出现，则它产生随机匹配质量 Q ikt () = h φ ikt (), w i + ξ ikt ()，其中 w ∈ R d+A 是未知模型参数，Q ikt () ∈ [0, c Q ]。 噪声值 ξ ikt () 是独立的 σ ξ -sub-Gaussian 随机变量，均值为零。
服务时间：我们的框架还考虑了随机服务时间。 如果在第 天为第 i 个客户选择服务器 k ∈ K 并且该客户出现了，它会产生一个随机服务时间 S ikt ()，期望值为 s ikt () = E S ikt () ≤ c 秒。 噪声值 η ikt () = S ikt () − s ikt () 是具有零均值的独立 σ η -sub-Gaussian 随机变量。
显然，如果患者在服务日期出现，系统就会观察到奖励。 因此，分配给 server-date (k, t) 的第 i 个客户在第 天的预期奖励可以计算为：
()
我们的个性化提前调度问题的目标是在长度为 L 的有限调度范围内最大化总预期奖励。出于技术原因，让 H̄ i表示第 i 个客户在第 天到达时可用的历史记录，包括上下文 向量、动作和实现的反馈结果。 设 M̄ 是每天到达的最大数量的上限，Δ 是实现反馈所需的最大天数。 请注意，我们认为两个反馈结果的上界 ∆ 只是为了便于表示。 为了简化符号，我们让 q ikt () 和 r ikt () 分别表示 p h φ ikt ()、wi 和 p h φ ikt ()、wi s ikt ()。 令 k(i, ) 和 t(i, ) 分别为第 i 个客户在第 天选择的服务器和服务日期。
为了符号方便，当索引 (i, ) 很明显时，我们通常将它们写为 k ∗ 和 t ∗。
不失一般性，我们假设 k w k ≤ 1 和 k φ ikt () k ≤ c φ 。
首先，我们提出了针对一般资源分配问题的在线算法，称为延迟学习时的个性化资源分配 (PRA-LD)。 接下来，我们展示了针对提前调度问题量身定制的第二个在线算法，称为延迟学习时的个性化提前调度 (PAS-LD)。 在第 3.1 节和第 3.3 节中，我们描述了我们算法的高级直觉。 我们在第 3.2 节和第 3.4 节中提供了我们算法的详细步骤。
3.1 延迟学习中个性化资源配置的主要思想
在我们的一般资源分配问题中，客户每天按顺序到达，每个客户都有一组独特的特征（上下文信息）。 然后，每个客户要么被分配到可用资源 k ∈ K，要么被拒绝。 回想一下，每个资源都可以在计划范围内的任何一天使用。 如果我们知道未知的模型参数 w 和客户上下文的序列 φ X = { φ X i () } ∈L,i∈M ，我们可以通过提前求解以下离线优化模型来为客户分配资源。
(1、2、3、4)
其中 x ik () 对应于在第 天将第 i 个客户分配给资源 k。 目标函数 (1) 是最大化总期望奖励。 约束 (2) 确保客户分配给每个资源的预期资源消耗值的总和不超过容量。 约束 (3) 确保不会为每个客户分配多个资源。
然而，我们事先既不知道与匹配质量相关的未知模型参数 w，也不知道客户上下文的顺序。 实际上，我们需要了解分布未知的模型参数，因为客户每天按顺序到达。 因此，我们设计了一种在线算法，该算法同时学习未知模型参数的分布，并在不知道以对抗方式选择的客户上下文的未来顺序的情况下明智地做出在线资源分配决策。 PRA-LD 算法利用上下文学习和在线资源分配技术来克服这些障碍并提供个性化的决策。
PRA-LD 算法有四个主要步骤。 通过第一步和第二步，该算法为每个到达客户的预期奖励提供了个性化的估计。 该估计取决于未知模型参数，该未知模型参数应基于截至当前时间的可用观测值迭代学习。 在这里，勘探与开发的权衡是一项重大挑战。 例如，根据我们在规划期早期的不确定估计，我们可能错误地得出结论，特定资源对于具有某些特征的客户来说不是一个好的选择，因此，我们可能无法识别这种错误信念 无需为非常相似的客户做出不同的分配决定。 受后验采样 (PS) 思想的启发，我们的算法计算未知模型参数的后验分布，然后从后验分布中抽取随机样本。 这种抽样背后的直觉是提供探索替代选择（进行探索）并平衡探索-利用权衡的机会。 在我们的算法中，我们假设未知模型参数上的高斯先验分布，但我们的理论结果与先验无关。
第三步，算法根据资源的可用容量、预期的资源消耗和样本奖励，为到达的客户分配资源或拒绝客户。 应在不假设未来客户上下文顺序的情况下做出分配决策。 如果一个策略短视地为每个客户提供了最好的分配（即贪婪策略），在某些情况下它不会产生一个健壮的解决方案。 例如，考虑这样一个场景，系统在规划范围的前半段主要接收低回报客户，而在后半段接收高回报客户。 在这种情况下，大部分可用资源可能被在计划期限的前半段到达的低回报客户所占据。 因此，由于容量有限，高回报客户要么被拒绝，要么被分配到次优资源。
为了克服这个问题，我们采用一种机制来做出在线资源分配决策，与优化模型 (1) - (4) 的自然 LP 松弛可能产生的决策相比，该决策具有良好的性能。 因此，我们的框架不仅学习了未知模型参数的分布，而且通过采用资源分配机制避免了贪婪的资源分配。
在最后一步，算法利用新实现的匹配质量反馈结果来更新未知模型参数的后验分布。 将客户分配给资源后，反馈会延迟显示。 估算器会按照我们的异步策略即时更新。 也就是说，我们使用实现的特征向量将每个客户分配给资源后更新估计器，但是一旦实现，客户反馈就会包含在更新过程中。
3.2 延迟学习时的个性化资源分配
让 (, i, k ∗ ) 是一个元组，指代分配给资源 k ∗ 的第 i 个客户。 为了更新向量 w 的后验分布，我们将 F (Q) (i, ) 定义为包含上次更新后具有实现匹配质量反馈结果的客户的元组 (s, n, k ∗ ) 的集合，其中 s ≤ 和 n < i。 我们在算法 1 中提供了 PRA-LD 的详细步骤。
Alogrithm 1
描述 首先，先验参数基于先验信念进行初始化。 L 天的每一天都有四个主要步骤。 首先，在客户到达时，从 w 的后验分布中抽取随机样本。 接下来，使用第一步获得的随机样本和实现的上下文向量获得样本奖励。 预期的资源消耗，这可以取决于客户的上下文，也可以在我们的环境中获得。 然后，每个到达的客户要么被分配到一个资源，要么被拒绝遵循由通用资源分配机制 O P RA r̃ ik (), s ik () 获得的分配决定 x ik () ，其中 x ik () = 1 表示必须将第 天的第 i 个客户分配给资源 k。 最后，我们在按照步骤 (8-14) 将客户分配给资源后更新 w 的后验分布。 请注意，我们不使用被拒绝客户的上下文向量来更新估计量。 我们的更新过程是动态的，因此估计器使用分配给资源的客户的已实现特征向量，但客户的反馈稍后在实现时包含在更新过程中。 更新方程遵循贝叶斯推理程序来更新后验分布（详见 Agrawal 和 Goyal 2013）。
资源分配机制 虽然 PRA-LD 算法旨在与许多资源分配机制一起工作，但这里我们将重点放在机制 1 作为算法 1 步骤 7 中资源分配机制的示例。特别是，我们采用了 Buchbinder 提出的 primal-dual 范式 等。 2007 年为我们的设置。 这种原始对偶范式的关键在于它维护了一组对偶变量来指导原始解，而原始解的演化决定了对偶变量的更新。 考虑优化模型 (1 - 4) 的自然 LP 松弛的对偶问题：
（）
Mechanism 1
在机制 1 中，对偶变量 y k 和 θ i () 对于 ∈ L 、 i ∈ M 、 k ∈ K 初始设置为零。
客户到达后，我们在步骤 1 中找到一个候选资源 k ∗，它使术语最大化，这是样本奖励减去分配预期容量的成本。 该术语可以被视为接受/拒绝标准，因此候选资源 k ∗ 的正值会将客户分配给该资源； 否则，客户应该被拒绝。 如果我们将客户分配给资源 k ∗ ，我们会在第 5 步中以递增方式更新对偶变量 y k ∗ 。第 5 步右侧的第一项将 y k ∗ 增加的数量与 被接受的客户使用的容量。 第二项取决于 β 和估计奖励与总容量的比率。 步骤 5 中的乘法更新方程必须确保 y k * 有足够大的增加，以防止在预期容量耗尽时接受任何最大的未来客户。 为了实现这一点，我们将 β 设置为 η Γ−1 , s ik () 其中 η max = max q̃ ik () } , Λ = max C 和 Γ = (1 + Λ) 1/Λ 。 请注意，设置 β i,k, i,k, k 的值需要知道 η max 和 Λ 的值。 虽然样本匹配质量和预期资源消耗值（如果资源消耗取决于客户的上下文）是预先未知的，但是在许多应用中可以计算出 η max 和 Λ，因为匹配质量和资源消耗值的范围是 通常由决策者选择并事先知道。 步骤 4 中对偶变量 θ i () 的更新方程确保对偶问题仍然可行。
3.3 延迟学习的个性化提前安排的主要思想
在我们的提前调度问题中，客户到达后，要么被拒绝，要么被分配到服务器和调度范围内的未来服务日期。 如果我们知道未知的模型参数（p 和 w）和客户上下文序列 φ X = { φ X i () } ∈L,i∈M ，我们可以通过求解以下离线优化模型来调度客户 调度范围的开始。
（5、6、7、8）
其中 x ikt () 对应于将第 i 个客户在 day 分配给 server-date (k, t)。 目标函数 (5) 是最大化总期望奖励。 约束 (6) 确保一天分配给服务器的客户的预期服务时间总和不超过该服务器当天的可用性。 约束 (7) 确保不分配每个客户到多个服务器日期。 请注意，到达客户的预定服务日期必须在到达日之后，即 t 应等于或大于 + 1。
在我们的在线设置中，解决上述优化模型是不可能的，因为模型参数和客户上下文的顺序是未知的。 与算法 1 不同，PASLD 算法被设计为允许不出现和多日调度的可能性。 所提出的算法有四个主要步骤。 通过第一步和第二步，该算法提供了提前调度所需的客户特定估计。 算法中使用的奖励取决于匹配的质量和未出现的概率。 为了进行探索，该算法从 pw 上的后验分布中抽取随机样本，并使用它们来获得样本奖励。 它还获得了我们设置中已知的预期服务时间。
在第三步中，算法要么将到达的客户分配给服务器日期（多天调度），要么在对客户上下文的未来序列没有假设时以在线方式拒绝客户。 与算法 1 类似，可以合并任何适合我们设置的高级调度机制。
在最后一步，该算法利用已实现的匹配质量和未出现的反馈结果来更新后验分布。 如果客户在服务日期出现，两种反馈结果都将延迟显示； 否则，只会显示未出现的反馈。
我们遵循我们的异步策略来更新估算器。
3.4 延迟学习的个性化提前安排
让 (, i, k ∗ , t ∗ ) 是一个元组，指代分配给 server-date (k ∗ , t ∗ ) 的第 天的第 i 个客户。
为了更新向量 pw 的后验分布，我们将 F (SU ,Q) (i, ) 定义为包含已实现未出现和匹配质量反馈的客户元组 (s, n, k ∗ , t ∗ ) 的集合 最后一次更新后的结果，其中 s ≤ 且 n < i。 我们在算法 2 中提供了 PAS-LD 的详细步骤。
描述 先验参数可以基于先验信念进行初始化。 该算法进行了 L 天。 与算法 1 不同，样本奖励应该通过考虑未出现的概率来获得。 决策变量 x ikt () 是通过一般的提前调度机制 O P AS r̃ ikt (), s ikt () 得到的，其中 x ikt () = 1 表示第 i 个客户在当天一定是 分配给服务器日期（k，t）。 估计量在算法中的步骤 (8-14) 之后更新。
提前调度机制 作为算法 2 步骤 7 中的提前调度机制的一个例子，我们关注机制 2，它是机制 1 的修改版本，适用于多日调度。 该机制是基于原始对偶范式设计的，该范式维护一组对偶变量来指导原始解决方案。 考虑优化模型 (5 − 8) 的自然 LP 松弛的对偶问题：
Alogrithm 2
（）
其中 y kt 和 θ i () 是分别对应于约束 (6) 和 (7) 的对偶变量。
在机制 2 中，对偶变量 y kt 和 θ i () 对于 ∈ L , i ∈ M , k ∈ K , t ≥ + 1 初始设置为零。直觉类似于机制 1。到达时 对于客户，我们在步骤 1 中找到一个使该术语最大化的候选服务器日期 (k ∗ , t ∗ )。请注意，我们只搜索 t ≥ + 1 以确保该客户的候选服务日期在 到达日。 步骤 2 中的术语可以被视为接受/拒绝标准，这样候选人 (k * , t * ) 的正值会将客户分配到此服务器日期； 否则，客户应该被拒绝。 如果我们将客户分配给服务器日期 (k ∗ , t ∗ )，我们会在步骤 5 中以递增方式更新对偶变量 y k ∗ t ∗ 以确保容量约束保持在 max e = max s ikt () 和 Γ e = (1 + Λ) e 1/ Λ e 。 , 其中 η e max = max q̃ ikt () } , Λ 期望值。 我们设置 β e = ( η e Γ−1) e C i,k,t, i,k,t, kt 注意，步骤 4 中对偶变量 θ i (`) 的更新方程确保对偶变量 θ i ()问题仍然可行。
Mechanism 2
我们使用贝叶斯遗憾的概念推导出 PRA-LD 和 PAS-LD 算法的非渐近（即有限时间）性能保证。 我们首先在第 4.1 节中讨论性能度量和辅助问题。 然后我们定义基准并在第 4.2 节中陈述主要的理论结果。 最后，我们讨论了我们的结果并将它们放置在第 4.3 节的相关文献中。
4.1 绩效测量和辅助问题
性能指标 我们根据贝叶斯遗憾评估我们算法的性能，这是文献中的标准指标（例如，参见 Rusmevichientong 和 Tsitsiklis 2010 以及 Russo 和 Van Roy 2014）。 这个度量被称为贝叶斯后悔，因为它代表贝叶斯风险。 算法的遗憾衡量相对于基准的累积损失，算法的贝叶斯遗憾只是对未知模型参数的先验分布的预期遗憾。 贝叶斯遗憾有两个主要优点：（i）它允许对未知模型参数进行任意先验分布，以及（ii）它在基于 PS 和基于 UCB 的方法之间建立了联系，这提供了利用一些 基于 UCB 的方法在推导贝叶斯遗憾时的吸引人的理论特性。
定义 2（遗憾和贝叶斯遗憾）。 给定未知的模型参数 ϑ，长度为 L 的规划范围内的遗憾定义为
（）
其中 OF V π 和 OF V ALG 分别是最优策略和在线算法获得的总奖励。 条件期望取代给定 ϑ 的随机实现（例如，奖励和资源消耗值的实现），以及在线算法中可能的随机化（例如，随机样本）。
长度为 L 的规划范围内的贝叶斯后悔定义为
（）
其中期望取代了 ϑ 的先验分布。
辅助问题 定义一个辅助问题并引入一种桥接技术，我们提供了一种使用个性化学习算法分析在线资源分配性能的通用方法。 这允许无缝集成在线资源分配算法的竞争比率界限和上下文学习算法的贝叶斯后悔界限。 辅助问题可以正式定义为在线资源分配问题，其中客户按顺序到达，并且应分配可用资源以对冲未来客户的对抗性到达顺序。 原始问题和辅助问题的主要区别在于模型参数是后者已知的，与前者不同。 值得注意的是，Cheung 等人最近的研究中引入了辅助问题的概念。 2022 年，通过学习推导出资源分配的信息理论下限。 然而，Cheung 等人定义的辅助问题。 2022 年不同于我们在分析中定义和使用的那个。 他们的辅助问题只关注勘探开发权衡，假设没有资源限制。 因此，它可以被视为一个上下文老虎机问题。 相反，我们的辅助问题只关注在线资源分配，假设模型参数已知。 由于我们正在处理不同的辅助问题，因此需要不同的桥接技术来导出我们算法的贝叶斯遗憾。
我们定义了对应于一般资源分配和提前调度问题的两个辅助问题。 在第一个辅助问题中，当客户到达时，客户的预期匹配质量和预期资源消耗是已知的。 然后，应该使用一种保证容量限制符合预期的机制做出决定（将客户分配给资源或拒绝客户）。 对应于我们的提前调度问题的第二个辅助问题可以类似地定义，使得在这个问题中，当客户到达时，预期的匹配质量、未出现的概率和预期的服务时间是已知的。 为了在我们的定理中保持结果的一般性，我们用一般机制为我们的算法推导出理论性能保证； 但推论提供了有关特定机制的性能保证。
4.2 提议的在线算法的性能
首先，我们在第 4.2.1 节中定义了 PRA-LD 算法的基准，并在第 4.2.2 节中提供了证明其主要理论结果（定理 1）的路线图。 接下来，我们在第 4.2.3 节中为 PAS-LD 算法定义了另一个基准，并在第 4.2.4 节中提供了证明其主要理论结果（定理 2）的路线图。 我们还提供了 PRA-LD 和 PAS-LD 在采用推论 1 和 3 中的原始双资源分配机制时的理论结果。
4.2.1 PRA-LD 算法的基准
我们需要定义一个基准来评估我们的 PRA-LD 算法的性能。 由于我们的一般资源分配问题包含在线学习和在线资源分配任务，因此基准在这两个任务方面应该是千里眼的。 预先知道未知模型参数 w、客户上下文序列以及奖励和资源消耗值的实现的离线最优基准太强大而无法与之竞争。 另一种选择是最优在线透视策略，它知道模型参数和客户上下文的顺序，但不知道奖励和资源消耗值的实现。 相反，我们引入了一个更强大的基于离线 LP 的基准，它可以访问与透视策略相同的信息，但只需要满足预期的容量限制，而不是所有实现。 特别是，我们基于离线 LP 的基准是对最优在线透视策略的放宽，仅要求容量约束保持在预期中。 基于离线 LP 的基准通常用于最近的在线资源分配问题文献中（例如，Golrezaei 等人 2014、Gong 等人 2021 和 Feng 等人 2020）。 我们基于离线 LP 的基准有两个主要优点：（i）正如我们将展示的，它提供了透视策略的预期总回报的上限，（ii）它自然地提供了结合原始对偶基准的机会 我们在线算法中的资源分配机制。
为了评估 PRA-LD 算法的性能，我们制定了基于离线 LP 的 benchmark-I，它知道未知模型参数 w 和客户上下文序列 φ X = { φ X i () } ∈L,i ∈M 并且仅在期望中满足容量约束。
（）
在引理 1（见附录 C）中，我们正式证明了透视策略的预期总奖励是上述基于 LP 的基准的上限。
4.2.2 PRA-LD 算法的贝叶斯遗憾
我们陈述了 PRA-LD 算法的主要理论结果。
定理 1（PRA-LD 的贝叶斯遗憾） PRA-LD 算法在长度为 L 的规划范围内的贝叶斯遗憾是有上限的，概率至少为 1 - 2δ，如下所示：
（）
其中 M̄ 是每天到达的最大数量的上限，Δ 是实现反馈所需的最大天数。 此外，V BM 1 是基于 LP 的 benchmark-I 的总预期回报，E[V BM 1 ] 是 V BM 1 在未知模型参数的先验分布上的预期值。 术语 α 对应于对冲客户上下文的对抗性到达，它是算法中包含的资源分配机制的恒定/预期竞争比率。 也就是说，将 V AU X 1 定义为解决辅助问题的机制获得的总期望奖励，我们有 V AU X 1 /V BM 1 ≥ α。
推论 1（使用机制 1 对 PRA-LD 的贝叶斯遗憾）。 当 δ = 1 时，采用机制 1 的 PRA-LD 算法在长度为 L 的规划范围内的贝叶斯遗憾 N L 如下：
（）
其中 ρ = E[ 1−η 1+β ], η max = max { q ik () } , Λ = max i,k, i,k, s ik () C k , Γ = ( 1 + Λ) 1/Λ 和 β = η max 。
Γ-1 当 Λ → 0 且 η max → 1 时，则系数 β → 1/(e - 1)。 因此，上述比率收敛到 1 - 1/e，这恢复了原始对偶范式中的经典结果。
虽然在定理 1 中推导出的贝叶斯后悔为具有一般资源分配机制的 PRA-LD 提供了性能保证，但这个推论将结果调整为机制 1。证明取决于机制 1 的竞争比率（见附录 C 中的命题 8） 以及定理 1 的结果，其中 δ = 1/N L 。 为简洁起见省略了证明。
推论 2（具有未知平均资源消耗的 PRA-LD 的贝叶斯遗憾）。
当 δ = 1 时，在长度 L 的规划范围内学习匹配质量和资源消耗时，PRA-LD 算法的贝叶斯遗憾 N L 如下：
（）
虽然在定理 1 中导出的贝叶斯遗憾为 PRA-LD 提供了在客户到达时具有已知平均资源消耗的性能保证，但该推论将结果定制为应该学习匹配质量和资源消耗的设置。 我们假设以下资源消耗模型：如果在第 天为第 i 个客户选择资源 k ∈ K，则客户使用该资源的 S ik () 单位，而不管。 我们假设 S ik () ∈ [c S , c S ] 是遵循具有期望值的线性模型的随机资源消耗：
（）
其中 z ∈ R d+K 是未知模型参数。 噪声值 η ik (） = S ik () − h φ ik (), z i 是独立的 σ η -sub-Gaussian 随机变量。
当应该学习未知模型参数 z 时，证明取决于惩罚损失的新高概率界限。 按照定理 1 中的相同步骤和 δ = 1/N L ，可以证明与随机奖励相关的损失（第一部分）具有 √ O (d + K) N L log N L + ( d + K) M̄ ∆ log N L 。 当随机资源消耗有一个未知参数的模型时，我们证明惩罚损失（第二部分）的量级为 √ O (d + K) N L log N L + (d + K) M̄ ∆ log N L （见附录 A 中的提案 4）。 正如预期的那样，与平均资源消耗为 √ 已知（即 O (K N L log N L )）时的惩罚损失相比，这种惩罚损失更高； 但是，它与随机奖励相关的损失具有相同的顺序。 因此，贝叶斯遗憾的顺序与平均资源消耗已知时的顺序相同。 为简洁起见省略了证明。
定理 1 的证明：为了获得贝叶斯遗憾，我们首先定义以下符号：
（9、10、11）
其中，上述三项分别表示（i）基于 LP 的 benchmark-I，它预先知道模型参数 w 以及客户上下文的序列 ϕX，（ii）资源分配机制获得的总期望奖励 用于解决辅助问题，它知道模型参数 w 但不知道客户上下文 φ X 的顺序，以及 (iii) PRA-LD 算法（忽略下面的惩罚项），它不知道模型参数 w 和 客户上下文 φ X 的序列。
我们应该注意到，资源消耗是随机的，PRA-LD 算法仅在预期中强制执行容量约束。 因此，在某些情况下可能会超出资源容量（详见附录 A 中的命题 3）。 我们对超过资源容量的分配容量施加惩罚，并将其称为 PenaltyLoss-I。 因此，可以使用以下桥接技术计算 PRA-LD 的贝叶斯遗憾：
（12）
其中第一项是与学习与客户匹配质量相关的未知模型参数分布相关的上下文学习损失。 第二项是用于解决辅助问题的资源分配机制的最优差距。 最后一项可以看作是与资源消耗的不确定性相关的损失。
在下文中，我们分别对 (12) 中的三个项进行约束。
第一部分（与随机奖励相关的损失） 根据 (10) 和 (11) 中 V AU X 1 和 V ALG 1 的定义，我们有：
（）
上述项极有可能受到命题 2 的结果的限制（见附录 A）。
对于任何 δ > 0，以下概率至少为 1 - δ。
（）
第二部分（与随机资源消耗相关的损失） 预期惩罚损失可以计算如下：
（）
其中 c Q 是匹配质量的最大可能值。
上述项极有可能受到命题 3 的结果的限制（见附录 A）。 对于任何 δ > 0，以下概率至少为 1 - δ。
（）
第三部分（与在线资源分配相关的损失） 回想一下，辅助问题是实际问题的更简单版本，其中未知模型参数 w 是预先知道的。 要解决辅助问题，必须采用一种资源分配机制，其中存在最优性差距。 假设α是PRA-LD的资源分配机制的恒定竞争比率。 然后，给定未知的模型参数 w，我们有 V AU X 1 /V BM 1 ≥ α。 接下来，我们通过一个简单的代数得到以下内容：
（）
对两边 w 的先验分布取期望值，我们得到：
（）
请注意，如果竞争比率 α 取决于模型参数，则上述结果通过将 α 替换为模型参数的先验分布上的预期值来成立。
根据(12)，将第一部分、第二部分和第三部分建立的上界相加即可完成证明。
4.2.3 PAS-LD 算法的基准
我们的提前调度问题和一般资源分配问题之间存在三个主要区别。 首先，我们将客户安排在多天的服务器上，而不是仅将客户分配到资源。 其次，一些客户可能不会在服务日期出现。 最后，与许多服务应用程序类似，资源（服务器的可用性）是易腐烂的。 也就是说，与一般资源分配问题中的全局资源约束不同，当天服务器剩余的可用性不能转移到第二天。 因此，需要一个不同的基准来评估 PAS-LD 算法的性能。
与我们为一般资源分配问题所争论的类似，一个可能的基准是最优的在线透视策略，它知道未知的模型参数和客户上下文的顺序，但不知道奖励和服务时间的实现。 我们采用了一个更强大的基于离线 LP 的基准，它可以访问与千里眼策略已知的相同信息，但只需要满足预期的容量限制。 我们称其为基于离线 LP 的 benchmark-II (LP 2 [φ X , p, w])，它是优化模型 (5) - (8) 的自然 LP 松弛，其中 x ikt ()≥ 0。
根据我们在引理 1 中的论点（见附录 C），可以证明透视策略的预期总回报是基于 LP 的 benchmark-II 的上限。 我们使用这个 LP 模型作为我们的基准来评估 PAS-LD 算法的性能。
4.2.4 PAS-LD 算法的贝叶斯遗憾
在定理 2 和推论 3 中，我们陈述了 PAS-LD 算法的主要理论结果。
定理 2（PAS-LD 的贝叶斯遗憾） PAS-LD 算法在长度为 L 的调度范围内的贝叶斯遗憾是有上限的，概率至少为 1 - 3δ，如下所示：
（）
在这个上限中，N L 是 L 天内到达的总人数，E(L, δ) 的阶数为
（）
其中 M̄ 是每天到达的最大数量的上限，Δ 是实现反馈所需的最大天数。 此外，V BM 2 是基于 LP 的 benchmark-II 的总期望回报，E[V BM 2 ] 是 V BM 2 在未知模型参数的先验分布上的期望值。 α 是算法中包含的提前调度机制的常数/预期竞争比。
推论 3（具有机制 2 的 PAS-LD 的贝叶斯遗憾） 当 δ = 1 时，采用机制 2 的 PAS-LD 算法在长度为 L 的调度范围内的贝叶斯遗憾 N L 如下：
（）
其中 ρ e = E[ 1−e e max = max { q ikt () } , Λ e ], η 1+ β i,k,t, e = (1 + Λ) e 1/ Λ e 和 β e = , Γ η e 最大值。
e Γ-1 当 e → 0 且 η e max → 1 时，则系数 β e → 1/(e - 1)。 因此，上述比率收敛到 1 - 1/e。
Λ 证明取决于机制 2 的竞争比（见附录 C 中的命题 9）和定理 2 的结果，δ = 1/N L 。 机制 2 的竞争比的证明可以通过处理 LP 2 [φ X , p, w] 的对偶问题而不是命题 8 中的 LP 1 [φ X , w] 来重现（见附录 C）。 为简洁起见省略了证明。
定理 2 的证明：为了获得我们的 PAS-LD 算法的贝叶斯遗憾，首先我们定义以下符号：
（13、14、15）
其中，上述三项分别表示（i）基于 LP 的 benchmark-II 获得的总期望奖励，它预先知道未知的模型参数 p 和 w 以及客户上下文 φ X 的序列，（ii）提前调度 解决辅助问题的机制，它知道未知的模型参数但不知道客户上下文的顺序，以及（iii）PAS-LD算法（忽略下面的惩罚项），它不知道未知的模型参数和 客户上下文的顺序。
我们应该注意到，服务时间是随机的，PAS-LD 算法仅在预期中强制执行容量约束。 因此，在某些情况下可能会超出服务器的可用性。 我们对超出服务器可用性的分配容量施加惩罚，并将其称为 PenaltyLoss-II。 因此，可以使用以下桥接技术计算贝叶斯遗憾：
（16）
其中第一项是与学习未知模型参数分布相关的上下文学习损失，第二项是用于解决辅助问题的提前调度机制的最优性差距，最后一项是与不确定性相关的损失 服务时间。
下面，我们分别对（16）中的三个项进行约束。
第一部分（与随机奖励相关的损失） 根据 (14) 和 (15) 中 V AU X 2 和 V ALG 2 的定义，我们有：
（）
根据命题 6 的结果（见附录 B），上述项可以高概率地有界。 对于任何 δ > 0，以下成立的概率至少为 1 - 2δ。
（）
第二部分（与随机服务时间相关的损失） 我们假设如果客户没有在服务日期出现，服务器的可用性仍然会降低客户的预期服务时间。 因此，预期的惩罚损失可以计算如下：
（）
根据命题 7 的结果（见附录 B），上述项可以高概率地有界。 对于任何 δ > 0，以下概率至少为 1 - δ。
（）
第三部分（与在线提前计划相关的损失） 辅助问题是实际问题的更简单版本，其中未知模型参数 p 和 w 是预先已知的。 解决辅助问题，需要提前调度机制。
与定理 1 的第三部分类似，这种解决辅助问题的机制的最优性差距可以使用竞争比率的概念来界定如下：
4.3 主要结果的讨论
我们讨论了我们的理论结果并将它们放在文献中。
首先，作为遗憾分析的副产品，我们在有界延迟反馈下为线性模型中的未知参数开发了一个新的置信界。 延迟反馈的影响 与其他设置相比，文献中对上下文强盗的探索要少得多，但我们注意到 Dudik 等人的研究。 2011（固定延迟）和 Zhou 等人。 2019 年（有界延迟）。
后者研究了一个带有延迟的 GLM bandit，并提出了带有预热期和非正则化 MLE 的延迟 UCB 算法。 当延迟只有一个上限时，他们 √ √ 建立了 Õ (d + dD max ) T 的遗憾界限，其中 D max 是延迟的上限，d 是特征维度。 对于 Zhou 等人研究的上下文老虎机问题。 2019 年，当奖励模型是线性且反馈延迟有界时，我们使用正则化的 OLS 估计器构建的置信界 √ 产生了 Õ d T + dD max 的遗憾界。 类似于 Zhou 等人的遗憾界。 2019 年，我们后悔界限的第一项不取决于延迟，延迟的上限仅影响第二项。 请注意，他们的遗憾 √ √ bound Õ (d + dD max ) T 是在 dD max ≤ T 的隐含假设下获得的。 在这个假设下，我们的遗憾界比 Zhou 等人得出的更严格。 2019 年。
在我们的提前安排问题中，客户在被分配到服务器和服务日期后可能不会出现在预定的服务中。 这增加了学习匹配质量的额外复杂性，因为如果客户没有在服务日期出现，则根本无法观察到客户的匹配质量反馈。 我们的 PAS-LD 算法学习 pw 向量的分布，其中 p 和 w 是对应于 noshow 和匹配质量的未知模型参数。 我们开发了一个 pw 估计器，并为延迟反馈下的 pw 提供了一个新的置信区间。 与为 w 导出的置信区间相比，此置信区间在到达次数中具有额外的附加对数项，可以将其视为估计 pw 而不是 w 的成本。
接下来，我们将涉及具有资源限制的上下文 MAB 的文献。 在这方面，巴达尼迪尤鲁等人的研究。 2014 年，Agrawal 和 Devanur 2016 年，以及 Agrawal 等人。 2016 年与我们的工作密切相关。 然而，他们的在线算法无法扩展到我们的设置，因为他们对客户上下文向量的 IID 假设导致存在底层（固定）最优随机分配策略。 张等人。 2022 年考虑了在没有 IID 假设的情况下，随着时间的推移将有限资源分配给异构客户。 在他们的环境中，奖励是已知的，并且应该随着时间的推移了解与每种客户类型和行为相关的资源消耗分布。 他们提供了一个信息论下限，该下限取决于预言机在解决类似于我们的辅助问题的问题时的竞争比率。 他们的方法和技术不同，无法与我们的工作相提并论。 我们的在线算法在不需要 IID 假设的情况下承认贝叶斯后悔上限。 我们的贝叶斯遗憾界限表明，与学习未知模型参数的分布相关的上下文学习损失在规划范围内的到达数量中是次线性的。 与不确定性相关的损失资源消耗值在规划范围内的到达数量上也是次线性的。
在我们的设置中，客户上下文的顺序是对抗性的，它的代价是使 (1 - α) E[V BM ] 项在界限内。 这一项确实是竞争比为 α 的资源分配机制解决辅助问题的最优差距。
在 PRA-LD 算法中，与带延迟的上下文学习相关的损失为 √ O (d + K) N L log(N L ) + (d + K) M̄ ∆ log(N L ) ，可以进一步分解为 两个术语。
√ 第一项 O (d + K) N L log(N L ) 与上下文学习问题的最先进的后悔界具有相同的阶数，第二项 O (d + K) M̄ ∆ log(N L ) 来自有界延迟反馈的假设。 与资源 p 消耗值的不确定性相关的损失为 O K N L log(N L ) 数量级。 此外，与最优性 max Λ E[V BM 1 ] 相关的损失，其中 η max = max { q ik () } , Λ = max s ik C () ，机制 1 的间隙为 1 − E 1−η 1+β i,k, Γ = (1 + Λ) 1/Λ 和 β = η max 。 Γ-1 从不同的角度来看，1-η max Λ 1+β i,k, k 可以看作是机制一的在线资源分配竞争比。 当 η max 趋于 1 且每个请求的预期资源消耗与总容量 Λ 的比率趋于 0 时，参数 β = η max Γ-1 趋于 1/(e - 1)，因为 Γ = (1 + Λ) 1 /Λ; 随后，竞争比收敛到 1-1/e，恢复了 Mehta 等人获得的经典结果。 2005 年和 Buchbinder 等人。 2007. 同样的论点和解释也适用于为 PAS-LD 导出的贝叶斯遗憾界。
我们的模型和方法受到医疗保健行业新兴技术的推动，旨在为患者提供在线提前安排。 在线学习有助于成功适应新方法并支持学习患者偏好。 我们的方法可以根据患者的需求和偏好提供个性化的预约访问，从而增加获得及时和适当的高质量护理的机会。 使用来自合作伙伴健康系统的临床数据，我们评估了我们提出的 PAS-LD 算法与其他算法/策略相比的性能。
5.1 数据描述和问题表述
数据说明 我们的合作伙伴健康系统提供预约访问，以提供诊断、咨询和多种程序，包括前列腺癌、显微泌尿外科、肾结石/癌症和膀胱癌。 医疗诊所配备了具有五个主要专业的医师 (MD) 和医师助理 (PA)：(i) 普通科，(ii) 男科 (Andro)，(iii) 肿瘤科 (Onco)，(iv) 内窥镜检查 (Endo)， (v) 神经泌尿科和骨盆重建手术 (NPR)。
我们使用了与 12 名提供者（即 8 名 MD 和 4 名 PA）相关的患者预约，每周 5 天从上午 8:00 到下午 5:00 在同一医疗诊所工作。
Figure 1
我们的临床数据集包含超过 4500 次预约就诊，我们有关于患者和提供者的信息。 每次就诊提供：(1) 年龄，(2) 患者的主诉（服务请求），(3) 患者的紧急程度（紧急、紧急、选择性），(4) 到达日期和提供预约延迟的预定日期，( 5) 服务时间/持续时间，(6) 患者的提供者，以及 (7) 提供者的证书 (MD/PA)。 我们选择了几个重要的变量，可分为以下两大类： • 患者特征：人口统计、服务类型请求（General、Andro、Onco、Endo 和 NPR）和紧急程度（Emergent、Urgent、Elective）， • 提供者技能：相关专业的证书 (MD/PA) 和专业知识水平。
由于当时没有对医疗诊所提供者的专业知识进行评分的系统，我们使用判断来创建一个。 咨询诊所并考虑每个提供者的主要和子专科，我们为每个提供者的相关五个主要专科分配了一个介于 0 和 1 之间的值。 在某些情况下，可以使用提供者对患者的评分来计算此信息。 未出现事件被建模为独立的伯努利试验。
正如我们所提到的，医疗诊所为有五项主要服务请求的患者提供预约访问。 我们的数据表明，患者在不同日期的到达模式存在很大差异。 例如，图 1 显示了每天收到 NPR 服务请求的患者数量。可以看出，到达模式是高度不确定的，同样的不确定性也适用于接受其他服务的患者的到达模式 要求。 因此，不需要关于到达或模式随时间分布的信息的数据驱动在线算法直观地优于传统方法。
问题表述 我们使用我们的提前安排框架来制定这个患者预约安排问题。 我们不对未来的到来做任何假设。 抵达后患者，应为患者分配提供者和预约日期，否则必须拒绝患者。 患者奖励取决于患者与提供者的匹配质量、服务时间和未出现的结果。 匹配质量可以通过患者满意度调查来获得，以更好地满足患者的需求。 值得注意的是，紧急、紧急和择期患者的优先类别（紧急级别）与预约延迟相结合，为更紧急的患者提供了间接减少访问延迟的机会。
为患者分配提供者日期的主要考虑因素是诊所的可用容量、预期的患者特定服务时间和预期的患者特定匹配质量。 为了计算预期的服务时间，我们需要有关患者特征和提供者技能的信息。 预期匹配质量还需要第三个要素，即预约延迟（即到达日期和预约日期之间的天数）。 假设在预约日期提供者为患者提供服务后立即显示有关匹配质量的反馈信息。 未出现的反馈会在预定的约会时间立即显示。 通过在整个数据集上训练的线性回归模型估计预期的特定于患者的服务时间。 该算法的目标是在有限时间调度范围内最大化总预期奖励。
实时评估是评估我们在线算法的理想方式。 用离线临床数据评估我们的算法有两个主要障碍。 首先，我们的算法尚未由我们的合作伙伴健康系统实施； 因此，缺乏关于患者-提供者匹配质量的数据，我们必须对其进行估计。 我们根据患者特征、所选提供者的技能和预约延迟，使用不同的均匀分布随机生成患者-提供者匹配质量结果。 其次，即使我们能够获得真正的患者-提供者匹配质量，基于观察数据回顾性评估我们的算法也将具有挑战性，因为我们需要反事实结果。 在实践中，不需要其他未做出决定的结果，因为该算法仅将患者分配给一个提供者-日期对并获得相应的结果。 然而，当我们根据观察数据评估我们的算法时，我们需要估计反事实。 特别是，如果患者被分配给数据集中的提供者日期，但我们的算法将患者分配给不同的提供者日期，我们必须估计与我们的算法决定相关的结果以评估其性能。
我们通过在整个数据集上训练的线性回归模型分别估计了与患者-提供者匹配质量相对应的反事实。
5.2 评估和实证结果
使用我们的临床数据，我们评估了 PAS-LD 算法相对于常用的先到先服务 (FCFS) 策略和其他算法的性能。 我们考虑 10我们的数据集的随机排列，以确保结果与患者到达的一种实现无关。 我们计算两个绩效指标：平均绩效和平均累积遗憾。 平均性能是算法/策略获得的累积预期奖励相对于基于 LP 的 benchmark-II 的最佳目标函数值的比率，该值在排列上平均。 平均累积遗憾衡量离线基于 LP 的基准-II 的累积预期奖励与排列平均的算法/策略之间的差异。
由于我们诊所提供者的可用时间有限，我们无法轻易地将我们的算法与文献中使用最广泛的在线学习算法进行比较。 我们设计并比较了以下算法/策略： (a) PAS-LD 算法：我们的框架使用机制 2 生成的在线算法，用于在线提前调度。
(b) 贪心算法：具有贪心提前调度机制的 PAS-LD 算法，其中应将患者分配到产生最高回报的提供者日期。
© FCFS 政策：为许多服务系统实施的普遍政策。 只要满足提供者的可用性，此策略就会将每位患者分配给最早可用的提供者。 领带被随机打破。
(d) PAS-LD-OFU 算法：具有机制 2 的 PAS-LD 算法的一种变体，用于在面对不确定性 (OFU) 方法时用 optimisim 替换 PS 方法（参见 Li et al. 2010）。
PS 方法与面对不确定性时的乐观 (OFU) 方法（参见 Li et al. 2010）。
平均性能 在此分析中，我们旨在深入了解平均性能对容量（供应商的可用时间）和平均服务时间变化的敏感性。 我们考虑 50 天的调度范围，并比较了 PAS-LD、Greedy 和 FCFS 在不同容量和平均服务时间尺度下的平均性能。
表 1 报告了容量规模不同级别的平均性能结果。 特别是，我们评估了关于容量尺度参数 c 1 ∈ { 1.5, 1.4, 的平均性能。 . . , 0.7 } ，其中 c 1 是每个提供者可用小时数的乘数。 结果表明，当容量增加时，平均性能会增加。 随着容量降低，平均性能降低。 这种洞察力是直观的，并且与我们的理论结果一致。 可以预见的是，PAS-LD 在其他策略/算法中具有最好的平均性能，因为 (i) 它利用了估计的患者特定匹配质量，并且 (ii) 它使用了提前调度机制，通过明智地分配来对冲未来的到达顺序 调度范围内的稀缺资源。 与 PAS-LD 相比，FCFS 和 Greedy 对容量变化更敏感（见表 3）。 FCFS 表现不佳很大程度上是由于在决策过程中对到达患者的奖励缺乏关注。 当提供商的可用时间增加时，FCFS 具有更好的性能，因为在这种情况下，更不需要明智地分配稀缺资源。 Greedy 的性能始终优于 FCFS，并且在容量充足时与 PAS-LD 的性能相当。 请注意，PAS-LD 和 Greedy 都自适应地学习预期的患者匹配质量，并在安排患者预约时将其考虑在内。 当容量充足时，将患者分配到产生最高回报（贪婪）的提供者日期可以提供一个很好的策略，因为对冲未来的到达顺序变得不那么重要了。 总体结果表明，PAS-LD算法在容量中等到低时提供了最大的价值。
表 2 报告了平均服务时间尺度的不同级别的平均性能结果。 特别是，我们评估平均服务时间尺度参数 c 2 ∈ { 0.7, 0.8, . . . , 1.5 } ，其中 c 2 是每位患者平均服务时间的乘数。 结果与表 1 中报告的结果一致，在某种意义上，PAS-LD 在平均服务时间尺度参数的所有值上都优于 FCFS 和 Greedy。 我们观察到，与 FCFS 和 Greedy 相比，PAS-LD 的平均性能对平均服务时间的变化不太敏感（见表 3）。 请注意，当平均服务时间较短时，平均性能会提高。 随着平均服务时间的增加，平均性能下降。 这种见解不仅与我们的理论结果一致，而且很直观。 增加平均服务时间，PAS-LD 在分配决策中的灵活性会降低，从而导致平均性能降低。 请注意，对于接下来的两个分析，我们将返回实际容量和平均服务时间（c 1 = 1 和 c 2 = 1 的尺度）。
平均累积遗憾 在本分析中，我们首先评估三种策略处理延迟反馈的性能。 接下来，我们研究另一种方法来平衡探索利用权衡并评估其对 PAS-LD 算法性能的影响。
我们考虑以下三种策略来处理延迟反馈并讨论相应的结果。 第一个是我们提出的异步 (ASYN) 策略，在该策略中，我们动态更新未知模型参数的估计器。 第二个和第三个是固定的
Table 1
Table 2
Table 3
等待时间 (FWT) 策略，其中我们根据固定天数 (c F W T ) 后的决策反馈更新估计量，该天数足以保证反馈得到实现。 也就是说，我们通过提供当天做出的决策的反馈来更新估计量，并假设此时反馈结果已经实现。 我们考虑了两种 FWT 策略，包括 (i) FWT-5：每个反馈实现的最长时间为 5 天，以及 (ii) FWT-10：与之前的场景类似，但为 10 天。 我们还考虑了没有延迟反馈（ND）的理想情况。 也就是说，我们假设在将患者分配给提供者日期后立即实现患者的反馈。
图 2 说明了 PAS-LD 变体的平均累积遗憾，采用不同的策略来处理延迟反馈以及没有延迟的理想情况。 理想的案例 ND 优于其他案例，因为这是一个不切实际的案例，在预约时会立即得到反馈。 可以看出，在我们实际的 PAS-LD 算法中实现的 ASYN 策略并不比 ND 差多少，并且优于两种 FWT 策略。 当样本很少时，ASYN 策略的平均累积后悔的斜率明显小于其他策略，因为它使用已实现的反馈结果而不是接收相同信息但有延迟的 FWT 策略学习得更快。 随着我们获得更多样本并且估计器越来越接近收敛，ASYN、FWT-5 和 FWT-10 的斜率收敛到理想情况的斜率。
在我们的 PAS-LD 算法中，通过使用 PS 方法来平衡探索-利用权衡。 OFU 是另一种用于平衡在线学习算法中探索-利用权衡的流行方法。 采用 OFU 方法的 PAS-LD-OFU 算法为未知模型参数构建置信集，并选择具有最高乐观估计（最高上限）的动作。 我们通过比较 PAS-LD-OFU 和 PAS-LD 获得的平均累积后悔来评估使用 PS 和 OFU 方法的影响。 为了进行公平比较，我们考虑了未知模型参数的非信息性先验。
图 3 显示了 PAS-LD 和 PAS-LD-OFU 超过 50 天的平均累积后悔。 总体而言，PAS-LD 的平均累积后悔小于 PAS-LD-OFU。 当样本较少时，PAS-LD-OFU 的平均累积后悔的斜率明显高于 PAS-LD，但随着我们获得更多样本，PAS-LD-OFU 的斜率越来越接近 PAS-LD 的斜率 .
这意味着与 PAS-LD 中使用的 PS 方法相比，我们的问题产生的遗憾较低对于PAS-LD-OFU中使用的OFU方法，尤其是在样本很少的情况下。 与使用 OFU 方法的算法相比，使用 PS 方法的算法具有更好的学习能力，在其他问题中也有经验（参见，例如，Chapelle 和 Li 2011）。 我们通过查看 PAS-LD 和 PAS-LD-OFU 的平均累积遗憾以及针对不同策略处理延迟反馈的相应比率来进一步研究 PAS-LD 和 PAS-LD-OFU 的性能差异。 表 4 显示了 ASYN 策略和三种 FWT 策略（即 FWT-5、FWT-10 和 FWT-15）对应的 50 天后 PAS-LD-OFU 和 PASLD 的平均累积后悔。 我们发现，与 PAS-LD-OFU 相比，PAS-LD 更稳健，因为当固定等待时间变长时，平均累积遗憾之间的比率会增加。 本分析中显示的 PS 优于 OFU 的优势可能是由于 PS 方法中使用的随机化过程以及与乐观估计的 OFU 方法相比，它能够更好地减轻延迟反馈结果的影响。
我们研究了具有个性化学习的资源分配问题，其中客户上下文序列是对抗性的，客户奖励和资源消耗是随机且未知的。 我们的目标是创建具有理论性能保证的算法优化程序，特别是允许医疗保健服务系统做出实时决定，及时将每位到达的患者分配给合适的临床医生。 这里强调学习以解决缺乏历史数据的设置。 我们为对抗性到达引入了一个通用框架，它明智地将在线学习与广泛的在线资源分配机制相结合。 在这个框架内，我们开发了两种在线算法，即 PRALD 和 PAS-LD，它们承认严格的性能保证。 而在一般的资源分配模型中，客户应该只被分配到资源，他们应该被分配到预先调度模型中的服务器和服务日期。 PRA-LD 算法是为一般的资源分配问题而设计的，在这种问题中，客户按顺序到达，应该被分配到某个资源或被拒绝。 PAS-LD 算法专为多日提前调度问题而设计，它为顺序到达的客户提供服务器和服务日期，同时考虑到未出现的可能性。 我们的算法在探索、利用，并对冲未来的到达顺序。 他们可以在实际环境下进行操作，学习过程是在延迟反馈结果下进行的。
我们为所提出的算法提供了理论性能保证，这需要一些新的技术思想，其中一些可能具有超出本研究范围的独立利益。 我们还使用来自我们合作伙伴健康系统的数据集，使用原始双提前调度机制评估了 PAS-LD 算法的经验性能。 实证结果表明，所提出的具有原始对偶提前调度机制的 PAS-LD 算法比它的贪婪变体表现更好，并且与普遍的 FCFS 策略相比非常好。 我们还发现，我们的提前调度算法可以很好地处理未出现和延迟反馈，这是医疗保健环境中的主要实际挑战之一。 我们更新未知模型参数估计量的异步策略大大优于其他策略，并且在没有延迟反馈的情况下，其性能并不比理想情况差多少。 我们的框架和提出的算法可以应用于许多其他需要在线学习和资源分配的实际问题。
