基于軌跡式的Q 學(xué)習(xí)算法對探索環(huán)境預(yù)處理的研究*

胡常禮，邵劍飛

（昆明理工大學(xué)，云南 昆明 650500）

0 引言

Q 學(xué) 習(xí)（Q-learning）算法[1]是 由Watkins 和Dayan 提出的，用于估計馬爾科夫決策過程的Q 函數(shù)，也是強化學(xué)習(xí)[2]中的經(jīng)典算法之一。強化學(xué)習(xí)是基于獎懲機制[3]來鼓勵智能體對環(huán)境進行探索，在智能體探索環(huán)境的每個狀態(tài)空間會形成的長的軌跡，而長軌跡探索使得智能體要經(jīng)過較長時間的學(xué)習(xí)才能獲得獎勵，形成延遲獎勵的現(xiàn)象。本文提出的基于軌跡式的Q 學(xué)習(xí)（TracesQ-learning，TQlearning），在智能體在每次探索新環(huán)境的狀態(tài)空間形成的軌跡以增量式軌跡T更新，從而減少延遲獎勵的形成。

Q-learning 是傳統(tǒng)的強化學(xué)習(xí)算法在穩(wěn)定的環(huán)境中的研究[4-7]，是智能體獲得探索能力和最優(yōu)策略的基礎(chǔ)。強化學(xué)習(xí)最初是運用在最優(yōu)控制[8]中，現(xiàn)在強化學(xué)習(xí)也運用在自動控制[9]、自動預(yù)測[10]等方面。由于現(xiàn)實世界的環(huán)境不斷變化，智能體要探索的環(huán)境會更復(fù)雜，因此需要新的知識加入到智能體學(xué)習(xí)系統(tǒng)中來預(yù)處理探索環(huán)境的變化。本文提出的基于TQ-learning 對探索環(huán)境先進行預(yù)處理然后再探索的算法，在原來形成的學(xué)習(xí)策略上加入環(huán)境預(yù)處理的知識來處理探索環(huán)境的變化。

1 TQ-learning 與探索環(huán)境預(yù)處理

1.1 Q-learning的表示方式

Q-learning的原理是：先建立Q表格，然后根據(jù)Q表格選擇動作再與環(huán)境交互得到獎勵值R，最后再更新Q表格。Q更新的表達(dá)式為：

式中：Q(s,a)為動作值函數(shù)也稱Q函數(shù)；R為在s狀態(tài)下的獎勵值；為下個狀態(tài)執(zhí)行下個動作a'選擇最大值；α為學(xué)習(xí)率；γ和λ為折扣因子；θ為閾值。

Q函數(shù)的更新為：實際更新值=當(dāng)前現(xiàn)實值+學(xué)習(xí)率×(現(xiàn)實值-估計值)。

1.2 TQ-learning

智能體在Q-learning的訓(xùn)練下在領(lǐng)域探索時可能會出現(xiàn)問題，例如在導(dǎo)航任務(wù)上可能在當(dāng)前狀態(tài)撞到返回到上個狀態(tài)的相同動作，導(dǎo)致智能體不采取動作或循環(huán)這一動作。為了阻止重復(fù)這樣的動作，采用增量軌跡的方式標(biāo)記，如圖1 所示。

圖1 軌跡標(biāo)記

A 為起始地點，D 為目標(biāo)地點，C 到D的軌跡標(biāo)記為1，B 到D 標(biāo)記為0。這樣標(biāo)記后，使智能體選擇最短步數(shù)時會優(yōu)先選擇B 到D的動作。增量軌跡記為T，其更新方式為：

當(dāng)訓(xùn)練過程中采取不是最優(yōu)動作時，為了避免所有狀態(tài)動作對的軌跡為零，采用了三角不等式去更新Q函數(shù)。三角不等式更新方式為：

根據(jù)三角不等式更新方式，則Q函數(shù)更新情況有：

當(dāng)T(s,a)=0，即采取了最優(yōu)動作，

當(dāng)T(s,a)≠0，即未采取最優(yōu)動作，

將標(biāo)記軌跡融入到Q-learning 算法中，利用軌跡更新特性標(biāo)記已走過的路線，使智能體積極探索，即遇到相同的狀態(tài)再重新探索時不再重復(fù)采用同一動作導(dǎo)致學(xué)習(xí)速度慢。

1.3 探索環(huán)境預(yù)處理

探索環(huán)境的預(yù)處理主要是通過先檢測探索的環(huán)境與之前環(huán)境是否相同，再判斷在相同狀態(tài)下采取相同動作的所獲得獎勵值是否和上次所獲得獎勵值相同。在原始環(huán)境下E，構(gòu)造具有已知狀態(tài)轉(zhuǎn)移函數(shù)和報酬函數(shù)的環(huán)境模型En，原始環(huán)境定義為E(S,A,R,P)，新的環(huán)境定義為En(Sn,An,Rn,Pn)。定義一個狀態(tài)二元組(st,at)，其中s∈S∩Sn，a∈A∩An，r∈R,rn∈Rn。如果r(s,a)≠rn(s,a)，則該二元組(s,a)是變化的。在開始時已知原始環(huán)境中狀態(tài)和動作對的總數(shù)記為Nsum。

對比本次訓(xùn)練和上次訓(xùn)練在下個狀態(tài)采用的相同動作所獲得的獎勵是否相同，即式（6），若不同則標(biāo)記此時的(st,at)為變化中狀態(tài)空間對，將收集的標(biāo)記構(gòu)建Ed。通過檢測這次探索的環(huán)境與上次探索環(huán)境所獲得的獎勵值是否相同，來標(biāo)記變化的環(huán)境。檢測和標(biāo)記完探索環(huán)境后對探索環(huán)境進行預(yù)處理，將檢測變化后的探索進行處理，處理方式為：

式中：Qtemp為現(xiàn)實值；為變化探索環(huán)境的下個狀態(tài)；rnd為變化探索環(huán)境的獎勵值；Qnd為變化探索環(huán)境的函數(shù)值；p(|snd,and)為在二元組(snd,and)到下個狀態(tài)s'nd的轉(zhuǎn)移概率；|Qtemp-Qnd(and,and)|為現(xiàn)實值減預(yù)測值的絕對值。

通過更新減小現(xiàn)實值和預(yù)測值的絕對值大小，使得智能體對變化的探索環(huán)境完成學(xué)習(xí)，即在原來的學(xué)習(xí)上可以對變化的部分進行補充學(xué)習(xí)。

探索環(huán)境預(yù)處理主要有兩個關(guān)鍵部分組成：一是將通過掃描判斷上一次探索所獲得的獎勵與這次探索原來的動態(tài)環(huán)境，標(biāo)記出來構(gòu)成Ed環(huán)境；二是通過對附近領(lǐng)域的環(huán)境掃描處理，使變化的狀態(tài)空間獎勵信息融合到原來的環(huán)境中組成新的探索環(huán)境。

在掃描過程中利用檢測智能體觀察到的新獎勵和原始環(huán)境的最優(yōu)值函數(shù)，并通過迭代更新這個變化的環(huán)境模型的值函數(shù)，將新信息融合到原來的環(huán)境中形成新的探索環(huán)境，然后再對新的環(huán)境進行探索學(xué)習(xí)，形成最優(yōu)函數(shù)和新的策略。

本文算法利用增量式軌跡標(biāo)記方式，使智能體在原始的環(huán)境再遇到相同狀態(tài)時，不會重復(fù)上一個動作或停止不動，而是返回上一個狀態(tài)空間，最后學(xué)習(xí)得到了原始的最優(yōu)策略。為應(yīng)對變化的環(huán)境的情況本文算法通過對探索環(huán)境進行掃描，對掃描出來變化的環(huán)境進行預(yù)處理形成新的探索環(huán)境，并通過軌跡標(biāo)記方式使智能體積極對新形成環(huán)境進行探索。本文算法使智能體不必從頭學(xué)習(xí)，并以更快的速度收斂到新的最優(yōu)策略。算法具體實現(xiàn)流程見第2 節(jié)。

2 算法實現(xiàn)

2.1 算法流程

本算法首先初始化Q值和軌跡T，根據(jù)軌跡獲取原始的最優(yōu)策略π*和Q*值；其次在新的變化的環(huán)境中，算法通過檢測變化動態(tài)的環(huán)境算法標(biāo)記變化的環(huán)境Ed；最后根據(jù)掃描處理End，初始化環(huán)境π*，開始新的學(xué)習(xí)。該算法流程中，增量式Q 學(xué)習(xí)更新最優(yōu)策略π*和Q*值，檢測學(xué)習(xí)環(huán)境是否變化和掃描處理變化的環(huán)境，并將處理的狀態(tài)環(huán)境更新到環(huán)境End中，形成帶有原來知識的環(huán)境，使智能體在可以在原有知識的前提下學(xué)習(xí)新的知識，而不必從頭學(xué)起，在將新的知識學(xué)習(xí)完后，通過迭代形成新的最優(yōu)策略。算法框架具體如圖2 所示。

圖2 算法框架

2.2 算法實現(xiàn)

TQ-learning 探索環(huán)境預(yù)處理算法的具體實現(xiàn)流程為：

本算法使智能體在探索過程中無需從頭學(xué)習(xí)探索中部分變化的環(huán)境，只需要返回到上一個狀態(tài)空間后繼續(xù)探索，然后再對探索環(huán)境變化的部分進行預(yù)處理，即先檢測動態(tài)環(huán)境后處理動態(tài)環(huán)境，更新狀態(tài)價值函數(shù)的分布。本算法利用了軌跡的標(biāo)記，使智能體可以在一段完整的訓(xùn)練學(xué)習(xí)期間達(dá)到目標(biāo)，而且通過對變化環(huán)境的檢測和預(yù)處理后，智能體可以在原來知識的基礎(chǔ)下繼續(xù)探索變化環(huán)境附近的領(lǐng)域，在遇到這部分變化的環(huán)境時會積極地采取動作去探索，最后探索形成新的策略。

3 實驗仿真與分析

為了查看本論文改進的算法效果，將文本算法與使用原始策略、不使用原始策略以及策略重用算法進行對比。實驗在60×60的二維變化迷宮中進行，如圖3 所示。

圖3 迷宮仿真實驗

迷宮的環(huán)境是可變的，迷宮中的右下角黑色格子是開始位置，左上角黑色代表目的地。連起來的細(xì)實線代表最優(yōu)的路線且成功到達(dá)目的地。

仿真結(jié)果如圖4 所示。

圖4 仿真結(jié)果

在仿真結(jié)果中，Q-learning（不具有原始策略）首次達(dá)到目標(biāo)后，經(jīng)過后面迭代次數(shù)后，步數(shù)也減少了。Q-learning（不具有原始策略）在開始一定時間迭代內(nèi)所用的步數(shù)是少于使用過原始策略和策略重用Q 學(xué)習(xí)的，但經(jīng)過一段時間后，其迭代速度降低了。Q-learning（具有原始策略）首次達(dá)到目標(biāo)，所探索的步數(shù)比較大，經(jīng)過很長的迭代周期后，所用步數(shù)慢慢少了，最后趨于一個收斂值。Q-learning（具有原始策略）在經(jīng)過一段episode 之后所用步數(shù)也增加了，但最后經(jīng)過一段時間后所用步數(shù)慢慢減少。造成Q-learning（具有原始策略）這種現(xiàn)象是由于它在原始訓(xùn)練達(dá)到目標(biāo)后形成一個策略，而這個在面對新的環(huán)境仍然按照之前的策略進行探索，然后在新的環(huán)境更新迭代原來的策略，最后根據(jù)這個策略使步數(shù)慢慢的減少，并到達(dá)一個閾值。沒有使用原來策略的Q-learning 算法在一開始的步數(shù)和使用原來策略步數(shù)是一樣；但使用原來策略經(jīng)歷迭代次數(shù)后，一段周期迭代后步數(shù)少于沒使用策略后的，而最終收斂步數(shù)值趨于相同。本文算法在探索環(huán)境下首次達(dá)到目標(biāo)所用的步數(shù)，明顯少于策略重用學(xué)習(xí)。使用策略重用算法[11]造成該結(jié)果的原因有：策略重用在迭代首次達(dá)到目標(biāo)的過程中由于不斷的失敗需要從頭學(xué)習(xí)，使用原來策略在新的環(huán)境探索時策略更新的慢，導(dǎo)致步數(shù)在首次達(dá)到目標(biāo)的步數(shù)遠(yuǎn)超于其它算法。

本文算法與其他算法相比，在整個迭代周期內(nèi)，到達(dá)目的地的步數(shù)在一定程度上是最少的。因為探索迷宮對于本算法和其他算法在首次到達(dá)目的時需要一定探索時間，所以在第一次所需的步數(shù)也比較多；但在一段訓(xùn)練時期后，其所需的步數(shù)在快速減少。本算法的優(yōu)點在于探索的過程中，遇到障礙物或者目的地的變化不必從頭開始，通過對所處狀態(tài)環(huán)境掃描預(yù)處理，返回上一個動作繼續(xù)探索。本算法和對比算法都是基于Q-learning的更新方式更新Q表格，只是更新Q表格的方式和速度不同；所以通過迭代次數(shù)的增多，最后所需步數(shù)收斂于相同閾值。

4 結(jié)語

本論文研究的算法是在Q-learning的基礎(chǔ)上對探索的途徑進行軌跡標(biāo)記，從而對探索的環(huán)境進行掃描，以及對變化環(huán)境進行預(yù)處理，然后對處理后的探索環(huán)境再學(xué)習(xí)，使智能體不必從頭開始學(xué)習(xí)。為驗證本文算法的有效性，本文利用二維變化迷宮環(huán)境模擬探索環(huán)境，通過與不具有原始策略和具有原始策略以及策略重用的Q-learning 算法在仿真環(huán)境結(jié)果分析對比，得出本文研究的算法在處理探索環(huán)境時一定程度上節(jié)約了探索時間和學(xué)習(xí)時間，且能有效處理探索環(huán)境的變化，改善了對探索環(huán)境變化處理的機制。