一種強化學(xué)習(xí)行動策略ε-greedy的改進方法

李琛 李茂軍 杜佳佳

摘 ? 要：強化學(xué)習(xí)作為機器學(xué)習(xí)中的一種無監(jiān)督式學(xué)習(xí)，在實際應(yīng)用中的難點之一便是如何平衡強化學(xué)習(xí)中探索和利用之間的關(guān)系。在Q學(xué)習(xí)結(jié)合ε-greedy的基礎(chǔ)上，提出了一種參數(shù) 動態(tài)調(diào)整的策略。該策略是以學(xué)習(xí)者在學(xué)習(xí)過程中各狀態(tài)下的學(xué)習(xí)狀況為依據(jù)，實現(xiàn)參數(shù) 的自適應(yīng)，從而更好地平衡探索和利用之間的關(guān)系。同時，引入一種結(jié)合了試錯法的動作刪減機制，對備選動作集合進行"刪減"，來提高學(xué)習(xí)者的探索效率。最后通過迷宮問題的實驗仿真，驗證了所提方法的有效性。

關(guān)鍵詞：強化學(xué)習(xí);ε-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

強化學(xué)習(xí)作為機器學(xué)習(xí)中的一種無監(jiān)督式學(xué)習(xí)，適用于解決序貫決策問題，即學(xué)會進行自動決策，且該決策能使問題朝預(yù)期較好的方向發(fā)展。其原理是通過學(xué)習(xí)者與外界環(huán)境的不斷交互，同時根據(jù)外界環(huán)境給予的評價性反饋去優(yōu)化自身的行動策略，從而學(xué)習(xí)到最優(yōu)行動策略[1-2]。正因如此，強化學(xué)習(xí)在調(diào)度管理[3]、智能控制[4]、智能機器人[5]等領(lǐng)域中得到了廣泛的應(yīng)用。

強化學(xué)習(xí)被應(yīng)用至實際問題時，學(xué)習(xí)者對于外界環(huán)境是未知的，所以學(xué)習(xí)者必須通過探索來獲取相關(guān)的外界環(huán)境知識。因此在選擇何種行動策略時，不可避免地會遇到強化學(xué)習(xí)的難點之一，即探索與利用的平衡[6-7]。過分的探索會影響強化學(xué)習(xí)的收斂速度，而過分利用會使強化學(xué)習(xí)容易陷入局部最優(yōu)解。而目前有兩種常見方法用于解決此問題：ε-greedy策略[1]和Boltzman探索機制[1]。其中，ε-greedy策略因?qū)崿F(xiàn)簡單而被廣泛使用。但其參數(shù) ε為固定值，對于動態(tài)的學(xué)習(xí)過程，其探索與利用問題仍然存在，在一定程度上影響了算法的學(xué)習(xí)速率和效率。

眾多學(xué)者在ε-greedy的基礎(chǔ)上對強化學(xué)習(xí)的探索與利用平衡問題進行了研究。文獻[8]提出以信息熵定義的狀態(tài)重要性測度為依據(jù)來動態(tài)調(diào)整參數(shù) ，它能夠根據(jù)不同狀態(tài)的重要性測度來進行合理調(diào)節(jié);文獻[9]提出了一種基于模糊規(guī)則動態(tài)調(diào)整參數(shù) 的方法，其中模糊變量由算法經(jīng)驗知識信息構(gòu)造;文獻[10]提出以學(xué)習(xí)者成功找到目標和不同可行解數(shù)量作為共同依據(jù)動態(tài)調(diào)整參數(shù) ，該方法本質(zhì)上仍是在分階段調(diào)整參數(shù) ;文獻[11]提出一種分段的搜索策略，使Q學(xué)習(xí)算法在學(xué)習(xí)過程中實現(xiàn)探索-學(xué)習(xí)-利用3個階段的漸近跳轉(zhuǎn)，雖將整個算法分為了三個階段，但各階段的跳轉(zhuǎn)依據(jù)并未提出，較難把握;而文獻[12]，從不同的角度出發(fā)，提出一種知識啟發(fā)式方法，它將每一輪獲得的知識進行修正、優(yōu)化，用于啟發(fā)下一幕的行動策略，使學(xué)習(xí)者脫離盲目的探索和利用。

對此，在Q學(xué)習(xí)結(jié)合ε-greedy的基礎(chǔ)上，以學(xué)習(xí)者在學(xué)習(xí)過程中各狀態(tài)下的學(xué)習(xí)狀態(tài)為依據(jù)，設(shè)計出一種調(diào)整機制使參數(shù) 動態(tài)調(diào)整。同時，通過累積的經(jīng)驗知識結(jié)合試錯法，對備選動作集合進行“刪減”來提高學(xué)習(xí)者的探索效率。

1 ? 強化學(xué)習(xí)與行動策略

源于TD（Temporal-Difference）時間差分法的Q-Learning算法、Sarsa算法為目前強化學(xué)習(xí)的常用算法[2]，而本文采用Q-Learning算法。

在Q-Learning算法中，每個狀態(tài)-動作對都有相對應(yīng)的一個Q值。所以，Q-Learning算法的學(xué)習(xí)過程是反復(fù)迭代計算學(xué)習(xí)狀態(tài)-動作對的Q值。最后學(xué)習(xí)者獲得的最優(yōu)行動策略是選用狀態(tài)s下最大Q值對應(yīng)的動作?；跔顟B(tài)s下動作a的Q值Q（s，a）定義是，在狀態(tài)s下學(xué)習(xí)者執(zhí)行動作a后，并按某一行動策略執(zhí)行下去所獲得的累積回報

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

式（1）中：a為狀態(tài)下可選動作;R st為t時刻狀態(tài)s下環(huán)境給予的立即獎賞;α為學(xué)習(xí)速率;Q（st，at），t時刻下狀態(tài)-動作對（s，a）的評價值。

由式（1）可見，學(xué)習(xí)者可通過反復(fù)嘗試各狀態(tài)下可能的動作，使Q值趨向最優(yōu)。那么，學(xué)習(xí)者若想要獲得較高的評價總和，行動策略應(yīng)均選擇最大Q值所對應(yīng)的動作作為執(zhí)行動作。但是，當算法處于學(xué)習(xí)初始階段時，其仍處于探索學(xué)習(xí)的過程，Q值不能準確地評估狀態(tài)-動作對的價值。而當算法處于學(xué)習(xí)中期階段時，若均選擇Q值最高所對應(yīng)的動作，那么可能會導(dǎo)致學(xué)習(xí)者陷入局部最優(yōu)[7]。如上所述，學(xué)習(xí)者的行動策略要有一定的隨機性，這樣能夠讓學(xué)習(xí)者在面對未知環(huán)境時具有自主學(xué)習(xí)能力。而本文研究所采用的行動策略為ε-greedy策略，是在貪婪策略的基礎(chǔ)上引入了參數(shù)ε。所以學(xué)習(xí)者會以概率 進行探索，以1-ε的概率利用已學(xué)習(xí)的經(jīng)驗，選擇當前Q值最高對應(yīng)的動作，其數(shù)學(xué)表達式為：

式（2）中π（s），為在狀態(tài)s下學(xué)習(xí)者動作的選擇策略;A為狀態(tài)s下學(xué)習(xí)者的可選動作集合;rand為一個范圍在（0，1）內(nèi)的一個隨機數(shù)，且參數(shù) 的值范圍為[0，1]。

2 ? 參數(shù)動態(tài)調(diào)整與動作“刪減”機制

2.1 ? 參數(shù)動態(tài)調(diào)整機制

Peter Auer[6]指出，若采用恒值的ε-greedy策略，那么其有悔值，即誤差，會隨著學(xué)習(xí)次數(shù)的增加呈線性增長。所以本文提出以學(xué)習(xí)者在各狀態(tài)s下的學(xué)習(xí)狀況為依據(jù)，對參數(shù) 進行調(diào)整，其基本原理如圖1所示。

其中difference用來分類學(xué)習(xí)者在各狀態(tài)下的學(xué)習(xí)狀況，其由狀態(tài)-動作對（s，a）當前時間步下的最大狀態(tài)-動作值Qmaxt（s，a）與（s，a）的上一時間步下對應(yīng)的最大狀態(tài)-動作值Qmaxt-1（s，a）與（s，a）之差表示，如式（3）所示。

若初始化時，將所有Q值初始化為0，那么根據(jù)difference及式（1）可將各狀態(tài)學(xué)習(xí)狀況分為如下三類所示：

（1）difference>0時，說明上一時間步，學(xué)習(xí)者根據(jù)行動策略選擇的動作是“好”的，后根據(jù)環(huán)比增長率D = difference/qold_max判斷學(xué)習(xí)者在該狀態(tài)下是否趨于收斂;

（2）difference<0時，說明上一時間步，學(xué)習(xí)者根據(jù)行動策略選擇的動作是“壞”的或選擇的動作暫時對學(xué)習(xí)無貢獻，那么當前時間步的動作應(yīng)盡量利用現(xiàn)有“經(jīng)驗知識”來擺脫這個困境;

（3）difference=0時，說明學(xué)習(xí)已收斂或上一時間步所執(zhí)行動作并不是更好的選擇。無論分屬于那種情況，此時學(xué)習(xí)者都應(yīng)繼續(xù)保持探索;

綜上所述，參數(shù)ε的調(diào)整策略數(shù)學(xué)表達式為：

2.2 ? 動作“刪減”機制

由ε-greedy策略原理可知，在動作集合中，除Q值最大對應(yīng)動作外的其余備選動作被選擇概率是均等的。而在這些備選動作中，有些動作是“壞”的，會增加學(xué)習(xí)者到達目標點的代價。為此，引入一種結(jié)合了試錯法的動作刪減機制，來提高學(xué)習(xí)者在探索階段的有效探索。

結(jié)合了試錯法的動作刪減機制是在行動策略作用前，將狀態(tài)s對應(yīng)動作集合中最小Q值對應(yīng)的動作選出并刪減，然后待執(zhí)行動作選擇完畢后，將被刪減的動作恢復(fù)至對應(yīng)狀態(tài)s下的動作集合中，當學(xué)習(xí)者再次經(jīng)歷該狀態(tài)時，根據(jù)更新過后的Q值，仍將Q值最小對應(yīng)的動作從備選動作集中刪減，如此循環(huán)執(zhí)行，直至學(xué)習(xí)者該次episode訓(xùn)練結(jié)束。

2.3 ? 基于改善 -greedy的強化學(xué)習(xí)實現(xiàn)步驟

步驟1：初始化，對于？坌s∈S，？坌a∈A，其對應(yīng)的Q值初始化為0，設(shè)定學(xué)習(xí)者的初始狀態(tài)、目標狀態(tài)，同時設(shè)定學(xué)習(xí)速率α、折扣因子γ、探索度ε、最大學(xué)習(xí)次數(shù)Tmax等參數(shù);

步驟2：將動作集中Q值最小對應(yīng)的動作從對應(yīng)動作集中剔除;

步驟3：按式（3）計算出difference，并根據(jù)式（4）計算參數(shù) ;然后利用新計算出的參數(shù) ，根據(jù)式（2）選擇動作，執(zhí)行并轉(zhuǎn)移至下一狀態(tài);并根據(jù)式（1）對Q值進行更新;

步驟4：將步驟2剔除的動作恢復(fù)至對應(yīng)狀態(tài)下動作集中;

步驟5：若學(xué)習(xí)者到達目標點，結(jié)束此次episode的訓(xùn)練，并轉(zhuǎn)至步驟6;否則轉(zhuǎn)步驟2，繼續(xù)此次episode訓(xùn)練;

步驟6：若學(xué)習(xí)者的學(xué)習(xí)次數(shù)T = Tmax，則結(jié)束學(xué)習(xí)者的學(xué)習(xí);否則轉(zhuǎn)至步驟1，進行下一次episode的訓(xùn)練;

3 ? 仿真實驗

利用迷宮問題，對引入動態(tài)調(diào)整及動作刪減的改進算法進行驗證。主要是將基于固定值ε-greedy（ε = 0.5）、固定值ε-greedy（ε = 0.5）并引入動作刪減結(jié)合Q-Learning進行仿真比較，以及基于固定值ε-greedy、ε-decrease、所提方法改進ε-greedy結(jié)合Q-Learning進行仿真比較。仿真實驗采用環(huán)境為20×20的二維網(wǎng)格，如圖2所示。圖中每一個網(wǎng)格代表學(xué)習(xí)者所處環(huán)境的一個狀態(tài)，其中S代表學(xué)習(xí)者的初始狀態(tài)，G代表學(xué)習(xí)者的目標狀態(tài)，四周藍色網(wǎng)格表示環(huán)境的邊界，深藍色網(wǎng)格表示學(xué)習(xí)者可自由活動的區(qū)域，青色網(wǎng)格表示障礙物。

仿真實驗使用Matlab2016a軟件完成。為了消除算法的隨機性，每次實驗均在實驗環(huán)境中獨立學(xué)習(xí)10次，取平均性能進行比較，其中性能由學(xué)習(xí)者從初始點到目標點所需的時間步、學(xué)習(xí)者收斂速度來綜合評價。強化學(xué)習(xí)基本參數(shù)設(shè)置如下：α = 0.25，γ = 0.9，Tmax = 400。學(xué)習(xí)者每一次episode的訓(xùn)練，即從初始狀態(tài)到目標狀態(tài)的學(xué)習(xí)過程，均從初始狀態(tài)出發(fā)，其動作方向設(shè)定有上、下、左、右四個方向。當學(xué)習(xí)者執(zhí)行動作后，便獲得外界環(huán)境反饋的即時獎賞，那么其獎賞函數(shù)設(shè)定為：

圖3比較了基于固定值 ε-greedy（ε=0.5）Q-Learning與基于固定值 ε-greedy（ε=0.5）并引入動作刪減的Q-Learning?？梢?，在學(xué)習(xí)前期，由于學(xué)習(xí)者對環(huán)境是未知的，根據(jù)Q值選出來的刪減動作并不是準確的，使得引入動作刪減的Q-Learning與未引入動作刪減的Q-Learning在收斂速度與學(xué)習(xí)效果上大致相同。但隨著學(xué)習(xí)者的不斷學(xué)習(xí)，根據(jù)Q值選出的動作越來越準確，從而提高了學(xué)習(xí)者的探索效率，最終使得引入動作刪減的Q-Learning要先于收斂。且在學(xué)習(xí)后期，引入動作刪減的Q-Learning其平均步數(shù)要比未引入動作刪減的Q-Learning少。所以實驗表明這種動作刪減方法的有效性。

對基于固定值ε-greedy的Q-Learning，選參數(shù) 為0.3、0.5以及0.8分別進行了實驗，并將其中最佳與所提方法改進的ε-greedy結(jié)合Q-Learning進行比較。圖4為基于固定值ε-greedy的Q-Learning學(xué)習(xí)曲線

可見，當參數(shù)ε = 0.8時，學(xué)習(xí)者探索過多，使得其學(xué)習(xí)收斂效果很差;而當參數(shù)ε = 0.5時，學(xué)習(xí)者在180次episode時，已基本達到收斂，但與參數(shù) ε = 0.3時相比較，其性能相對較差。所以在本次實驗中，基于參數(shù)ε = 0.3的Q-Learning表現(xiàn)出性能最好。

后將基于固定值ε-greedy的Q-Learning（參數(shù)ε = 0.3）、基于所提方法改進ε-greedy的Q-Learning及基于ε-decrease結(jié)合Q-Learning進行比較，如圖5所示?？梢姡谒岱椒ǜ倪Mε-greedy的Q-Learning，其學(xué)習(xí)過程較平滑，且學(xué)習(xí)收斂速度較快，最終完成的路徑長度為22步左右，而基于ε-decrease及固定值ε-greedy（ε = 0.3）的最終完成的路徑長度分別為26步、35步。明顯，基于所提方法改進ε-greedy的算法尋得的路徑更優(yōu)。而且，基于ε-decrease的Q-Learning，因在學(xué)習(xí)過程中僅通過時間變化來調(diào)整參數(shù)ε，無法正確衡量Q值的評估是否準確，使得在學(xué)習(xí)過程中出現(xiàn)了較大的震蕩。

此外，考慮到學(xué)習(xí)者可能陷入局部最優(yōu)，所以當學(xué)習(xí)者收斂于一個解后，即一條可行路徑，參數(shù) 便重新設(shè)定為0.5，使得學(xué)習(xí)者重新進入探索。顯然，之前獲得的解為當前環(huán)境下的最優(yōu)解。所以，基于所提方法改進ε-greedy的Q-Learning其平均時間步數(shù)在大約100次episode時開始緩慢增大，直至200次episode后要略大于另外兩種方法。但是，就整體而言，基于所提方法改進ε-greedy的Q-Learning是要比基于參數(shù)ε = 0.3及基于ε-decrease的Q-Learning具有更快更好的學(xué)習(xí)性能。

4 ? 結(jié) ? 論

針對強化學(xué)習(xí)的難點之一，探索與利用之間的平衡，在Q學(xué)習(xí)結(jié)合ε-greedy的基礎(chǔ)上，提出了一種參數(shù) 動態(tài)調(diào)整策略。該策略是以學(xué)習(xí)者在學(xué)習(xí)過程中各狀態(tài)下的學(xué)習(xí)狀態(tài)為依據(jù)，實現(xiàn)參數(shù) 的自適應(yīng)。同時，引入了一種結(jié)合試錯法的動作刪減機制。兩者共同作用，使策略ε-greedy得到了改進。最后，迷宮問題的仿真實驗結(jié)果表明，較之基于固定值以及ε-decrease的方法，基于所提方法改進ε-greedy的Q-Learning不僅實現(xiàn)了在學(xué)習(xí)過程中自適應(yīng)調(diào)節(jié)探索與利用的平衡，還提高了學(xué)習(xí)者的探索效率，使得學(xué)習(xí)者在性能上表現(xiàn)的更快更好。

參考文獻

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

[2] ? 高陽，陳世福，陸鑫.強化學(xué)習(xí)研究綜述[J].自動化學(xué)報，2004（01）：86—100.

[3] ? 宗群，孫正雅.基于平均報酬強化學(xué)習(xí)的電梯群組調(diào)度研究[J].系統(tǒng)仿真學(xué)報，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，F(xiàn)ISCHER 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] ? ?趙昀，陳慶偉.一種基于信息熵的強化學(xué)習(xí)算法[J].系統(tǒng)工程與電子技術(shù)，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學(xué)習(xí)算法在軌跡規(guī)劃中的應(yīng)用[J].吉林大學(xué)學(xué)報：信息科學(xué)版，2016，34（05）：697—702.

[11] ?趙英男.基于強化學(xué)習(xí)的路徑規(guī)劃問題研究[D].哈爾濱：哈爾濱工業(yè)大學(xué)，2017.

[12] ?劉智斌，曾曉勤. 基于路徑引導(dǎo)知識啟發(fā)的強化學(xué)習(xí)方法[J]. 工程科學(xué)與技術(shù)，2012，44（5）：136—142.

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