基于軌跡式的Q 學習算法對探索環境預處理的研究*

胡常禮，邵劍飛

（昆明理工大學，云南 昆明 650500）

0 引言

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

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

1 TQ-learning 與探索環境預處理

1.1 Q-learning的表示方式

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

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

Q函數的更新為：實際更新值=當前現實值+學習率×(現實值-估計值)。

1.2 TQ-learning

智能體在Q-learning的訓練下在領域探索時可能會出現問題，例如在導航任務上可能在當前狀態撞到返回到上個狀態的相同動作，導致智能體不采取動作或循環這一動作。為了阻止重復這樣的動作，采用增量軌跡的方式標記，如圖1 所示。

圖1 軌跡標記

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

當訓練過程中采取不是最優動作時，為了避免所有狀態動作對的軌跡為零，采用了三角不等式去更新Q函數。三角不等式更新方式為：

根據三角不等式更新方式，則Q函數更新情況有：

當T(s,a)=0，即采取了最優動作，

當T(s,a)≠0，即未采取最優動作，

將標記軌跡融入到Q-learning 算法中，利用軌跡更新特性標記已走過的路線，使智能體積極探索，即遇到相同的狀態再重新探索時不再重復采用同一動作導致學習速度慢。

1.3 探索環境預處理

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

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

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

通過更新減小現實值和預測值的絕對值大小，使得智能體對變化的探索環境完成學習，即在原來的學習上可以對變化的部分進行補充學習。

探索環境預處理主要有兩個關鍵部分組成：一是將通過掃描判斷上一次探索所獲得的獎勵與這次探索原來的動態環境，標記出來構成Ed環境；二是通過對附近領域的環境掃描處理，使變化的狀態空間獎勵信息融合到原來的環境中組成新的探索環境。

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

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

2 算法實現

2.1 算法流程

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

圖2 算法框架

2.2 算法實現

TQ-learning 探索環境預處理算法的具體實現流程為：

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

3 實驗仿真與分析

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

圖3 迷宮仿真實驗

迷宮的環境是可變的，迷宮中的右下角黑色格子是開始位置，左上角黑色代表目的地。連起來的細實線代表最優的路線且成功到達目的地。

仿真結果如圖4 所示。

圖4 仿真結果

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

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

4 結語

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