Page 129 - 《软件学报》2021年第8期

杨世贵 等:基于强化学习的温度感知多核任务调度 2411

2 基础知识

2.1 强化学习概述
强化学习属于机器学习范畴内的一个重要分支,其本质是通过与环境连续的交互来寻找一个最优的决策.
强化学习中包含有智能体(agent)、环境(environment)、状态(state)、动作(action)和奖励(reward).强化学习模仿
了生物通过与外界交互来在环境中进行决策的行为(如图 1 所示):智能体通过执行动作来影响环境,环境接收到
新动作之后会产生新的状态,并对刚才的动作进行一个奖励反馈,根据所返回的新的状态来决定其需要进行的
动作.强化学习的训练过程就是智能体不断地根据当前环境状态进行动作决策,同时根据环境反馈的奖励值及
时改进其决策的过程,最终的目标是找寻一个最优策略,即智能体能够从环境状态改变的过程中累积尽可能多
的奖励值.

State t(状态)

Reward t(奖励)
ENV(环境) Agent(智能体)

(奖励)
Action t
Fig.1 Reinforcement learning
图 1 强化学习
强化学习与机器学习中其他需要大量训练数据的学习算法不同,它不需要使用大量的数据样本,而是通过
不断的试错进行自我学习,这种自动进行学习和决策的方法能够解决监督学习方法所面临的由于系统动态性
所导致的训练数据不全面的问题,更适用于多核温度感知调度算法.
2.2 Q-Learning算法
随着强化学习的发展,在 Q-Learning 的基础上出现了很多效果更稳定的强化学习算法,如 A3C [23] 、DDPG [24]
等.但是这些算法相比于 Q-Learning 会带来更大的开销:更新策略过程中的算力开销和推理最佳动作的时间开
销,这对于系统级的算法来说是不可接受的.为了权衡调度算法的开销和调度算法的最终效果,ReLeTA 最终选
择 Q-Learning 作为框架中的学习算法.Q-Learning 算法是一个基于价值的离轨策略算法,Q 值指的是智能体在
特定状态下执行特定动作所能够获得奖励的期望值 [25] ,算法通过建立一个以状态(state)为行、动作(action)为列
的 Q 表来存储和更新 Q 值,Q 值的更新如式(1)所示:
Q(S t ,A t )←Q(S t ,A t )+α[R t+1 +γmaxQ(S t+1 ,A t+1 )−Q(S t ,A t )] (1)
其中,α,γ分别表示学习率和折扣系数.α用于控制每次 Q 值更新的幅度,决定了算法收敛的速度以及最终算法的
收敛效果,学习率较大则收敛较快但可能导致最终的性能不稳定.为了节省时间和保证最终收敛的效果,一般将
学习率初始化为较大的值,然后逐渐缩小.γ是数值在 0~1 之间的折扣因子,强化学习的目标是为了能获得更多的
长期收益,智能体会对未来动作的收益进行考虑.但是未来动作的选择具有不确定性,且离当前时间点越远对当
前动作的影响越小,所以在 Q 值的计算中,将未来可能执行动作的 Q 值进行折扣.γ值为 0,则只考虑当前的奖励.γ
值越大,则表示对未来考虑的越多.Q-Learning 中智能体的决策使用了ε-greedy 策略:智能体的决策包括两个部
分,其中一个是应用(exploit),另一个是探索(explore).智能体以 1−ε(0<ε<1)的概率选择目前 Q 值最大的动作,这
就是对当前学习到的策略的应用.而探索是指智能体以ε的概率随机选择动作来探索可能存在的更优的策略,这
样做能防止智能体学到次优策略.
Q-Learning 算法通过图 2 所示的步骤实现:首先构建一个 m×n 的 Q 表(其中,m 为状态数,n 为动作数),并将
表格内的值初始化为 0.智能体根据当前的状态来计算所有动作的 Q 值,结合 Q 值和ε-greedy 策略来选择动作,
决策后会获得新的状态和一个回报值,然后使用式(1)来更新 Q 表,在反复的迭代更新 Q 表后,智能体会学习到较