PAC 最優的RMAX-KNN 探索算法*

李 超，門昌騫，王文劍

1.山西大學 計算機與信息技術學院，太原030006

2.計算智能與中文信息處理教育部重點實驗室（山西大學），太原030006

1 引言

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

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

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

綜合狀態空間自適應離散化劃分和探索與利用的均衡這兩個問題，本文提出了基于狀態空間自適應離散化的RMAX-KNN 強化學習算法，該算法經理論證明是一種PAC 最優探索算法，可以在短時間內逼近最優策略，并且該算法可以在有效探索狀態空間的同時實現對狀態空間的自適應離散化。此外，在三個常見的benchmark 環境上測試此算法，結果表明本文算法是可行且高效的。

2 背景知識

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

2.1 狀態值函數和狀態行為值函數

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

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

2.2 時間差分算法

時間差分算法是基于值函數的強化學習方法中的核心算法[1]，其更新公式為：

根據行為策略和評估策略是否一致，時間差分方法分為兩大主流算法Q-learning和Sarsa，Q-learning的學習目標為：

Sarsa的學習目標為：

3 RMAX-KNN 算法

算法分為狀態空間學習和值函數學習兩部分，這兩部分同步進行。在Agent 與環境交互的過程中，通過判斷新狀態與已有離散狀態的最小距離是否大于某一閾值來決定是否添加此新狀態為新的狀態空間代表點，這一部分被稱為狀態空間學習；同時，通過狀態空間學習學習到的狀態空間表示點在值函數學習過程中被用來衡量狀態的已知程度。根據當前狀態已知程度計算相應的狀態行為值，并根據此值進行動作選擇并轉移到下一狀態；同時根據下一狀態的已知程度計算出相應的更新量，最終對已學到的狀態空間表示點的狀態行為值進行更新，值函數計算和值函數更新合稱為值函數學習。

3.1 相關假設與狀態空間學習

假設1 確定性狀態轉移函數和已知的回報函數。假設當前狀態為s,執行動作a，則P(s′|s,a)=1 且，同時已知且非負，同時Rmax。當然也可以類推出狀態轉移函數不確定時的情況。

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

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

狀態空間學習之后，根據動作選擇函數選擇相應動作a并執行，得到環境返還的立即回報r′，環境轉換到下一狀態s′，此時進行值函數學習，值函數學習之后，當前狀態變為s′，重復上述狀態空間學習和值函數學習過程，直到學習到最優策略。在線學習過程中，如果設計的算法無法合理地均衡探索和利用，則Agent 會局限在某一塊狀態區域內，學習到的狀態空間表示將會局限在此區域內，同時無法學習到最優策略，因此在值函數學習過程中需要合理地進行探索。

3.2 值函數計算

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

則狀態s的k近鄰集合表示為：

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

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

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

同時計算權重集合：

以及近鄰點貢獻比集合：

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

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

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

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

3.3 值函數更新

考慮滿足所做假設的強化學習問題，在Agent 與環境交互的過程中，本算法使用經典的Sarsa 算法來進行值函數更新，Sarsa原始值函數更新公式為：

其中，在計算具體的狀態行為值Q(s′,a′)時，同樣使用列表D中狀態s′的k個近鄰點相應的狀態行為值來估計Q(s′,a′)，根據式（2）得：

因此，本文算法值函數更新公式變為：

上式可以看作是傳統RMAX 算法[10]在連續狀態空間上不確定性度量的拓展，在傳統RMAX 算法中，某一狀態的已知程度的取值是布爾型數值，此狀態已知時，對其進行正常的狀態行為值更新；當其未知時，更新量變為而本文算法中對傳統RMAX進行擴展，根據狀態已知程度賦予不同程度的更新量，使探索和利用之間的轉換相比傳統RMAX 更加平緩，更適用于連續狀態空間MDP。

值得注意的是，本文算法無法直接對Q(s,a)進行更新，只能更新當前狀態s的k個近鄰點對應當前動作a的狀態行為值，假設狀態s的k近鄰集合為：

則值函數更新公式變為：

從上述值函數更新公式可以看出，在Agent 與環境交互的每一步更新時，僅僅更新當前狀態的k個近鄰點對應當前動作的狀態行為值，這樣算法的學習效率不太理想。聯想經典強化學習算法，使用資格跡來提升本文算法性能。

3.4 資格跡的引入

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

在本文算法中引入資格跡，就必須為所有的狀態空間表示點分配一個矩陣e來存放每個狀態空間表示點的跡。使用資格跡之后，本文算法在每次進行值函數更新時，值函數更新的范圍將不僅僅局限于當前狀態的k個近鄰點，而是擴散到目前所學習到的所有狀態空間表示點，此時值函數更新公式變為：

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

其中，P(s)是狀態s相對應的近鄰點貢獻比集合，a是Agent 在當前狀態s所執行的動作。通常資格跡e會以下式衰減：

結合狀態空間學習、值函數計算、引入資格跡的值函數更新三部分，就得到了本文所提算法，算法的主要步驟總結如下：

算法1 RMAX-KNN

輸入：最大離散狀態數Nmax，距離閾值d_target，離散動作集合A，近鄰點數k，有效近鄰點距離閾值d_point，最大回合數max_episode，最大步數max_step。

輸出：最優策略。

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

步驟2當回合數小于max_episode時，在每一回合中重復以下步驟：

步驟2.1回合開始時由環境自帶的reset 函數給定初始狀態。

步驟2.2在當前狀態下根據式（2）計算相應值函數，然后通過貪婪策略選取并執行動作，轉移到下一狀態，在下一狀態同樣根據式（2）計算值函數并選取相應動作。

步驟2.3根據式（1）對當前狀態進行狀態空間學習，同時根據式（5）進行值函數更新。

步驟2.4將下一狀態變為當前狀態，返回步驟2.2，重復以上步驟直到本回合終止。

步驟3當最大回合數完成時，算法結束。

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

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

4.1 PAC-MDP

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

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

定義2[14]根據定義1，某一算法A 的樣本復雜度是用算法所學策略沒有逼近最優策略的總時間步數來度量。在離散狀態空間MDP 中（假設動作空間離散），如果算法A 的樣本復雜度可以由MDP 狀態和動作總數量的多項式表示，則稱算法A 是滿足PACMDP 的強化學習算法。

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

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

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

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

4.2 PAC-MDP 證明

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

若當前狀態不存在無效近鄰點集合，則值函數計算公式變為：

但當前狀態的k近鄰集合對應的狀態行為值如果沒有更新一直是初始值max，則此時值函數計算公式與存在無效近鄰點集合時相一致。本文算法通過判斷當前狀態s的k近鄰集合是否等于其有效近鄰點集合來衡量當前狀態行為對是否已知，此時判斷條件為：

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

在對本文算法進行PAC-MDP 分析前，首先闡述相關引理和定理。

引理1[15]最多添加kNSA(d_point)個樣本可以使所有從初始狀態可達的狀態行為對變為已知。

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

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

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

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

定理1 的證明見附錄。

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

當算法狀態空間學習完成之后，所有從初始位置可達的狀態都為已知狀態，此時對于任意狀態行為 對(s,a) 和(s′,a′)，存 在U(s)=K(s) 和U(s′)=K(s′)，根據式（2），計算其狀態行為值：

則本文算法值函數更新公式變為：

由上式可知，近鄰點值函數的更新本質上依舊是在Agent 真實軌跡上進行Sarsa 學習，通過一次次迭代更新，近鄰點的值函數收斂并最終逼近于它們各自真實的值函數。但是Agent 真實軌跡中的狀態行為對的狀態行為值是根據此狀態行為對近鄰點對應的狀態行為值加權平均所得，存在一定誤差，導致最終值函數學習完成之后近鄰點的值函數也會存在一定的誤差。為了方便討論，這里假設通過本文算法所得到的近鄰點狀態行為值與其真實的狀態行為值之間的誤差為εn。

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

定理2如果那么

定理1 和定理2 分別闡述了本文算法所學狀態行為值函數存在的誤差與對應狀態值函數誤差的一致性以及保持所學狀態行為值與真實狀態行為值差值在某一誤差區間內所需充分條件。通過以上引理及定理，可得定理3，如下：

定理3令M表示一個MDP，表示在t時刻根據當前所學狀態行為值函數采取貪婪策略所得到的策略，st表示t時刻時的狀態，并且k≥對于一個任意長度的軌跡，當

有：

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

定理2 和定理3 的相關證明見附錄。

5 實驗與結果

在3個經典強化學習環境Mountain Car、Cart Pole、Inverted Pendulum 上測試本文算法，算法的源代碼地址為https://github.com/chaobiubiu/RMAX-KNN。

5.1 Benchmark domains

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

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

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

5.2 實驗結果

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

（1）參數對算法性能的影響

本文算法中有3個參數k、d_target、d_point，其中k的取值決定了計算當前狀態行為對的狀態行為值時所選近鄰點的個數，k取值太小，當前狀態行為值逼近效果差；k取值太大，當前狀態行為值逼近誤差過大，難以達到實驗目標。d_target的取值決定了對于狀態空間的劃分精度，d_target取值小，劃分精度高，最終算法收斂效果好，但是收斂速度慢；d_target取值大，劃分精度低，最終算法收斂速度快，但是收斂效果較差。d_point是有效近鄰點距離閾值，衡量一個狀態行為對未知程度的參數，d_point取值小，如果狀態空間劃分精度低，則Agent 在算法學習過程中遇到的狀態行為對全部變為已知需要很長時間，造成算法難以收斂最終學習失敗；d_point取值大，如果狀態劃分精度高，則Agent 遇到的所有狀態行為對在較短的時間內可以變為已知，算法收斂速度很快，但是收斂效果較差。參數k、d_target、d_point彼此之間相互影響，圖2、圖3、圖4 分別是固定其中兩個參數，調整另外一個參數對于算法性能影響的實驗結果圖。

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

圖2（a）中橫坐標為回合數，縱坐標為每個回合內小車到達目標點所需步數，所需步數越少越好。從圖中可以看出：當k取值為1 時，算法性能波動較大，算法性能差；當k取值為3 或5 時，算法快速收斂且收斂效果極好；當k取值為7 或9 時，小車無法達到目標點，算法難以學習到最優策略。圖2（b）中橫坐標為回合數，縱坐標為每個回合的平均回報，平均回報越高越好。從圖中可以看出：當k取值為1 時，算法難以學習到最優策略；當k取值為3 時，算法可以快速收斂且收斂效果極好；當k取值為5、7、9 時，算法收斂速度較慢且收斂結果較差。圖2（c）中橫坐標為回合數，縱坐標為每個回合內獲得的總回報，總回報越高越好。從圖中可以看出：當k取值為1 時，算法收斂速度較慢且收斂效果較差；當k取值為3 時，算法快速收斂且收斂效果極好；當k取值為5、7、9 時，算法性能波動較大，算法性能差。

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

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

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

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

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

Fig.5 Comparison result of two algorithms圖5 兩種算法實驗對比結果

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

表1 為在各自最優參數下本文算法與采用Tilecoding 編碼的Sarsa(λ)算法回報rew、點數num以及收斂所需回合數epi的比較。

Table 1 Comparison result of two algorithms表1 兩種算法對比實驗結果

從表1 中可以看出，在回報方面，本文算法在Mountain Car、Cart Pole、Inverted Pendulum 環境下所得回報均大于對比算法所得回報，回報越高，則算法性能越好；在狀態空間表示點數目方面，本文算法在3個實驗環境下達到實驗目標所需狀態空間表示點數目均遠遠小于對比算法，點數越少則算法空間復雜度越低；在收斂所需回合數方面，本文算法在3個實驗環境下收斂所需回合數均遠小于對比算法，收斂所需回合數越少則算法時間復雜度越低，性能越好。綜合以上三方面，可知本文算法性能遠優于對比算法。

6 結束語

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

附錄

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

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

定理得證。 □

定理2如果，那么：

證明是式（2）的唯一且固定解，(s,a)是狀態行為對(s,a)的k個近鄰點對應于當前動作a的狀態行為值加權平均所得值，Q(s,a)是狀態行為對(s,a)的真實狀態行為值，則：

可見對(s,a)的k個近鄰點對應的狀態行為值進行加權平均計算出(s,a)，而本文算法中近鄰點逼近的狀態行為值存在誤差εn，即：

其中，Q(xi,a)為近鄰點真實的狀態行為值。考慮使用有限數量個近鄰點的真實狀態行為值來計算當前狀態行為值引入的誤差εs，即：

當上式中pi取時，由Hoeffding 不等式得：

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

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

因為k≥1，所以：

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

定理得證。 □

定理3令M表示一個MDP，表示在t時刻根據當前所學狀態行為值函數采取貪婪策略所得到的策略，st表示t時刻時的狀態，并且對于一個任意長度的軌跡，當

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

（2）對于t時刻的狀態st，，則：

定理得證。 □