于 飛 郝建國 張中杰

(國防科技大學智能科學學院 湖南 長沙 410005)

0 引 言

近年來,算法的改進、計算能力的進步為機器學習帶來了長足的發(fā)展,但機器學習需要大量訓練樣本支持限制了其在某些領域的發(fā)展。2016年以來,將深度學習與強化學習相結合的AlphaGo[1]擊敗世界圍棋冠軍,AlphaGo Zero[2]將深度強化學習進一步與樹搜索的lookahead 機制相融合僅訓練3天就擊敗了前輩AlphaGo,它們的出現(xiàn)將強化學習研究推向頂峰,使得強化學習受到極大的推動發(fā)展。

強化學習是一種有別于監(jiān)督學習和無監(jiān)督學習的機器學習方法,它通過控制動作與環(huán)境交互獲得環(huán)境獎勵,利用獎勵值更新動作策略,以實現(xiàn)決策的優(yōu)化。 強化學習的兩個最重要的特征是試錯搜索和延遲獎勵[3]。

在強化學習過程中,Agent的目標是在未知環(huán)境中通過試錯來獲得最大的獎勵。在未對環(huán)境進行充分地探索前,Agent難以找到最優(yōu)的策略。因此存在如何根據(jù)環(huán)境狀態(tài)進行動作選擇的問題,即探索(exploration)與利用(exploitation)問題[4]。

探索與利用的平衡不僅僅是強化學習中存在的困境,包括人類、動物等生物在任何未知環(huán)境中進行決策都會存在探索與利用問題。一般認為,如果行為在各個選項之間沒有重點的交替選擇,則認為是探索。如果只在某些選項中進行重點選擇且隨著時間的推移變得穩(wěn)定,則認為是在利用。人類或動物在動作探索后會獲取某些信息或獎勵來指導下一次的動作探索[5]。

在強化學習中,Agent在強化學習過程中依據(jù)已有經(jīng)驗選擇當前最優(yōu)的動作,即貪婪地選擇動作認為是利用。Agent在強化學習過程中隨機地進行動作選擇認為是在探索。

一方面,更多地探索未知的動作空間,可以獲得更多的信息以搜索全局最優(yōu)解,但探索過多會降低算法性能且會導致算法不收斂的情況。另一方面,過多的利用會因對環(huán)境知識的未知而導致選擇次優(yōu)的行為。因此,如何平衡探索與利用之間的關系成為影響強化學習算法性能的關鍵。通常的辦法是ε-greedy策略和Softmax分布策略[3]。ε-greedy策略是在貪婪算法的基礎上增加了參數(shù)ε,當ε為0時,ε-greedy策略就轉化為貪婪策略,ε由0逐漸增大至1的過程中,探索的程度逐漸增加;ε為1時,ε-greedy策略就轉化為隨機選擇動作。Sutton已經(jīng)證明了,ε-greedy策略性能優(yōu)于貪心策略。ε-greedy策略雖然一定程度上解決了探索與利用之間的問題,但由于參數(shù)ε固定,探索與利用的問題仍然存在,且存在參數(shù)ε難以設定,對非最優(yōu)動作之間不加區(qū)分等問題。Softmax分布策略依據(jù)動作的價值大小計算動作選擇概率,對不同價值的動作進行了概率上的區(qū)分,克服了ε-greedy策略存在的不足,但是存在當動作價值差距不大時無法區(qū)分最優(yōu)動作與其他動作且計算量較大的問題[6]。

大量學者針對ε-greedy策略和Softmax分布策略存在的問題做了改進和完善。文獻[7-9]均將計數(shù)機制引入到動作探索中,來改善基礎方法在動作探索中存在的不足。Guo等[10]將模擬退火(Simulated Annealing)算法中的Metropolis準則引入Q-learning的動作選擇機制,提出了SA-Q-learning算法。Chen等[11]將量子系統(tǒng)中兩個量子態(tài)之間的保真度作為反饋信息,提出了基于保真度的概率動作選擇機制,基于此提出了基于保真度的概率Q-learning算法,并在量子系統(tǒng)中進行了驗證。陳啟軍等[12]針對強化學習存在的問題提出了“行動分值”的概念,據(jù)此來進行動作選擇,并在行動分值的基礎上優(yōu)化獎勵函數(shù)。文獻[4, 13]將ε-greedy與Softmax結合來解決開發(fā)與利用的平衡問題,其中文獻[13]利用時間差分誤差來動態(tài)調整ε參數(shù),而文獻[4]利用中長期獎勵的差異來動態(tài)調整ε參數(shù)。

以上的動作探索策略可以統(tǒng)一地歸為無向探索方法,另一類與之對應的探索策略稱為有向探索[14]。Sledge等[15]利用各狀態(tài)中有關動作的信息,將信息論的相關方法引入到強化學習的動作探索中,以此啟發(fā)式方法來提高探索效率。李晨溪等[16]利用云推理模型,將先驗知識、規(guī)則引入強化學習,引導Agent的動作選擇,減少動作探索前期的盲目性。文獻[17-19]則是將先驗知識引入到動作探索策略中,來減少前期的無效探索以提高探索效率。

本文提出了一種新的動作選擇策略。新策略定義了“動作概率(action probability)”的概念,并據(jù)此進行動作偏好選擇,以解決探索與利用之間的平衡問題。最后通過實驗驗證了該方法的可行性。

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

1.1 馬爾可夫決策過程

許多強化學習問題都是基于馬爾可夫決策過程(MDP)提出的,一個MDP由元組(S,A,P,R,γ)構成,其中:S為狀態(tài)集,A為動作集,P為狀態(tài)轉移函數(shù)P:S×A×S→[0,1],R為獎勵函數(shù)R:S×A→R,γ為折扣系數(shù)。

在每個時間步t,Agent觀察到狀態(tài)st∈S,依據(jù)策略π選擇動作at∈A,與環(huán)境進行交互,環(huán)境依概率轉移到新的狀態(tài)st+1,并給予Agent獎勵R。這里對狀態(tài)的轉移做出了馬爾可夫假設,即轉化到下一狀態(tài)的概率,只與當前狀態(tài)有關,與之前的狀態(tài)無關。

1.2 強化學習

當策略π(a|s)確定后,存在一個完整的狀態(tài)序列(s1,a1,r1,s2,a2,r2,…,st,at,rt)。強化學習的目的就是最大化序列獎勵。

為了便于描述狀態(tài)之間的優(yōu)劣,強化學習引入了狀態(tài)價值函數(shù):

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

…|St=s)

(1)

和動作價值函數(shù):

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

…|St=s,At=a)

(2)

由此可以得到兩個函數(shù)的貝爾曼方程:

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)

而最優(yōu)狀態(tài)價值函數(shù)與最優(yōu)動作價值函數(shù)分別為:

(5)

(6)

這里以Q-learning算法為例。Q-learning算法[20]由Watkins在1989年最先提出,是一種不需要知道模型狀態(tài)轉移概率的模型無關(Model-free)算法,是一種時序差分離線控制算法。Q-learning是在知道環(huán)境狀態(tài)集S,動作集A,即時獎勵R的條件下,求解最優(yōu)動作價值函數(shù)q*和最優(yōu)策略π*。此類問題的求解,與蒙特卡洛(Monte Carlo)類似均是采用值迭代的方法,通過值函數(shù)的更新,來更新策略,通過策略來產(chǎn)生新的狀態(tài)和即時獎勵,進而更新值函數(shù)。

Q-learning算法使用兩個控制策略,一個策略用于選擇新的動作,另一個策略用于更新值函數(shù)。基于當前狀態(tài)S,依據(jù)動作選擇策略選擇執(zhí)行動作A,環(huán)境因此轉移到狀態(tài)S′,選擇狀態(tài)S′中價值最大的動作A′更新值函數(shù)。Q-learning算法過程如圖 1所示, 其數(shù)學表示為:

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算法步驟:

輸入:狀態(tài)集S,動作集A,步長α,衰減因子γ,迭代輪數(shù)T。

輸出:所有的狀態(tài)-動作對Q(s,a)值。

初始化Q(s,a);

從1循環(huán)至T;

1) 初始化一個初始狀態(tài)s;

2) 依據(jù)探索策略選擇狀態(tài)s下執(zhí)行動作a;

3) 執(zhí)行動作a,得到新狀態(tài)s’和獎勵r;

4) 更新動作價值函數(shù):

5)s=s′;

6) 如果S′是終止狀態(tài),當前輪迭代完畢否則轉到步驟2)。

1.3 動作探索策略

強化學習問題的解決就是要找到Agent與環(huán)境交互的最優(yōu)策略π*,尋找在各個狀態(tài)S下的最優(yōu)動作價值函數(shù)q*使得在各個狀態(tài)S下選擇最優(yōu)的動作,其數(shù)學式表示為:

(8)

(9)

因此,尋找最優(yōu)策略問題轉化為尋找在所有策略下產(chǎn)生的動作狀態(tài)值函數(shù)中的最大者。

常用的方法中ε-greedy策略是最接近貪婪的動作選擇策略,通常設置一個參數(shù)ε,以(1-ε)的概率選擇當前最優(yōu)動作,以ε的概率在所有動作中隨機選擇,其公式表示為:

(10)

式中:m為狀態(tài)s下動作集的大小。

而Softmax分布策略則是根據(jù)動作值函數(shù)的大小來計算動作選擇概率,將動作的值函數(shù)轉化為范圍在[0,1]的概率分布,其數(shù)學表示為:

(11)

無論是ε-greedy策略還是Softmax分布策略,都是在迭代的過程中,使動作值函數(shù)最大的動作擁有最大的選擇概率?；诖?本文提出了基于動作概率的選擇機制。

定義1動作概率表示Agent在某個狀態(tài)下執(zhí)行某一動作的概率值。狀態(tài)-動作對的動作概率初始值為該狀態(tài)的動作集大小的倒數(shù),即:

(12)

式中:card(As)表示狀態(tài)s下動作集As中動作的個數(shù)。

動作概率根據(jù)動作的值函數(shù)大小進行動態(tài)調整。Agent在狀態(tài)S下,根據(jù)動作概率選擇動作A,執(zhí)行動作后,Agent獲取獎勵R,進入狀態(tài)S′,并選擇值函數(shù)最大的動作A′來更新價值函數(shù)。隨后,依據(jù)狀態(tài)S下各個動作的值函數(shù)大小進行排序,將動作分成兩類:值函數(shù)最大的為一類;其余的為第二類。將第二類中各個動作的動作概率值減半平均加到最大類中。其更新的過程如圖2所示。

圖2 算法更新過程

Agent在完成一次動作后,按照狀態(tài)動作值函數(shù)的大小,更新動作概率。其更新規(guī)則如下:

(13)

式中:m為變化率,表示動作概率的變化速率;A*(s)為值函數(shù)最大的動作集,ai為集合A*(s)中的動作,aj為值函數(shù)非最大的動作。

在初始階段,所有動作概率是相等的,動作選擇是隨機選擇。當某一動作探索過后,若此次探索導致其獎勵值為負值,會使這一動作的動作概率值減半,其他動作的動作概率值增加,在探索初期,會使得動作探索更傾向于選擇未執(zhí)行過的動作。若探索導致動作獎勵為正,表明這次的探索是有益的探索,會使這個動作的動作概率增加,其他動作的動作概率降低,傾向于更多地選擇此動作;但其他動作仍存在探索的概率,可以防止動作探索陷入局部最優(yōu)的情況發(fā)生。

例如,Agent在狀態(tài)s下的動作空間A(s)={up, down, left, right}。先后經(jīng)歷了三次,分別選擇了{up}、{down}、{left},獲取的獎勵值分別為-1、-2和1。其動作概率的更新見表 1。

表1 動作概率更新過程

續(xù)表1

基于動作概率的Q-learning算法步驟如下:

輸入:狀態(tài)集S,動作集A,步長α,衰減因子γ,迭代輪數(shù)T。

輸出:所有的狀態(tài)-動作對Q(s,a)值。

從1循環(huán)至T;

1) 初始化一個初始狀態(tài)s;

2) 依據(jù)探索策略選擇狀態(tài)s下執(zhí)行動作a;

3) 執(zhí)行動作a,得到新狀態(tài)s′和獎勵r;

4) 更新動作價值函數(shù):

5) 更新動作概率:

6)s=s′;

7) 如果s′是終止狀態(tài),當前輪迭代完畢否則轉到步驟2)。

2 實驗與結果分析

本文設置兩組對照實驗,分別為實驗一和實驗二。兩次實驗均采用格子世界作為實驗環(huán)境,不同之處在于實驗一中障礙為固定的,實驗二中為移動障礙物,學習難度更大。在兩次實驗中,分別采用了Q-learning算法和DeepSARSA算法以驗證本文提出的動作探索策略的靈活性,并與ε-greedy策略和Softmax分布策略做出對比。

2.1 實驗一

實驗采用強化學習中常用的迷宮世界為實驗環(huán)境,其界面如圖3所示。

圖3 迷宮世界

采用了21×9的方格表示,其中車輛表示Agent,旗幟表示迷宮出口,實心方格表示墻體。Agent動作空間A(s)={up, down, left, right},每次動作,Agent移動一個方格。當Agent到達邊界時選擇朝向邊界的動作并不會使Agent離開地圖而是保持不動,當Agent在墻體附近并選擇向墻體運動時不會使Agent撞墻而是保持不動。

有關強化學習中參數(shù)設置,如表2所示。

表2 強化學習參數(shù)

2.2 實驗一分析

實驗分別使用ε-greedy策略、Softmax分布策略與動作概率策略進行對比分析,其中ε-greedy策略分別采用ε值為0.1、0.2和0.3三個值,強化學習算法均采用Q-learning算法,以排除學習算法對不同探索策略的影響。每輪迭代不設置最大動作上限,共迭代500輪,每種策略運行5次,采集5組數(shù)據(jù)進行分析。

圖4為5種探索策略經(jīng)過5次實驗后得到的結果,為了防止出現(xiàn)單次數(shù)據(jù)對實驗的影響,圖中數(shù)據(jù)為5次實驗后取平均值得到。該迷宮地圖的最優(yōu)解為25步,動作概率策略在迭代至40輪后開始收斂至最優(yōu)解,Softmax分布策略在迭代至60輪后開始收斂,ε-greedy策略同樣在迭代至60輪后開始收斂,但因ε值固定導致收斂效果較差。

圖4 不同探索策略最優(yōu)解比例

圖5為5種探索策略前200輪迭代中,迭代步數(shù)的箱式圖?？梢钥闯?動作概率策略和Softmax策略的中位數(shù)相近,ε-greedy策略的中位數(shù)要大于前兩種策略;動作概率策略的探索步數(shù)較其他策略更加集中且步數(shù)最少。

圖5 不同探索策略迭代步數(shù)

2.3 實驗二

實驗環(huán)境與實驗一類似,同樣為格子世界,如圖6所示。

圖6 格子世界

采用了10×10的方格表示,其中方塊為Agent,圓形為目標,三角形為障礙物。Agent動作空間與實驗一一致,障礙物每兩個離散時間步會左移一格,到達邊界時變?yōu)橄喾捶较蛞苿?。其中強化學習的相關參數(shù)設置,如表3所示。

表3 強化學習實驗參數(shù)

2.4 實驗二分析

此實驗,采用三種動作探索策略,分別為ε-greedy策略、Softmax分布策略及本文提出的探索策略。并將三種動作探索策略與深度強化學習DeepSARSA算法結合。其中,DeepSARSA采用三層全連接層的模型進行訓練。

本次實驗中,為防止因ε值固定導致收斂效果差的情況發(fā)生,采用了參數(shù)值隨探索次數(shù)增大而降低的方法。ε初始值設為1,隨后根據(jù)探索次數(shù)不斷降低,直至降到0.01。

每輪迭代不設置最大動作上限,共迭代1 000輪,每種策略運行5次,采集5組數(shù)據(jù)進行分析。

圖7為三種不同策略經(jīng)過迭代1 000輪迭代后最優(yōu)路徑占總迭代輪數(shù)的比例,其中最優(yōu)路徑以最高得分82分為準?？梢钥闯?本文提出的動作探索策略在迭代至25輪左右,就探索至最優(yōu)路徑;Softmax分布探索策略在迭代至45輪左右,探索至最優(yōu)路徑;而ε-greedy探索策略在迭代至200輪左右,才可探索至最優(yōu)路徑。圖中的線條在80輪、400輪、600輪和800輪時發(fā)生明顯的抖動,說明算法陷入到局部最優(yōu)的情況,但是經(jīng)過一段時間的探索,Softmax探索和本文提出的探索策略均能跳出局部最優(yōu)的情況收斂至全局最優(yōu),但本文提出的探索策略收斂速度更快,且更加穩(wěn)定。

圖7 三種探索策略最優(yōu)解占比

表4給出了三種算法的實驗結果。

表4 三種算法的實驗結果

3 結 語

本文研究了強化學習中動作探索策略,介紹了現(xiàn)有的平衡探索與利用問題的多種算法,分析了它們存在的不足。提出了一種基于動作概率的動作探索策略,通過動態(tài)調整動作概率來進行動作偏好選擇。并將動作探索策略分別與Q-learning和DeepSARSA結合。實驗表明,該方法較現(xiàn)有算法能夠更快收斂至最優(yōu)解,探索步數(shù)分布更加集中且數(shù)量更少,且靈活性較大,可與多種強化學習算法結合。

下一步工作是將該動作概率探索策略應用于連續(xù)狀態(tài)空間中,利用概率密度函數(shù)來表述動作概率,以拓展該策略的應用范圍。