一種強化學習行動策略ε-greedy的改進方法

李琛 李茂軍 杜佳佳

摘 ? 要：強化學習作為機器學習中的一種無監督式學習，在實際應用中的難點之一便是如何平衡強化學習中探索和利用之間的關系。在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.