李琛 李茂军 杜佳佳

摘   要：强化学习作为机器学习中的一种无监督式学习，在实际应用中的难点之一便是如何平衡强化学习中探索和利用之间的关系。在Q学习结合ε-greedy的基础上，提出了一种参数 动态调整的策略。该策略是以学习者在学习过程中各状态下的学习状况为依据，实现参数 的自适应，从而更好地平衡探索和利用之间的关系。同时，引入一种结合了试错法的动作删减机制，对备选动作集合进行"删减"，来提高学习者的探索效率。最后通过迷宫问题的实验仿真，验证了所提方法的有效性。

关键词：强化学习;ε-greedy策略;探索与利用

中图分类号：TP181                                                 文献标识码：A

A Modified Method to Reinforcement Learning Action Strategy ε-greedy

LI Chen，LI Mao-jun？覮，DU Jia-jia

（School of Electrical and Information Engineering，Changsha University of Science

and Technology，Changsha，Hunan 410114，China）

Abstract：Reinforcement learning，as an unsupervised learning in machine learning，one of difficulties problem in practical application is how to balance the relation between exploration and exploitation. To solve this problem，a dynamic adjustment strategyof parameter  basis of Q learning combined with ε-greedy strategy is presented. This strategy is based on the learning status of agent in various states of environment in the learning process，making parameter self-adaptation，to better balance the relation between exploration and exploitation.Meanwhile，an reduction method combiningtrial and error method is introduced to delete the action sets，so as to improve the exploration efficiency of agent. The simulation resultof maze verify the effectiveness of the proposed method.

Key Words：reinforcement learning;ε-greedy strategy;exploration and exploitation

強化学习作为机器学习中的一种无监督式学习，适用于解决序贯决策问题，即学会进行自动决策，且该决策能使问题朝预期较好的方向发展。其原理是通过学习者与外界环境的不断交互，同时根据外界环境给予的评价性反馈去优化自身的行动策略，从而学习到最优行动策略[1-2]。正因如此，强化学习在调度管理[3]、智能控制[4]、智能机器人[5]等领域中得到了广泛的应用。

强化学习被应用至实际问题时，学习者对于外界环境是未知的，所以学习者必须通过探索来获取相关的外界环境知识。因此在选择何种行动策略时，不可避免地会遇到强化学习的难点之一，即探索与利用的平衡[6-7]。过分的探索会影响强化学习的收敛速度，而过分利用会使强化学习容易陷入局部最优解。而目前有两种常见方法用于解决此问题：ε-greedy策略[1]和Boltzman探索机制[1]。其中，ε-greedy策略因实现简单而被广泛使用。但其参数 ε为固定值，对于动态的学习过程，其探索与利用问题仍然存在，在一定程度上影响了算法的学习速率和效率。

众多学者在ε-greedy的基础上对强化学习的探索与利用平衡问题进行了研究。文献[8]提出以信息熵定义的状态重要性测度为依据来动态调整参数 ，它能够根据不同状态的重要性测度来进行合理调节;文献[9]提出了一种基于模糊规则动态调整参数 的方法，其中模糊变量由算法经验知识信息构造;文献[10]提出以学习者成功找到目标和不同可行解数量作为共同依据动态调整参数 ，该方法本质上仍是在分阶段调整参数 ;文献[11]提出一种分段的搜索策略，使Q学习算法在学习过程中实现探索-学习-利用3个阶段的渐近跳转，虽将整个算法分为了三个阶段，但各阶段的跳转依据并未提出，较难把握;而文献[12]，从不同的角度出发，提出一种知识启发式方法，它将每一轮获得的知识进行修正、优化，用于启发下一幕的行动策略，使学习者脱离盲目的探索和利用。

对此，在Q学习结合ε-greedy的基础上，以学习者在学习过程中各状态下的学习状态为依据，设计出一种调整机制使参数 动态调整。同时，通过累积的经验知识结合试错法，对备选动作集合进行“删减”来提高学习者的探索效率。

1   强化学习与行动策略

源于TD（Temporal-Difference）时间差分法的Q-Learning算法、Sarsa算法为目前强化学习的常用算法[2]，而本文采用Q-Learning算法。

在Q-Learning算法中，每个状态-动作对都有相对应的一个Q值。所以，Q-Learning算法的学习过程是反复迭代计算学习状态-动作对的Q值。最后学习者获得的最优行动策略是选用状态s下最大Q值对应的动作。基于状态s下动作a的Q值Q（s，a）定义是，在狀态s下学习者执行动作a后，并按某一行动策略执行下去所获得的累积回报

值[13]。其Q值更新的基本方程为：

式（1）中：a为状态下可选动作;R st为t时刻状态s下环境给予的立即奖赏;α为学习速率;Q（st，at），t时刻下状态-动作对（s，a）的评价值。

由式（1）可见，学习者可通过反复尝试各状态下可能的动作，使Q值趋向最优。那么，学习者若想要获得较高的评价总和，行动策略应均选择最大Q值所对应的动作作为执行动作。但是，当算法处于学习初始阶段时，其仍处于探索学习的过程，Q值不能准确地评估状态-动作对的价值。而当算法处于学习中期阶段时，若均选择Q值最高所对应的动作，那么可能会导致学习者陷入局部最优[7]。如上所述，学习者的行动策略要有一定的随机性，这样能够让学习者在面对未知环境时具有自主学习能力。而本文研究所采用的行动策略为ε-greedy策略，是在贪婪策略的基础上引入了参数ε。所以学习者会以概率 进行探索，以1-ε的概率利用已学习的经验，选择当前Q值最高对应的动作，其数学表达式为：

式（2）中π（s），为在状态s下学习者动作的选择策略;A为状态s下学习者的可选动作集合;rand为一个范围在（0，1）内的一个随机数，且参数 的值范围为[0，1]。

2   参数动态调整与动作“删减”机制

2.1   参数动态调整机制

Peter Auer[6]指出，若采用恒值的ε-greedy策略，那么其有悔值，即误差，会随着学习次数的增加呈线性增长。所以本文提出以学习者在各状态s下的学习状况为依据，对参数 进行调整，其基本原理如图1所示。

其中difference用来分类学习者在各状态下的学习状况，其由状态-动作对（s，a）当前时间步下的最大状态-动作值Qmaxt（s，a）与（s，a）的上一时间步下对应的最大状态-动作值Qmaxt-1（s，a）与（s，a）之差表示，如式（3）所示。

若初始化时，将所有Q值初始化为0，那么根据difference及式（1）可将各状态学习状况分为如下三类所示：

（1）difference>0时，说明上一时间步，学习者根据行动策略选择的动作是“好”的，后根据环比增长率D = difference/qold_max判断学习者在该状态下是否趋于收敛;

（2）difference<0时，说明上一时间步，学习者根据行动策略选择的动作是“坏”的或选择的动作暂时对学习无贡献，那么当前时间步的动作应尽量利用现有“经验知识”来摆脱这个困境;

（3）difference=0时，说明学习已收敛或上一时间步所执行动作并不是更好的选择。无论分属于那种情况，此时学习者都应继续保持探索;

综上所述，参数ε的调整策略数学表达式为：

2.2   动作“删减”机制

由ε-greedy策略原理可知，在动作集合中，除Q值最大对应动作外的其余备选动作被选择概率是均等的。而在这些备选动作中，有些动作是“坏”的，会增加学习者到达目标点的代价。为此，引入一种结合了试错法的动作删减机制，来提高学习者在探索阶段的有效探索。

结合了试错法的动作删减机制是在行动策略作用前，将状态s对应动作集合中最小Q值对应的动作选出并删减，然后待执行动作选择完毕后，将被删减的动作恢复至对应状态s下的动作集合中，当学习者再次经历该状态时，根据更新过后的Q值，仍将Q值最小对应的动作从备选动作集中删减，如此循环执行，直至学习者该次episode训练结束。

2.3   基于改善 -greedy的强化学习实现步骤

步骤1：初始化，对于？坌s∈S，？坌a∈A，其对应的Q值初始化为0，设定学习者的初始状态、目标状态，同时设定学习速率α、折扣因子γ、探索度ε、最大学习次数Tmax等参数;

步骤2：将动作集中Q值最小对应的动作从对应动作集中剔除;

步骤3：按式（3）计算出difference，并根据式（4）计算参数 ;然后利用新计算出的参数 ，根据式（2）选择动作，执行并转移至下一状态;并根据式（1）对Q值进行更新;

步骤4：将步骤2剔除的动作恢复至对应状态下动作集中;

步骤5：若学习者到达目标点，结束此次episode的训练，并转至步骤6;否则转步骤2，继续此次episode训练;

步骤6：若学习者的学习次数T = Tmax，则结束学习者的学习;否则转至步骤1，进行下一次episode的训练;

3   仿真实验

利用迷宫问题，对引入动态调整及动作删减的改进算法进行验证。主要是将基于固定值ε-greedy（ε = 0.5）、固定值ε-greedy（ε = 0.5）并引入动作删减结合Q-Learning进行仿真比较，以及基于固定值ε-greedy、ε-decrease、所提方法改进ε-greedy结合Q-Learning进行仿真比较。仿真实验采用环境为20×20的二维网格，如图2所示。图中每一个网格代表学习者所处环境的一个状态，其中S代表学习者的初始状态，G代表学习者的目标状态，四周蓝色网格表示环境的边界，深蓝色网格表示学习者可自由活动的区域，青色网格表示障碍物。

仿真实验使用Matlab2016a软件完成。为了消除算法的随机性，每次实验均在实验环境中独立学习10次，取平均性能进行比较，其中性能由学习者从初始点到目标点所需的时间步、学习者收敛速度来综合评价。强化学习基本参数设置如下：α = 0.25，γ = 0.9，Tmax = 400。学习者每一次episode的训练，即从初始状态到目标状态的学习过程，均从初始状态出发，其动作方向设定有上、下、左、右四个方向。当学习者执行动作后，便获得外界环境反馈的即时奖赏，那么其奖赏函数设定为：

图3比较了基于固定值 ε-greedy（ε=0.5）Q-Learning与基于固定值 ε-greedy（ε=0.5）并引入動作删减的Q-Learning。可见，在学习前期，由于学习者对环境是未知的，根据Q值选出来的删减动作并不是准确的，使得引入动作删减的Q-Learning与未引入动作删减的Q-Learning在收敛速度与学习效果上大致相同。但随着学习者的不断学习，根据Q值选出的动作越来越准确，从而提高了学习者的探索效率，最终使得引入动作删减的Q-Learning要先于收敛。且在学习后期，引入动作删减的Q-Learning其平均步数要比未引入动作删减的Q-Learning少。所以实验表明这种动作删减方法的有效性。

对基于固定值ε-greedy的Q-Learning，选参数 为0.3、0.5以及0.8分别进行了实验，并将其中最佳与所提方法改进的ε-greedy结合Q-Learning进行比较。图4为基于固定值ε-greedy的Q-Learning学习曲线

可见，当参数ε = 0.8时，学习者探索过多，使得其学习收敛效果很差;而当参数ε = 0.5时，学习者在180次episode时，已基本达到收敛，但与参数 ε = 0.3时相比较，其性能相对较差。所以在本次实验中，基于参数ε = 0.3的Q-Learning表现出性能最好。

后将基于固定值ε-greedy的Q-Learning（参数ε = 0.3）、基于所提方法改进ε-greedy的Q-Learning及基于ε-decrease结合Q-Learning进行比较，如图5所示。可见，基于所提方法改进ε-greedy的Q-Learning，其学习过程较平滑，且学习收敛速度较快，最终完成的路径长度为22步左右，而基于ε-decrease及固定值ε-greedy（ε = 0.3）的最终完成的路径长度分别为26步、35步。明显，基于所提方法改进ε-greedy的算法寻得的路径更优。而且，基于ε-decrease的Q-Learning，因在学习过程中仅通过时间变化来调整参数ε，无法正确衡量Q值的评估是否准确，使得在学习过程中出现了较大的震荡。

此外，考虑到学习者可能陷入局部最优，所以当学习者收敛于一个解后，即一条可行路径，参数 便重新设定为0.5，使得学习者重新进入探索。显然，之前获得的解为当前环境下的最优解。所以，基于所提方法改进ε-greedy的Q-Learning其平均时间步数在大约100次episode时开始缓慢增大，直至200次episode后要略大于另外两种方法。但是，就整体而言，基于所提方法改进ε-greedy的Q-Learning是要比基于参数ε = 0.3及基于ε-decrease的Q-Learning具有更快更好的学习性能。

4   结   论

针对强化学习的难点之一，探索与利用之间的平衡，在Q学习结合ε-greedy的基础上，提出了一种参数 动态调整策略。该策略是以学习者在学习过程中各状态下的学习状态为依据，实现参数 的自适应。同时，引入了一种结合试错法的动作删减机制。两者共同作用，使策略ε-greedy得到了改进。最后，迷宫问题的仿真实验结果表明，较之基于固定值以及ε-decrease的方法，基于所提方法改进ε-greedy的Q-Learning不仅实现了在学习过程中自适应调节探索与利用的平衡，还提高了学习者的探索效率，使得学习者在性能上表现的更快更好。

参考文献

[1] SUTTON R S，BARTO A G. Reinforcement learning： an introduction[J]. IEEE Transactions on Neural Networks，1998，9（5）：1054—1054.

[2]   高阳，陈世福，陆鑫.强化学习研究综述[J].自动化学报，2004（01）：86—100.

[3]   宗群，孙正雅.基于平均报酬强化学习的电梯群组调度研究[J].系统仿真学报，2007（21）：4945—4948.

[4]   ABDULHAI B，PRINGLE R，KARAKOULAS G J. Reinforcement learning for true adaptive traffic signal control[J].Journal of Transportation Engineering，2003，129（3）：278—285.

[5]    YEN G G，HICKEY T W. Reinforcement learning algorithms for robotic navigation in dynamic environments[J].Isa Transac-tions，2004（2）：217—230

[6]    AUER P，ACESA-BIANCHI N，FISCHER P. Finite-time analysis of the multiarmed bandit problem[J].Machine Learning，2002，47：235—256.

[7]    MARCH J G. Exploration and exploitation in organizational learning[J]. Organization Science，1991，2（1）：71—87.

[8]    赵昀，陈庆伟.一种基于信息熵的强化学习算法[J].系统工程与电子技术，2010，32（05）：1043-1046.

[9]    HAJFOROOSH S，MENHAJ M B，ALI D M，et al. Exploration and exploitation tradeoff infuzzy reinforcement learning[J]. International Journal of Computer Applications，2011，9（5）：26—31.

[10]  赵辉，刘雅 .改进的Q学习算法在轨迹规划中的应用[J].吉林大学学报：信息科学版，2016，34（05）：697—702.

[11]  赵英男.基于强化学习的路径规划问题研究[D].哈尔滨：哈尔滨工业大学，2017.

[12]  刘智斌，曾晓勤. 基于路径引导知识启发的强化学习方法[J]. 工程科学与技术，2012，44（5）：136—142.

[13]  WATKINS C J H，DAYAN P.Q-learning[J]. Machine Learning，1992：279—292.