一種結合演示數據和演化優化的強化學習方法

宋拴,俞揚

SONG Shuan, YU Yang

南京大學 計算機軟件新技術國家重點實驗室,南京 210023

National Key Laboratory for Novel Software Technology, Nanjing University, Nanjing 210023, China

1 引言

強化學習是機器學習的一個重要研究領域，它要解決的問題可描述為：agent通過與環境交互，根據環境反饋的獎賞值改善自身行為策略，使得長期累積獎賞值最大[1,2]。強化學習算法就是要找到一個策略，它將agent所處狀態映射為agent在該狀態應采取的動作。

由于強化學習具有自主學習的特點，適用于大空間、復雜非線性問題，已經應用到多個領域[1,3]。例如在自動控制領域，將強化學習算法用于倒立擺問題，取得了優于手動設計傳遞函數的效果[4]。此外，在服務器調度、電梯調度以及Backgammon游戲等問題上也得到了成功的應用[1,3]。

在強化學習的早期研究中，強化學習多采用試錯法[1,2]。在引入MDP理論后，值函數法在強化學習研究中占據了主導地位，并取得了豐碩成果，代表性的算法如 Q學習等[1,2]，這類算法通過各種值函數逼近的方法來計算最優策略。隨著研究的不斷深入，很多新的方法被提出，以解決傳統強化學習算法效率低、收斂慢等不足[2]。演化強化學習將演化算法和強化學習相結合，通過演化算法搜索強化學習的最優策略[5]或最優值函數[6]，取得了良好的效果。Stanley等人首先將一種稱作NEAT[7]的演化神經網絡算法用于解決倒立擺問題，演化得到的神經網絡用于選擇動作，這相當于在策略空間直接搜索最優策略[8]。Shimon Whiteson等人提出的NEAT+Q[6]算法，用神經網絡逼近強化學習的值函數，通過演化神經網絡搜索最優值函數表示，其實驗結果表明NEAT+Q算法的性能遠優于Q學習。在NEAT+Q算法的基礎上，Shimon Whiteson等人提出了Sample Efficient NEAT+Q的算法，它記錄學習過程中成功執行了的例子，用這些例子來訓練神經網絡[9]。強化學習算法效率低下的一個原因是因為agent通過自主探索的方式來與環境交互，在學習的早期階段，agent需要反復探索大量無用的狀態，在狀態空間很大時，學習算法的性能會急劇降低。從示例中學習[10]是一種借助先驗知識或經驗來幫助agent學習的方法，它可以有效的減少agent在學習初期對狀態空間的大量低效探索。它的主要思路是教師演示某問題的解決方法，agent通過某種方式利用教師的演示信息，來加快自身的學習。典型的方法是通過示例數據學習出一個從狀態到動作的映射函數，agent用該函數進行動作選擇，或者從示例數據中學習出一個獎賞函數，解決強化學習過程中的信用分配的問題。

由于基于演化的強化學習和從示例中學習各自所具有的優點，一種自然的想法是，能否將這兩種方法結合起來，進一步提高學習算法的性能？基于這一想法,本文提出了一種稱為 iNEAT+Q(imitation based NEAT+Q)的算法，它基于 NEAT+Q算法，在演化強化學習值函數的過程中，通過有效地利用示例數據幫助agent學習。在Mountain Car實驗平臺上的結果表明，本文提出的方法取得了優于NEAT+Q算法的性能。

本文的內容組織如下。第一節介紹強化學習的相關定義、應用、演化強化學習，以及本文的組織和工作。第二節介紹與本文有關的背景知識。第三節介紹本文的主要工作，即 iNEAT+Q的算法。第四節介紹本文的實驗及實驗結果。第五節總結了本文的工作。

2 背景

2.1 MDP

強化學習問題通常建模為一個 MDP[1,3]。MDP可以用一個五元組表示，其中，S為狀態集合，A為agent的動作集合，R為獎賞函數，R(s, a)定義了agent在狀態s執行動作a所獲得的獎賞，P為狀態轉移概率，P(s, a, s')定義了agent在狀態s下執行動作a轉移到狀態 s'的概率，γ為折扣因子。

值函數的一個基本屬性就是它滿足遞歸性質，可以表示為Bellman方程的形式。

上式表明在狀態s的期望獎賞值可以表示為它的立即獎賞與下一狀態的期望獎賞值的加權和。對于給定MDP，它的目標是要找到一條能夠最大化累積獎賞最優策略。因此，最優策略π*對應的值函數可表示為：

2.2 Q學習

Q學習[1]是一種應用廣泛的強化學習算法，它的目標是是學習一個值函數Q(s,a)，它將(狀態,動作)映射到一個實數值。在值表法中Q(s,a)，通過下式進行更新：

當強化學習問題的狀態空間較小時，可通過值表法求解。對于規模較大以及連續的問題，值表法不再適用，需要值函數近似方法來求解，神經網絡就是其中一種典型的非線性近似方法[1]。

2.3 神經網絡

神經網絡[11]又稱多層感知機。一個典型的三層神經網絡包含輸入層、隱藏層和輸出層，其中，輸入層接收待學習的問題的模式，經網絡傳輸到隱藏層，隱藏層相當于一個特征檢測器，它的輸出經網

絡傳遞給輸出層，輸出層輸出學習的結果。神經元常采用Sigmoid函數作為其變換函數，實現輸入到輸出的非線性變換。

神經網絡常采用反向傳播(BP)算法[11]進行訓練，它通過梯度下降法最小化均方誤差實現，在輸出層計算網絡當前輸出和目標值之間的誤差，并將誤差逆向傳播，依次更新神經網絡的權值。

2.4 NEAT

Stanley等人在2002年提出NEAT (NeuroEvolution of Augmenting Topologies)[7]算法，它使用演化算法來自動尋找合適的神經網絡結構和初始權值。

NEAT算法的初始種群為一組沒有任何隱藏節點的神經網絡，神經網絡的所有輸入節點和輸出節點直接相連。為適應神經網絡結構進化的需要，神經網絡被編碼為一組邊，每條邊由入點、出點及該邊的權重組成。在演化的過程中，引入了兩種變異操作，增加一個隱藏層節點和增加一條邊。神經網絡的結構通過變異發生變化，只有能夠提高個體適應度的變異才可以在進化中保留下來。NEAT通過這種方式尋找最優的網絡拓撲結構。

NEAT算法最初用于強化學習問題時，是為agent選擇合適的動作，從這個角度看相當于搜索策略空間中的最優策略。Whiteson等人在Mountain Car等實驗上驗證了NEAT算法的有效性，它取得了優于Q學習的結果[2,12]。

2.5 NEAT+Q

NEAT+Q[6]算法由Whiteson等人于2006年提出，它將演化算法和強化學習算法結合起來，目的是搜索最優的值函數表示。因為神經網絡具有強大的表達能力，常用于表示強化學習的值函數，但是針對具體的問題，要找到最佳的神經網絡結構和權值并不容易，NEAT+Q算法在演化神經網絡的過程中，通過Q學習評價神經網絡的性能，并且在每個神經網絡個體學習過程中，使用時序差值錯誤更新神經網絡的權值，從而在優化神經網絡結構的同時優化神經網絡的權值。NEAT+Q算法的性能好于NEAT算法和Q學習。

2.6 從示例中學習

從示例中學習(Learning from Demonstration) 這一概念來源于機器人的模仿學習[10]。示例由教師提供，記錄了教師在演示一個任務成功執行的過程。從 agent的角度來看，它所觀察到的信息為教師演示過程中的每個狀態以及在每個狀態所采取的動作。因此，記錄下教師演示過程中的(狀態,動作)序列，就是 agent能夠加以利用的示例數據。例如一條執行了n步的示例數據的記錄可以表示為一個(狀態,動作)一一對應的序列，如，其中s為狀態，a為動作。

現有的從示例中學習算法大概可分為兩類[10]。第一類方法使用示例數據學習一個從狀態空間到動作空間的映射，該函數可看做是一條策略，agent可以用它來選擇動作。第二類方法從示例中學習一個獎賞函數，這類方法又稱為逆強化學習(Inverse Reinforcement Learning)[13]，它可以用于解決強化學習中的信用分配問題。

3 本文工作

在演化強化學習的過程中,如何結合示例數據進行學習是本文關注的重點。在已有的從示例中學習算法中，無論是從示例數據中學習到一個策略或者學習到一個獎賞函數，都難以直接用到演化強化學習的過程當中。

在演化神經網絡的過程中，不僅要改變神經網絡的結構，還要改變神經網絡的權值，對于神經網絡而言，無論是結構還是權值，都會影響到神經網絡的性能，因此，首先考慮使用示例數據作為訓練樣本，在演化過程中每一代直接訓練每個神經網絡，在每個神經網絡都有一個較優的初始權值的情況下，其性能的差異更多的依賴于網絡結構。

使用示例數據的另一種思路是，將示例數據看做是提供指導信息的教師[14,15]，教師根據agent當前狀態s和所選動作a給出獎賞信息H(s, a)，教師給出的獎賞H(s, a)加入到agent所接收到的獎勵RH(s, a)中，以引導agent的動作選擇。

當H(s, a)＞0時，可以看做是教師對agent在狀態s選擇動作a的額外獎勵，agent在該狀態所選的動作會得到強化。當H(s,a)＜0時，可看做是對該動作的懲罰，則這一動作將被弱化。從演化的角度來看，修改了agent的獎賞函數，相當于修改了演化過程中每個神經網絡個體的適應度評價函數，與演示數據更相似的個體有更高的適應度，與演示數據差異較大的個體適應度會變低。

3.1 預訓練神經網絡

在演化算法的每一代開始之前，執行如下算法(算法描述中步驟2 1))：

(1) 將示例數據作為訓練樣本，使用BP算法訓練種群P中的每個神經網絡N。

3.2 修改獎賞函數

在agent每次選擇了動作a之后，執行如下算法(算法描述中步驟2 2) 中的(4)(5)(8))：

(1) 根據 agent當前狀態s，尋找它在示例中的最近鄰狀態，返回該狀態的動作，a '=NearestNeighbour(s)，最近鄰使用歐氏距離度量。

(2) 比較 a'和a,給出獎賞值 H(s, a)。如果 a' 和a相同，則，否則

3.3 算法描述

算法中所用到的參數如表1所述。

Table 1 Parameters used in iNEAT+Q表1 iNEAT+Q算法中用到的參數

m 增加邊的概率g 演化的代數e 個體執行的周期數α 學習率γ 折扣因子λ 資格跡衰減率ε Q學習探索率l

算法執行過程如下：

步驟1 初始化種群P、示例數據D以及各參數。

步驟 2 g為演化的最大代數，p為種群中個體的數目，e為每個個體在每一代中執行的周期數。在演化算法的第i代，對于種群P中的第 j個個體N：

1) 使用示例數據D訓練神經網絡N，

2) 神經網絡N在e個周期中的一次執行過程如下：

步驟3 如果當前種群中還有個體未評估，轉步驟2，否則，根據每個個體的適應度值，生成新的種群：

步驟4 如果到達最后一代，算法結束，否則，轉步驟2。

4 實驗

4.1 Mountain Car

Mountain Car[1]問題的設定是在一輛小車停在一個二維山谷的底部，目標是到達較高的一個山頂，小車沒有足夠的動力無法持續加速到山頂，所以必須先向反方向加速，以獲得更大的沖量。

簡單的Mountain Car問題狀態僅有兩維，分別是小車的位置p和速度v，小車在狀態s可選擇的動作a分別為向左加速、不加速和向右加速，可分別表示為-1，0，1。

在每個周期，小車的初始位置隨機化為山谷中任意一點，初始速度為0。如果小車在2500步內到達目標則視為成功，否則停止。小車每運行一步，根據它是否達到目標獲得獎賞，如果到達目標獎賞為 0，否則為-1。

4.2 生成演示數據

實驗中所用到的示例數據是由兩個不同結構的神經網絡執行Q學習算法得來的。其中一個神經網絡無隱藏層節點，另一個隱藏層節點數為12，輸入節點和輸出節點數目分別為20和3。神經網絡的輸入是小車的狀態，它被離散化為一個20維的向量。這兩個神經網絡在隨機初始點反復執行Mountain Car任務多次，從中選出執行步數較少的作為示例。每個示例記錄的信息為，從初始狀態到目標狀態的一系列二元組(狀態,動作)。所采集的示例數據初始點在(-1.2，0.5)之間近似均勻分布。一條典型的示例數據如表2所示，每一行表示一個記錄，是一個(位置，速度，動作)三元組，前兩個對應的是小車的狀態，后一個表示小車在該狀態的動作。

表2 示例數據

表2中的示例數據經離散化后如表3所示，狀態為一個20維的向量。

表3 離散化后的示例數據

4.3 實驗設置

在Mountain Car實驗中，小車的狀態信息作為神經網絡的輸入，進行了離散化，將位置和速度各劃分為10個區域，如果小車的位置和狀態落入某個區域，則對應的值為1，否則為0。神經網絡的3個輸出節點，分別對應小車的3個動作。

實驗中用到的演示數據數量為923條，所有示例的初始點近似均勻分布在-1.2和0.5之間。

本文進行了2組實驗。第一組實驗為了驗證本文所提出算法，比較了NEAT+Q、iNEAT+Q和iNEAT+Q退化版三種方法，iNEAT+Q是指僅使用示例數據預訓練神經網絡的方法，iNEAT+Q退化版是指僅使用示例數據修改獎賞函數的方法。每種方法各執行20次。第二組實驗驗證演示數據數量對iNEAT+Q算法性能的影響。

4.4 實驗結果

圖1顯示的是第一組實驗的結果，每條曲線顯示其對應算法每一代中最優個體在該代所接收到的平均獎賞值。最優個體指的是在它所在的那一代平均獎賞值最高的個體。每個算法執行20次，選出最好的10個取平均。

從圖 1中可以看出，使用示例數據對算法的性能有明顯提升。預訓練神經網絡和修改獎賞函數兩種方法的收斂時間均早于NEAT+Q算法。NEAT+Q算法在演化較長一段時間后，性能趨向于預訓練神經網絡方法，但是付出了較長的時間代價?？傮w來看，預訓練神經網絡方法的效果最好，但是訓練神經網絡的時間開銷不可忽略。修改獎賞值的性能不如預訓練神經網絡的方法，但是它也能夠在較早的時間內收斂。這表明，如果有充足的計算資源，可以考慮使用示例數據對每個神經網絡個體進行充分的訓練，在計算資源比較昂貴時，可以通過修改獎賞函數的方式來利用演示數據同樣可以獲得性能的提升。

圖 2中顯示的是第二組實驗的結果，它顯示了不同數量的示例數據對算法性能的影響。因為示例數據的數量對修改獎賞函數的方法影響很小，因此，僅比較預訓練神經網絡方法在示例數據數量不同時算法性能的變化。從圖中可以看出，獎賞值隨著演示數據數量的增加先增大，到達一定數量后開始下降，這表明，演示數據并非越多越好。

圖1 NEAT+Q、iNEAT+Q和iNEAT+Q退化版性能的比較

圖2 演示數據數量對iNEAT+Q算法性能的影響

5 總結

演化強化學習是一種基于演化優化的方法，通過在值函數空間搜索最優值函數，來得到最優策略。從示例中學習通過示例引導agent學習，提高agent的學習效率。這兩種方法從不同角度出發，均有效提高了強化學習的性能。本文嘗試著結合這兩種方法，提出了 iNEAT+Q算法，并給出了兩種使用演示數據的方法。在演化神經網絡的過程中，可以使用演示數據預訓練神經網絡，給每一代的所有個體一個較好的初始權值，也可以在演化的過程中，在agent選擇動作時，由演示數據提供教師信號指導agent學習，由于同時修改了相應個體的適應度，使得與演示數據動作選擇相似的個體具有更高的適應度，從而引導個體的進化方向。實驗表明，這兩種方法均可以有效提高學習算法的性能。此外，本文還驗證了示例數據數量對算法性能的影響，實驗結果表明，演示數據的數量并非越多越好，而是要保證在一個合理的數量。

[1]Richard S. Sutton, Andrew G. Barto. Reinforcement Learning: An Introduction. Cambridge: MIT Press, 1998

[2]Marco W, Martijn V O. Reinforcement Learning: State of the Art.New York:Springer-Verlag, 2012.

[3]高陽,陳世福,陸鑫.強化學習研究綜述.自動化學報, 2004,30(1):86-100.

[4]王瑞霞,孫亮,阮曉鋼.基于強化學習的二級倒立擺控制.計算機仿真,2006,23(4):305-308.

[5]Moriarty D E, Schultz A C, Grefenstette J J. Evolutionary algorithms for reinforcement learning. Journal of Artificial Intelligence Research, 1999,11: 241-276.

[6]Whiteson S, Stone P. Evolutionary function approximation for reinforcement learning. Journal of Machine Learning Research,2006,7: 877-917.

[7]Stanley K O, Miikkulainen R. Evolving neural networks through augmenting topologies. Evolutionary Computation, 2002,10(2): 99-127.

[8]Stanley K O, Miikkulainen R. Efficient reinforcement learning through evolving neural network topologies. In Proceedings of the Genetic and Evolutionary Computation Coference(GECCO-2002). San Francisco, CA, 2002,569-577.

[9]Whiteson S, Stone P. Sample efficient evolutionary function approximation for reinforcement learning. In Proceedings of the 21th National Conference on Artificial Intelligence. Boston, MA, 2006, 518-23.

[10]Argall B D, Chernova S, Veloso M, Browning B. A survey of robot learning from demonstration. Robotics and Autonomous Systems, 2009,57(5):469-483.

[11]Mitchell TM.Machine learning.McGraw Hill,NY,1997.

[12]Whiteson S, Taylor M E, Stone P. Critial factors in the empirical performance of temporal difference and evolutioinary methods for reinforcement learning. Journal of Autonomous Agents and Multi-Agent Systems, 2009, 21(1):1-27.

[13]Andrew N g., Russell S. Algorithms for inverse reinforcement learning. In Proceedings of the 17th International Conference on Machine Learning. Stanford, CA, 2000, 663–670.

[14]Knox W B, Setapen A, Stone P. Reinforcement learning with human feedback in mountain car.In Proceedings of AAAI Spring Symposium: Help Me Help You: Bridging the Gaps in Human-Agent Collaboration, 2011.

[15]Laud A, DeJong G. Reinforcement learning and shaping: encouraging intended behaviors. In Proceedings of the 19th International Conference on Machine Learning. Sydney, Australia, 2002, 355-362.