【深度学习】论文推荐：DeepRM——系统自己学习管理自己的资源

推荐一篇关于DeepRM的论文

《Resource Management with Deep Reinforcement Learning》

系统和网络中的资源管理问题已经是计算机系统中一个很常见的问题，通常表现为困难的在线决策任务，其包括集群的作业调度、云计算中虚拟机的放置、视频流中的比特率自适应、拥塞控制等，适当的解决方案依赖于对工作负载和环境的理解。

目前大部分问题都使用了启发式的方法解决了，这种启发式方法典型的设计流程是：

（1）为简化的问题模型并提出启发式方法;

（2）在实践中不断测试和调整启发式方法以获得良好的性能。 如果问题的某些方面（例如负载或度量）发生变化，则通常必须重复此过程。

那么之所以资源管理比较具有挑战性有以下几点原因：

（1）系统本身很复杂，并且很难去为它准确的建模；

（2）实际的实例化需要在有噪声输入的情况下做出在线决策，并且还需要在不同的条件下运行的很好；

（3）一些性能指标很难以一定的原则进行优化。

受人工智能问题深度强化学习最近取得的进展的启发，这篇论文中作者构建能够直接从经验学习管理资源的系统。本文提出DeepRM，这是一个示例解决方案，它是一个简单的集群资源调度器，将深度强化学习的方法应用到系统的资源管理上，DeepRM将多资源维度下的任务打包问题转化为了一个学习问题，通过反馈学习来优化各种目标进而保证资源管理的高效性，例如最小化作业完成时间等。DeepRM不需要提前知道系统的一些知识，即它刚开始对手头的任务是一无所知的，它直接通过和系统交互产生的经验来进行更好的决策，根据它在任务中的表现得到的奖励来进行学习。本文表明，将深度强化学习技术应用于大规模系统是可行的。实验表明，对于多资源集群调度问题，DeepRM的性能与最先进的启发式算法相当，可以适应不同的条件，快速收敛，并学习后见之明的策略。

这可能听起来像是我们提议构建天网，但最近将机器学习应用到其他具有挑战性的决策领域的成功表明，这个想法可能不是太遥不可及。特别是，强化学习已经成为机器学习研究中的一个活跃领域。RL研究的是那些直接从与环境互动的经验中学习做出更好决定的智能体。开始对手头的任务一无所知，并通过强化来学习——这是一种基于它完成任务的好坏而获得的奖励。RL有着悠久的历史，但最近它与深度学习技术相结合，在一些应用中发挥了巨大的作用，如玩视频游戏，计算机围棋，冷却数据中心等。

我们认为RL方法特别适合于资源管理系统。首先，这些系统做出的决策通常具有高度重复性，因此会为RL算法生成大量的训练数据（例如，集群调度决策和结果性能）。 第二，RL可以将复杂的系统和决策策略建模为类似于用于游戏代理的模型的深层神经网络。 可以将不同的“原始”和嘈杂信号合并为这些神经网络的输入，并且可以将所得到的策略用于在线随机环境中。 第三，有可能对难以直接优化的目标进行培训，因为如果存在与目标相关的奖励信号，它们就缺乏精确的模型。 最后，通过继续学习，RL代理可以针对特定的工作负载（例如，小工作，低负载，周期性）进行优化，并在变化的条件下保持良好。

作为了解RL在资源管理方面的潜力的第一步，我们设计和评估DeepRM（一种简单的多资源集群调度程序）。 DeepRM在在线设置中运行，其中作业动态到达，并且一旦计划就无法抢占。 DeepRM学会优化各种目标，例如最大程度地减少平均作业速度或完成时间。 我们将在文中描述模型，并将调度任务作为RL问题来处理。 为了学习，DeepRM采用了文中描述的标准策略梯度强化学习算法。

我们在综合数据集上使用DeepRM进行了模拟实验。 我们的初步结果表明，在各种负载下，DeepRM的性能均比标准启发式算法（如最短工作优先（SJF）和受Tetris启发的打包方案）好。 它从经验中学习策略，并留出一些资源直接为将来到来的短期工作提供服务。 特别是，DeepRM不需要了解系统行为的任何先验知识即可学习这些策略。 而且，DeepRM可以通过使用不同的强化奖励来支持各种目标。

强化学习

考虑图1所示的一般设置，其中代理与环境进行交互。 在每个时间步骤t，代理观察到某种状态st，并要求其选择一个动作。 在执行该操作之后，环境状态将转换为st + 1，并且代理会收到回报rt。状态转换和奖励是随机的，且状态转换的概率和报酬仅取决于环境的状态和代理商采取的行动。

RL公式

图二表示状态表示的示例，具有两个资源和三个挂起的作业插槽。

状态空间

我们将系统状态（群集资源的当前分配和等待调度的作业的资源配置文件）表示为不同的图像（请参见图2）。 群集图像（每个资源一个；图中最左边的两个图像）显示了从当前时间步长开始到未来的T个时间步长，每个资源对已计划服务的作业的分配。 这些图像中不同的颜色代表不同的工作。 例如，图2中的红色作业计划在接下来的三个时间步使用两个CPU单元和一个内存单元。 作业插槽图像表示等待作业的资源需求。 例如，在图2中，插槽1中的作业具有两个时间步长，其中需要两个CPU单元和一个内存单元。

理想情况下，该状态下的作业槽位映像数量与等待服务的作业数量一样多。 但是，希望具有固定状态表示，以便可以将其用作神经网络的输入。 因此，我们仅维护要到达的前M个作业（尚未调度）的图像。 状态的待办事项部分汇总了有关除第一个M之外的任何作业的信息，该信息仅计算此类作业的数量。 从直觉上讲，将注意力集中在较早到达的工作上就足够了，因为合理的政策可能更喜欢等待时间更长的工作。 这种方法还具有限制动作空间的优势，从而使学习过程更加有效。

行动空间

在每个时间点，调度程序都可能希望接受M个作业的任何子集。但是，这将需要2M大小的大型动作空间，这可能会使学习非常困难。我们使用一个技巧来使操作空间保持较小：我们允许代理在每个时间步长执行一个以上的操作。动作空间由{∅，1，，。 。 。 ，M}，其中a = i表示“将作业安排在第i个位置”； a =∅是“无效”操作，它指示代理程序不希望在当前时间步长安排进一步的作业。在每个时间步长，时间都将冻结，直到调度程序选择无效操作或无效操作（例如，尝试调度不“适合”的作业，例如图2中插槽3的作业）。有了每个有效的决定，就会在集群中的第一个可能的时间步（即可以完全满足任务的资源要求直到完成）的第一个时间步中计划一个作业。然后，代理会观察到状态转换：计划的作业将移动到群集映像中的适当位置。代理选择a =∅或无效操作后，时间实际上就会继续：群集图像会向上移动一个时间步，并且所有新到达的作业都会显示给代理。通过将座席的决策序列与实时解耦，座席可以在同一时间步安排多个作业，同时使动作空间保持线性。

Training algorithm

我们将策略表示为神经网络（称为策略网络），该神经网络将上述图像的集合作为输入，并输出所有可能动作的概率分布。我们在情景环境中训练政策网络。在每个情节中，都会有固定数量的作业到达并根据策略进行安排。当所有作业完成执行时，情节终止。

为了训练通用的策略，我们考虑了训练过程中职位到达顺序的多个示例，此后称为工作集。在每次训练迭代中，我们为每个作业集模拟N个情节，以探索使用当前策略的可能动作的概率空间，并使用结果数据来改进所有作业集的策略。具体来说，我们记录每个情节所有时间步的状态，动作和奖励信息，并使用这些值来计算每个情节每个时间步t的（折扣）累积奖励vt。然后，我们使用第2节中所述的REINFORCE算法的变体训练神经网络。

回想一下，REINFORCE使用公式（2）估计策略梯度。 该方程式的缺点是梯度估计可能具有高方差。 为了减少方差，通常会从收益率vt中减去基线值。 基线可以以不同的方式计算。 我们采用的简单方法是使用返回值的平均值vt，其中平均值是在具有相同工作集的所有情节4的相同时间步长t上获取的。 图3显示了训练算法的伪代码。

图4绘制了DeepRM与其他方案在不同负载水平下的平均作业速度降低情况。每个数据点平均是100多个新的实验，其中训练期间未使用作业集。正如预期的那样，我们看到（1）平均速度随着群集负载的增加而增加；（2）SJF的性能优于Packer，因为它首先分配了较小的作业，并且（3）Tetris通过结合它们的优势胜过两种启发式方法。该图还显示，DeepRM可与所有启发式算法相媲美，并且往往优于所有启发式方法。正如我们将很快看到的那样，DeepRM在较高的负载下击败了Tetris⋆，因为它会自动学习以保持一些资源的空闲状态，以便可以快速安排在不久的将来到达的小型作业。使用Tetris⋆，有时小任务可能需要等待，直到现有的任务完成，因为Tetris⋆会强制执行工作保护，当无法抢占工作时，这可能并不总是最好的策略。值得注意的是，DeepRM能够直接从经验中学习此类策略，而无需事先知道哪种策略适用。

DeepRM与其他方案在不同负载水平下的平均作业速度降低情况

 图5显示了群集高度负载（负载= 130％）时两个目标的行为（平均作业减速和平均作业完成时间）。

结论

这篇文章表明将最新的Deep RL技术应用于大规模系统是可行的。早期实验表明，对于多资源集群调度问题，RL代理具有可比性，并且比临时启发式算法好一些。 如果能够从实践中直接学习资源管理策略，那么它可以为当前基于启发式的方法提供真正的替代方案。