Resource Management with Deep Reinforcement Learning

GitHub地址：https://github.com/hongzimao/deeprm

算法说明：

本次实验采用策略梯度强化学习算法，并附加同SJF,Packer,Tetris三种调度策略的对比。代码运行之初，可选则Sjf或者Packer进行调度，获得决策数据，再运用监督学习进行网络模型的初始化，最后进行策略梯度优化比对。
整体框架结构

一.先进行监督学习

1.监督学习流程图

设计一个网络，其输入是state，通过隐藏层，输出action，再通过softmax得出动作的概率。

2.剖析监督学习流程图

2.1数据收集，获取数据

先用“SJF”或者“PACKER”的数据进行调度，获得决策轨迹，在这里，如果获得SJF，就进行get_sjf_action;如果获得PACKER，就进行get_packer_action,否则就没有评估的策略，输出no policy known to evaluate

if pa.evaluate_policy_name == "SJF":
	    evaluate_policy = other_agents.get_sjf_action
	elif pa.evaluate_policy_name == "PACKER":
	    evaluate_policy = other_agents.get_packer_action
	else:
	    print("Panic: no policy known to evaluate.")	

2.2保存环境状态为数据X，对应决策为标签y，将X，y划分为训练集，测试集

X_train, X_test = X[:num_train], X[num_train: num_train + num_test]
y_train, y_test = y[:num_train], y[num_train: num_train + num_test]

2.3进行监督学习的训练start trainin
（1）训练数据迭代，先初始化training的err，acc，batches，初始为0

for batch in iterate_minibatches(X_train, y_train, pa.batch_size, shuffle=True):
	    inputs, targets = batch
	    err, prob_act = pg_learner.su_train(inputs, targets)
	    pg_act = np.argmax(prob_act, axis=1)
	    train_err += err
	    train_acc += np.sum(pg_act == targets)
	    train_batches += 1

（2）测试数据迭代，先初始化test的err，acc，batches，初始为0

for batch in iterate_minibatches(X_test, y_test, pa.batch_size, shuffle=False):
    inputs, targets = batch
    err, prob_act = pg_learner.su_test(inputs, targets)
    pg_act = np.argmax(prob_act, axis=1)
    test_err += err
    test_acc += np.sum(pg_act == targets)
    test_batches += 1	

（3）打印出迭代的结果，training loss,training accuracy,test loss,test accuracy

print("Epoch {} of {} took {:.3f}s".format(
    epoch + 1, pa.num_epochs, time.time() - start_time))
print("  training loss:    \t\t{:.6f}".format(train_err / train_batches))
print("  training accuracy:\t\t{:.2f} %".format(
    train_acc / float(num_train) * 100))
print("  test loss:        \t\t{:.6f}".format(test_err / test_batches))
print("  test accuracy:    \t\t{:.2f} %".format(
    test_acc / float(num_test) * 100))

二.再进行Policy Gradient算法训练

1.policy Gradient流程图

在神经网络中，输入state，输出动作，根据softmax得到动作的概率，并用策略梯度进行训练迭代，输出的动作作用于环境environment，环境作用于下一个状态state_,并输出reward，利用reward的奖励直接对选择行为的可能性进行增强或减弱，再得到下一个动作，重复上述过程。

2.代码解读及相关问题

2.1，思路
作者的实现思路基本是，先根据网络结果选动作，进行蒙特卡洛采样以获得一个完整的episode，即具有序列时间步的(s,a,r)；利用(s,a)作为训练数据，训练三层的神经网络：

	输入层节点数：20*124；
	隐藏层节点数：20；
	输出层节点数：6；
	训练参数：20*124*20+20+20*6+6=49746

2.2，解读
（1）策略函数表示为

用马尔可夫决策过程的一个轨迹（trajectory）

for _ in xrange(episode_max_length):
    act_prob = agent.get_one_act_prob(ob)
    csprob_n = np.cumsum(act_prob)
    a = (csprob_n > np.random.rand()).argmax()

    obs.append(ob)  # store the ob at current decision making step
    acts.append(a)

将策略生成轨迹T的概率为

for i in xrange(len(trajs)):
    for j in xrange(len(trajs[i]['reward'])):
        all_ob[timesteps, 0, :, :] = trajs[i]['ob'][j]
        timesteps += 1

策略梯度方法的目标就是找到一组最佳的参数来表示策略函数使得累计奖励的期望最大，即

（2）采用RMS算法进行参数的训练
RMSprop 全称 root mean square prop 算法，和动量方法一样都可以加快梯度下降速度

for dim in range(len(grads)):
    accums[dim] = rho * accums[dim] + (1 - rho) * grads[dim] ** 2
    params[dim] += (stepsize * grads[dim] / np.sqrt(accums[dim] + epsilon))
（

（3）定义交叉熵函数，用于反应算法收敛程度
损失函数设置为交叉熵损失（s状态下真实动作a和网络预测动作a的差距）和价值函数（在一个episode中，每个时间步状态的值函数）的乘积。
softmax与交叉熵结合输出先过softmax函数，再计算y与y_的交叉熵损失函数

`tf.nn.softmax_cross_entropy_with_logits(y_,y)          y是预测值y_是已知答案`

tf.nn.sparse_softmax_cross_entropy_with_logits函数的计算过程。简单说，就是先对网络输出通过softmax即类别的概率分布，接着根据分类维度将正确标签转换为one-hot向量，最后计算交叉熵。

（4）进行蒙特卡洛采样
函数在某个变量θ处的梯度等于该处函数值与该函数的对数函数在此处梯度的乘积：

这里用到了Softmax策略：是针对一些具有离散的行为常用的一个策略。我们希望有平滑的参数化的策略来决策：针对每一个离散的行为，应该以什么样的概率来执行它。

l_out = lasagne.layers.DenseLayer(
    l_hid,
    num_units=output_length,
    nonlinearity=lasagne.nonlinearities.softmax,
    # W=lasagne.init.Normal(.0001),
    W=lasagne.init.Normal(.01),
    b=lasagne.init.Constant(0)

Softmax策略下Score函数的值容易计算，可以写成如下的形式：

三.结果分析

3.1，打印出相关数据，最大奖励，平均奖励，平均收敛，平均交叉熵等

3.2，绘制出“SJF”，“Tetris”，“Random”，“PG”的测试数据CDF对比图

3.3，训练490次后的PG，Tetris，SJF，Random的奖励和情况

3.4，训练490次后的奖励和，收敛曲线对比图：PG最优

四.细节补充

Dedign：

具有d种资源类型的集群（CPU，memory，I/O、、、、）
作业以离散的时间步长以在线方式到达集群，调度程序在每个时间步选择一个或多个等待作业进行调度，每个job j的资源概况由资源要求的向量给出rj= (rj,1, . . . , rj,d)，和工作的持续时间Tj，我们先假定没有抢占和固定的分配配置，也就是说从作业开始到执行完成，rj必须是连续分配的资源，

Objective：

我们将job slow作为主要的系统目标，对于每一个slow，Sj：Sj= Cj/Tj。Cj是工作的完成时间。Tj表示工作的持续时间，Sj≥ 1

State space :

我们代表系统的state–集群资源的当前分配和等待调度的作业的资源配置文件—作为不同的图像，我们只为到的前M个作业（尚未被调度）来维护图像，

Action space:

调度器可能想要接纳M个作业的任何子集。但是这将需要一个2^M大的动作空间，这将使学习变得非常具有挑战性，我们使用小的技巧来保持动作空间：我们允许agent在每个时间步骤中执行多个操作，动作空间是{∅,1, . . . , M}，a = i意思是在第i个节点中调度job，a = ∅是一个无效动作，表示agent不希望在当前时间步长内安排更多作业，每个步长中，时间被冻结，直到调度选择无效的动作。
集群映像上移一个时间步长，新到达的作业就会显示给agent，通过将代理的决策序列从实时解耦，代理可以在同一时间步长调度多个作业，同时保持动作空间在M

Training:

为了是策略一般化，我们考虑在训练期间工作到达序列的多种例子（jobset），在每次的训练迭代中，对每个jobset，我们模拟N个episode来去探索可能动作的可能空间，使用resulting data来提高所有jobset的策略，我们记录每个episode所有步的（state，action，reward）计算折扣累积奖励，使用梯度下降训练神经网络。