基于动作概率的强化学习动作探索策略

于 飞 郝建国 张中杰

(国防科技大学智能科学学院 湖南 长沙 410005)

0 引 言

近年来,算法的改进、计算能力的进步为机器学习带来了长足的发展,但机器学习需要大量训练样本支持限制了其在某些领域的发展。2016年以来,将深度学习与强化学习相结合的AlphaGo[1]击败世界围棋冠军,AlphaGo Zero[2]将深度强化学习进一步与树搜索的lookahead 机制相融合仅训练3天就击败了前辈AlphaGo,它们的出现将强化学习研究推向顶峰,使得强化学习受到极大的推动发展。

强化学习是一种有别于监督学习和无监督学习的机器学习方法,它通过控制动作与环境交互获得环境奖励,利用奖励值更新动作策略,以实现决策的优化。 强化学习的两个最重要的特征是试错搜索和延迟奖励[3]。

在强化学习过程中,Agent的目标是在未知环境中通过试错来获得最大的奖励。在未对环境进行充分地探索前,Agent难以找到最优的策略。因此存在如何根据环境状态进行动作选择的问题,即探索(exploration)与利用(exploitation)问题[4]。

探索与利用的平衡不仅仅是强化学习中存在的困境,包括人类、动物等生物在任何未知环境中进行决策都会存在探索与利用问题。一般认为,如果行为在各个选项之间没有重点的交替选择,则认为是探索。如果只在某些选项中进行重点选择且随着时间的推移变得稳定,则认为是在利用。人类或动物在动作探索后会获取某些信息或奖励来指导下一次的动作探索[5]。

在强化学习中,Agent在强化学习过程中依据已有经验选择当前最优的动作,即贪婪地选择动作认为是利用。Agent在强化学习过程中随机地进行动作选择认为是在探索。

一方面,更多地探索未知的动作空间,可以获得更多的信息以搜索全局最优解,但探索过多会降低算法性能且会导致算法不收敛的情况。另一方面,过多的利用会因对环境知识的未知而导致选择次优的行为。因此,如何平衡探索与利用之间的关系成为影响强化学习算法性能的关键。通常的办法是ε-greedy策略和Softmax分布策略[3]。ε-greedy策略是在贪婪算法的基础上增加了参数ε,当ε为0时,ε-greedy策略就转化为贪婪策略,ε由0逐渐增大至1的过程中,探索的程度逐渐增加;ε为1时,ε-greedy策略就转化为随机选择动作。Sutton已经证明了,ε-greedy策略性能优于贪心策略。ε-greedy策略虽然一定程度上解决了探索与利用之间的问题,但由于参数ε固定,探索与利用的问题仍然存在,且存在参数ε难以设定,对非最优动作之间不加区分等问题。Softmax分布策略依据动作的价值大小计算动作选择概率,对不同价值的动作进行了概率上的区分,克服了ε-greedy策略存在的不足,但是存在当动作价值差距不大时无法区分最优动作与其他动作且计算量较大的问题[6]。

大量学者针对ε-greedy策略和Softmax分布策略存在的问题做了改进和完善。文献[7-9]均将计数机制引入到动作探索中,来改善基础方法在动作探索中存在的不足。Guo等[10]将模拟退火(Simulated Annealing)算法中的Metropolis准则引入Q-learning的动作选择机制,提出了SA-Q-learning算法。Chen等[11]将量子系统中两个量子态之间的保真度作为反馈信息,提出了基于保真度的概率动作选择机制,基于此提出了基于保真度的概率Q-learning算法,并在量子系统中进行了验证。陈启军等[12]针对强化学习存在的问题提出了“行动分值”的概念,据此来进行动作选择,并在行动分值的基础上优化奖励函数。文献[4, 13]将ε-greedy与Softmax结合来解决开发与利用的平衡问题,其中文献[13]利用时间差分误差来动态调整ε参数,而文献[4]利用中长期奖励的差异来动态调整ε参数。

以上的动作探索策略可以统一地归为无向探索方法,另一类与之对应的探索策略称为有向探索[14]。Sledge等[15]利用各状态中有关动作的信息,将信息论的相关方法引入到强化学习的动作探索中,以此启发式方法来提高探索效率。李晨溪等[16]利用云推理模型,将先验知识、规则引入强化学习,引导Agent的动作选择,减少动作探索前期的盲目性。文献[17-19]则是将先验知识引入到动作探索策略中,来减少前期的无效探索以提高探索效率。

本文提出了一种新的动作选择策略。新策略定义了“动作概率(action probability)”的概念,并据此进行动作偏好选择,以解决探索与利用之间的平衡问题。最后通过实验验证了该方法的可行性。

1 基于动作概率的动作探索策略

1.1 马尔可夫决策过程

许多强化学习问题都是基于马尔可夫决策过程(MDP)提出的,一个MDP由元组(S,A,P,R,γ)构成,其中:S为状态集,A为动作集,P为状态转移函数P:S×A×S→[0,1],R为奖励函数R:S×A→R,γ为折扣系数。

在每个时间步t,Agent观察到状态st∈S,依据策略π选择动作at∈A,与环境进行交互,环境依概率转移到新的状态st+1,并给予Agent奖励R。这里对状态的转移做出了马尔可夫假设,即转化到下一状态的概率,只与当前状态有关,与之前的状态无关。

1.2 强化学习

当策略π(a|s)确定后,存在一个完整的状态序列(s1,a1,r1,s2,a2,r2,…,st,at,rt)。强化学习的目的就是最大化序列奖励。

为了便于描述状态之间的优劣,强化学习引入了状态价值函数:

vπ(s)=Επ(Rt+1+γRt+2+γ2Rt+3+

…|St=s)

(1)

和动作价值函数:

qπ(s,a)=Επ(Rt+1+γRt+2+γ2Rt+3+

…|St=s,At=a)

(2)

由此可以得到两个函数的贝尔曼方程:

vπ(s)=Επ(Rt+1+γvπ(St+1)|St=s)

(3)

qπ(s,a)=Επ(Rt+1+γqπ(St+1,At+1)|St=

s,At=a)

(4)

而最优状态价值函数与最优动作价值函数分别为:

(5)

(6)

这里以Q-learning算法为例。Q-learning算法[20]由Watkins在1989年最先提出,是一种不需要知道模型状态转移概率的模型无关(Model-free)算法,是一种时序差分离线控制算法。Q-learning是在知道环境状态集S,动作集A,即时奖励R的条件下,求解最优动作价值函数q*和最优策略π*。此类问题的求解,与蒙特卡洛(Monte Carlo)类似均是采用值迭代的方法,通过值函数的更新,来更新策略,通过策略来产生新的状态和即时奖励,进而更新值函数。

Q-learning算法使用两个控制策略,一个策略用于选择新的动作,另一个策略用于更新值函数。基于当前状态S,依据动作选择策略选择执行动作A,环境因此转移到状态S′,选择状态S′中价值最大的动作A′更新值函数。Q-learning算法过程如图 1所示, 其数学表示为:

Q(S,A))

(7)

图1 Q-learning算法拓扑图

Watkins等[21]在1992年证明满足以下条件:

(1) 奖励值有界|rn|≤R。

(2) 学习率0≤αn<1。

当n→∞时,Q(s,a)以概率1收敛为Q*(s,a)。

Q-learning算法步骤:

输入:状态集S,动作集A,步长α,衰减因子γ,迭代轮数T。

输出:所有的状态-动作对Q(s,a)值。

初始化Q(s,a);

从1循环至T;

1) 初始化一个初始状态s;

2) 依据探索策略选择状态s下执行动作a;

3) 执行动作a,得到新状态s’和奖励r;

4) 更新动作价值函数:

5)s=s′;

6) 如果S′是终止状态,当前轮迭代完毕否则转到步骤2)。

1.3 动作探索策略

强化学习问题的解决就是要找到Agent与环境交互的最优策略π*,寻找在各个状态S下的最优动作价值函数q*使得在各个状态S下选择最优的动作,其数学式表示为:

(8)

(9)

因此,寻找最优策略问题转化为寻找在所有策略下产生的动作状态值函数中的最大者。

常用的方法中ε-greedy策略是最接近贪婪的动作选择策略,通常设置一个参数ε,以(1-ε)的概率选择当前最优动作,以ε的概率在所有动作中随机选择,其公式表示为:

(10)

式中:m为状态s下动作集的大小。

而Softmax分布策略则是根据动作值函数的大小来计算动作选择概率,将动作的值函数转化为范围在[0,1]的概率分布,其数学表示为:

(11)

无论是ε-greedy策略还是Softmax分布策略,都是在迭代的过程中,使动作值函数最大的动作拥有最大的选择概率。基于此,本文提出了基于动作概率的选择机制。

定义1动作概率表示Agent在某个状态下执行某一动作的概率值。状态-动作对的动作概率初始值为该状态的动作集大小的倒数,即:

(12)

式中:card(As)表示状态s下动作集As中动作的个数。

动作概率根据动作的值函数大小进行动态调整。Agent在状态S下,根据动作概率选择动作A,执行动作后,Agent获取奖励R,进入状态S′,并选择值函数最大的动作A′来更新价值函数。随后,依据状态S下各个动作的值函数大小进行排序,将动作分成两类:值函数最大的为一类;其余的为第二类。将第二类中各个动作的动作概率值减半平均加到最大类中。其更新的过程如图2所示。

图2 算法更新过程

Agent在完成一次动作后,按照状态动作值函数的大小,更新动作概率。其更新规则如下:

(13)

式中:m为变化率,表示动作概率的变化速率;A*(s)为值函数最大的动作集,ai为集合A*(s)中的动作,aj为值函数非最大的动作。

在初始阶段,所有动作概率是相等的,动作选择是随机选择。当某一动作探索过后,若此次探索导致其奖励值为负值,会使这一动作的动作概率值减半,其他动作的动作概率值增加,在探索初期,会使得动作探索更倾向于选择未执行过的动作。若探索导致动作奖励为正,表明这次的探索是有益的探索,会使这个动作的动作概率增加,其他动作的动作概率降低,倾向于更多地选择此动作;但其他动作仍存在探索的概率,可以防止动作探索陷入局部最优的情况发生。

例如,Agent在状态s下的动作空间A(s)={up, down, left, right}。先后经历了三次,分别选择了{up}、{down}、{left},获取的奖励值分别为-1、-2和1。其动作概率的更新见表 1。

表1 动作概率更新过程

续表1

基于动作概率的Q-learning算法步骤如下:

输入:状态集S,动作集A,步长α,衰减因子γ,迭代轮数T。

输出:所有的状态-动作对Q(s,a)值。

从1循环至T;

1) 初始化一个初始状态s;

2) 依据探索策略选择状态s下执行动作a;

3) 执行动作a,得到新状态s′和奖励r;

4) 更新动作价值函数:

5) 更新动作概率:

6)s=s′;

7) 如果s′是终止状态,当前轮迭代完毕否则转到步骤2)。

2 实验与结果分析

本文设置两组对照实验,分别为实验一和实验二。两次实验均采用格子世界作为实验环境,不同之处在于实验一中障碍为固定的,实验二中为移动障碍物,学习难度更大。在两次实验中,分别采用了Q-learning算法和DeepSARSA算法以验证本文提出的动作探索策略的灵活性,并与ε-greedy策略和Softmax分布策略做出对比。

2.1 实验一

实验采用强化学习中常用的迷宫世界为实验环境,其界面如图3所示。

图3 迷宫世界

采用了21×9的方格表示,其中车辆表示Agent,旗帜表示迷宫出口,实心方格表示墙体。Agent动作空间A(s)={up, down, left, right},每次动作,Agent移动一个方格。当Agent到达边界时选择朝向边界的动作并不会使Agent离开地图而是保持不动,当Agent在墙体附近并选择向墙体运动时不会使Agent撞墙而是保持不动。

有关强化学习中参数设置,如表2所示。

表2 强化学习参数

2.2 实验一分析

实验分别使用ε-greedy策略、Softmax分布策略与动作概率策略进行对比分析,其中ε-greedy策略分别采用ε值为0.1、0.2和0.3三个值,强化学习算法均采用Q-learning算法,以排除学习算法对不同探索策略的影响。每轮迭代不设置最大动作上限,共迭代500轮,每种策略运行5次,采集5组数据进行分析。

图4为5种探索策略经过5次实验后得到的结果,为了防止出现单次数据对实验的影响,图中数据为5次实验后取平均值得到。该迷宫地图的最优解为25步,动作概率策略在迭代至40轮后开始收敛至最优解,Softmax分布策略在迭代至60轮后开始收敛,ε-greedy策略同样在迭代至60轮后开始收敛,但因ε值固定导致收敛效果较差。

图4 不同探索策略最优解比例

图5为5种探索策略前200轮迭代中,迭代步数的箱式图。可以看出,动作概率策略和Softmax策略的中位数相近,ε-greedy策略的中位数要大于前两种策略;动作概率策略的探索步数较其他策略更加集中且步数最少。

图5 不同探索策略迭代步数

2.3 实验二

实验环境与实验一类似,同样为格子世界,如图6所示。

图6 格子世界

采用了10×10的方格表示,其中方块为Agent,圆形为目标,三角形为障碍物。Agent动作空间与实验一一致,障碍物每两个离散时间步会左移一格,到达边界时变为相反方向移动。其中强化学习的相关参数设置,如表3所示。

表3 强化学习实验参数

2.4 实验二分析

此实验,采用三种动作探索策略,分别为ε-greedy策略、Softmax分布策略及本文提出的探索策略。并将三种动作探索策略与深度强化学习DeepSARSA算法结合。其中,DeepSARSA采用三层全连接层的模型进行训练。

本次实验中,为防止因ε值固定导致收敛效果差的情况发生,采用了参数值随探索次数增大而降低的方法。ε初始值设为1,随后根据探索次数不断降低,直至降到0.01。

每轮迭代不设置最大动作上限,共迭代1 000轮,每种策略运行5次,采集5组数据进行分析。

图7为三种不同策略经过迭代1 000轮迭代后最优路径占总迭代轮数的比例,其中最优路径以最高得分82分为准。可以看出,本文提出的动作探索策略在迭代至25轮左右,就探索至最优路径;Softmax分布探索策略在迭代至45轮左右,探索至最优路径;而ε-greedy探索策略在迭代至200轮左右,才可探索至最优路径。图中的线条在80轮、400轮、600轮和800轮时发生明显的抖动,说明算法陷入到局部最优的情况,但是经过一段时间的探索,Softmax探索和本文提出的探索策略均能跳出局部最优的情况收敛至全局最优,但本文提出的探索策略收敛速度更快,且更加稳定。

图7 三种探索策略最优解占比

表4给出了三种算法的实验结果。

表4 三种算法的实验结果

3 结 语

本文研究了强化学习中动作探索策略,介绍了现有的平衡探索与利用问题的多种算法,分析了它们存在的不足。提出了一种基于动作概率的动作探索策略,通过动态调整动作概率来进行动作偏好选择。并将动作探索策略分别与Q-learning和DeepSARSA结合。实验表明,该方法较现有算法能够更快收敛至最优解,探索步数分布更加集中且数量更少,且灵活性较大,可与多种强化学习算法结合。

下一步工作是将该动作概率探索策略应用于连续状态空间中,利用概率密度函数来表述动作概率,以拓展该策略的应用范围。