毛國(guó)君，顧世民

(福建工程學(xué)院 機(jī)器學(xué)習(xí)與智能科學(xué)研究所，福州 350118)

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

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

基本的強(qiáng)化學(xué)習(xí)思想是通過智能體對(duì)當(dāng)前環(huán)境狀態(tài)的感知，并對(duì)可能采取的動(dòng)作(Action)獲得的回報(bào)(Reward))進(jìn)行評(píng)價(jià)來完成的。圖1給出了強(qiáng)化學(xué)習(xí)的基本模型[6]。

圖1 強(qiáng)化學(xué)習(xí)的基本模型Fig.1 Reinforcement learning model

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

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

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

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

1 相關(guān)工作

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

此外，強(qiáng)化學(xué)習(xí)的模型或者算法基本都是基于馬爾可夫(Markov)屬性構(gòu)造的[4-5]。馬爾可夫?qū)傩允侵敢粋€(gè)系統(tǒng)下的狀態(tài)只與當(dāng)前狀態(tài)有關(guān)，而與更早之前的狀態(tài)無關(guān)，即公式(1)：

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

(1)

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

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

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

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

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

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

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

評(píng)價(jià)機(jī)制包括4個(gè)基本方面。

1.1 策略π

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

1.2 回報(bào)R(s)

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

給定一個(gè)探索的時(shí)間序列<1,2,…,t,t+1,…>,設(shè)當(dāng)前時(shí)間為t，根據(jù)馬爾可夫?qū)傩裕瑒tR(s)的理論值就是：

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

(2)

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

基于回報(bào)估計(jì)是強(qiáng)化學(xué)習(xí)的理論基礎(chǔ)，也是構(gòu)建強(qiáng)化學(xué)習(xí)算法的基本依據(jù)。當(dāng)然，不同的算法在實(shí)現(xiàn)路徑上會(huì)有不同，在回報(bào)值的計(jì)算及其評(píng)價(jià)函數(shù)的設(shè)計(jì)上會(huì)有所區(qū)別[19]。

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

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

(3)

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

如上所述，環(huán)境的變化在強(qiáng)化學(xué)習(xí)中表現(xiàn)為狀態(tài)的更新。值函數(shù)將理論上的回報(bào)值轉(zhuǎn)化成可以計(jì)算的V值、并通過反復(fù)迭代來實(shí)現(xiàn)強(qiáng)化學(xué)習(xí)的目標(biāo)?；赩值學(xué)習(xí)的模型和算法已經(jīng)成為強(qiáng)化學(xué)習(xí)的一個(gè)重要方法。

給定一個(gè)時(shí)間t和當(dāng)前狀態(tài)st，值函數(shù)方法是一個(gè)“前探+回推”的過程?；谟邢拚劭劾塾?jì)回報(bào)策略，下面的公式(4)給出了對(duì)應(yīng)值函數(shù)的計(jì)算方法：

(4)

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

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

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

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

(5)

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

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

2 Q-Learning算法分析

2.1 基本原理

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

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

Q-table的數(shù)據(jù)結(jié)構(gòu)簡(jiǎn)單易用，表1給出了一個(gè)4個(gè)狀態(tài)、2個(gè)動(dòng)作的結(jié)構(gòu)示意。

表1 Q-Table結(jié)構(gòu)示意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′分別是當(dāng)前狀態(tài)和下個(gè)狀態(tài)，a則是使s到s′的有效動(dòng)作，而A(s′)則是下狀態(tài)s′可能采取的候選動(dòng)作；α∈[0,1]被稱為為學(xué)習(xí)率，用于調(diào)節(jié)學(xué)習(xí)過程中的可能誤差；γ為折扣因子。

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

為了準(zhǔn)確刻畫改進(jìn)的算法，本文采用的主要符號(hào)及其意義見表2.

表2 符號(hào)表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)找終點(diǎ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算法的描述大多過于簡(jiǎn)單[4,8]，不利于讀者閱讀和本文后面算法的介紹。算法1把整個(gè)Q-Learning的主要步驟整合到一起，對(duì)細(xì)節(jié)進(jìn)行了更詳細(xì)描述。

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

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

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

2.2 改進(jìn)Q-Learning算法

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

一般地講，Boltzmann基本上是隨機(jī)選擇策略，缺乏探索的目的性，效率很難保證，特別是在復(fù)雜情況下很難完成。相對(duì)來說，貪婪策略增加了探索的目的性，但是很容易陷入局部?jī)?yōu)化，甚至經(jīng)?！芭霰凇倍黄冉K止。目前的算法也都致力于解決該問題，但是仍然存在很大的改進(jìn)空間。

本文引入動(dòng)態(tài)搜索因子ε，嘗試改進(jìn)Q-Learning算法。算法2給出了改進(jìn)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)找終點(diǎ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)境的反饋來動(dòng)態(tài)調(diào)整貪婪因子ε.正如算法2中間描述那樣，ε-greedy策略是通過條件rand()<ε來決定是隨機(jī)選擇還是選擇最大Q值的下動(dòng)作。很顯然，ε越大則隨機(jī)搜索下動(dòng)作的概率就會(huì)增大，這在一定程度上避免陷入局部?jī)?yōu)化。

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

3 實(shí)驗(yàn)結(jié)果及分析

實(shí)驗(yàn)在Anaconda上采用36×36的迷宮環(huán)境模擬智能體運(yùn)動(dòng)進(jìn)行仿真，將改進(jìn)的ε-Q-Learning算法和傳統(tǒng)的Q-Learning算法進(jìn)行比較性實(shí)驗(yàn)。實(shí)驗(yàn)中使用的主要參數(shù)見表3.

表3 實(shí)驗(yàn)參數(shù)設(shè)置表Table 3 Main parameter setting for the experiments

智能體所在位置的坐標(biāo)(x,y)對(duì)應(yīng)Q-table的一個(gè)狀態(tài)，智能體的動(dòng)作選擇有4種:北、南、西、東，分別用N、S、W、E來表示，這樣Q-table的容量就是1 296×4.迷宮中還有障礙物，若進(jìn)行動(dòng)作選擇后碰到障礙物和迷宮墻壁則智能體保持在原狀態(tài)，否則進(jìn)入下一個(gè)狀態(tài)。智能體的開始位置設(shè)置在迷宮環(huán)境的(0，35)處，目標(biāo)位置設(shè)置在(35,0)處。

根據(jù)上述的實(shí)驗(yàn)環(huán)境和參數(shù)設(shè)置，使用上面的算法1和2，我們進(jìn)行了損失函數(shù)、運(yùn)行效率和收斂性等方面的跟蹤實(shí)驗(yàn)。實(shí)驗(yàn)結(jié)果如圖2-5所示。在圖中圓點(diǎn)表示的是ε-Q-Learning算法的值，線表示的是傳統(tǒng)的Q-Learning算法的值。

3.1 損失比較

算法的損失函數(shù)所反映的是算法所形成的路徑與最優(yōu)路徑的相似度。強(qiáng)化學(xué)習(xí)中已經(jīng)出現(xiàn)了7種損失函數(shù)：平方誤差損失函數(shù)、絕對(duì)誤差損失函數(shù)、Huber損失函數(shù)、二元交叉熵?fù)p失函數(shù)、Hinge損失函數(shù)、多分類交叉熵?fù)p失函數(shù)、KL散度損失函數(shù)。本文采用是絕對(duì)誤差損失函數(shù)，公式(7)給出了它的計(jì)算方法:

L=|y-f(x)|/maxIter .

(7)

式中：y表示每次迭代的路徑的總回報(bào)，f(x)表示表示人為設(shè)置最優(yōu)路徑的總回報(bào)。顯然，損失函數(shù)的值越小越好。圖2給出了兩種算法在損失函數(shù)值上的變化趨勢(shì)。

分析圖2，ε-Q-Learning算法和Q-Learning算法在迭代次數(shù)n<60時(shí)對(duì)環(huán)境模型的學(xué)習(xí)都不足夠深入，且ε-Q-Learning算法也沒有很好體現(xiàn)出其調(diào)節(jié)ε效果。然而，但當(dāng)n超過60以后，由于ε-Q-Learning算法對(duì)環(huán)境模型的學(xué)習(xí)越來越深入，ε也越來越優(yōu)化，ε-Q-Learning算法就顯示出了它明顯的優(yōu)越性，其損失函數(shù)值漸漸小于傳統(tǒng)的Q-Learning算法，且更快收斂于穩(wěn)定值。

圖2 算法損失函數(shù)圖Fig.2 Loss function graph

3.2 運(yùn)行效率比較

圖3給出了兩種算法的運(yùn)行時(shí)間比較。

圖3 算法時(shí)間圖Fig.3 Executive time graph

從圖3中可以看出，在250次迭代之前，ε-Q-Learning算法的運(yùn)行時(shí)間和Q-Learning算法基本沒有差距。然而，隨著迭代次數(shù)的增多，ε-Q-Learning算法對(duì)環(huán)境越來越適應(yīng)，學(xué)習(xí)效率提升，算法的運(yùn)行效率更高。

3.3 回報(bào)函數(shù)值比較

迭代過程中總回報(bào)函數(shù)值的變化反映了算法的收斂情況。圖4是兩個(gè)算法的總回報(bào)的比較結(jié)果。

從圖4中可以看出在n<60時(shí)，由于迭代次數(shù)太少，ε的調(diào)整效果并不明顯，因此ε-Q-Learning算法中的回報(bào)值與Q-Learning算法大致相同。當(dāng)n≥60時(shí)，由于ε-Q-Learning開始適應(yīng)環(huán)境，當(dāng)?shù)?00次后總的回報(bào)函數(shù)值基本不再變化。因此，從回報(bào)函數(shù)值的變化，可以推斷出ε-Q-Learning算法要比Q-Learning算法的收斂性要好。

圖4 算法總回報(bào)圖Fig.4 Cumulative rewards graph

3.4 探索步數(shù)比較

總的探索步數(shù)反映學(xué)習(xí)算法尋優(yōu)過程所付出的代價(jià)。一般而言，一個(gè)算法使用更少的步數(shù)而找到最優(yōu)解，那么它的代價(jià)就小，因而性能也就要好。圖5給出了兩個(gè)算法隨著迭代次數(shù)增加時(shí)累計(jì)的總步數(shù)的變化情況。

圖5 算法步數(shù)圖Fig.5 Cumulative step graph

從圖5中可以看出，當(dāng)n<5的時(shí)候，ε-Q-Learning算法的總步數(shù)是大于Q-Learning算法的，這很有可能是算法隨機(jī)探索所造成的。當(dāng)5≤n<60時(shí)，兩種算法的總步數(shù)大致相當(dāng)。但是，當(dāng)n≥60時(shí)，ε-Q-Learning算法步數(shù)就逐漸開始小于Q-Learning算法的步數(shù)，而且隨著迭代次數(shù)的增多，ε-Q-Learning算法的總步數(shù)基本穩(wěn)定，收斂也比Q-Learning算法要好些。

4 總結(jié)

傳統(tǒng)的Q-Learning算法在路徑規(guī)劃中存在收斂速度慢和易陷入局部?jī)?yōu)化等問題，本文提出了一種改進(jìn)的ε-Q-Learning算法。通過引入動(dòng)態(tài)的探索因子ε，不僅可以有效地提高算法的搜索效率，而且也能保證最終路徑的優(yōu)化。ε-Q-Learning算法根據(jù)每一次迭代的總步數(shù)來判斷本次探索的有效性，并通過修改貪心算法的搜索因子ε來提高下次探索的成功率。特別是，動(dòng)態(tài)的搜索因子技術(shù)可以有效地避免局部搜索困境，提高探索的成功率。實(shí)驗(yàn)結(jié)果表明，改進(jìn)的ε-Q-Learning算法相比現(xiàn)有的Q-Learning算法，在收斂速度、運(yùn)行效率和搜索代價(jià)等方面都表現(xiàn)出不同程度的優(yōu)勢(shì)。