改進的Q-Learning算法及其在路徑規(guī)劃中的應用

2021-01-21 07:51:12毛國君顧世民

太原理工大學學報 2021年1期

毛國君，顧世民

(福建工程學院機器學習與智能科學研究所，福州 350118)

人類知識的獲取是通過感知環(huán)境(Environment)并與之交互來完成的，因此所謂的智能學習就是智能體(Agent)不斷適應環(huán)境來完善自己的過程。強化學習(reinforcement learning,RL)是機器學習的方法論之一，用于描述和解決智能體在與環(huán)境的交互過程中如何學習和優(yōu)化策略的問題[1]。事實上，許多應用中的環(huán)境是動態(tài)變化和不確定性的，如機器人的路徑規(guī)劃問題，智能體必須在不確定性環(huán)境中主動地對周圍環(huán)境進行探索[2-3]。在探索過程中不斷地認知環(huán)境，形成適應環(huán)境的正確行為。

強化學習不同于目前廣泛研究的監(jiān)督學習(supervised learning)和無監(jiān)督學習(unsupervised learning)，它的學習不是被動地從已有數(shù)據(jù)中進行歸納或提取，而是一個主動適應環(huán)境并進行自我完善的過程。強化學習是從計算機科學、數(shù)學、神經(jīng)學等多個相關學科發(fā)展而來的，已經(jīng)成為機器學習的主要分支之一[4-5]。由于強化學習強調在環(huán)境變化情況下智能體的主動學習，因此近年受到廣泛關注，并在機器人控制以及智能計算等領域得到應用。

基本的強化學習思想是通過智能體對當前環(huán)境狀態(tài)的感知，并對可能采取的動作(Action)獲得的回報(Reward))進行評價來完成的。圖1給出了強化學習的基本模型[6]。

圖1 強化學習的基本模型Fig.1 Reinforcement learning model

強化學習是一個“探索-利用”的迭代過程[6-7]。首先，智能體通過感知環(huán)境的當前狀態(tài)，并采取某一個動作來探索環(huán)境，探索的結果一般以某種形式的獎勵或者回報來表示。然后，對已經(jīng)獲得的回報進行評價，尋找在當前狀態(tài)下的一個最優(yōu)的動作加以利用。當然，“探索-利用”是一個不斷反復循環(huán)的過程，直到獲得滿意的最終策略。

不同的強化學習算法在“探索”“利用”方法及其融合機制上會有所差異。就強化學習的經(jīng)典算法Q-Learning而言，在探索階段所用的方法是ε-貪心(ε-greedy)方法，即優(yōu)先利用最大Q值對應的動作來向前推進探索。

傳統(tǒng)的Q-Learning存在探索效率低下的致命問題[8]。實際上，探索與利用是強化學習的兩個不可分割的部分，同時也是一對矛盾共同體。當智能體過多地探索環(huán)境時必然會導致效率下降，但當智能體在探索不充分情況下盲目地相信某種決策而加以利用時也會增加后續(xù)的探索代價。因此，制定一個合適的探索計劃來平衡探索和利用的代價，以便在正確決策的同時盡可能地提高收斂速度，是強化學習的一個重要任務。

本文針對傳統(tǒng)的Q-Learning算法收斂速度慢的問題，提出一個改進算法ε-Q-Learning.基本思想是通過動態(tài)地改變搜索因子參數(shù)來快速適應環(huán)境的變化，既可以提高探索效率，也可以避免陷入無效的局部搜索，因而提高全局優(yōu)化的可能性。

1 相關工作

路徑規(guī)劃(Path planning)是機器人研究領域的一個關鍵性的工作，同時也是許多應用(如電子游戲、無人駕駛等)的基礎。1986年，Khatib第一次提出用人工勢場法(Artificial potential field method)解決了機器人躲避障礙物的問題，此后這個方法也成為許多路徑規(guī)劃研究與應用的基礎[9]。然而，隨著人工智能技術的研究進展，利用智能學習方法來解決路徑規(guī)劃問題成為新的發(fā)展趨勢，其中強化學習扮演了十分重要的角色。例如：利用BP神經(jīng)網(wǎng)絡和Q-Learning算法，在未知環(huán)境下的自主避障問題被研究[10]；將模糊邏輯引入到強化學習中[11]；Agent的自主強化學習等[12-14]。我國學者也在機器人、無人機等強化學習模型方面開展了卓有成效的工作[15-16]。

此外，強化學習的模型或者算法基本都是基于馬爾可夫(Markov)屬性構造的[4-5]。馬爾可夫屬性是指一個系統(tǒng)下的狀態(tài)只與當前狀態(tài)有關，而與更早之前的狀態(tài)無關，即公式(1)：

P(st+1|st,st-1…s1)=P(st+1|st) .

(1)

基本的馬爾可夫決策(MDP)[4]模型由一個四元組來刻畫：

其中，S表示環(huán)境中的所有狀態(tài)集合；A表示是作用于環(huán)境的所有可能動作集合；P表示狀態(tài)之間的轉移概率；R表示采取某一動作到達下一狀態(tài)后的回報。

基于MDP模型，目前的強化學習算法主要是圍繞著回報的評價機制、狀態(tài)與動作的影響估算等方面進行研究和實踐，因而出現(xiàn)了不同的解決模型，也在算法的可用性等方面進行有效探索[17-18]。

目前的典型強化學習算法大致有3種，分別為Q-Learning算法、Sarsa算法和TD算法[4,16-17]。分析這些典型算法的理論基礎，基本上是由2個實體和4個評價機制組成的。當然在不同的強化學習算法中可能依賴的評價機制或者函數(shù)有所側重。

實體主要有環(huán)境和智能體。

1) 環(huán)境是學習的對象。一般而言，在一個確定時刻，一個環(huán)境一定有一個確定的狀態(tài)(State)，但是當智能體在該環(huán)境中活動后，其狀態(tài)就會發(fā)生改變。因此智能體必須對其活動結果(下一個狀態(tài))有一個估算，并借此形成下一步的決策。

2) 智能體則是學習者。一般而言，智能體是通過采取動作(Action)來適應環(huán)境的。就是說，智能體需要通過不斷地嘗試某狀態(tài)下可能動作的效果，來認知環(huán)境并采取恰當?shù)膭幼鱽砝^續(xù)探索。

評價機制包括4個基本方面。

1.1 策略π

在強化學習過程中，智能體在某個狀態(tài)采取什么樣的動作到下一個狀態(tài)是由策略控制的。簡單地說，策略就是從狀態(tài)到動作的映射。特別地，當環(huán)境存在障礙或者陷阱時，策略就必須保證下個動作不能碰到障礙或者掉入陷阱。策略的好壞決定了智能體行動的好壞，進而決定了整個算法的學習質量。

1.2 回報R(s)

回報R(s)是智能體處在狀態(tài)s下可能形成正確決策的可能性：可能性大則回報值就大，反之亦然。強化學習的任務就是不斷地探索來改變狀態(tài)，達到尋優(yōu)目的。因此，一個狀態(tài)s的回報是在不斷地探索中加以完善的。

給定一個探索的時間序列<1,2,…,t,t+1,…>,設當前時間為t，根據(jù)馬爾可夫屬性，則R(s)的理論值就是：

Rt(s)←f(Rt(s),Rt+1(s),…) .

(2)

其中，Rt(s)為狀態(tài)s在t時刻的回報，f則代表對向前探索的回報值的綜合評價函數(shù)。

基于回報估計是強化學習的理論基礎，也是構建強化學習算法的基本依據(jù)。當然，不同的算法在實現(xiàn)路徑上會有不同，在回報值的計算及其評價函數(shù)的設計上會有所區(qū)別[19]。

從公式(2)可以看出，一個狀態(tài)s的理論回報值的計算是一個反復探索直到穩(wěn)定的過程。特別地，當環(huán)境的狀態(tài)空間很大或者情況復雜的情況下，這種探索可能耗時很長、甚至是無限的。因此，實際的算法經(jīng)常使用的是有限T步的探索策略。此外，在回報值的綜合評價函數(shù)方面，最常用的方法是“折扣累計回報”，即給定探索的步數(shù)T>0和折扣因子γ∈[0,1]，基于有限折扣累計回報策略，t時刻的狀態(tài)回報值計算如下：

R(s)←Rt(s)+γ×Rt+1(s)+…+γT×Rt+T(s) .

(3)

1.3 狀態(tài)值函數(shù)V(s)

如上所述，環(huán)境的變化在強化學習中表現(xiàn)為狀態(tài)的更新。值函數(shù)將理論上的回報值轉化成可以計算的V值、并通過反復迭代來實現(xiàn)強化學習的目標。基于V值學習的模型和算法已經(jīng)成為強化學習的一個重要方法。

給定一個時間t和當前狀態(tài)st，值函數(shù)方法是一個“前探+回推”的過程。基于有限折扣累計回報策略，下面的公式(4)給出了對應值函數(shù)的計算方法：

(4)

其中：π是學習的策略；R(st)是t時刻的回報(也被稱為t時刻的即時回報)；P(s1,s2)為狀態(tài)s1可能轉移到狀態(tài)s2的概率；γ∈[0,1]是折扣因子，而且整個后面一項是前探T步的V值函數(shù)的綜合評估，即相對于即時回報R(st)而言，這部分是t后可能的回報(強化學習中也被稱為未來回報)，它需要通過V值的迭代計算來完成。

1.4 動作值函數(shù)Q(s,a)

在強化學習中，狀態(tài)的轉移是通過執(zhí)行動作來完成的。一個狀態(tài)下實施了某種動作就到達一個新狀態(tài)。這在機器人系統(tǒng)或者棋牌對弈系統(tǒng)中得到充分體現(xiàn)。例如，在圍棋對弈系統(tǒng)中，每落一個棋子就意味著棋局(狀態(tài))發(fā)生改變，但是這種改變需要持續(xù)進行評價。同樣，在機器人路線規(guī)劃中，機器人每前進一步意味著新的狀態(tài)產(chǎn)生，但是這并不意味著接近目標點，所以每個動作引發(fā)的狀態(tài)更新都需要進行評價并累計到之前的獎勵回報中。

假設一個環(huán)境用狀態(tài)集S和動作集A來描述。給定t時刻的當前狀態(tài)s∈S，動作a∈A是s狀態(tài)下可以執(zhí)行的一個候選動作，則π策略下的關于狀態(tài)s和動作集a的回報可以用動作值函數(shù)來估計。公式(5)給出了對應的表達公式:

(5)

其中：R(st)和γ分別是t時刻的立即回報和折扣因子；A(*)是狀態(tài)*可能采取的下動作集合，整個的后面一項就是t時刻的未來Q值的累計估計。

除了經(jīng)典的上述3種算法外，還有在此3種算法基礎上大量改進的強化學習算法，比如在Q-Learning中加入多個智能體，將TD與神經(jīng)網(wǎng)絡相結合以及將啟發(fā)函數(shù)與Sarsa相結合等等，這些算法都在實驗中表現(xiàn)出了優(yōu)異的成績。

2 Q-Learning算法分析

2.1 基本原理

Q-Learning是強化學習三種最流行的算法之一，是基于Q值迭代的無模型算法。如前所述，給定某一時刻的狀態(tài)si和準備采取的動作ai，Q(si,ai)就是在該時刻的狀態(tài)si下采取動作ai獲得回報的估計值。理論上講，當探索了一個給定時刻的狀態(tài)si和所有可能動作A(si)后，就可以根據(jù)環(huán)境的反饋回報信息選取一個最優(yōu)動作進入下一次狀態(tài)si+1；如此反復直到終點或者人為終止，一次迭代過程結束。當然，一個狀態(tài)的Q值也是隨著探索的不斷推進在不斷更新中，直到所有狀態(tài)的Q值相對穩(wěn)定為止。

Q-Learning算法的特點是根據(jù)潛在的狀態(tài)與動作來構建一張二維表(被稱為Q-table)來存儲Q值，然后通過查表方式獲得Q值來尋找最優(yōu)的動作。該方法具有簡單直接的特點，在環(huán)境大小適中的應用場景中(如簡單棋牌對弈等)，已經(jīng)證明非常有效。

Q-table的數(shù)據(jù)結構簡單易用，表1給出了一個4個狀態(tài)、2個動作的結構示意。

表1 Q-Table結構示意Table 1 Q-Table schematic

基于Q-table，Q-Learning算法主要使用公式(6)來更新Q值：

Q(s,a)←Q(s,a)+α×((R(s′)+γ×maxa′∈A(s′)
{Q(s′,a′)-Q(s,a)}) .

(6)

其中：s和s′分別是當前狀態(tài)和下個狀態(tài)，a則是使s到s′的有效動作，而A(s′)則是下狀態(tài)s′可能采取的候選動作；α∈[0,1]被稱為為學習率，用于調節(jié)學習過程中的可能誤差；γ為折扣因子。

依據(jù)公式(6)，Q-Learning算法在一個特定狀態(tài)下將貪婪地對所有可能的路徑進行探索，每前進一步都是在尋找當前狀態(tài)下的局部最優(yōu)解。

為了準確刻畫改進的算法，本文采用的主要符號及其意義見表2.

表2 符號表Table 2 Symbols in this paper

算法1給出了Q-Learning算法的偽碼描述。

Input: learning rate α, discount factor γ, greedy factor ε, reward matrix R(|S|,|A|), maximum forward steps maxStep, maximum number of Q-table modifications maxIter.Output: Q-table Q(|S|,|A|).Process:Initialize Q-table;所有Q(s,a)元素為0iter←0;Reapeat //循環(huán)更新Q表 s←start; 開始狀態(tài)為start step←0; Repeat// 循環(huán)找終點terminal: For(each action a∈A(s)) call ε-greedy obtain a'∈A(s);//用貪婪策略前探 Q(s,a)←Q(s,a)+α*(R(s)+γ*(Q(s(a),a')-Q(s,a))); s←s(a'); step++; Until (step>=maxStep) or (s=terminal) iter←iter++;Until (iter>=maxIter) or (Q-table no again change)Return Q-Table.

值得注意地是，考慮到現(xiàn)有Q-Learning算法的描述大多過于簡單[4,8]，不利于讀者閱讀和本文后面算法的介紹。算法1把整個Q-Learning的主要步驟整合到一起，對細節(jié)進行了更詳細描述。

簡單地講，Q-Learning算法除了必要的初始化外，主要是一個雙層循環(huán)：

1) 在內層循環(huán)里要完成一次從起點到終點狀態(tài)的探索，并對探索過的路徑的Q值進行更新。它的理想出口是每次探索都能到達終點。這種(內循環(huán))正常出口只意味著找到一條可行的路徑來完成從起點到終點的工作，但它不一定是最優(yōu)的，因此還需要通過Q-Table的迭代來尋優(yōu)。當然，當內循環(huán)人為終止(超過步驟閾值)時，就說明本次探索失敗，需要重新開始探索。此外，在一個狀態(tài)下尋找下動作采用的是ε-greedy策略。

2) 外循環(huán)的正常結束條件是Q-table不再變化。這意味著經(jīng)過多次迭代后，已經(jīng)產(chǎn)生了從起點到終點狀態(tài)的穩(wěn)定情況，因而達到了優(yōu)化的目標，最后的答案也就是從起點到終點的“最大Q值”形成的路徑。當然，當外循環(huán)觸動“意外的結束條件”時，就說明循環(huán)探索已經(jīng)達到極限，沒有必要繼續(xù)下去了。

2.2 改進Q-Learning算法

強化學習和監(jiān)督學習、半監(jiān)督學習等其他學習方法不同，它需要不斷探索環(huán)境并獲得反饋。目前最常用的探索策略有兩個：貪婪策略和Boltzmann策略[4-5]。

一般地講，Boltzmann基本上是隨機選擇策略，缺乏探索的目的性，效率很難保證，特別是在復雜情況下很難完成。相對來說，貪婪策略增加了探索的目的性，但是很容易陷入局部優(yōu)化，甚至經(jīng)常“碰壁”而被迫終止。目前的算法也都致力于解決該問題，但是仍然存在很大的改進空間。

本文引入動態(tài)搜索因子ε，嘗試改進Q-Learning算法。算法2給出了改進Q-Learning算法ε-Q-Learning的偽碼描述。

Input: learning rate α, discount factor γ, basic greedy factor ε, greed incremental θ, reward matrix R(|S|,|A|), maxi-mum forward steps maxStep, maximum number of Q-table modifications maxIter.Output: The optimal path P.Process:Initialize Q-table;所有Q(s,a)元素為0iter←0;Reapeat //循環(huán)更新Q表 s←start; 開始狀態(tài)為start step←0; Repeat// 循環(huán)找終點terminal: For(each action a∈A(s)) IF rand()<ε Then a'← a random forward action from s Else call ε-greedy get a'∈A(s);//用貪婪策略前探 Q(s,a)←Q(s,a)+α*(R(s)+γ*(Q(s(a),a')-Q(s,a)) End Do s←s(a'); step++;Until (step>=maxStep) or (s=terminal)iter←iter++;If (step>=maxStep) Then □←□+θElse Then □←□-θ;Until (iter>=maxIter) or (Q-table no again change);For (s=start To terminal) Do a←argmax{Q(s,a)|a∈A(s)} P←P+;Return P.

ε-Q-Learning主要改變是根據(jù)環(huán)境的反饋來動態(tài)調整貪婪因子ε.正如算法2中間描述那樣，ε-greedy策略是通過條件rand()<ε來決定是隨機選擇還是選擇最大Q值的下動作。很顯然，ε越大則隨機搜索下動作的概率就會增大，這在一定程度上避免陷入局部優(yōu)化。

算法2引入動態(tài)的貪婪因子ε.簡單地說，在算法2中，假如在一次從起點到終點的探索失敗，則通過增大ε來使下一次探索的隨機性增大，以免陷入之前的局部優(yōu)化困境。反之，則通過減少ε來增加目的性。當然，算法2中的基礎貪婪因子ε和增幅θ是一個經(jīng)驗值，也需要根據(jù)應用中環(huán)境的不斷變化進行嘗試實驗來確定。