通过 ML 预测改进在线算法 ^† ^†thanks: 本文的会议版本 [18] 发表在 2018 年 NeurIPS 上。

Ravi Kumar
Google
ravi.k53@gmail.com
Manish Purohit
Google
mpurohit@google.com
Zoya Svitkina
Google
zoya@google.com

摘要

在这项工作中，我们研究了使用机器学习预测来提高在线算法性能的问题。我们考虑了两个经典问题：滑雪租赁和非先见之明的作业调度，并获得了使用预测做出决策的新在线算法。这些算法对预测器的性能一无所知，在预测更准确的情况下会得到改善，但如果预测不准确，也不会严重下降。

1 介绍

处理不确定性是现实世界计算任务（除了人类）面临的最具挑战性问题之一。从“下周会下雪吗？”到“我应该租公寓还是买房子？”，有一些问题无法在没有未来知识的情况下可靠地回答。同样，“我应该运行哪个作业？”这个问题对于 CPU 调度程序来说很难，因为调度程序不知道此作业将运行多长时间以及未来可能会到达哪些其他作业。

有两种有趣且经过充分研究的计算范式旨在解决不确定性。第一个是机器学习领域，其中通过对未来做出预测来解决不确定性。这通常通过检查过去并根据数据构建稳健模型来实现。然后使用这些模型对未来进行预测。人类和现实世界应用程序可以使用这些预测来调整他们的行为：知道下周可能会下雪可以用来计划滑雪旅行。第二个领域是算法设计。在这里，努力在于发展一个关于算法优劣的竞争比率的概念， ¹ ¹1非正式地说，竞争比将在线算法的最坏情况性能与知道未来的最佳离线算法进行比较。针对未知的未来，并开发在线算法，这些算法在不考虑未来的情况下做出决策，但在最坏情况下具有可证明的优越性，即即使在最悲观的未来情况下也是如此。这种在线算法在现实世界系统中很流行且成功，并且已被用于模拟包括分页、缓存、作业调度等问题（参见 Borodin 和 El-Yaniv 的书[5]）。

最近，人们对使用机器学习预测来提高在线算法的质量很感兴趣[21, 19]。这条研究路线的主要动机是双重的。首先是设计新的在线算法，这些算法可以避免假设最坏情况，从而在理论和实践中都具有更好的性能保证。第二个是利用机器学习中大量的建模工作，这些工作正是处理如何进行预测。此外，由于机器学习模型通常会在新数据上重新训练，因此这些算法可以自然地适应不断变化的数据特征。使用预测时，重要的是在线算法不知道预测器的性能，并且不假设预测错误的类型。此外，我们希望算法具有两个关键属性：（i）如果预测器很好，那么在线算法应该接近最佳离线算法的性能（一致性），以及（ii）如果预测器很差，那么在线算法应该优雅地退化，即它的性能应该接近没有预测的在线算法的性能（稳健性）。

我们的问题。我们考虑在线算法中的两个基本问题，并展示如何使用机器学习预测以可证明的方式提高它们的性能。第一个是滑雪租赁，其中滑雪者将滑雪未知天数，每天可以选择以单位价格租赁滑雪板，或者以更高的价格购买 $b$ ，从那时起免费滑雪。不确定性在于滑雪天数，预测器可以估计该天数。例如，可以通过构建基于天气预报和其他滑雪者过去行为的模型来合理地进行这种预测。滑雪租赁问题是这类在线租用或购买问题的典型例子，这类问题在需要在廉价的短期解决方案（“租赁”）和昂贵的长期解决方案（“购买”）之间做出选择时出现。滑雪租赁问题已经过多种扩展和概括，导致了许多应用，例如动态 TCP 确认[11]，购买停车许可证[22]，租赁云服务器[14]，嗅探缓存[13]等等。滑雪租赁最著名的确定性算法是盈亏平衡算法：在最初的 $b-1$ 天租赁，并在第 $b$ 天购买。很容易观察到，盈亏平衡算法的竞争比为 2，并且没有确定性算法可以做得更好。另一方面，Karlin 等人[12]设计了一种随机算法，其竞争比为 $\frac{e}{e-1}\approx 1.58$ ，这也是最优的。

我们考虑的第二个问题是非先知作业调度。在这个问题中，必须在一台机器上调度一组作业，所有作业都立即可用；任何作业都可以被抢占并在以后恢复。目标是最小化作业的完成时间之和。这个问题的不确定性在于，调度程序在作业实际完成之前不知道作业的运行时间。请注意，在这种情况下，预测器可以通过构建基于作业的特性、资源需求及其过去行为的模型，来预测作业的运行时间。由 Motwani 等人[24]提出的非先知作业调度是在线算法中的一个基本问题，它有着悠久的历史，除了它在现实世界系统中的明显应用外，它的许多变体和扩展在文献中得到了广泛的研究[9, 3, 1, 10]。 Motwani 等人[24]表明，循环算法的竞争比为 2，这是最优的。

主要结果。在介绍我们的主要结果之前，我们需要一些正式的概念。在在线算法中，算法的 竞争比 被定义为算法成本与离线最优解之间的最坏情况比率。在我们的设置中，这是一个 $c(\eta)$ 预测器误差 $\eta$ 的函数。 ² ²2预测误差 $\eta$ 的定义是特定于问题的。在本文中考虑的这两个问题中， $\eta$ 被定义为误差的 $L_{1}$ 范数。 . 我们说一个算法是 $\gamma$ -鲁棒的 ，如果 $c(\eta)\leq\gamma$ 对于所有 $\eta$ ，并且它是 $\beta$ -一致的 ，如果 $c(0)=\beta$ 。所以一致性衡量的是算法在完美预测的最佳情况下表现如何，而鲁棒性衡量的是算法在糟糕预测的最坏情况下表现如何。

令 $\lambda\in(0,1)$ 为超参数。对于带有预测器的滑雪租赁问题，我们首先获得一个确定性的在线算法，该算法是 $(1+1/\lambda)$ -鲁棒的和 $(1+\lambda)$ -一致的（第 2.2 节）。接下来，我们通过获得一个 $(\frac{1+1/b}{1-e^{-(\lambda-\nicefrac{{1}}{{b}})}})$ -鲁棒和 $(\frac{\lambda}{1-e^{-\lambda}})$ -一致的随机算法来改进这些界限，其中 $b$ 是购买成本（第 2.3 节）。对于非先见调度问题，我们获得一个 $(2/(1-\lambda))$ -鲁棒和 $(1/\lambda)$ -一致的随机算法。请注意，所有这些算法的一致性界限都规避了较低的界限，这只有因为预测才有可能。

事实证明，对于这些问题，人们必须谨慎地使用预测。我们通过一个例子说明，如果天真地使用预测，则无法保证鲁棒性（第 2.1 节）。我们的算法通过打开这些问题的经典在线算法并以明智的方式使用预测来进行。我们还进行了实验以表明我们开发的算法是实用的，并且与不使用任何预测的算法相比，它们实现了良好的性能。

相关工作。与我们最接近的工作是 Medina 和 Vassilvitskii [21] 以及 Lykouris 和 Vassilvitskii [19] 的工作。前者使用预测预言机来改进保留价格优化，将预期出价与收入之间的差距与平均预测器损失相关联。从某种意义上说，这篇论文开启了对配备机器学习预测的在线算法的研究。后者进一步发展了这一框架，引入了鲁棒性和一致性的概念，并考虑了带有预测的在线缓存问题。它修改了著名的 Marker 算法，使用预测来确保鲁棒性和一致性。虽然我们在同一个框架内运行，但他们的技术都不适用于我们的设置。最近的另一项工作是 Kraska 等人的工作。 [17] 通过实证表明可以使用机器学习模型构建更好的索引；它没有为其方法提供任何可证明的保证。

还有一些其他计算模型试图解决不确定性问题。鲁棒优化领域 [16] 考虑不确定的输入，并旨在设计能够针对输入的任何潜在实现提供良好性能保证的算法。已经有一些关于在输入是随机的或来自已知分布的情况下分析算法的工作 [20, 23, 6]。在优化领域，整个在线随机优化领域关注在线决策下的不确定性，通过假设未来输入的分布；参见 Russell Bent 和 Pascal Van Hentenryck 的著作 [4]。我们的工作不同于这些，因为我们不假设输入有任何东西；事实上，我们也不假设预测器有任何东西！

2 带有预测的滑雪租赁

在滑雪租赁问题中，假设每天的租赁费用为一个单位， $b$ 是购买的成本， $x$ 是实际的滑雪天数，该天数对算法是未知的，而 $y$ 是预测的天数。那么 $\eta=|y-x|$ 是预测误差。请注意，我们没有对它的分布做出任何假设。最佳成本为 $\mathsf{OPT}=\min\{b,x\}$ 。

2.1 预热：一个简单的、一致的、非鲁棒的算法

我们首先表明，一个简单地使用预测天数来决定是否购买的算法是 1-一致的，即，当 $\eta=0$ 时，它的竞争比率为 1。但是，该算法并不健壮，因为在预测错误的情况下，竞争比率可以任意大。

如果 $y\geq b$ 则

在第一天购买。

否则

在所有滑雪日保持租赁。

结束 if

算法 1 一个简单的 1-一致算法

Lemma 2.1.

令 $\mathsf{ALG}$ 表示由算法 1 获得的解的成本，并令 $\mathsf{OPT}$ 表示同一实例上的最优解成本。那么 $\mathsf{ALG}\leq\mathsf{OPT}+\eta$ 。

证明。

我们根据预测 $y$ 和实例的实际天数 $x$ 的相对值来考虑不同的情况。回想一下，当预测至少为 $b$ 时，算法 1 会产生 $b$ 的成本，否则会产生 $x$ 的成本。

•

$y\geq b,x\geq b$ $\implies$ $\mathsf{ALG}=b=\mathsf{OPT}$ 。
•

$y<b,x<b$ $\implies$ $\mathsf{ALG}=x=\mathsf{OPT}$
•

$y\geq b,x<b$ $\implies$ $\mathsf{ALG}=b\leq x+y-x=x+\eta=\mathsf{OPT}+\eta$
•

$y<b,x\geq b$ $\implies$ $\mathsf{ALG}=x<b+x-y=b+\eta=\mathsf{OPT}+\eta$ ∎

算法 1 的一个主要缺点是缺乏鲁棒性。特别是，如果预测 $y$ 很小，但 $x\gg b$ ，那么它的竞争比率将是无界的。我们的下一个目标是获得一种既一致又鲁棒的算法。

2.2 一种确定性的鲁棒且一致的算法

在本节中，我们证明了对算法 1 的一个小修改可以产生一种既一致又鲁棒的算法。令 $\lambda\in(0,1)$ 为一个超参数。正如我们稍后将看到的那样，改变 $\lambda$ 会使算法的鲁棒性和一致性之间产生平滑的权衡。

如果 $y\geq b$ 那么

在

\lceil\lambda b\rceil

日开始购买

别的

在

\lceil b/\lambda\rceil

日开始购买

结束如果

算法 2 一个确定性的、鲁棒的和一致的算法。

Theorem 2.2。

对于参数 $\lambda\in(0,1)$ ，算法 2 的竞争比最多为 $\min\left\{\dfrac{1+\lambda}{\lambda},~{}(1+\lambda)+\dfrac{\eta}{(1-\lambda)% \mathsf{OPT}}\right\}$ 。特别地，算法 2 是 $(1+1/\lambda)$ -鲁棒的和 $(1+\lambda)$ -一致的。

证明。

我们从第一个界限开始。假设 $y\geq b$ 且算法在第 $\lceil\lambda b\rceil$ 天开始购买滑雪板。由于算法在 $x\geq\lceil\lambda b\rceil$ 时会产生 $b+\lceil\lambda b\rceil-1$ 的成本，因此当 $x=\lceil\lambda b\rceil$ 时，会得到最差的竞争比，对于这种情况， $\mathsf{OPT}=\lceil\lambda b\rceil$ 。在这种情况下，我们有 $\mathsf{ALG}=b+\lceil\lambda b\rceil-1\leq b+\lambda b\leq\left(\frac{1+% \lambda}{\lambda}\right)\lceil\lambda b\rceil=\left(\frac{1+\lambda}{\lambda}% \right)\mathsf{OPT}$ 。另一方面，当 $y<b$ 时，算法在第 $\lceil\nicefrac{{b}}{{\lambda}}\rceil$ 天开始购买滑雪板，并在之前租用。在这种情况下，当 $x=\lceil\nicefrac{{b}}{{\lambda}}\rceil$ 时，会达到最差的竞争比，因为我们有 $\mathsf{OPT}=b$ 和 $\mathsf{ALG}=b+\lceil\nicefrac{{b}}{{\lambda}}\rceil-1\leq b+b/\lambda=\left(% \frac{1+\lambda}{\lambda}\right)\mathsf{OPT}$ 。

为了证明第二个界限，我们需要考虑以下两种情况。假设 $y\geq b$ 。那么，对于所有 $x<\lceil\lambda b\rceil$ ，我们有 $\mathsf{ALG}=\mathsf{OPT}=x$ 。另一方面，对于 $x\geq\lceil\lambda b\rceil$ ，我们有 $\mathsf{ALG}=b+\lceil\lambda b\rceil-1\leq(1+\lambda)b\leq(1+\lambda)(\mathsf{% OPT}+\eta)$ 。第二个不等式成立是因为要么 $OPT=b$ （如果 $x\geq b$ ）要么 $b\leq y\leq\mathsf{OPT}+\eta$ （如果 $x<b$ ）。假设 $y<b$ 。那么，对于所有 $x\leq b$ ，我们有 $\mathsf{ALG}=\mathsf{OPT}=x$ 。同样，对于所有 $x\in(b,\lceil\nicefrac{{b}}{{\lambda}}\rceil)$ ，我们有 $\mathsf{ALG}=x\leq y+\eta<b+\eta=\mathsf{OPT}+\eta$ 。最后，对于所有 $x\geq\lceil\nicefrac{{b}}{{\lambda}}\rceil$ ，注意到 $\eta=x-y>\nicefrac{{b}}{{\lambda}}-b=(1-\lambda)\nicefrac{{b}}{{\lambda}}$ ，我们有 $\mathsf{ALG}=b+\lceil\nicefrac{{b}}{{\lambda}}\rceil-1\leq b+\nicefrac{{b}}{{% \lambda}}<b+(\frac{1}{1-\lambda})\eta=\mathsf{OPT}+(\frac{1}{1-\lambda})\eta$ 。因此，我们得到 $\mathsf{ALG}\leq(1+\lambda)\mathsf{OPT}+(\frac{1}{1-\lambda})\eta$ ，完成了证明。 ∎

因此，算法 2 提供了一个权衡一致性和鲁棒性的选择。特别地，对预测者更加信任意味着将 $\lambda$ 设置为接近零，因为当 $\eta$ 很小时，这将导致更好的竞争比。另一方面，将 $\lambda$ 设置为接近一是保守的，并且会产生更稳健的算法。

2.3 一种随机的鲁棒且一致的算法

在本节中，我们考虑一类随机算法，并将其性能与一个无知对手进行比较。特别地，我们设计了鲁棒且一致的算法，这些算法比上述确定性算法具有更好的权衡。令 $\lambda\in(\nicefrac{{1}}{{b}},1)$ 为一个超参数。对于给定的 $\lambda$ ，算法 3 根据接收到的预测，基于两种不同的概率分布对购买滑雪板的日期进行采样，并在该日期之前进行租赁。

if $y\geq b$ then

令

k\leftarrow\lfloor\lambda b\rfloor

；

定义

q_{i}\leftarrow\left(\frac{b-1}{b}\right)^{k-i}\cdot\frac{1}{b(1-(1-\nicefrac{% {1}}{{b}})^{k})}

对于所有

1\leq i\leq k

；

从由

q_{i}

定义的分布中随机选择

j\in\{1\ldots k\}

；

在第

j

天开始购买。

否则

令

\ell\leftarrow\lceil\nicefrac{{b}}{{\lambda}}\rceil

；

为所有

1\leq i\leq\ell

定义

r_{i}\leftarrow\left(\frac{b-1}{b}\right)^{\ell-i}\cdot\frac{1}{b(1-(1-% \nicefrac{{1}}{{b}})^{\ell})}

；

从由

r_{i}

定义的分布中随机选择

j\in\{1\ldots\ell\}

；

在第

j

天开始购买。

结束 if

算法 3 一种随机的、鲁棒且一致的算法

Theorem 2.3.

算法 3 的竞争比最多为 $\min\{\frac{1+1/b}{1-e^{-(\lambda-\nicefrac{{1}}{{b}})}},\frac{\lambda}{1-e^{-% \lambda}}(1+\frac{\eta}{\mathsf{OPT}})\}$ 。特别地，算法 3 是 $(\frac{1+1/b}{1-e^{-(\lambda-\nicefrac{{1}}{{b}})}})$ 鲁棒和 $(\frac{\lambda}{1-e^{-\lambda}})$ 一致的。 ³³3 本文会议版本 [18] 错误地声称 $\frac{1}{1-e^{-(\lambda-1/b)}}$ 的鲁棒性略强。

证明。

我们根据 $y$ 和 $x$ 的相对值考虑不同的情况。

(i) $y\geq b,x\geq k$ 。在这里，我们有 $\mathsf{OPT}=\min\{b,x\}$ . 由于算法在第 $i$ 天开始购买时会产生 $(b+i-1)$ 的成本，所以我们有

	$\displaystyle\mathbb{E}[\mathsf{ALG}]$	$\displaystyle=\sum_{i=1}^{k}(b+i-1)q_{i}=\sum_{i=1}^{k}(b+i-1)\left(\frac{b-1}% {b}\right)^{k-i}\frac{1}{b(1-(1-\nicefrac{{1}}{{b}})^{k})}\enspace=\enspace% \frac{k}{1-(1-\nicefrac{{1}}{{b}})^{k}}$
		$\displaystyle\leq\frac{k}{1-e^{\nicefrac{{-k}}{{b}}}}\enspace\leq\enspace\left% (\frac{\nicefrac{{k}}{{b}}}{1-e^{\nicefrac{{-k}}{{b}}}}\right)(\mathsf{OPT}+% \eta)\enspace\leq\enspace\left(\frac{\lambda}{1-e^{-\lambda}}\right)(\mathsf{% OPT}+\eta).$

(ii) $y\geq b,x<k$ . 在这里，我们有 $\mathsf{OPT}=x$ . 另一方面，该算法仅在第 $i\leq x$ 天开始购买时才会产生 $(b+i-1)$ 的成本。特别地，我们有

	$\displaystyle\mathbb{E}[\mathsf{ALG}]$	$\displaystyle=\sum_{i=1}^{x}(b+i-1)q_{i}+\sum_{i=x+1}^{k}xq_{i}$
		$\displaystyle=\frac{1}{b(1-(1-\nicefrac{{1}}{{b}})^{k})}\left[\sum_{i=1}^{x}(b% +i-1)\left(\frac{b-1}{b}\right)^{k-i}+\sum_{i=x+1}^{k}x\left(\frac{b-1}{b}% \right)^{k-i}\right]$
		$\displaystyle=\frac{x}{1-(1-\nicefrac{{1}}{{b}})^{k}}\enspace\leq\enspace\left% (\frac{1}{1-e^{\nicefrac{{-k}}{{b}}}}\right)\mathsf{OPT}\enspace\leq\enspace% \left(\frac{1}{1-e^{-(\lambda-\nicefrac{{1}}{{b}})}}\right)\mathsf{OPT},$

这就建立了鲁棒性。为了证明一致性，我们可以将 RHS 重写如下

	$\displaystyle\mathbb{E}[\mathsf{ALG}]$	$\displaystyle\leq\left(\frac{1}{1-e^{\nicefrac{{-k}}{{b}}}}\right)\mathsf{OPT}% \enspace=\enspace\left(\frac{\nicefrac{{k}}{{b}}}{1-e^{\nicefrac{{-k}}{{b}}}}% \right)\mathsf{OPT}+\left(\frac{\nicefrac{{(b-k)}}{{b}}}{1-e^{\nicefrac{{-k}}{% {b}}}}\right)x$
		$\displaystyle\leq\left(\frac{\nicefrac{{k}}{{b}}}{1-e^{\nicefrac{{-k}}{{b}}}}% \right)\mathsf{OPT}+\left(\frac{\nicefrac{{k}}{{b}}}{1-e^{\nicefrac{{-k}}{{b}}% }}\right)\eta\enspace\leq\enspace\left(\frac{\lambda}{1-e^{-\lambda}}\right)(% \mathsf{OPT}+\eta),$

因为 $x<k$ 和 $b-k\leq\eta$ .

(iii) $y<b,x<\ell$ 。在这里，我们有 $\mathsf{OPT}=\min\{b,x\}$ . 另一方面，该算法的预期成本可以类似于 (ii) 计算

	$\displaystyle\mathbb{E}[\mathsf{ALG}]$	$\displaystyle=\sum_{i=1}^{x}(b+i-1)r_{i}+\sum_{i=x+1}^{\ell}xr_{i}\enspace\leq% \enspace\left(\frac{1}{1-e^{\nicefrac{{-\ell}}{{b}}}}\right)x$
		$\displaystyle\leq\left(\frac{1}{1-e^{\nicefrac{{-1}}{{\lambda}}}}\right)(% \mathsf{OPT}+\eta)\enspace\leq\enspace\left(\frac{\lambda}{1-e^{-\lambda}}% \right)(\mathsf{OPT}+\eta).$

(iv) $y<b,x\geq\ell$ 。在这里，我们有 $\mathsf{OPT}=b$ . 该算法产生的预期成本与 (i) 中相同。

	$\displaystyle\mathbb{E}[\mathsf{ALG}]$	$\displaystyle=\sum_{i=1}^{\ell}(b+i-1)r_{i}\enspace=\enspace\frac{\ell}{1-(1-% \nicefrac{{1}}{{b}})^{\ell}}\enspace\leq\enspace\frac{\lceil\nicefrac{{b}}{{% \lambda}}\rceil}{(1-e^{\nicefrac{{-\ell}}{{b}}})}$
		$\displaystyle\leq\left(\frac{\nicefrac{{1}}{{\lambda}}+\nicefrac{{1}}{{b}}}{(1% -e^{\nicefrac{{-1}}{{\lambda}}})}\right)\mathsf{OPT}\enspace\leq\enspace\left(% \frac{1+1/b}{1-e^{-(\lambda-\nicefrac{{1}}{{b}})}}\right)\mathsf{OPT},$
where the last inequality is proven in Lemma A.2 in the Appendix. This completes the proof of robustness. To prove consistency, we rewrite the RHS as follows.
	$\displaystyle\mathbb{E}[\mathsf{ALG}]$	$\displaystyle\leq\frac{\ell}{1-e^{\nicefrac{{-\ell}}{{b}}}}\enspace\leq% \enspace\frac{\ell}{1-e^{\nicefrac{{-1}}{{\lambda}}}}\enspace=\enspace\frac{1}% {1-e^{\nicefrac{{-1}}{{\lambda}}}}\left(b+\ell-b\right)$
		$\displaystyle\leq\frac{1}{1-e^{\nicefrac{{-1}}{{\lambda}}}}(\mathsf{OPT}+\eta)% \enspace\leq\enspace\left(\frac{\lambda}{1-e^{-\lambda}}\right)(\mathsf{OPT}+% \eta).\qed$

算法 2 和 3 都为滑雪租赁问题提供了鲁棒性和一致性保证之间的平滑权衡。如图 1 所示，随机算法通过始终保证给定鲁棒性保证下的较小一致性，提供了更好的权衡。我们注意到，在算法 2 和 3 中设置 $\lambda=1$ 允许我们恢复经典滑雪租赁问题中最佳确定性和随机算法，而无需使用预测。

2.4 扩展

考虑滑雪租赁问题的一般化，其中我们每天 $i$ 对计算资源的需求 $x_{i}$ 不同。这种情況模拟了在设计小型企业数据中心时所面临的问题。系统设计人员可以选择以高设置成本购买机器，或者从云服务提供商租用机器来处理企业的计算需求。可以通过两种方式满足需求：要么支付 $1$ 租用一台机器，并满足一天的需求量为一个单位；要么支付 $b$ 购买一台机器，并使用它来满足未来所有天数的需求量为一个单位。通过将前 $x$ 天的 $x_{i}=1$ 设置为 0，然后将其设置为 0，可以轻松地在此框架中解决经典的滑雪租赁问题。 Kodialam [15] 考虑了这种推广，并给出了具有 2 的竞争比率的确定性算法，以及具有 $\frac{e}{e-1}$ 的竞争比率的随机算法。

现在假设我们对第 $i$ 天的需求有预测 $y_{i}$ 。我们定义 $\eta=\sum_{i}|x_{i}-y_{i}|$ 为预测的总 $L_{1}$ 误差。算法 2 和 3 都自然地扩展到此设置，以产生与定理 2.2 和 2.3 中相同的鲁棒性和一致性保证。我们的结果来自于将具有可变需求的滑雪租赁实例视为 $k$ 个经典滑雪租赁问题的独立实例，其中 $k$ 是任何一天的最大需求的上限。证明类似于第 2.2 节和 2.3 节中的证明；为了简洁起见，我们省略了它们。

3 带有预测的非先知作业调度

我们考虑非先知作业调度的最简单变体，即在没有发布日期的情况下，在单台机器上调度 $n$ 个作业。作业 $j$ 的处理需求 $x_{j}$ 对算法未知，只有在作业完成处理后才能知道。任何作业都可以在任何时候被抢占并在稍后时间恢复，而不会产生任何成本。目标函数是最小化作业完成时间的总和。请注意，如果不允许抢占，则没有任何算法可以产生任何非平凡的保证。

令 $x_{1},\ldots,x_{n}$ 表示 $n$ 个作业的实际处理时间，这些时间对非先知算法是未知的。在先知情况下，当处理时间事先已知时，最佳算法是简单地按照作业长度的非递减顺序调度作业，即最短作业优先。一种称为轮循 (RR) 的确定性非先知算法产生了 2 [24] 的竞争比，这被认为是最好的。

现在，假设算法没有真正非先知，而是有一个预言机来预测每个作业的处理时间。令 $y_{1},\ldots,y_{n}$ 表示 $n$ 个作业的预测处理时间。那么 $\eta_{j}=|x_{j}-y_{j}|$ 是作业 $j$ 的预测误差，而 $\eta=\sum_{j=1}^{n}\eta_{j}$ 是总误差。我们假设没有零长度作业，并且单位被归一化，使得最短作业的实际处理时间至少为 1。本节的目标是设计既健壮又一致的算法，即可以利用良好的预测来突破 2 的下界，同时保证最坏情况下的常数竞争比。

3.1 优先轮循算法

在具有抢占的调度问题中，我们可以通过谈论机器上同时运行的多个作业来简化说明，这些作业的速率之和最多为 1。例如，在循环算法中，在任何时刻，所有 $k$ 在机器上以相同的 $1/k$ 运行。这只是为了简便起见，表示在任何无穷小的时段内， $1/k$ 的一部分用于运行每个作业。

如果一个非先见调度算法具有以下性质，我们称其为 单调的：给定两个具有相同输入和实际作业处理时间的实例 $(x_{1},\ldots,x_{n})$ 和 $(x^{\prime}_{1},\ldots,x^{\prime}_{n})$ ，使得 $x_{j}\leq x^{\prime}_{j}$ 对于所有 $j$ 成立，则该算法针对第一个实例找到的目标函数值不高于针对第二个实例的值。很容易看出循环算法是单调的。

我们考虑 最短预测作业优先 (SPJF) 算法，该算法按作业的预测处理时间 $y_{j}$ 的升序排序作业，并按此顺序执行作业直至完成。请注意，SPJF 是单调的，因为如果处理时间 $x_{j}$ 变小（预测 $y_{j}$ 保持不变），所有作业只会更早完成，从而减少总完成时间目标。 SPJF 在预测完美的条件下产生最佳调度，但对于错误的预测，其最坏情况性能不受常数限制。为了兼顾两全其美，即对良好的预测获得良好的性能以及在最坏情况下获得常数因子近似，我们将 SPJF 与 RR 相结合，使用以下方法，将该算法称为 优先循环 (PRR)。

Lemma 3.1.

给定两个具有竞争比 $\alpha$ 和 $\beta$ 的单调算法，用于具有抢占的最小总完成时间问题，以及参数 $\lambda\in(0,1)$ ，可以获得一个竞争比为 $\min\{\frac{\alpha}{\lambda},\frac{\beta}{1-\lambda}\}$ 的算法。

证明。

结合后的算法并行运行两个给定的算法。 $\alpha$ 近似值（称为 $A$ ）以 $\lambda$ 的速率运行，而 $\beta$ 近似值 ( $B$ ) 以 $1-\lambda$ 的速率运行。与以速率 1 运行相比，如果算法 $A$ 以较慢的速率 $\lambda$ 运行，所有完成时间都会增加 $\nicefrac{{1}}{{\lambda}}$ 倍，因此它成为一个 $\frac{\alpha}{\lambda}$ 近似值。现在，由于一些作业正在由算法 $B$ 并行执行，因此从 $A$ 的角度来看，它们的处理时间只会减少，因此根据单调性，这不会使 $A$ 的目标函数更糟糕。同样，当算法 $B$ 以较低的速率 $1-\lambda$ 运行时，它成为一个 $\frac{\beta}{1-\lambda}$ 近似值，并且根据单调性，它只会从与 $A$ 的并发中得到改进。因此，这两个边界同时成立，整体保证是它们的最小值。 ∎

接下来，我们分析 SPJF 的性能。

Lemma 3.2。

SPJF 算法的竞争比最多为 $\left(1+\frac{2\eta}{n}\right)$ 。

证明。

假设不失一般性。作业按其实际处理时间的非递减顺序编号，即 $x_{1}\leq\ldots\leq x_{n}$ 。对于任何一对作业 $(i,j)$ ，定义 $d(i,j)$ 为作业 $i$ 在作业 $j$ 完成时间之前已执行的量。换句话说， $d(i,j)$ 是 $i$ 延迟 $j$ 的时间量。令 $\mathsf{ALG}$ 表示 SPJF 的输出。然后

\mathsf{ALG}=\sum_{j=1}^{n}x_{j}+\sum_{(i,j):i<j}(d(i,j)+d(j,i)).

对于 $i<j$ 满足 $y_{i}<y_{j}$ 的情况，较短的作业先调度，因此 $d(i,j)+d(j,i)=x_{i}+0$ ，但对于预测错误的作业对，较长的作业先调度，因此 $d(i,j)+d(j,i)=0+x_{j}$ 。这将产生

	$\displaystyle\mathsf{ALG}$	$\displaystyle=\sum_{j=1}^{n}x_{j}+\sum_{\begin{subarray}{c}(i,j):i<j\\ y_{i}<y_{j}\end{subarray}}x_{i}+\sum_{\begin{subarray}{c}(i,j):i<j\\ y_{i}\geq y_{j}\end{subarray}}x_{j}\enspace=\enspace\sum_{j=1}^{n}x_{j}+\sum_{% (i,j):i<j}x_{i}+\sum_{\begin{subarray}{c}(i,j):i<j\\ y_{i}\geq y_{j}\end{subarray}}(x_{j}-x_{i})$
		$\displaystyle\leq\sum_{j=1}^{n}x_{j}+\sum_{(i,j):i<j}x_{i}+\sum_{\begin{% subarray}{c}(i,j):i<j\\ y_{i}\geq y_{j}\end{subarray}}\eta_{i}+\eta_{j}=\mathsf{OPT}+\sum_{\begin{% subarray}{c}(i,j):i<j\\ y_{i}\geq y_{j}\end{subarray}}\eta_{i}+\eta_{j}\leq\mathsf{OPT}+(n-1)\eta,$

这将产生 $\frac{\mathsf{ALG}}{\mathsf{OPT}}\leq 1+\frac{(n-1)\eta}{\mathsf{OPT}}$ 。现在，根据我们的假设，所有作业的长度至少为 1，我们有 $\mathsf{OPT}\geq\frac{n(n+1)}{2}$ 。这产生了 SPJF 竞争比的 $1+\frac{2(n-1)\eta}{n(n+1)}<1+\frac{2\eta}{n}$ 的上限。 ∎

我们给出一个例子，表明这个界限是渐近紧密的。假设有 $n-1$ 个作业，处理时间为 $1$ ，还有一个作业，处理时间为 $1+\epsilon$ ，并假设所有作业的预测长度为 $y_{j}=1$ 。然后是 $\eta=\epsilon$ 、 $\mathsf{OPT}=\frac{n(n+1)}{2}+\epsilon$ ，并且，如果 SPJF 碰巧先安排了最长的作业，则将 $n-1$ 作业的完成时间增加 $\epsilon$ 每个， $\mathsf{ALG}=\mathsf{OPT}+(n-1)\epsilon$ 。这就得到了 $\frac{\mathsf{ALG}}{\mathsf{OPT}}=1+\frac{2(n-1)\eta}{n(n+1)+2\epsilon}$ 的比率，当 $n$ 增加而 $\epsilon$ 减小时，该比率接近引理 3.2 中的界限。

最后，我们限制了优先轮循算法的性能。

Theorem 3.3.

带有参数 $\lambda\in(0,1)$ 的优先轮循算法的竞争比率最多为 $\min\{\frac{1}{\lambda}(1+\frac{2\eta}{n}),\frac{2}{1-\lambda}\}$ 。特别地，它是 $\frac{2}{1-\lambda}$ -鲁棒的和 $\frac{1}{\lambda}$ -一致的。

证明。

这是从 SPJF 的竞争比率（引理 3.2）和轮循的竞争比率 2 推导出来的，并且通过使用引理 3.1 将这两种算法结合起来。 ∎

设置 $\lambda>0.5$ 给出一种算法，在预测足够好的情况下，该算法优于轮循的比率 $2$ 。对于零预测误差的特殊情况（或者更一般地，如果按 $y_{j}$ 排序的作业顺序与按 $x_{j}$ 排序的作业顺序相同），我们可以通过更复杂的分析获得 $\frac{1+\lambda}{2\lambda}$ 的改进竞争比率。

Theorem 3.4.

带有参数 $\lambda\in(0,1)$ 的优先轮循算法的竞争比率最多为 $(\frac{1+\lambda}{2\lambda})$ ，当 $\eta=0$ 时。

证明。

假设 w.l.o.g。任务按照非递减的任务长度（实际和预测的）排序，即 $x_{1}\leq\cdots\leq x_{n}$ 和 $y_{1}\leq\cdots\leq y_{n}$ 。由于最佳解决方案是按顺序调度任务，因此我们有

\displaystyle\mathsf{OPT}

\displaystyle=\sum_{j=1}^{n}(n-j+1)x_{j}=\sum_{j=1}^{n}x_{j}+\sum_{(i,j):i<j}x% _{i}.

(1)

如果一个任务尚未完成，我们称其为活动任务。当有 $k$ 个活动任务时，优先级轮循算法以 $\frac{1-\lambda}{k}$ 的速率执行所有活动任务，并将预测处理时间最短的活动任务（我们称此任务为当前任务）以额外的 $\lambda$ 的速率执行。注意，每个任务 $j$ 在成为当前任务时完成。这可以归纳地表示：假设作业 $j-1$ 在时间 $t$ 完成。然后，到时间 $t$ 时，作业 $j$ 收到的处理量严格少于 $j-1$ ，但其大小至少一样大。因此，它还有一些剩余的处理时间，这意味着它在时间 $t$ 成为当前任务，并保持当前任务状态直到完成。令阶段 $k$ 表示算法中任务 $k$ 为当前任务的时间间隔。

对于任何一对任务 $(i,j)$ ，定义 $d(i,j)$ 为在 $j$ 完成时间之前执行的任务 $i$ 的数量。换句话说， $d(i,j)$ 是 $i$ 延迟 $j$ 的时间。现在我们可以将算法的成本表示为

\displaystyle\mathsf{ALG}

\displaystyle=\sum_{j=1}^{n}x_{j}+\sum_{(i,j):i<j}d(i,j)+\sum_{(i,j):i<j}d(j,i).

(2)

如果 $i<j$ ，因为任务 $i$ 在任务 $j$ 完成之前完成，我们有 $d(i,j)=x_{i}$ 。为了计算 (2) 中的最后一项，考虑任何阶段 $k$ ，并令 $t_{k}$ 表示其长度。在此阶段，当前任务 $k$ 以至少 $\lambda$ 的速率执行，这意味着 $t_{k}\leq\frac{x_{k}}{\lambda}$ 。在阶段 $k$ 期间，任务 $\{k+1,...,n\}$ 接收 $\frac{t_{k}(1-\lambda)}{n-k+1}$ 数量的处理时间。这样的任务 $k+i$ 会延迟索引较小的 $i$ 个任务，即 $\{k,...,k+i-1\}$ 。令 $d^{k}(i,j)$ 表示相位 $k$ 中的延迟：

\sum_{(i,j):i<j}d^{k}(j,i)~{}=~{}\frac{t_{k}(1-\lambda)}{n-k+1}\cdot\sum_{i=1}% ^{n-k}i~{}=~{}\frac{t_{k}(1-\lambda)(n-k)}{2}~{}\leq~{}\frac{x_{k}(1-\lambda)(% n-k)}{2\lambda}.

代入方程 (2)，

	$\displaystyle\mathsf{ALG}~{}$	$\displaystyle=~{}\sum_{j=1}^{n}x_{j}+\sum_{(i,j):i<j}d(i,j)+\sum_{(i,j):i<j}% \sum_{k=1}^{n}d^{k}(j,i)$
		$\displaystyle\leq~{}\sum_{j=1}^{n}x_{j}+\sum_{(i,j):i<j}x_{i}+\sum_{k=1}^{n}% \frac{x_{k}(1-\lambda)(n-k)}{2\lambda}=~{}\mathsf{OPT}+\sum_{k=1}^{n}\frac{x_{% k}(1-\lambda)(n-k)}{2\lambda}$
		$\displaystyle\leq~{}\mathsf{OPT}+\frac{1-\lambda}{2\lambda}\sum_{k=1}^{n}x_{k}% (n-k+1)=~{}\mathsf{OPT}+\frac{1-\lambda}{2\lambda}\mathsf{OPT}~{}=~{}\frac{1+% \lambda}{2\lambda}\mathsf{OPT},$

使用方程 (1) 作为最后一行。 ∎

4 实验结果

4.1 滑雪租赁

我们通过模拟测试了我们的算法在滑雪租赁问题上的性能。对于所有实验，我们将购买成本设定为 $b=100$ ，实际滑雪天数 $x$ 是从 $[1,4b]$ 中随机均匀抽取的整数。预测的滑雪天数 $y$ 模拟为 $y=x+\epsilon$ ，其中 $\epsilon$ 从均值为 0，标准差为 $\sigma$ 的正态分布中随机抽取。我们考虑了两种不同权衡参数 $\lambda$ 值的随机和确定性算法。回想一下，通过设置 $\lambda=1$ ，我们的算法忽略了预测，并简化为已知的最佳算法（分别是确定性和随机的）[12]。我们将 $\lambda=0.5$ 设置为保证最坏情况竞争比为 3 的确定性算法。为了获得相同的最坏情况竞争比，我们将 $\lambda=\ln(\nicefrac{{3}}{{2}})$ 设置为随机算法。对于每个 $\sigma$ ，我们在图 2(a) 中绘制了每个算法在 10000 次独立试验中获得的平均竞争比。我们观察到，即使对于相当大的预测误差，我们的算法也比其经典对应算法表现得明显更好。特别地，即使是使用预测的确定性算法，其在误差高达标准差为 $2b$ 时，也比经典随机算法表现得更好。

4.2 非先知调度

N min max mean $\sigma$ 50 1 22352 2168 5475.42

表 1: 作业长度统计.

我们生成一个包含 50 个作业的合成数据集，其中每个作业的处理时间独立地从帕累托分布中采样，该分布的指数为 $\alpha=1.1$ . (如先前工作 [7, 8, 2] 中观察到的，在许多情况下，作业大小分布可以通过帕累托分布很好地建模，其中 $\alpha$ 接近 1.) 生成的数据集的相关特征在表 1 中给出. 为了模拟预测的作业长度并比较不同算法在预测误差方面的性能，我们设置预测的作业长度为 $y_{i}=x_{i}+\epsilon_{i}$ ，其中 $\epsilon_{i}$ 从均值为零、标准差为 $\sigma$ 的正态分布中抽取.

图 2(b) 显示了三种算法在不同预测误差下的竞争比率. 对于参数 $\sigma$ ，我们绘制了 1000 次独立试验的平均竞争比率，其中预测误差具有指定的标准差. 正如预期的那样，在误差较低时，按照预测作业长度非递减顺序调度作业的朴素策略 (SPJF) 性能非常好，但随着误差的增加，性能迅速下降. 相反，我们的优先级轮询算法（ $\lambda=0.5$ ）即使在预测误差非常大的情况下，其性能也不比轮询算法差.

5 结论

在本文中，我们进一步研究了利用机器学习预测来证明改进在线算法的最坏情况性能。还有许多其他重要的在线算法，包括 $k$ -服务器，投资组合优化等，看看预测是否对它们也有用将很有趣。另一个研究方向是利用机器学习预测器的误差分布来进一步改进界限。

致谢

感谢徐辰阳指出了会议版本中的一个错误 [18]，并感谢 Erik Vee 在修复错误方面的帮助。

参考文献

[1] Nikhil Bansal, Kedar Dhamdhere, Jochen Könemann, and Amitabh Sinha. Non-clairvoyant scheduling for minimizing mean slowdown. Algorithmica, 40(4):305–318, 2004.
[2] Nikhil Bansal and Mor Harchol-Balter. Analysis of SRPT scheduling: Investigating unfairness. In SIGMETRICS, pages 279–290, 2001.
[3] Luca Becchetti and Stefano Leonardi. Non-clairvoyant scheduling to minimize the average flow time on single and parallel machines. In STOC, pages 94–103, 2001.
[4] Russell Bent and Pascal Van Hentenryck. Online Stochastic Combinatorial Optimization. MIT Press, 2009.
[5] A. Borodin and R. El-Yaniv. Online Computation and Competitive Analysis. Cambridge University Press, 1998.
[6] Sebastien Bubeck and Aleksandrs Slivkins. The best of both worlds: Stochastic and adversarial bandits. In COLT, pages 42.1–42.23, 2012.
[7] Mark E Crovella and Azer Bestavros. Self-similarity in world wide web traffic: Evidence and possible causes. Transactions on Networking, 5(6):835–846, 1997.
[8] Mor Harchol-Balter and Allen B Downey. Exploiting process lifetime distributions for dynamic load balancing. ACM TOCS, 15(3):253–285, 1997.
[9] Sungjin Im, Janardhan Kulkarni, and Kamesh Munagala. Competitive algorithms from competitive equilibria: Non-clairvoyant scheduling under polyhedral constraints. J. ACM, 65(1):3:1–3:33, 2017.
[10] Sungjin Im, Janardhan Kulkarni, Kamesh Munagala, and Kirk Pruhs. Selfishmigrate: A scalable algorithm for non-clairvoyantly scheduling heterogeneous processors. In FOCS, pages 531–540, 2014.
[11] Anna R Karlin, Claire Kenyon, and Dana Randall. Dynamic TCP acknowledgement and other stories about $e/(e-1)$ . Algorithmica, 36(3):209–224, 2003.
[12] Anna R. Karlin, Mark S. Manasse, Lyle A. McGeoch, and Susan Owicki. Competitive randomized algorithms for nonuniform problems. Algorithmica, 11(6):542–571, 1994.
[13] Anna R. Karlin, Mark S. Manasse, Larry Rudolph, and Daniel Dominic Sleator. Competitive snoopy caching. Algorithmica, 3:77–119, 1988.
[14] Ali Khanafer, Murali Kodialam, and Krishna P.N. Puttaswamy. The constrained ski-rental problem and its application to online cloud cost optimization. In INFOCOM, pages 1492–1500, 2013.
[15] Rohan Kodialam. Competitive algorithms for an online rent or buy problem with variable demand. In SIAM Undergraduate Research Online, volume 7, pages 233–245, 2014.
[16] Panos Kouvelis and Gang Yu. Robust Discrete Optimization and its Applications, volume 14. Springer Science & Business Media, 2013.
[17] Tim Kraska, Alex Beutel, Ed H. Chi, Jeffrey Dean, and Neoklis Polyzotis. The case for learned index structures. In SIGMOD, pages 489–504, 2018.
[18] Ravi Kumar, Manish Purohit, and Zoya Svitkina. Improving online algorithms via ML predictions. In NeurIPS, pages 9684–9693, 2018.
[19] Thodoris Lykouris and Sergei Vassilvitskii. Competitive caching with machine learned advice. In ICML, pages 3302–3311, 2018.
[20] Mohammad Mahdian, Hamid Nazerzadeh, and Amin Saberi. Online optimization with uncertain information. ACM TALG, 8(1):2:1–2:29, 2012.
[21] Andres Muñoz Medina and Sergei Vassilvitskii. Revenue optimization with approximate bid predictions. In NIPS, pages 1856–1864, 2017.
[22] Adam Meyerson. The parking permit problem. In FOCS, pages 274–282, 2005.
[23] Vahab S. Mirrokni, Shayan Oveis Gharan, and Morteza Zadimoghaddam. Simultaneous approximations for adversarial and stochastic online budgeted allocation. In SODA, pages 1690–1701, 2012.
[24] Rajeev Motwani, Steven Phillips, and Eric Torng. Nonclairvoyant scheduling. Theoretical Computer Science, 130(1):17–47, 1994.

附录 A 延迟证明

我们首先陈述一些简单的观察结果，这些结果将很有用。

Lemma A.1.

对于 $0<x\leq 1$ ，

（我）

$e^{x-\frac{1}{x}}\leq 1$ 。
(二)

$\frac{x}{e}-e^{-\frac{1}{x}}\geq 0$ 。
(三)

$1-\frac{1}{x}+\frac{e^{-x}}{x}\geq\frac{x}{e}$ 。

证明。

(i) 对于 $x\in(0,1]$ ，我们有 $x\leq 1/x\implies e^{x}\leq e^{1/x}$ ，因此 $e^{x-\frac{1}{x}}\leq 1$ 。

(ii) 对于任何 $y\leq 1$ ，我们有 $1-y\leq e^{-y}\implies e^{y}\leq\frac{1}{1-y}$ 。显示 (ii) 等同于显示 $x-e^{1-\frac{1}{x}}\geq 0$ 。但由于 $1-\frac{1}{x}\leq 1$ ，我们可以代入 $y=1-\frac{1}{x}$ 以获得

x-e^{1-\frac{1}{x}}\geq x-\frac{1}{1-(1-\frac{1}{x})}=0

(iii) 我们首先证明 $h(x):=1-\frac{1}{x}+\frac{e^{-x}}{x}$ 对于 $x\geq 0$ 是凹的（由于 $\lim_{x\rightarrow 0}h(x)=0$ ，我们在 $0$ 处定义 $h(0)=0$ 使其连续）。实际上，考虑 $h^{\prime\prime}(x)=\frac{e^{-x}(x^{2}+2x+2-2e^{x})}{x^{3}}$ 。注意，对于所有 $x\geq 0$ ，我们有 $e^{x}\geq 1+x+x^{2}/2$ ，因此我们有 $h^{\prime\prime}(x)\leq 0$ 。因此 $h(x)$ 在范围 $x\geq 0$ 内是凹的。由于凹性，我们得到对于所有 $0<x\leq 1$ ， $h(x)\geq(1-x)\cdot h(0)+x\cdot h(1)=\frac{x}{e}$ ，如预期的那样。 ∎

Lemma A.2。

令 $b\geq 2$ 为整数，令 $\lambda\in(1/b,1)$ 为实数。那么，

\frac{1/\lambda+1/b}{1-e^{-1/\lambda}}\leq\frac{1+1/b}{1-e^{-(\lambda-1/b)}}.

证明。

为方便起见，令 $y=1/b$ 并重新排列项，使得引理语句等效于显示以下内容，受制于 $\lambda\in(y,1)$ 。

(1+y)(1-e^{-1/\lambda})-(1/\lambda+y)+(1/\lambda+y)e^{y-\lambda}\geq 0.

请注意，我们在重新排列项时使用了 $\lambda\geq y$ 。使用 $e^{y}\geq 1+y$ ，只需证明以下不等式。

(1+y)(1-e^{-1/\lambda})-(1/\lambda+y)+(1/\lambda+y)(1+y)e^{-\lambda}\geq 0.

(3)

(3) 的左侧是关于 $y$ 的二次方程，写成：

f(y):=y^{2}(e^{-\lambda})+y((1/\lambda+1)e^{-\lambda}-e^{-1/\lambda})+(1-e^{-1% /\lambda}-1/\lambda+e^{-\lambda}/\lambda).

(4)

目标是证明当 $1\geq\lambda\geq y\geq 0$ 时，(4) 非负。为此，我们最小化 $f(y)$ ，受约束条件 $0\leq y\leq\lambda$ 。

$f(y)$ 的最小值在

\partial f/\partial y=0=2y(e^{-\lambda})+(1/\lambda+1)e^{-\lambda}-e^{-1/% \lambda},

产生

y_{\min}=\frac{e^{\lambda-1/\lambda}-(1/\lambda+1)}{2}\stackrel{{\scriptstyle% \mathrm{Lemma~{}\ref{lem:helper}(i)}}}{{\leq}}0.

因此，在约束条件 $y\geq 0$ 下， $f(y)$ 的最小值在 $y=0$ 处取得。将 $y=0$ 代入 (4)，我们得到

\displaystyle f(y)\geq f(0)=1-e^{-\frac{1}{\lambda}}-\frac{1}{\lambda}+\frac{e% ^{-\lambda}}{\lambda}\stackrel{{\scriptstyle\mathrm{Lemma~{}\ref{lem:helper}(% iii)}}}{{\geq}}\frac{\lambda}{e}-e^{-\frac{1}{\lambda}}\stackrel{{\scriptstyle% \mathrm{Lemma~{}\ref{lem:helper}(ii)}}}{{\geq}}0.

这完成了证明。 ∎

通过 ML 预测改进在线算法 † †thanks: 本文的会议版本 [18] 发表在 2018 年 NeurIPS 上。

摘要