PAC 最優(yōu)的RMAX-KNN 探索算法*

李 超，門昌騫，王文劍

1.山西大學(xué) 計(jì)算機(jī)與信息技術(shù)學(xué)院，太原030006

2.計(jì)算智能與中文信息處理教育部重點(diǎn)實(shí)驗(yàn)室（山西大學(xué)），太原030006

1 引言

強(qiáng)化學(xué)習(xí)是基于自然界動物試錯學(xué)的一種學(xué)習(xí)方法。在強(qiáng)化學(xué)習(xí)中，智能體（Agent）采取動作不斷與環(huán)境進(jìn)行交互，通過觀測到環(huán)境的變化以及接收環(huán)境返還給它的獎勵，從這些反饋之中學(xué)習(xí)到一個動作序列，通常稱之為策略。Agent 的目標(biāo)就是學(xué)習(xí)到一個最優(yōu)策略，在它根據(jù)此最優(yōu)策略與環(huán)境進(jìn)行交互時(shí)，所獲得的累積獎勵最大化。策略是狀態(tài)到動作的映射，Agent 可以在具體的狀態(tài)處根據(jù)策略選取相應(yīng)的動作。根據(jù)Agent 學(xué)習(xí)策略方式的不同強(qiáng)化學(xué)習(xí)方法大致分為基于策略搜索的強(qiáng)化學(xué)習(xí)方法、行為-評判器方法（Actor-Critic）以及基于值函數(shù)的強(qiáng)化學(xué)習(xí)方法?；诓呗运阉鞯膹?qiáng)化學(xué)習(xí)方法和Actor-Critic 方法將策略參數(shù)化，通過求解最優(yōu)參數(shù)進(jìn)而尋找最優(yōu)策略，適用于具有高維連續(xù)動作空間的強(qiáng)化學(xué)習(xí)問題。相比之下基于值函數(shù)的強(qiáng)化學(xué)習(xí)方法更適用于具有低維離散動作空間的強(qiáng)化學(xué)習(xí)問題[1]。

基于值函數(shù)的強(qiáng)化學(xué)習(xí)方法通過評估每個狀態(tài)的狀態(tài)值或者每個狀態(tài)行為對的狀態(tài)行為值來學(xué)習(xí)最優(yōu)策略，分為表格法和值函數(shù)逼近的方法。前者通過遍歷所有的狀態(tài)行為對，建立一張狀態(tài)行為值表，之后根據(jù)該表中的數(shù)據(jù)進(jìn)行策略的學(xué)習(xí)；后者通過函數(shù)逼近的方法來計(jì)算狀態(tài)值函數(shù)或者狀態(tài)行為值函數(shù)，但是對函數(shù)逼近器的逼近能力和泛化能力要求極高，且函數(shù)逼近方法一般難以收斂[1]，因此在表格法的基礎(chǔ)上開展值函數(shù)學(xué)習(xí)的研究仍具有重要的應(yīng)用價(jià)值。表格法在狀態(tài)空間和動作空間規(guī)模較小的問題中表現(xiàn)出了極好的收斂性，當(dāng)狀態(tài)空間和動作空間很大甚至連續(xù)時(shí)，不可能窮舉出所有的狀態(tài)行為對并計(jì)算相應(yīng)的值，此時(shí)就需要對狀態(tài)空間進(jìn)行離散化劃分，以此建立狀態(tài)行為值表，之后對該表進(jìn)行更新，用表中已有的狀態(tài)行為值去評估未知狀態(tài)行為值，最終學(xué)到最優(yōu)策略。傳統(tǒng)的狀態(tài)離散化方法對整個狀態(tài)空間進(jìn)行等精度劃分，實(shí)際上求取最優(yōu)策略并不需要在整個狀態(tài)空間上進(jìn)行學(xué)習(xí)，Barto 等人指出只需要在相關(guān)狀態(tài)上進(jìn)行嘗試就可以學(xué)到最優(yōu)策略[2]。對于等精度劃分得到的離散狀態(tài)空間，Lin 等人估計(jì)，當(dāng)學(xué)習(xí)完成后，與最優(yōu)決策相關(guān)的狀態(tài)數(shù)不到整個離散狀態(tài)空間的25%[3]。因此對于整個狀態(tài)空間進(jìn)行等精度劃分是不必要的，相比等精度劃分，自適應(yīng)狀態(tài)劃分法可以根據(jù)需要對狀態(tài)空間進(jìn)行變精度劃分，從而降低空間復(fù)雜度。自適應(yīng)狀態(tài)劃分法主要分為兩類：一類是離散狀態(tài)總數(shù)固定的方法，即劃分狀態(tài)總數(shù)固定，各狀態(tài)范圍可調(diào)整，這類方法有徑向基調(diào)整法[4]、自組織網(wǎng)絡(luò)法[5]等，但劃分狀態(tài)總數(shù)如果過多，則空間復(fù)雜度變大，學(xué)習(xí)速率減慢；總數(shù)過少，學(xué)習(xí)效果變差。另一類是事先規(guī)定離散狀態(tài)閾值，在線學(xué)習(xí)過程中如果遇到的狀態(tài)與已有離散狀態(tài)距離大于此規(guī)定閾值，則將此狀態(tài)添加為離散狀態(tài)，這類方法有徑向基生長法[6]、基于樹的表示方法[7]等。

探索與利用的均衡一直是強(qiáng)化學(xué)習(xí)研究的核心問題之一。在強(qiáng)化學(xué)習(xí)算法執(zhí)行過程中，探索未知的狀態(tài)行為空間可能會產(chǎn)生比當(dāng)前更優(yōu)的決策；同時(shí)利用則是根據(jù)當(dāng)前已經(jīng)學(xué)到的知識來產(chǎn)生當(dāng)前最優(yōu)決策，合理分配探索和利用的比重會對強(qiáng)化學(xué)習(xí)結(jié)果產(chǎn)生重大的影響。其中啟發(fā)式探索方法近期取得了巨大的成功，比如?-greedy 在DQN（deep Q network）以及DQN的一系列變種方法中表現(xiàn)出了優(yōu)異的成果[8]，但是啟發(fā)式探索方法在探索時(shí)隨機(jī)選取非最優(yōu)動作，不考慮次優(yōu)動作以及其余動作的不確定性，探索效率低下；而且啟發(fā)式探索方法通常需要大量的數(shù)據(jù)和時(shí)間才可以產(chǎn)生優(yōu)秀的結(jié)果。針對啟發(fā)式探索方法這些缺點(diǎn)，PAC（probably approximately correct）最優(yōu)探索算法極大地提升了探索的效率，但是傳統(tǒng)的PAC 最優(yōu)探索算法僅僅適用于低維離散狀態(tài)空間和動作空間強(qiáng)化學(xué)習(xí)問題，在狀態(tài)空間和動作空間很大甚至連續(xù)的問題上，傳統(tǒng)PAC 最優(yōu)探索算法并不適用[9]。

綜合狀態(tài)空間自適應(yīng)離散化劃分和探索與利用的均衡這兩個問題，本文提出了基于狀態(tài)空間自適應(yīng)離散化的RMAX-KNN 強(qiáng)化學(xué)習(xí)算法，該算法經(jīng)理論證明是一種PAC 最優(yōu)探索算法，可以在短時(shí)間內(nèi)逼近最優(yōu)策略，并且該算法可以在有效探索狀態(tài)空間的同時(shí)實(shí)現(xiàn)對狀態(tài)空間的自適應(yīng)離散化。此外，在三個常見的benchmark 環(huán)境上測試此算法，結(jié)果表明本文算法是可行且高效的。

2 背景知識

為了更好地了解本文算法，在闡述算法之前簡單介紹一下值函數(shù)的相關(guān)定義以及時(shí)間差分算法。

2.1 狀態(tài)值函數(shù)和狀態(tài)行為值函數(shù)

強(qiáng)化學(xué)習(xí)中Agent 與環(huán)境不斷進(jìn)行交互的過程可以理解為一個序貫決策問題，即不斷進(jìn)行決策的問題，這里的決策就是Agent 從交互數(shù)據(jù)中學(xué)到的策略。這一過程可以抽象為一個馬爾可夫決策過程（Markov decision process，MDP）。馬爾可夫決策過程MDP 可以表示為一個五元組，其中S表示有限的狀態(tài)集，A表示有限的動作集，R表示回報(bào)函數(shù)，P表示狀態(tài)轉(zhuǎn)移概率，γ表示折扣因子。在定義好MDP 之后，強(qiáng)化學(xué)習(xí)的學(xué)習(xí)過程就可以表示為s0a0r1s1a1…statrt+1st+1，在這里假設(shè)st+1為終止?fàn)顟B(tài)，此時(shí)強(qiáng)化學(xué)習(xí)的目標(biāo)就是找到一個最優(yōu)策略π(a|s)來使累積折扣回報(bào)G=r1+γr2+γ2r3+…+γtrt+1最大化，這里的策略π(a|s)是一個函數(shù)，對于狀態(tài)集S中的每一個狀態(tài)s，π(a|s)表示了在當(dāng)前狀態(tài)s選取動作a的概率，即π(a|s)=P(At=a|St=s)。

基于值函數(shù)的強(qiáng)化學(xué)習(xí)方法通過評估每個狀態(tài)或者狀態(tài)行為對的價(jià)值然后選擇策略，其中狀態(tài)值函數(shù)表示從當(dāng)前狀態(tài)開始依照當(dāng)前策略期望的返還，即Vπ(s)=Eπ(Gt|St=s)；狀態(tài)行為值函數(shù)表示從當(dāng)前狀態(tài)執(zhí)行某個動作之后遵循當(dāng)前策略期望的返還，即Qπ(s,a)=Eπ(Gt|St=s,At=a)，其中Gt=rt+1+γrt+2+γ2rt+3+…+γkrt+k+1，表示了某一時(shí)間步t時(shí)的累積回報(bào)[1]。當(dāng)算法學(xué)習(xí)到最優(yōu)狀態(tài)值函數(shù)V*(s)或者最優(yōu)狀態(tài)行為值函數(shù)Q*(s,a)時(shí)，值函數(shù)滿足貝爾曼最優(yōu)方程，貝爾曼最優(yōu)方程如下：

2.2 時(shí)間差分算法

時(shí)間差分算法是基于值函數(shù)的強(qiáng)化學(xué)習(xí)方法中的核心算法[1]，其更新公式為：

根據(jù)行為策略和評估策略是否一致，時(shí)間差分方法分為兩大主流算法Q-learning和Sarsa，Q-learning的學(xué)習(xí)目標(biāo)為：

Sarsa的學(xué)習(xí)目標(biāo)為：

3 RMAX-KNN 算法

算法分為狀態(tài)空間學(xué)習(xí)和值函數(shù)學(xué)習(xí)兩部分，這兩部分同步進(jìn)行。在Agent 與環(huán)境交互的過程中，通過判斷新狀態(tài)與已有離散狀態(tài)的最小距離是否大于某一閾值來決定是否添加此新狀態(tài)為新的狀態(tài)空間代表點(diǎn)，這一部分被稱為狀態(tài)空間學(xué)習(xí)；同時(shí)，通過狀態(tài)空間學(xué)習(xí)學(xué)習(xí)到的狀態(tài)空間表示點(diǎn)在值函數(shù)學(xué)習(xí)過程中被用來衡量狀態(tài)的已知程度。根據(jù)當(dāng)前狀態(tài)已知程度計(jì)算相應(yīng)的狀態(tài)行為值，并根據(jù)此值進(jìn)行動作選擇并轉(zhuǎn)移到下一狀態(tài)；同時(shí)根據(jù)下一狀態(tài)的已知程度計(jì)算出相應(yīng)的更新量，最終對已學(xué)到的狀態(tài)空間表示點(diǎn)的狀態(tài)行為值進(jìn)行更新，值函數(shù)計(jì)算和值函數(shù)更新合稱為值函數(shù)學(xué)習(xí)。

3.1 相關(guān)假設(shè)與狀態(tài)空間學(xué)習(xí)

假設(shè)1 確定性狀態(tài)轉(zhuǎn)移函數(shù)和已知的回報(bào)函數(shù)。假設(shè)當(dāng)前狀態(tài)為s,執(zhí)行動作a，則P(s′|s,a)=1 且，同時(shí)已知且非負(fù)，同時(shí)Rmax。當(dāng)然也可以類推出狀態(tài)轉(zhuǎn)移函數(shù)不確定時(shí)的情況。

假設(shè)2值函數(shù)滿足利普希茨連續(xù)條件，即存在常數(shù)LQ，滿足|Q(s,a)-Q(s′,a)|≤LQd(s,a,s′,a)。在連續(xù)狀態(tài)空間MDP 中，同一狀態(tài)行為對很難出現(xiàn)第二次，當(dāng)值函數(shù)滿足利普希茨連續(xù)條件時(shí)，就可以用該狀態(tài)行為對“旁邊”的狀態(tài)行為對代替此狀態(tài)行為對來進(jìn)行值函數(shù)學(xué)習(xí)，同時(shí)不會造成太大的誤差。

算法單獨(dú)設(shè)置一個存放狀態(tài)空間表示點(diǎn)的列表D，初始化為空，同時(shí)設(shè)置一個距離閾值d_target來決定是否應(yīng)該添加新的狀態(tài)空間表示點(diǎn)到此列表中，以及一個最大離散狀態(tài)數(shù)Nmax。在Agent 與環(huán)境交互的過程中，假設(shè)某一時(shí)刻狀態(tài)為s，此時(shí)判斷式（1）是否成立，如果成立，則將s添加入D中；若不成立，則說明D中已有可以表示狀態(tài)s的代表點(diǎn)或者D已滿。

狀態(tài)空間學(xué)習(xí)之后，根據(jù)動作選擇函數(shù)選擇相應(yīng)動作a并執(zhí)行，得到環(huán)境返還的立即回報(bào)r′，環(huán)境轉(zhuǎn)換到下一狀態(tài)s′，此時(shí)進(jìn)行值函數(shù)學(xué)習(xí)，值函數(shù)學(xué)習(xí)之后，當(dāng)前狀態(tài)變?yōu)閟′，重復(fù)上述狀態(tài)空間學(xué)習(xí)和值函數(shù)學(xué)習(xí)過程，直到學(xué)習(xí)到最優(yōu)策略。在線學(xué)習(xí)過程中，如果設(shè)計(jì)的算法無法合理地均衡探索和利用，則Agent 會局限在某一塊狀態(tài)區(qū)域內(nèi)，學(xué)習(xí)到的狀態(tài)空間表示將會局限在此區(qū)域內(nèi)，同時(shí)無法學(xué)習(xí)到最優(yōu)策略，因此在值函數(shù)學(xué)習(xí)過程中需要合理地進(jìn)行探索。

3.2 值函數(shù)計(jì)算

考慮滿足所做假設(shè)的強(qiáng)化學(xué)習(xí)問題，在Agent 與環(huán)境交互過程中，假設(shè)某一時(shí)刻狀態(tài)為s，此時(shí)需要計(jì)算該狀態(tài)對應(yīng)的狀態(tài)行為值來進(jìn)行動作選擇。在計(jì)算具體的狀態(tài)行為值Q(s,a)時(shí)，使用該時(shí)刻列表D中當(dāng)前狀態(tài)s的k個近鄰點(diǎn)相應(yīng)的狀態(tài)行為值來估計(jì)Q(s,a)。假設(shè)當(dāng)前列表D={x1,x2,…,xn},n≤Nmax，動作集合為A={a0,a1,a2}，則狀態(tài)s在狀態(tài)空間表示點(diǎn)中的k個近鄰點(diǎn)如圖1 所示（圖中僅表示出D中的一部分點(diǎn)）。

則狀態(tài)s的k近鄰集合表示為：

分別計(jì)算K(s)中k個近鄰點(diǎn)x1,x2,…,xk與s的距離：

Fig.1 k neighborhoods of s(k=4)圖1 狀態(tài)s 的k 近鄰（k=4）

得到K(s)相對應(yīng)的距離集合，表示為：

同時(shí)計(jì)算權(quán)重集合：

以及近鄰點(diǎn)貢獻(xiàn)比集合：

給定有效近鄰點(diǎn)距離閾值d_point，返回k個近鄰點(diǎn)中相應(yīng)距離di≤d_point的近鄰點(diǎn)集合，稱此近鄰點(diǎn)集合為有效近鄰點(diǎn)集合，定義為：

狀態(tài)s的k近鄰集合K(s)中與狀態(tài)s距離大于有效近鄰點(diǎn)距離閾值d_point的那些點(diǎn)的集合稱為無效近鄰點(diǎn)集合，定義為：

列表D中存放的狀態(tài)空間表示點(diǎn)對應(yīng)一張狀態(tài)行為值表，隨著狀態(tài)空間學(xué)習(xí)的進(jìn)行，這張表中的值函數(shù)被不斷填充和修改。在計(jì)算具體的狀態(tài)行為值Q(s,a)時(shí)，使用當(dāng)前狀態(tài)s的k個近鄰點(diǎn)相應(yīng)的狀態(tài)行為值來估計(jì)Q(s,a)。在計(jì)算時(shí)，對于當(dāng)前狀態(tài)有效近鄰點(diǎn)集合U(s)中的近鄰點(diǎn)相應(yīng)的狀態(tài)行為值，使用上述狀態(tài)行為值表中存放的數(shù)據(jù)；對于當(dāng)前狀態(tài)無效近鄰點(diǎn)集合R(s)中的近鄰點(diǎn)相應(yīng)的狀態(tài)行為值，賦值為，因此取值為同時(shí)考慮當(dāng)前狀態(tài)s的k個近鄰點(diǎn)各自的貢獻(xiàn)比，則狀態(tài)行為值計(jì)算公式為：

當(dāng)U(s)=K(s)，即R(s)=?時(shí)，稱當(dāng)前狀態(tài)s是已知的；當(dāng)U(s)≠K(s)，R(s)≠?，U(s)=?時(shí)，稱當(dāng)前狀態(tài)s是未知的；否則當(dāng)前狀態(tài)s是部分已知的。當(dāng)前狀態(tài)已知程度不同，max在(s,a)的計(jì)算中所占比重不同。

3.3 值函數(shù)更新

考慮滿足所做假設(shè)的強(qiáng)化學(xué)習(xí)問題，在Agent 與環(huán)境交互的過程中，本算法使用經(jīng)典的Sarsa 算法來進(jìn)行值函數(shù)更新，Sarsa原始值函數(shù)更新公式為：

其中，在計(jì)算具體的狀態(tài)行為值Q(s′,a′)時(shí)，同樣使用列表D中狀態(tài)s′的k個近鄰點(diǎn)相應(yīng)的狀態(tài)行為值來估計(jì)Q(s′,a′)，根據(jù)式（2）得：

因此，本文算法值函數(shù)更新公式變?yōu)椋?/p>

上式可以看作是傳統(tǒng)RMAX 算法[10]在連續(xù)狀態(tài)空間上不確定性度量的拓展，在傳統(tǒng)RMAX 算法中，某一狀態(tài)的已知程度的取值是布爾型數(shù)值，此狀態(tài)已知時(shí)，對其進(jìn)行正常的狀態(tài)行為值更新；當(dāng)其未知時(shí)，更新量變?yōu)槎疚乃惴ㄖ袑鹘y(tǒng)RMAX進(jìn)行擴(kuò)展，根據(jù)狀態(tài)已知程度賦予不同程度的更新量，使探索和利用之間的轉(zhuǎn)換相比傳統(tǒng)RMAX 更加平緩，更適用于連續(xù)狀態(tài)空間MDP。

值得注意的是，本文算法無法直接對Q(s,a)進(jìn)行更新，只能更新當(dāng)前狀態(tài)s的k個近鄰點(diǎn)對應(yīng)當(dāng)前動作a的狀態(tài)行為值，假設(shè)狀態(tài)s的k近鄰集合為：

則值函數(shù)更新公式變?yōu)椋?/p>

從上述值函數(shù)更新公式可以看出，在Agent 與環(huán)境交互的每一步更新時(shí)，僅僅更新當(dāng)前狀態(tài)的k個近鄰點(diǎn)對應(yīng)當(dāng)前動作的狀態(tài)行為值，這樣算法的學(xué)習(xí)效率不太理想。聯(lián)想經(jīng)典強(qiáng)化學(xué)習(xí)算法，使用資格跡來提升本文算法性能。

3.4 資格跡的引入

資格跡的引入可以極大地提升時(shí)間差分算法的性能[1]。傳統(tǒng)時(shí)間差分算法在每一步進(jìn)行值函數(shù)更新時(shí)，僅僅更新當(dāng)前狀態(tài)的值函數(shù)；而資格跡的引入使得值函數(shù)每一步的更新擴(kuò)散到之前Agent 經(jīng)歷過的所有狀態(tài)中。資格跡由一個取值在0 到1 的變量λ來控制，當(dāng)λ等于0 時(shí)，帶有資格跡的時(shí)間差分算法就是傳統(tǒng)的時(shí)間差分算法，即不帶有資格跡的時(shí)間差分算法；當(dāng)λ等于1 時(shí)，此時(shí)帶有資格跡的時(shí)間差分算法就等效于蒙特卡羅算法。

在本文算法中引入資格跡，就必須為所有的狀態(tài)空間表示點(diǎn)分配一個矩陣e來存放每個狀態(tài)空間表示點(diǎn)的跡。使用資格跡之后，本文算法在每次進(jìn)行值函數(shù)更新時(shí)，值函數(shù)更新的范圍將不僅僅局限于當(dāng)前狀態(tài)的k個近鄰點(diǎn)，而是擴(kuò)散到目前所學(xué)習(xí)到的所有狀態(tài)空間表示點(diǎn)，此時(shí)值函數(shù)更新公式變?yōu)椋?/p>

其中，替代資格跡e更新公式如下：

其中，P(s)是狀態(tài)s相對應(yīng)的近鄰點(diǎn)貢獻(xiàn)比集合，a是Agent 在當(dāng)前狀態(tài)s所執(zhí)行的動作。通常資格跡e會以下式衰減：

結(jié)合狀態(tài)空間學(xué)習(xí)、值函數(shù)計(jì)算、引入資格跡的值函數(shù)更新三部分，就得到了本文所提算法，算法的主要步驟總結(jié)如下：

算法1 RMAX-KNN

輸入：最大離散狀態(tài)數(shù)Nmax，距離閾值d_target，離散動作集合A，近鄰點(diǎn)數(shù)k，有效近鄰點(diǎn)距離閾值d_point，最大回合數(shù)max_episode，最大步數(shù)max_step。

輸出：最優(yōu)策略。

步驟1初始化列表D為空，建立Nmax行|A|列的Q表，表中所有元素初始化為max；同時(shí)建立相同大小的e表，表中所有元素初始化為0。

步驟2當(dāng)回合數(shù)小于max_episode時(shí)，在每一回合中重復(fù)以下步驟：

步驟2.1回合開始時(shí)由環(huán)境自帶的reset 函數(shù)給定初始狀態(tài)。

步驟2.2在當(dāng)前狀態(tài)下根據(jù)式（2）計(jì)算相應(yīng)值函數(shù)，然后通過貪婪策略選取并執(zhí)行動作，轉(zhuǎn)移到下一狀態(tài)，在下一狀態(tài)同樣根據(jù)式（2）計(jì)算值函數(shù)并選取相應(yīng)動作。

步驟2.3根據(jù)式（1）對當(dāng)前狀態(tài)進(jìn)行狀態(tài)空間學(xué)習(xí)，同時(shí)根據(jù)式（5）進(jìn)行值函數(shù)更新。

步驟2.4將下一狀態(tài)變?yōu)楫?dāng)前狀態(tài)，返回步驟2.2，重復(fù)以上步驟直到本回合終止。

步驟3當(dāng)最大回合數(shù)完成時(shí)，算法結(jié)束。

4 RMAX-KNN 算法的PAC-MDP 證明

在對RMAX-KNN 算法進(jìn)行分析之前，首先簡要介紹一下PAC-MDP 相關(guān)定義。

4.1 PAC-MDP

PAC-MDP 是一種強(qiáng)化學(xué)習(xí)算法的度量準(zhǔn)則，用于約束強(qiáng)化學(xué)習(xí)算法所學(xué)策略沒有逼近最優(yōu)策略的總時(shí)間步數(shù)。這一準(zhǔn)則最早被Fiechter 在文獻(xiàn)[11]中引入到強(qiáng)化學(xué)習(xí)中，之后被Kearns、Singh 在文獻(xiàn)[12]和Kakade 在文獻(xiàn)[13]以及Strehl 在文獻(xiàn)[14]分別重新定義。本文使用Strehl在文獻(xiàn)[14]中定義的PAC-MDP概念，定義如下：

定義1[14]令ht=(s0,a0,r1,s1,a1,…,st) 表示由一強(qiáng)化學(xué)習(xí)算法A 到時(shí)間t生成的路徑，令πt表示t時(shí)刻算法學(xué)習(xí)到的策略。對于任意給定的參數(shù)?>0，算法A 學(xué)習(xí)到的策略沒有逼近最優(yōu)策略，即滿足Vπt(st)≤V*(st)-?的總時(shí)間步數(shù)定義為算法A 的樣本復(fù)雜度。

定義2[14]根據(jù)定義1，某一算法A 的樣本復(fù)雜度是用算法所學(xué)策略沒有逼近最優(yōu)策略的總時(shí)間步數(shù)來度量。在離散狀態(tài)空間MDP 中（假設(shè)動作空間離散），如果算法A 的樣本復(fù)雜度可以由MDP 狀態(tài)和動作總數(shù)量的多項(xiàng)式表示，則稱算法A 是滿足PACMDP 的強(qiáng)化學(xué)習(xí)算法。

定義1 和定義2 分別是針對離散狀態(tài)空間MDP問題所定義的樣本復(fù)雜度和PAC-MDP 準(zhǔn)則。在連續(xù)狀態(tài)空間MDP 中，狀態(tài)數(shù)量為無限多，定義2 不再適用，因此本文使用文獻(xiàn)[9]中連續(xù)狀態(tài)空間的覆蓋數(shù)概念，同時(shí)基于此概念給出連續(xù)狀態(tài)空間下的PAC-MDP 準(zhǔn)則，定義如下：

定義3[9]連續(xù)狀態(tài)空間MDP（假設(shè)動作空間離散）中，假設(shè)此MDP 中所有從初始狀態(tài)可達(dá)的狀態(tài)行為對都包含于集合U中，存在集合C滿足：

其中，d是一種距離度量方式，r是給定的距離閾值。若集合C最小時(shí)元素個數(shù)為NU(r)，則稱NU(r)為集合U的覆蓋數(shù)。在連續(xù)狀態(tài)空間MDP 中，集合U對應(yīng)SA，則NSA(r)稱為連續(xù)狀態(tài)空間MDP 狀態(tài)行為空間的覆蓋數(shù)。

定義4[9]在連續(xù)狀態(tài)空間MDP（假設(shè)動作空間離散）中，如果算法A 的樣本復(fù)雜度可以由此MDP 狀態(tài)行為空間的覆蓋數(shù)NSA(r)的多項(xiàng)式表示，則稱算法A 在此連續(xù)狀態(tài)空間MDP 上滿足PAC-MDP 準(zhǔn)則。

4.2 PAC-MDP 證明

本文算法樣本集合，即狀態(tài)空間表示點(diǎn)集合中存放的僅僅是狀態(tài)，并非狀態(tài)行為對，在狀態(tài)空間學(xué)習(xí)完成之后，樣本集合中的狀態(tài)空間表示點(diǎn)可以代表當(dāng)前MDP 的整個連續(xù)狀態(tài)空間，聯(lián)系定義3 和狀態(tài)空間學(xué)習(xí)，此時(shí)D中元素?cái)?shù)量為當(dāng)前MDP 狀態(tài)空間S的覆蓋數(shù)，記為NS(d_point)。本文算法根據(jù)這NS(d_point)個狀態(tài)空間表示點(diǎn)建立了一張相應(yīng)的狀態(tài)行為值表，其中每個元素分別對應(yīng)一個狀態(tài)行為值并初始化為max，這樣在計(jì)算當(dāng)前狀態(tài)的狀態(tài)行為值來進(jìn)行動作選擇時(shí)，如果當(dāng)前狀態(tài)存在無效近鄰點(diǎn)集合，則值函數(shù)計(jì)算公式為：

若當(dāng)前狀態(tài)不存在無效近鄰點(diǎn)集合，則值函數(shù)計(jì)算公式變?yōu)椋?/p>

但當(dāng)前狀態(tài)的k近鄰集合對應(yīng)的狀態(tài)行為值如果沒有更新一直是初始值max，則此時(shí)值函數(shù)計(jì)算公式與存在無效近鄰點(diǎn)集合時(shí)相一致。本文算法通過判斷當(dāng)前狀態(tài)s的k近鄰集合是否等于其有效近鄰點(diǎn)集合來衡量當(dāng)前狀態(tài)行為對是否已知，此時(shí)判斷條件為：

可見其實(shí)是計(jì)算狀態(tài)行為對之間的距離，只是所取動作相同。在本文算法中，對于當(dāng)前MDP，NSA(d_point)=|A|×NS(d_point)。

在對本文算法進(jìn)行PAC-MDP 分析前，首先闡述相關(guān)引理和定理。

引理1[15]最多添加kNSA(d_point)個樣本可以使所有從初始狀態(tài)可達(dá)的狀態(tài)行為對變?yōu)橐阎?/p>

引理2[12]如果，則|Vπ(s,T)-Vπ(s)|≤

引理3[16]令M表示一個MDP，K表示一個狀態(tài)行為對的集合，M′表示一個在集合K中所有狀態(tài)行為對上與M具有相同狀態(tài)轉(zhuǎn)移函數(shù)和回報(bào)函數(shù)的MDP，π表示一個策略，T為任一正整數(shù)。令A(yù)M表示在M中從狀態(tài)s1開始遵循策略π與環(huán)境交互T步生成的路徑中遇到一個不在集合K中的狀態(tài)行為對這一事件。則：

引理4[17]令x1,x2,…∈B 表示一個由m個獨(dú)立伯努利實(shí)驗(yàn)組成的序列，其中每個實(shí)驗(yàn)成功概率均大于等于μ：E[xi]≥μ,μ>0 。給定任意實(shí)數(shù)l∈N和δ∈(0,1)，如果，有：

定理1令ε≥0 滿足?(s,a)∈(S,A),|(s,a)-Q(s,a)|≤ε，且V*(s)≤V，則在值函數(shù)上采用貪婪策略所得回報(bào)Vπ滿足：

定理1 的證明見附錄。

本文算法在進(jìn)行值函數(shù)更新時(shí)，采用帶有資格跡的時(shí)間差分算法。為了方便討論，考慮單步更新的Sarsa算法，原始Sarsa的值函數(shù)更新公式如下：

當(dāng)算法狀態(tài)空間學(xué)習(xí)完成之后，所有從初始位置可達(dá)的狀態(tài)都為已知狀態(tài)，此時(shí)對于任意狀態(tài)行為 對(s,a) 和(s′,a′)，存 在U(s)=K(s) 和U(s′)=K(s′)，根據(jù)式（2），計(jì)算其狀態(tài)行為值：

則本文算法值函數(shù)更新公式變?yōu)椋?/p>

由上式可知，近鄰點(diǎn)值函數(shù)的更新本質(zhì)上依舊是在Agent 真實(shí)軌跡上進(jìn)行Sarsa 學(xué)習(xí)，通過一次次迭代更新，近鄰點(diǎn)的值函數(shù)收斂并最終逼近于它們各自真實(shí)的值函數(shù)。但是Agent 真實(shí)軌跡中的狀態(tài)行為對的狀態(tài)行為值是根據(jù)此狀態(tài)行為對近鄰點(diǎn)對應(yīng)的狀態(tài)行為值加權(quán)平均所得，存在一定誤差，導(dǎo)致最終值函數(shù)學(xué)習(xí)完成之后近鄰點(diǎn)的值函數(shù)也會存在一定的誤差。為了方便討論，這里假設(shè)通過本文算法所得到的近鄰點(diǎn)狀態(tài)行為值與其真實(shí)的狀態(tài)行為值之間的誤差為εn。

因此，在本文算法中，計(jì)算某一狀態(tài)行為對的值函數(shù)時(shí)所存在的誤差可以被分為兩部分：一部分是使用有限數(shù)量個近鄰點(diǎn)的狀態(tài)行為值來計(jì)算當(dāng)前狀態(tài)行為值引入的誤差εs；另一部分是近鄰點(diǎn)即狀態(tài)空間表示點(diǎn)各自逼近的狀態(tài)行為值自身存在的誤差εn。

定理2如果那么

定理1 和定理2 分別闡述了本文算法所學(xué)狀態(tài)行為值函數(shù)存在的誤差與對應(yīng)狀態(tài)值函數(shù)誤差的一致性以及保持所學(xué)狀態(tài)行為值與真實(shí)狀態(tài)行為值差值在某一誤差區(qū)間內(nèi)所需充分條件。通過以上引理及定理，可得定理3，如下：

定理3令M表示一個MDP，表示在t時(shí)刻根據(jù)當(dāng)前所學(xué)狀態(tài)行為值函數(shù)采取貪婪策略所得到的策略，st表示t時(shí)刻時(shí)的狀態(tài)，并且k≥對于一個任意長度的軌跡，當(dāng)

有：

通過定理3 可知從初始狀態(tài)開始，本文算法逼近最優(yōu)策略所需總時(shí)間步數(shù)t可以由連續(xù)狀態(tài)空間MDP 的覆蓋數(shù)NSA(d_point)的多項(xiàng)式表示，因此本文算法滿足PAC-MDP 準(zhǔn)則。

定理2 和定理3 的相關(guān)證明見附錄。

5 實(shí)驗(yàn)與結(jié)果

在3個經(jīng)典強(qiáng)化學(xué)習(xí)環(huán)境Mountain Car、Cart Pole、Inverted Pendulum 上測試本文算法，算法的源代碼地址為https://github.com/chaobiubiu/RMAX-KNN。

5.1 Benchmark domains

Mountain Car：在此環(huán)境中，Agent 的目標(biāo)是讓一個動力不足的小車在來回跑動后可以到達(dá)右側(cè)山頂。小車的狀態(tài)空間是連續(xù)的，分為兩個維度，第一個是小車所在位置position∈[-1.2,0.6]，第二個是小車當(dāng)前速度velocity∈[-0.07,0.07]；小車的動作空間是離散的A={0,1,2}，動作0 代表給小車一個向左的力，動作1 代表不施加力，動作2 代表給小車一個向右的力。小車初始位置在山谷最低處，問題的難度在于從初始位置給小車直接施加向右的力小車是無法到達(dá)右側(cè)山頂?shù)?，小車只有先往左走然后獲得一定的動能，才可以到達(dá)右邊目標(biāo)點(diǎn)。在小車沒有到達(dá)目標(biāo)點(diǎn)之前，小車每走一步所獲得的獎勵一直是-1，只有到達(dá)目標(biāo)點(diǎn)獲得獎勵為0。實(shí)驗(yàn)參數(shù)設(shè)置為：總回合數(shù)為500，每個回合最大步數(shù)為1 000，學(xué)習(xí)率α=0.9，折扣因子γ=0.99，資格跡衰減參數(shù)λ=0.95。學(xué)習(xí)率、折扣因子以及資格跡衰減參數(shù)等參數(shù)的設(shè)置參考文獻(xiàn)[18]，每一回合開始時(shí)小車位置由gym 環(huán)境自帶的reset函數(shù)初始化。

Cart Pole：在此環(huán)境中，存在一個小車，小車上方豎著一根桿子，Agent 的目標(biāo)就是左右移動這個小車來保持桿子豎直。如果桿子的傾斜角度大于15°或者小車左右移動超出了限定范圍，此次模擬結(jié)束。該環(huán)境的狀態(tài)也是連續(xù)的，分為4個維度：第一個是小車的水平位置；第二個是桿子與垂直方向的夾角；第三個是小車的速度；第四個是桿子的角速度。動作空間為離散空間：A={0,1}，動作0 代表小車往左走，動作1 代表小車往右走。在保持桿子豎直時(shí)，小車每走一步所獲得的獎勵為1；當(dāng)桿子過度傾斜或者小車移動超出限定范圍時(shí)，獲得獎勵為0。在本文算法中，當(dāng)桿子過度傾斜或小車移動超出限定范圍時(shí)，修改獲得獎勵為-200，這一修改是為了加速算法學(xué)習(xí)速率，在計(jì)算回合平均回報(bào)時(shí)，仍按照0 來計(jì)算。實(shí)驗(yàn)參數(shù)設(shè)置為：總回合數(shù)為500，每個回合最大步數(shù)為200，學(xué)習(xí)率α=0.2，折扣因子γ=0.95，資格跡衰減參數(shù)λ=0.95。學(xué)習(xí)率、折扣因子以及資格跡衰減參數(shù)等參數(shù)的設(shè)置參考文獻(xiàn)[18]，開始位置由gym環(huán)境自帶的reset 函數(shù)初始化。當(dāng)100個連續(xù)回合內(nèi)所得平均獎勵大于195 時(shí)，認(rèn)為該問題被解決。

Inverted Pendulum：在此環(huán)境中，電機(jī)需要來回?cái)[動鐘擺來收集能量，最終將鐘擺抬高并保持鐘擺平衡。狀態(tài)空間分為3個維度：第一個是當(dāng)前鐘擺與垂直方向夾角的余弦值cos(theta)∈[-1,1]；第二個是當(dāng)前鐘擺與垂直方向夾角的正弦值sin(theta)∈[-1,1]；第三個是當(dāng)前鐘擺的角速度thetadot∈[-8,8]，動作空間為連續(xù)空間A={a|-2 ≤a≤2}。實(shí)驗(yàn)參數(shù)設(shè)置為：總回合數(shù)為500，每個回合最大步數(shù)為500，學(xué)習(xí)率α=0.9，折扣因子γ=0.95，資格跡衰減參數(shù)λ=0.95。學(xué)習(xí)率、折扣因子以及資格跡衰減參數(shù)等參數(shù)的設(shè)置參考文獻(xiàn)[19]，開始位置初始化為[1,0,0]，同時(shí)參考文獻(xiàn)[20]，將環(huán)境的立即回報(bào)函數(shù)修改為reward=1-exp[-xTdiag([1,0.2])x]。

5.2 實(shí)驗(yàn)結(jié)果

實(shí)驗(yàn)中，首先考察了算法中3個參數(shù)k、d_target、d_point對算法性能的影響，然后與采用Tilecoding 編碼的Sarsa(λ)算法進(jìn)行比較。

（1）參數(shù)對算法性能的影響

本文算法中有3個參數(shù)k、d_target、d_point，其中k的取值決定了計(jì)算當(dāng)前狀態(tài)行為對的狀態(tài)行為值時(shí)所選近鄰點(diǎn)的個數(shù)，k取值太小，當(dāng)前狀態(tài)行為值逼近效果差；k取值太大，當(dāng)前狀態(tài)行為值逼近誤差過大，難以達(dá)到實(shí)驗(yàn)?zāi)繕?biāo)。d_target的取值決定了對于狀態(tài)空間的劃分精度，d_target取值小，劃分精度高，最終算法收斂效果好，但是收斂速度慢；d_target取值大，劃分精度低，最終算法收斂速度快，但是收斂效果較差。d_point是有效近鄰點(diǎn)距離閾值，衡量一個狀態(tài)行為對未知程度的參數(shù)，d_point取值小，如果狀態(tài)空間劃分精度低，則Agent 在算法學(xué)習(xí)過程中遇到的狀態(tài)行為對全部變?yōu)橐阎枰荛L時(shí)間，造成算法難以收斂最終學(xué)習(xí)失?。籨_point取值大，如果狀態(tài)劃分精度高，則Agent 遇到的所有狀態(tài)行為對在較短的時(shí)間內(nèi)可以變?yōu)橐阎?，算法收斂速度很快，但是收斂效果較差。參數(shù)k、d_target、d_point彼此之間相互影響，圖2、圖3、圖4 分別是固定其中兩個參數(shù)，調(diào)整另外一個參數(shù)對于算法性能影響的實(shí)驗(yàn)結(jié)果圖。

Fig.2 Effect of k on algorithm圖2 k 值對算法的影響

圖2（a）中橫坐標(biāo)為回合數(shù)，縱坐標(biāo)為每個回合內(nèi)小車到達(dá)目標(biāo)點(diǎn)所需步數(shù)，所需步數(shù)越少越好。從圖中可以看出：當(dāng)k取值為1 時(shí)，算法性能波動較大，算法性能差；當(dāng)k取值為3 或5 時(shí)，算法快速收斂且收斂效果極好；當(dāng)k取值為7 或9 時(shí)，小車無法達(dá)到目標(biāo)點(diǎn)，算法難以學(xué)習(xí)到最優(yōu)策略。圖2（b）中橫坐標(biāo)為回合數(shù)，縱坐標(biāo)為每個回合的平均回報(bào)，平均回報(bào)越高越好。從圖中可以看出：當(dāng)k取值為1 時(shí)，算法難以學(xué)習(xí)到最優(yōu)策略；當(dāng)k取值為3 時(shí)，算法可以快速收斂且收斂效果極好；當(dāng)k取值為5、7、9 時(shí)，算法收斂速度較慢且收斂結(jié)果較差。圖2（c）中橫坐標(biāo)為回合數(shù)，縱坐標(biāo)為每個回合內(nèi)獲得的總回報(bào)，總回報(bào)越高越好。從圖中可以看出：當(dāng)k取值為1 時(shí)，算法收斂速度較慢且收斂效果較差；當(dāng)k取值為3 時(shí)，算法快速收斂且收斂效果極好；當(dāng)k取值為5、7、9 時(shí)，算法性能波動較大，算法性能差。

Fig.3 Effect of d_target on algorithm圖3 d_target值對算法的影響

Fig.4 effect of d_point on algorithm圖4 d_point值對算法的影響

圖3（a）中橫坐標(biāo)為回合數(shù)，縱坐標(biāo)為每個回合內(nèi)小車到達(dá)目標(biāo)點(diǎn)所需步數(shù)，所需步數(shù)越少越好。從圖中可以看出：當(dāng)d_target取值為0.05 或0.07 時(shí)，算法性能波動較大；當(dāng)d_target取值為0.09 或0.11時(shí)，算法快速收斂且收斂效果較好；當(dāng)d_target取值在0.13 時(shí)，算法性能差。圖3（b）中橫坐標(biāo)為回合數(shù)，縱坐標(biāo)為每個回合的平均回報(bào)，平均回報(bào)越高越好。從圖中可以看出：當(dāng)d_target取值為0.03 時(shí)，算法收斂速度較慢；當(dāng)d_target取值為0.05 或0.07 時(shí)，算法可以快速收斂且收斂效果極好；當(dāng)d_target取值為0.09 或0.11 時(shí)，算法性能差。圖3（c）中橫坐標(biāo)為回合數(shù)，縱坐標(biāo)為每個回合內(nèi)獲得的總回報(bào)，總回報(bào)越高越好。從圖中可以看出，當(dāng)d_target取值為0.03、0.05、0.07 時(shí)，算法性能最優(yōu)；當(dāng)d_target取值為0.06或0.08 時(shí)，算法性能差。

圖4（a）中橫坐標(biāo)為回合數(shù)，縱坐標(biāo)為每個回合內(nèi)小車到達(dá)目標(biāo)點(diǎn)所需步數(shù)，所需步數(shù)越少越好。從圖中可以看出：當(dāng)d_point取值為0.10 時(shí)，算法難以學(xué)習(xí)到最優(yōu)策略；當(dāng)d_point取值為0.12 或0.14 時(shí)，算法性能波動較大；當(dāng)d_point取值為0.16 時(shí)，算法可以快速收斂且收斂效果極好；當(dāng)d_point取值為0.18 時(shí)，算法收斂速度較慢且收斂效果較差。圖4（b）中橫坐標(biāo)為回合數(shù)，縱坐標(biāo)為每個回合的平均回報(bào)，平均回報(bào)越高越好。從圖中可以看出：當(dāng)d_point取值為0.07 時(shí)，算法難以學(xué)習(xí)到最優(yōu)策略；當(dāng)d_point取值為0.09、0.13 時(shí)，算法收斂速度較慢且收斂效果較差；當(dāng)d_point取值為0.11、0.15 時(shí)，算法快速收斂且收斂速度極好。圖4（c）中橫坐標(biāo)為回合數(shù)，縱坐標(biāo)為每個回合內(nèi)獲得的總回報(bào)，總回報(bào)越高越好。從圖中可以看出：當(dāng)d_point取值為0.06、0.07 時(shí)，算法性能較差；當(dāng)d_point取值為0.09、0.11、0.13 時(shí)，算法快速收斂且收斂效果極好。

（2）本文算法與采用Tilecoding 編碼的Sarsa(λ)算法的比較

Fig.5 Comparison result of two algorithms圖5 兩種算法實(shí)驗(yàn)對比結(jié)果

為進(jìn)一步驗(yàn)證本文算法的性能，與采用Tilecoding編碼的Sarsa(λ) 算法進(jìn)行比較，比較結(jié)果如圖5 所示。在Mountain Car 問題中，本文算法在多次實(shí)驗(yàn)之后選取最優(yōu)參數(shù)k=3，d_target=0.09，d_point=0.16；而對比實(shí)驗(yàn)中采用20×20 的表格對二維狀態(tài)空間進(jìn)行劃分，分別設(shè)置Tilings=5、10、20，對比結(jié)果如圖5（a）所示。圖中橫坐標(biāo)表示回合數(shù)，縱坐標(biāo)表示每個回合中小車到達(dá)目標(biāo)點(diǎn)所需步數(shù)（如果所需步數(shù)為實(shí)驗(yàn)所設(shè)最大步數(shù)，則表示此回合小車沒有到達(dá)目標(biāo)點(diǎn)），所需步數(shù)越少，則實(shí)驗(yàn)結(jié)果越好。相比之下，本文算法更快收斂且收斂效果更好（到達(dá)目標(biāo)點(diǎn)最優(yōu)步數(shù)為83 步），而對比算法收斂較慢且收斂效果較差（到達(dá)目標(biāo)點(diǎn)最優(yōu)步數(shù)為113 步）。在Cart Pole 問題中，同樣在多次實(shí)驗(yàn)之后本文算法選取最優(yōu)參數(shù)k=3，d_target=0.07，d_point=0.11；對比實(shí)驗(yàn)中采用20×20×20×20 的表格對四維狀態(tài)空間進(jìn)行劃分，分別設(shè)置Tilings=5、10、20，對比結(jié)果如圖5（b）所示。圖中橫坐標(biāo)表示回合數(shù)，縱坐標(biāo)為每個回合的平均回報(bào)，平均回報(bào)越高實(shí)驗(yàn)結(jié)果越好。相比之下，本文算法最優(yōu)平均回報(bào)為200，表現(xiàn)遠(yuǎn)遠(yuǎn)優(yōu)于對比算法（對比算法最優(yōu)平均回報(bào)為125）。在Inverted Pendulum 問題中，在多次實(shí)驗(yàn)之后選取最優(yōu)參數(shù)k=3，d_target=0.05，d_point=0.09；對比實(shí)驗(yàn)中采用20×20×20 的表格覆蓋三維狀態(tài)空間，分別設(shè)置Tilings=5、10、20，對比結(jié)果如圖5（c）所示。圖中橫坐標(biāo)表示回合數(shù)，縱坐標(biāo)表示每個回合中所獲得的總回報(bào)，總回報(bào)越高實(shí)驗(yàn)結(jié)果越好。相比之下，本文算法可以快速收斂且收斂效果優(yōu)秀（收斂之后每個回合總回報(bào)為-0.26），而對比算法收斂較慢且收斂結(jié)果略差（收斂之后每個回合總回報(bào)最優(yōu)為-0.68）。此外，本文算法在達(dá)到實(shí)驗(yàn)?zāi)繕?biāo)時(shí)所學(xué)到的狀態(tài)空間表示點(diǎn)數(shù)量分別為：Mountain Car 環(huán)境下狀態(tài)空間表示點(diǎn)數(shù)量為239個；Cart Pole 環(huán)境下狀態(tài)空間表示點(diǎn)數(shù)量為220個；Inverted Pendulum 環(huán)境下狀態(tài)空間表示點(diǎn)為1 016個，遠(yuǎn)小于對比實(shí)驗(yàn)中離散狀態(tài)空間點(diǎn)的個數(shù)，降低了算法的空間復(fù)雜度。

表1 為在各自最優(yōu)參數(shù)下本文算法與采用Tilecoding 編碼的Sarsa(λ)算法回報(bào)rew、點(diǎn)數(shù)num以及收斂所需回合數(shù)epi的比較。

Table 1 Comparison result of two algorithms表1 兩種算法對比實(shí)驗(yàn)結(jié)果

從表1 中可以看出，在回報(bào)方面，本文算法在Mountain Car、Cart Pole、Inverted Pendulum 環(huán)境下所得回報(bào)均大于對比算法所得回報(bào)，回報(bào)越高，則算法性能越好；在狀態(tài)空間表示點(diǎn)數(shù)目方面，本文算法在3個實(shí)驗(yàn)環(huán)境下達(dá)到實(shí)驗(yàn)?zāi)繕?biāo)所需狀態(tài)空間表示點(diǎn)數(shù)目均遠(yuǎn)遠(yuǎn)小于對比算法，點(diǎn)數(shù)越少則算法空間復(fù)雜度越低；在收斂所需回合數(shù)方面，本文算法在3個實(shí)驗(yàn)環(huán)境下收斂所需回合數(shù)均遠(yuǎn)小于對比算法，收斂所需回合數(shù)越少則算法時(shí)間復(fù)雜度越低，性能越好。綜合以上三方面，可知本文算法性能遠(yuǎn)優(yōu)于對比算法。

6 結(jié)束語

本文提出的基于狀態(tài)空間自適應(yīng)離散化的RMAXKNN 強(qiáng)化學(xué)習(xí)算法在值函數(shù)學(xué)習(xí)中嵌入了探索與利用的均衡，同時(shí)實(shí)現(xiàn)了狀態(tài)空間的自適應(yīng)離散化。該算法通過改寫值函數(shù)形式，使探索與環(huán)境狀態(tài)空間離散化相結(jié)合，逐步加深A(yù)gent 對于環(huán)境的認(rèn)知程度，極大地提升了探索效率，降低了時(shí)間復(fù)雜度；同時(shí)自適應(yīng)離散化環(huán)境狀態(tài)空間，降低了空間復(fù)雜度。本文提出的算法可以在一定程度上緩解維數(shù)災(zāi)難，但當(dāng)連續(xù)狀態(tài)空間維度很高時(shí)，維數(shù)災(zāi)難仍會加重，未來將致力于在值函數(shù)逼近和策略搜索兩者結(jié)合的Actor Critic 方法及其一系列變種方法中實(shí)現(xiàn)探索與利用的均衡。

附錄

定理1令ε≥0 滿足?(s,a)∈(S,A),|(s,a)-Q(s,a)|≤ε，且V*(s)≤V，則在值函數(shù)上采用貪婪策略所得回報(bào)Vπ滿足：

證明?(s,a)∈(S,A),|(s,a)-Q(s,a)|≤ε，則?(s,a)∈(S,A),|(s,a)-Q*(s,a)|≤ε。由貝爾曼最優(yōu)方程V*(s)=maaxQ*(s,a)可得：

定理得證。 □

定理2如果，那么：

證明是式（2）的唯一且固定解，(s,a)是狀態(tài)行為對(s,a)的k個近鄰點(diǎn)對應(yīng)于當(dāng)前動作a的狀態(tài)行為值加權(quán)平均所得值，Q(s,a)是狀態(tài)行為對(s,a)的真實(shí)狀態(tài)行為值，則：

可見對(s,a)的k個近鄰點(diǎn)對應(yīng)的狀態(tài)行為值進(jìn)行加權(quán)平均計(jì)算出(s,a)，而本文算法中近鄰點(diǎn)逼近的狀態(tài)行為值存在誤差εn，即：

其中，Q(xi,a)為近鄰點(diǎn)真實(shí)的狀態(tài)行為值?？紤]使用有限數(shù)量個近鄰點(diǎn)的真實(shí)狀態(tài)行為值來計(jì)算當(dāng)前狀態(tài)行為值引入的誤差εs，即：

當(dāng)上式中pi取時(shí)，由Hoeffding 不等式得：

考慮pi不為的情況，此時(shí)由Hoeffding 不等式的一般形式可得：

由定義3 可知，連續(xù)狀態(tài)空間MDP 中所有從初始狀態(tài)可達(dá)的狀態(tài)行為對都可以由此MDP 狀態(tài)動作空間的覆蓋數(shù)來表示，因此NSA(d_point)個樣本可以代表所有從初始狀態(tài)可達(dá)的狀態(tài)行為對。而所有從初始狀態(tài)可達(dá)的狀態(tài)行為對的狀態(tài)行為值是根據(jù)其k個近鄰點(diǎn)相應(yīng)的狀態(tài)行為值來計(jì)算，等價(jià)于這NSA(d_point)個樣本每個都取k次來評估各自代表的狀態(tài)行為對，因此所有從初始狀態(tài)可達(dá)的狀態(tài)行為對根據(jù)各自近鄰點(diǎn)狀態(tài)行為值加權(quán)平均所得的狀態(tài)行為值與其真實(shí)狀態(tài)行為值的差值大于等于(εs+εn)的概率δ滿足：

因?yàn)閗≥1，所以：

給定概率δ和誤差εs和εn，由上式得：

定理得證。 □

定理3令M表示一個MDP，表示在t時(shí)刻根據(jù)當(dāng)前所學(xué)狀態(tài)行為值函數(shù)采取貪婪策略所得到的策略，st表示t時(shí)刻時(shí)的狀態(tài)，并且對于一個任意長度的軌跡，當(dāng)

證明令M′表示一個在所有已知狀態(tài)行為對上狀態(tài)轉(zhuǎn)移函數(shù)與M相同的MDP，假設(shè)其他狀態(tài)行為對都可以確定性轉(zhuǎn)移到一個假設(shè)存在的狀態(tài)s*，該狀態(tài)狀態(tài)值為0，且所得回報(bào)為R(s,a)=(s,a)。令A(yù)M表示在T時(shí)間步數(shù)內(nèi)遇見一個未知狀態(tài)行為對這一事件。在每一時(shí)間步時(shí)，僅會發(fā)生下述兩件事之一：

（2）對于t時(shí)刻的狀態(tài)st，，則：

定理得證。 □