一种用于网格计算中作业调度的新型多智能体强化学习方法

原标题：A novel multi-agent reinforcement learning approach for job scheduling in Grid computing

Abstract

网格计算利用分布式异构资源来支持大规模或复杂的计算任务，合适的资源调度算法对于网格应用的成功至关重要。由于网格环境的复杂性和动态特性，传统的基于模型的方法在实践中可能会导致调度性能不佳。可扩展性和适应性是网格作业调度的主要目标之一。在本文中，针对作业调度问题，特别是在网格中实现负载平衡，提出了一种称为顺序共享学习 (OSL) 方法的新型多智能体强化学习方法。该方法通过使用有序的分布式学习策略规避了可扩展性问题，并基于有限通信的信息共享机制实现了多主体协调。仿真结果表明，OSL方法可以有效地达到负载均衡的目的，其性能在大多数情况下甚至可以与某些集中式调度算法相媲美。还说明了所提方法的收敛性和适应性。

Introduction

主要介绍了网格计算的背景和作业调度问题，指出了传统的基于模型的方法在面对资源异构性、资源性能变化和应用程序多样性等方面存在的挑战。然后，介绍了强化学习在解决这些问题方面的优势，并提出了一种基于多智能体强化学习的作业调度方法。

在本文中，为了在大规模网格环境中实现基于学习的协调和泛化，提出了一种称为序数共享学习 (OSL) 方法的新型多智能体强化学习方法来解决网格计算的作业调度问题。在OSL方法中，基于序号信息共享机制设计了一种快速分布式学习算法。与以前用于作业调度的多智能体强化学习（MARL）方法相比，OSL 方法有两个方面的创新。一方面简化了作业调度中最优决策的建模，其中仅在线学习效用表来估计资源效率，而不是构建复杂的网格信息系统（GIS）。另一方面通过多智能体系统有限通信的有效信息共享机制规避了可扩展性和协调问题，其中有序共享策略使所有智能体共享它们的效用表并依次做出决策。在模拟的大规模网格计算环境中对所提出的方法进行了评估，结果表明了其有效性和可行性。

最后，简要介绍了本文的组织结构和贡献。

Problem statement

A general job scheduling model in Grids

由于网格计算的NP-Complete特性和调度算法在网格场景中的最优性难以证明，现有的研究总是试图寻找次优解。为了描述网格计算的动态性，随机性以及异构性，研究了通用的 Gird 作业调度模型，如图2所示：

主要组件包括用户、调度程序和资源，其中不同的调度程序并行处理作业。他们负责从用户那里接收作业并将其分配给资源。与传统并行和分布式系统中的对应物不同，网格调度器通常不能直接控制资源，而是像代理体一样工作.每个调度器都可以向任何计算资源提交作业，并最终生成作业到资源的映射.在上述模型中，用户只是生产并向调度程序提交作业，他们的角色可以完全由作业创建者代替。工作到达或工作负荷的模型可以用泊松过程或其他基于概率的模型或自相关模型来描述.

在大型网格系统中，由于缺乏对资源的控制，资源更新周期长，调度器可用的资源信息存在时间延迟，可能不准确。因此，作业调度器的有限可观察性成为基于及时准确信息的作业调度算法的障碍，有必要开发更鲁棒和自适应的调度算法，这是本文的主要动机之一。

一般来说，Grids 中的分散作业调度问题可以建模为多智能体作业调度系统 [29]，表示为 6 元组$⟨G，R，P，D，C，SR⟩$，其中$G=⟨g_1,…,g_N⟩$是一组智能体，$s = {s_1,…,s_M}$是一组资源，$P:G\times N\rightarrow[0,1]$是作业提交函数,$D:G\times N \rightarrow \mathbb R$是概率作业大小函数,$C:G\times N \rightarrow \mathbb R$是概率容量函数，SR是作业调度规则。

为了专注于作业调度任务，上述模型进行了一些抽象，但保持了网格计算环境的主要特征，即动态的、大规模的用户和资源的异构性。尽管没有详细考虑实际实施的设计问题，例如网络拓扑，但图 2 中的模型足够通用，因为可以开发不同的代表性模型，包括随机作业提交函数、作业大小函数和容量函数，以描述网格工作负载的显着属性。利用网格工作负载的随机或自相关模型，可以研究处理网格作业调度问题的动态性、随机性和异构性的作业调度算法。

下面，为了便于讨论，假设所有的调度器都使用相同的调度算法，并且所有的作业只需要 CPU 资源，因此它们的持续时间 J 是唯一的。

Performance measures for job scheduling in Grids

在上面的 Grid 调度模型中，资源执行分配的作业，并且它们的能力可能不同.每个资源都以其处理能力 C 为特征，它被定义为完成单位长度作业所需的 CPU 时间的倒数，即如果资源需要持续时间 t 来完成长度为 J = 1 的单位作业，则其容量为$C = 1/t$。此外，假设队列中的所有作业都按到达时间排列优先级，因此在给定时间只有一个作业在资源上执行，而其他作业则在队列中等待。

网格作业调度中的常见性能度量是平均每个动作时间 (ATPT)。time-per-token (TPT) 是通过作业生成和完成之间经过的时间来衡量的，因此相应的平均标准，即 ATPT，可以制定如下：

$ATPT=\frac{1}{L} \sum_{i=1}^{L}TPT^i = \frac{1}{L}\sum_{i=1}^{L}(t_{wait}^i + t_{execute}^i)$

$TPT^i$是第i个作业的总耗时，它是队列等待时间$t_{wait}^i$（一个作业提交到开始执行的耗用时间）与实际执行时间$t_{execute}^i$之和，L表示所有资源完成的工作的总数。但是ATPT无法及时表征整个网格系统的调度性能，因为只有在作业完成后，才能更新此指标。如果资源中的作业队列很长，ATPT 的更新会严重延迟。最后，ATPT 的值仅仅反映了过去的作业调度效率，而不是当前的。

因此，使用了另一个有效的指标，即资源负载（LoR，或 makespan）。LoR定义为队列中作业的总长度$l_{total}$除以当前资源的容量$C_i$，系统的平均LoR（ALoR）可以完全代替平均每令牌时间。 ALoR 可以表示为：

$ALoR = \frac{1}{M}\sum_{i=1}^{M}LoR^i=\frac{1}{M}\sum_{i=1}^{M}(l_{total}^{i}/C_i) \=\frac{1}{M}\sum_{i=1}^{M}(\sum_{j=1}^{L^i}J_j^i/C_i)$

其中 $LoR_i$ 是第 i 个资源的负载,$l^i_{total}$ 是队列中作业的总长度，它是所有排队作业长度$J_j^i$的总和,$L_i$ 是第 i 个资源队列中的作业数，$M$是资源数。新绩效指标的优点是显而易见的，因为它能够及时、全面地反映系统绩效。

作业调度算法的目标是最小化 ALoR 及其标准偏差。最小化上述两个量将确保整个系统的效率和公平性。除了上述两个指标外，资源中的最大 LoR 是反映瞬态性能的另一个指标。

The OSL method for adaptive job scheduling

如上所述，在实际的大型网格应用中，即使有 GIS 系统的帮助，调度器中的资源信息也存在时间延迟并且可能不准确。因此，开发一种不依赖于精确模型的鲁棒调度算法是合理的。为了满足自适应作业调度的要求，协调的多智能体强化学习方法可能是一个合适的解决方案。在下文中，在对不同的 MARL 框架进行分析之后，提出了一种用于资源选择和作业调度的新型分散式 MARL 方法，其中多个智能体或调度程序之间的协作控制是通过顺序共享学习方法实现的。

Basic frameworks for multi-agent reinforcement learning

大多数单智能体 RL 算法都基于马尔可夫决策过程 (MDP) 的形式.然而，作为强化学习在分布式决策环境中的延伸，多智能体强化学习必须解决多个智能体共存打破环境平稳性的问题。到目前为止，许多 MARL 算法都是基于随机博弈 (SG) 模型 [33] 开发的，例如 JAL [34] 和 Team-Q 算法 [35]。然而，可扩展性差和信息利用效率低是MARL成功应用于大规模应用的两大障碍。对于图 2 中描述的作业调度问题，调度器和资源的数量非常多，因此，以前的MARL方法很难被采用。

除了SG模型，MARL的另一个框架是将单智能体强化学习技术直接扩展到多智能体系统，即让每个智能体根据局部状态和局部奖励独立学习，无需显式通信。这种技术在 MARL [34] 中称为独立学习器 (IL) 方法，并且在文献 [5,36,37] 中开发了一些 IL 算法。尽管 IL 的 MARL 方法不需要探索呈指数增长的联合状态-动作空间，但环境将不再是静止的，MARL 中将存在收敛问题和振荡行为。正如我们将在 4.1 节中说明的那样，如果在网格中的作业调度中使用没有协调和通信的 IL 方法，通常会出现羊群行为 [22]。

为了解决上述困难，多智能体强化学习的一种有前途的方法是通过信息共享和协调进行局部学习，以实现效率和最优性之间的平衡。基于这个想法，一种称为 OSL 算法的新 MARL 方法将在以下讨论中提出。

The OSL algorithm for job scheduling in Grids

为了克服 MARL 中的“维数灾难”问题，我们提出了具有降低的计算复杂性和改进的协调机制的 OSL 算法。新算法有两个主要特点。首先，它采用分布式 RL 框架并采用新颖的基于效用表的学习策略。由于 OSL 方法仅利用局部信息进行学习，因此它是一种基于独立学习者的 RL 方法。其次，它利用通信成本有限的信息共享机制来解决多主体协调问题。

OSL 的方案如图 3 所示。上面的循环表示共享实用程序表的调度程序。效用表仅随资源数量 M 线性增加，因此通信成本有限。下半部分详细表示调度程序智能体。每个调度器智能体主要包括两部分：Learner 和 Actor。 Learner 以有序的方式从前面的 agent 接收并共享效用表，并决定为 Job Buffer 中排队的作业选择资源。 Reward Converter 可以分析作业的完成信号并将其转换为奖励信号，这对于更新效用表至关重要。 Actor接收到新的job，并安排它们在Job Buffer中排队，然后根据Learner的决定将其提交到相应的资源中，并将提交记录在Submitted Job List中。最后，Actor 根据作业的完成情况更新 Submitted Job List，即如果一个作业完成了，那么它将从 Submitted Job List 中删除。

一般来说，OSL的实施需要考虑两个关键问题：

首先，虽然众所周知全局资源状态是调度器决策的基础，但由于调度器的观察和通信能力有限，很难在动态环境中获得所有调度器的准确信息。在本文中，提出了一种利用职位信息来估计状态的间接方法。调度器将提交作业的信息记录为向量$（n_r，t_s，t_e，J）$，即使用的资源名称$n_r$，作业开始时间$t_s$，作业完成时间$t_e$，作业大小$J$.然后，它抽象估计相应资源状态的信息。但是，如果调度程序从未向资源提交作业，则它对此一无所知。因此，这种来自个人经验的估计仅包含全局状态的部分信息。为提高估算精度，必须采取信息共享等有效手段。

其次，很难直接获得学习的即时奖励。环境不能直接提供任何全局强化信号，而只能提供单个作业完成信号。因此调度器智能体必须将此类信息转换为奖励信息。事实上，由于其他调度器的存在，一个作业的time-per-token是由所有调度器的策略共同决定的。如何从上述信息中计算出合适的强化信号将是一个问题。更重要的是，当一个调度器等待其提交的作业的反馈时，网格环境可能会由于其他调度器的操作而发生变化，因此一个调度器只有在作业完成后才更新其效用表为时已晚。一种可能的解决方案是开发一种奖励机制，无论调度程序是否执行作业提交，都会在每个时间步创建奖励信息。

在下面的小节中，为了解决上述问题，将提出一种新颖的奖励生成机制和信息共享机制。

The decentralized learning strategy using utility tables

在上述模型中，调度智能体被描述为 $G = {g_1, g_2, . . . , g_N }$，其中每个调度智能体 gi 可以负责多个用户的作业调度。资源由$ S = {s_1, s_2, . . . , S_M}$表示。类似于强盗问题 [24] 的学习方法，智能体 $g_i$ 保留一个效用表 $U_i$ 来对资源的效率进行评分，其中 $U^i{(j)}$ 表示第 j 个资源的效率，或者对从资源集 S，即 $j ∈ {1, 2, . . . , |S|} = {1, 2, . . . , M}$中选择第 j 个资源的动作进行评分。调度程序 $g_i$的效用表如图 4 所示。

对于去中心化学习过程中的每个时间步，agent $g_i$基于以下两个步骤执行资源选择操作和效用更新操作：

第1步：agent $g_i$检查判断是否有新的job到达。如果不是，转步骤2。如果是，重复执行步骤1，直到所有作业都被调度。 Agent $g_i$ 选择得分最高的资源 $s_j$，然后将作业提交给资源 $s_j$，并将其作为未完成的作业记录在已提交的作业列表中。如果执行第 j 个动作，则获得瞬时奖励 $r(j) = −1$，同时更新该动作对应的效用 $U^i{(j)}$：

$U^i(j) = (1 - \alpha) * U^i(j) + \alpha * r(j)$

其中的$\alpha$是学习率。

第 2 步：Agent $g_i$ 推进空闲调度进程并更新效用。如上所述，即使没有作业提交，也会为每个步骤设计一个瞬时奖励信号。Agent $g_i$ 根据提交的作业列表中的作业状态为每个动作创建强化信号，即：

$u(j) =\left {
\begin{array}{c}
+1 \ \ \ only \ the \ job \ is \ finished \
0 \ \ \ no \ job \
-1 \ \ \ job\ is\ unfinished
\end{array}
\right. \ \ j \in {1,2,…,M}.$

如果多个作业被提交到同一个资源，每个作业都会有一个独立的强化信号。最后，可以通过将所有信号相加来计算相应动作的奖励：

$r(j)=\sum_{k=1}^{K^j}u(k)$

其中 $K^j$ 表示当前提交给第 j 个资源的作业数。例如，假设当前智能体向第一个资源提交了 3 个作业，并且在一个时间步之后，一个作业完成而另外两个作业未完成。所以选择第一个资源的瞬时奖励是：$r(1) = 1 + 2 * (−1) = −1$。当获得整个奖励向量$ (r(1), r(2), . . , r(N))$ 时，可以使用上面的等式更新每个资源的效用。

此时，agent $g_i$ 可以使用效用表 Ui 来估计所有资源的效率。例如，如果一个资源的队列很长或者资源的容量很差，调度器向它提交作业后，调度器必须等待很长时间才能收到资源的完成响应。因此，调度器获得奖励信号 −1 的次数要比获得奖励 +1 的次数多得多。最后，这种资源对应的效用价值会很小。显然，根据效用表，效用值越大，资源状态越好。连续更新操作及时反馈资源的工作状态，为分配连续作业做出可行的决策至关重要。

在上面的小节中，建立了一个效用表来估计资源的效率。开发了一种改进的奖励和更新机制来指示资源的效率。然而，在网格应用程序中，有多个调度程序智能体。如果所有智能体都独立且同时学习和做出决策，则会出现协调问题。显然，调度器的任何决定都会改变资源的状态，但其他调度器在将作业提交到同一资源之前不会检测到更改（它们通过使用队列中的等待时间间接检测到这一点）。因此，特定智能体中的效用表不能准确指示资源的真实状态。此外，随着调度器数量的增加，可能的冲突将变得更加严重。因此，必须为网格作业调度问题中的分布式学习开发一种可行的协调机制。

由于每个智能体都拥有一个本地效用表来估计资源的效率，因此通过共享效用表来提高估计精度是一种自然的方式。但是，由于Grids中的scheduler agent数量非常多，不可能直接共享每个utility table。因此，本文提出了一种有限通信的序号共享机制来满足上述需求。智能体之间的协调是通过按顺序和迭代共享相邻智能体的效用表来实现的。如图4所示，效用表仅与资源规模成线性比例。因此智能体之间的总通信成本很低并且始终保持不变。

为了实现信息共享机制，通过将Agent排序为$g_1，g_2，… . . , g_N$，为所有调度智能体定义了一个序数结构。 , 那么智能体共享它们的效用表并按顺序进行决策，即智能体 $g_i$ 共享前面智能体的效用信息如下：

$U^i(j) = (1 - \beta) * U^i{j} + \beta * U^{i-1}(j)$

其中的$\beta$是共享因子。$U^{i-1}(j)$是相邻智能体$g_{i-1}$的效用表并且它包含了所有的之前的智能体对资源效用的估计。最终，最后一个agent的效用表返回给第一个agent再次共享。换句话说，效用共享过程是有序的和迭代的。

表 1 显示了网格作业调度中智能体 gi 的 OSL 算法的主要过程。

与其他MARL算法相比，OSL算法更适合在大规模作业调度应用中实现。作为一种基于效用表的学习方法，效用表函数中没有显式的状态变量，因此更适应资源和应用高度多样化和动态化的网格场景。此外，OSL 的另一个重要优势是协调的通信成本低。信息交换总量是简单效用表，其规模与资源数量成线性关系，远低于直接通信模式下的指数级。

Performance evaluation and discussions

在本节中，将在模拟中评估和分析用于作业调度的基于 OSL 的选择 (OSLS) 规则的性能。此外，将所提出的 OSLS 方法与其他四种资源调度或选择规则进行了比较，它们是分散的最小-最小选择（DMMS）[38]、随机选择（RS）、最小负载选择（LLS）和简单学习选择（ SLS）[5]。 Min-Min算法是一种启发式调度方法，成为性能比较的基准调度算法[38]。基于分散的调度模型，每个调度器独立执行分散的Min-Min算法。即使有 GIS 系统的帮助，在动态环境中调度程序的决策也可能无法被其他人准确知晓。原因是GIS中的信息更新总是不可避免地存在时间延迟。在 RS 方法中，智能体根据均匀概率分布为作业随机选择资源。在 LLS 方法中，智能体选择负载最少的资源来提交作业。如果有多个资源具有相同的最小负载，则随机选择其中一个。该选择规则假定智能体可以获得准确的全球资源信息，例如，来自理想的 GIS 系统。在 SLS 方法中，智能体执行独立的强化学习过程。它与提议的 OSLS 方法的不同之处在于，智能体在收到来自资源的已提交作业的最终完成信号之前不会更新其效用表，并且每个智能体都在没有任何协调信息的情况下独立学习 [5]。

网格系统的规模可以定义为智能体数$(N)$和资源数$(M)$的组合$(N，M)$。在每个时间步中，每个调度智能体$g_i$ 可能会收到带有泊松过程生成的随机数的作业。工作的到达率表示为 $ξ$ 。作业的长度是从 $[J_{min}, J_{max}]$ 区间内的均匀分布中随机生成的。资源的容量也在区间 $[C_{min}, C_{max}]$ 中统一选择。所以系统可以用参数集$(N，M，ξ，[J_{min}，J_{max}]，[C_{min}，C_{max}])$来描述。因此，由Grids的总处理能力和到达的作业总数共同确定的期望系统负载$γ_{system}$可以计算为：

$γ_{system} = \frac{J_{total}}{C_{total}} = \frac{\sum_{j=1}^N(J_j^{\alpha v}\xi)}{\sum_{i=1}^{N}C_i} = \frac{\sum_{j=1}^N((J_{min} + J_{max})/2\xi_{j})}{\sum_{i=1}^{N}C_i} * 100%$

其中$J_j^{\alpha v}$ 是第 j 个调度程序的作业长度的中值。显然，系统负载不应超过 100%，否则调度系统会崩溃。事实上，超过 90% 的系统负载对于 Grids 来说是非常沉重的。一个有效的作业调度算法可以公平、充分地利用所有资源来平衡系统的负载。为了测试新方法的负载均衡能力，下面进行了几个实验。

Performance evaluations under different system scales

为了实验不同的系统规模，选择了三种系统规模，即(30, 100)、(100, 250)和(300, 1000)。这些配置足够大，可以代表典型网格计算环境的规模。作业长度的分散范围设置为 [5, 995]。资源容量的区间为[50, 350]。工作到达率分别为0.93、0.7和0.93。所以所有的系统负载大约在 70% 左右。它是网格应用程序的典型中等系统负载。仿真结果如图 5 所示。

图5中不同作业调度方法的ALoR曲线表明，在中等系统负载下，只有OSL方法、DMMS方法和LLS方法在不同的系统规模下实现了高效的负载均衡。显然，LLS方法是一种集中式的方法，可以达到最优的调度策略。但昂贵的计算和通信成本阻碍了它在现实世界网格中的有效应用。 DMMS方法可以平衡负载，但效率低于LLS方法，因为非协调决策可能会发生冲突，导致某些资源的过度利用/利用不足。 OSL算法是去中心化的，只需要有限的通信成本，但可以针对不同的系统规模获得更好的次优策略。结果表明，一开始，OSL 方法的性能可能比 DMMS 和 LLS 差。这是因为使用 OSL 方法的调度器没有网格的先验知识，但是使用其他两种启发式方法的调度器可以从 GIS 系统中获取环境信息。当基于 OSL 的调度器通过试验积累了足够的经验时，最终可以获得良好的调度性能。

如图所示，SLS规则的性能很差，无法完成作业调度任务。出现这种现象的主要原因是奖励机制不当和同步问题。对于 SLS 方法，无论其 bandit-like 模型如何，它都采用延迟奖励机制。此外，基于 SLS 的调度器无需协调即可独立学习和工作。显然，这种行为会导致某些资源过度利用，而导致其他资源利用不足，这会降低调度性能。这种病理被称为羊群行为 [18,19]。

具有 RS 规则的智能体随机选择资源，根本不考虑它们的效率，因此低容量资源上的 LoR 将无限增长。最后，平均负载 ALoR 增加失控。此外，对于 RS 规则，确实规模越大，性能越差。

Performance evaluations under different system loads

为了测试新方法在不同系统负载下的自适应性能，选择了50%、70%和90%三种系统负载配置，系统规模设置为(100, 250)。其他参数与前一个实验相同。图 6 显示了不同系统负载下 ALoR 的变化曲线。很明显，OSL 方法允许智能体比 RS 和 SLS 方法更有效地在资源之间安排作业。此外，即使系统负载增加，OSL 方法也可以收敛到次优策略。因此，所提出的 OSL 方法可以适应不同的系统负载。从图 6 可以看出，对于低系统负载，OSL 甚至可以收敛到一个接近最优的策略，其性能与集中式 LLS 方法相似。当系统负载增加时，OSL 也可以找到与 LLS 相当的次优策略。

Performance evaluations under different resource capacities

在前面的模拟中，资源容量的区间很宽，即 [50, 350]。事实上，不同的时间间隔会显着影响系统性能。下面选择资源容量的一个窄区间[150, 250]，再次进行上述系统规模(200, 500)的模拟。结果如图 7 所示。

在图 7 中，当系统负载较轻时（γsystem ≤ 70%），RS 方法可以很好地进行作业调度。原因可能是所有资源的容量都大于 150，足以避免保持较长的作业队列。此外，SLS 方法在系统负载较低时也可以获得良好的性能，如图 7（a）所示。然而，RS 和 SLS 都无法在高系统负载下获得良好的性能，如图 7（b）和（c）所示。当系统负载增加时，RS方法的性能下降，最终变得不可行。然而，OSL 方法可以实现不同资源容量一致的负载平衡。

Performance evaluations under different numbers of schedulers and resources

在下面的模拟中，调度器数量和资源数量的不同比例被选择为（500, 200）和（1000, 500）。作业长度的区间和资源容量的区间分别为 [5, 995] 和 [250, 750]。作业到达率为 0.2 和 0.4（因此系统负载分别为 50% 和 80%）。结果如图 8 所示。从图 8 可以看出，当调度器的数量远大于资源的数量时，SLS 方法具有良好的性能。结果与文献[5]的结论一致。如此好的成绩，可能是因为就业率低，资源能力强。然而，对于现实世界的网格，调度器的数量多于资源的数量并不常见。此外，请注意 SLS 规则的性能在不同条件下仍然不如 OSL 方法。

Other performance measures

除了平均资源负载 (ALoR) 之外，还可以使用其他指标来衡量系统性能。通常，ALoR 表示系统的宏观性能，但瞬态性能，例如资源中的最大 LoR（或完工跨度）也很重要。此外，LoR 的标准偏差是评估作业调度算法效率的另一个指标。无花果。图 9 和图 10 显示了 4.1 节中相应的实验结果。

从以上两个图中可以发现，OSLS 的最大 LoR 和偏差收敛，而 RS、SLS 和 DMMS 规则发散很快。尽管 OSLS 曲线的幅度随着系统规模的增加而增加，但它们最终趋于平稳。在不同的系统负载下获得了相同的结果。换句话说，所有结果表明OSL算法的瞬态性能和效率是令人满意的。

在上述所有模拟中，学习率和共享因子均设置为 0.5。事实上，学习因素和共享因素可以看作是新信息和过去经验之间的折衷，以及代理人自己的知识和他人的知识。可以为这两个参数选择一些不同的配置。下面进行与4.1(b)节相同条件的实验，分别评估不同的学习率和共享因子。

图 11(a) 显示了 OSL 在不同学习率下的性能变化，分别为 0.2、0.5 和 0.8，其中共享因子等于 0.5。图 11(b) 显示了 OSL 在不同共享率下的性能变化，分别为 0.2、0.5 和 0.8，其中学习率等于 0.5。结果表明，α 和 β 的值太大或太小都可能导致不理想的调度性能。从实证研究中，可以选择学习率和共享因子的中间值以获得良好的性能。

Summary

根据以上实验，OSL算法的优势是显而易见的。通过使用序数共享学习机制，OSL 算法实现了与集中式和基于模型的方法（即 LLS 方法）相当的性能，但计算成本低得多且通信受限。此外，新方法对工作条件的敏感性低于其他算法，并实现了基于 MARL 的有效负载平衡。表 2 显示了本文研究的不同作业调度方法之间的比较总结。

对于 Grids 中基于 RL 的作业调度问题，还有一些其他相关工作。在[5]中，SLS 方法被用于网格作业调度。然而，上述实验结果表明，SLS方法仅在用户数远大于资源数的某些特殊情况下具有良好的性能。此外，其性能仍有待提高。

在 [6] 中，作者针对网格和其他分布式系统等领域的分布式任务分配问题引入了一种名为加权策略学习器 (WPL) 的新梯度上升学习算法。 WPL 可以在不观察其他智能体行为的情况下学习随机策略。然而，由于观测信息有限且难以获得平衡解，多智能体梯度上升法的收敛速度较慢，尤其是对于大规模问题。因此，作者只是针对一个小规模的问题测试了 WPL，其中服务器和用户的数量都不超过 5 个。

为了解决动态资源分配中的协调学习问题，在[39,27]中提出了一些基于价值函数的RL算法。为了将标准 Q 学习扩展到具有较大或连续状态-动作空间的资源分配问题，研究了具有函数逼近的 RL 方法。然而，大规模网格应用的问题仍然难以解决。在 [25,26] 中，一种名为 Fair Action Learner (FAL) 算法的多智能体 RL 方法被应用于以分散的方式跨集群共享资源。 FAL 采用直接策略搜索技术，即策略梯度上升 (PGA) 算法来学习决策策略。但是从他们的实验结果来看，学习过程的收敛速度还是很慢.

在 [40] 中，作者将资源分配问题视为复合 MDP，并提出了一种简化的本地化 RL 方法，其中动作、状态和奖励都是绝对本地化的。本地 RL 方法在数据中心原型的资源分配任务中进行了测试，并获得了一些有希望的结果。但是，智能体之间的适当协调对于获得更好的系统性能至关重要。

Conclusions

网格计算的主要关注点之一是开发在动态环境中具有自配置和自优化能力的自主计算系统。本文提出了基于多智能体强化学习的OSL方法来解决Grids中的作业调度问题。该方法通过使用分布式学习策略规避了可扩展性问题，并实现了基于有序信息共享机制的多智能体协调。最后，对OSL算法的性能进行了评价，并与其他算法进行了比较，研究并模拟了一种通用的网格作业调度模型，以描述网格的动态性、随机性、异构性。仿真结果表明，适当的在线学习方法可以对异构网格系统中的负载平衡质量产生实质性的积极影响，并说明了OSL算法的有效性和效率。未来的工作可能包括在实际网格环境中改进和应用所提出的方法。