增強型深度確定策略梯度算法

陳建平，何超，劉全，吳宏杰，胡伏原，傅啟明

?

增強型深度確定策略梯度算法

陳建平1,2,3,4，何超1,2,3，劉全5，吳宏杰1,2,3,4，胡伏原1,2,3,4，傅啟明1,2,3,4

（1. 蘇州科技大學電子與信息工程學院，江蘇 蘇州 215009；2. 蘇州科技大學江蘇省建筑智慧節能重點實驗室，江蘇 蘇州 215009； 3. 蘇州科技大學蘇州市移動網絡技術與應用重點實驗室，江蘇 蘇州 215009； 4. 蘇州科技大學蘇州市虛擬現實智能交互及應用技術重點實驗室，江蘇 蘇州 215009；5. 蘇州大學計算機科學與技術學院，江蘇 蘇州 215006）

針對深度確定策略梯度算法收斂速率較慢的問題，提出了一種增強型深度確定策略梯度（E-DDPG）算法。該算法在深度確定策略梯度算法的基礎上，重新構建兩個新的樣本池——多樣性樣本池和高誤差樣本池。在算法執行過程中，訓練樣本分別從多樣性樣本池和高誤差樣本池按比例選取，以兼顧樣本多樣性以及樣本價值信息，提高樣本的利用效率和算法的收斂性能。此外，進一步從理論上證明了利用自模擬度量方法對樣本進行相似性度量的合理性，建立值函數與樣本相似性之間的關系。將E-DDPG算法以及DDPG算法用于經典的Pendulum問題和MountainCar問題，實驗結果表明，E-DDPG具有更好的收斂穩定性，同時具有更快的收斂速率。

深度強化學習；樣本排序；自模擬度量；時間差分誤差

1 引言

強化學習的基本思想是通過最大化智能體（agent）從環境中獲得的累計獎賞值，以學習完成目標的最優策略[1]。依據策略表示方法和求解的不同，可以將強化學習方法分為3類：“評論家”算法，該算法利用值函數對策略進行評估，最終利用最優值函數求解最優策略；“行動者”算法，該算法利用類似啟發式搜索的方法從策略空間中找出最優策略；“行動者—評論家”算法，行動者部分用于動作的選取，評論家部分用于評估動作的好壞，利用值函數信息指導策略的搜索[2]。然而對于上述任意一類算法，在學習過程中，都需要人工設定狀態表示方法，而通過深度學習方法，可以實現狀態特征的自動學習，以實現“端到端”的任務學習。目前，深度學習作為在機器學習領域的一個研究熱點，已經在圖像分析、語音識別、視頻分類、自然語言處理等領域獲得令人矚目的成就。深度學習的基本思想是通過多層的網絡結構和非線性變換，組合低層特征，形成抽象的、易于區分的高層表示，以發現數據的分布式特征表示[3]。深度學習模型通常由多層的非線性運算單元組合而成，將較低層的輸出作為更高一層的輸入，通過這種方式自動地從大量訓練數據中學習抽象的特征表示[4-5]。

谷歌的DeepMind團隊將深度學習和強化學習結合起來，提出深度強化學習方法，并將深度強化學習應用于圍棋問題。2016年，Alpha Go[6]在人機圍棋比賽中以4:1戰勝圍棋大師李世石，而新版的Alpha Zero[7]可以不需要任何歷史棋譜知識，不借助任何人類先驗知識，僅利用深度強化學習進行自我對弈，最終能以100:0的戰績完勝Alpha Go。目前，深度強化學習已經成為人工智能領域的研究熱點。Mnih等[8-9]將卷積神經網絡與傳統的Q學習[10]算法相結合，提出了深度Q網絡（DQN, deep Q-network）模型。DQN將未被處理過的像素點（原始圖像）作為輸入，通過樣本池存儲歷史經驗樣本，同時利用經驗回放打破樣本間的聯系，以避免網絡參數的震蕩。但是DQN只能解決離散的、低維的動作空間問題，將DQN應用到連續動作領域最簡單的做法是將連續動作離散化，但是這會導致離散動作的數量隨動作維度的增加而呈指數型增長，同時對連續動作進行簡單的離散化會忽略動作域的結構，然而在很多情況下，動作域的結構對于問題的求解是非常重要的，因此，目前基于DQN算法提出了很多關于DQN的變體。Hasselt等[11]在雙重Q學習算法[12]的基礎上提出了深度雙重Q網絡（DDQN, deep double Q-network）算法。Schaul等[13]在DDQN的基礎上提出了一種基于比例優先級采樣的深度雙Q網絡（double deep Q-network with proportional prioritization）等。然而，這些改進的算法都不能夠很好地解決連續動作空間問題。在連續動作空間中，策略梯度是常用的方法，它通過不斷計算策略期望總獎賞關于策略參數的梯度來更新策略參數，最終收斂于最優策略[14]。因此，在解決深度強化學習問題時，可以采用深度神經網絡表示策略，并利用策略梯度方法求解最優參數。此外，在求解深度強化學習問題時，基于策略梯度的算法能夠直接優化策略的期望總獎賞，并以端對端的方式直接在策略空間中搜索最優策略。因此，與DQN及其改進算法相比，基于策略梯度的深度強化學習方法適用范圍更廣，策略優化的效果也更好。Lillicrap等[15]將DPG（deterministic policy gradient）算法[16]與DQN相結合，提出了DDPG（deep deterministic policy gradient）算法。DDPG可用于解決連續動作空間的強化學習問題。實驗表明，DDPG不但在一系列連續動作空間的任務中表現穩定，而且求得最優解所需要的時間步也遠低于DQN，但是DDPG需要大量的樣本數據，且算法的收斂速度也有待提高。

本文在DDPG算法的基礎上提出了增強型深度確定策略梯度（E-DDPG, enhanced deep deterministic policy gradient）算法。針對DDPG算法收斂速度慢的問題，E-DDPG算法在原始樣本池的基礎上構建了兩個樣本池——高誤差樣本池和多樣性樣本池。高誤差樣本池將TD（temporal-difference）error作為啟發式信息對樣本進行排序，以提高誤差較大的樣本的選取概率。同時，多樣性樣本池利用自模擬度量方法度量樣本間的距離，在原始樣本池的基礎上，選擇低相似樣本，以提高樣本池中樣本的多樣性，提高算法的執行效率。在算法學習過程中，訓練樣本將分別從高誤差樣本池和多樣性樣本池按比例選取，以兼顧樣本多樣性以及樣本價值信息，提高樣本的利用效率和算法的收斂性能。實驗結果表明，與DDPG算法相比，E-DDPG算法具有更快的收斂速度以及更好的收斂穩定性。

2 相關理論

2.1 馬爾可夫決策過程

式(1)也被稱作Bellman公式。

式(2)被稱作最優Bellman公式。

2.2 深度確定策略梯度算法

在隨機策略中，策略梯度取決于狀態和動作，而在確定策略中，策略梯度僅取決于狀態。因此，與隨機策略梯度算法相比，確定策略梯度算法收斂需要的樣本相對較少。

其中，有

值得注意的是，確定策略梯度算法缺少對環境的探索，而DDPG算法通過引入隨機噪聲來完成策略探索。通過添加隨機噪聲，使動作的選擇具有一定的隨機性，以完成一定程度的策略探索，具體如式(6)所示。

2.3 自模擬度量與狀態之間的距離

為了度量MDP中狀態的關系，自模擬關系被Givan等[17]引入MDP中。簡而言之，如果兩個狀態滿足自模擬關系，那么這兩個狀態就共享相同的最優值函數以及最優動作。

從定義1可以得出，任意兩個狀態要么滿足自模擬關系，要么不滿足自模擬關系。這種度量方法過于苛刻，且限制其使用的范圍。Ferns等[18]提出了一種可用于衡量兩個狀態之間遠近關系的自模擬度量方法（bisimulation metric）。

計算兩個狀態距離的算法如算法1所示。

算法1 狀態之間距離度量算法

5) end for

7) end for

3 增強型深度確定策略梯度算法

3.1 樣本池的構建

同時，為了保證選取樣本的多樣性，引入自模擬度量方法。從原始樣本池0和高誤差樣本池2中隨機選取的樣本，可能存在很多近似樣本，甚至是重復樣本，這會降低算法的執行效率。因此，考慮間隔個情節，利用算法1計算出原始樣本池0中樣本之間的距離，將低相似性樣本放入多樣性樣本池1，以保證所選擇樣本的多樣性。此后，算法1將分別從多樣性樣本池1和高誤差樣本池2按一定比例選取樣本，進行學習，同時兼顧樣本多樣性以及高價值樣本信息，進一步提高算法的執行效率。

3.2 行動者—評論家網絡參數更新

3.3 E-DDPG算法

根據3.1節和3.2節的介紹，下面給出詳細的E-DDPG算法的流程，如算法2所示。

算法2 E-DDPG算法

2) for= 1 todo

4) 利用自模擬度量方法，將低相似性樣本放入多樣性樣本池1

5) 獲得初始觀察狀態1

6) for= 1 todo

14) else

21) end if

22) end if

23) end if

24) end for

25) end if

26) end for

3.4 關于多樣性樣本池的分析

證畢。

因此，利用自模擬度量方法計算樣本間的距離，利用該距離確定樣本間的相似性可以進一步反映樣本在值函數空間中的相似性。從參數更新的角度而言，在算法學習過程中，高相似性的樣本具有較低的價值，而低相似性的樣本將提高算法的更新效率，進而加快算法收斂速度。

3.5 關于高誤差樣本池的分析

在強化學習中，從歷史樣本池中進行均勻采樣，可能會導致較多的更新集中在某一些低價值的樣本上，如果將更新集中在某些特殊的樣本上，則會使算法的更新更加高效。在均勻采樣訓練的過程中，會浪費大量時間和計算資源進行很多無用的更新，隨著學習的不斷進行，有用的更新區域不斷增加，但是與將更新集中在高價值的樣本上相比，學習的效率和效果差了很多。在連續狀態空間中，這種非集中式搜索的效率將會非常低下。

本文以TD error作為啟發式信息，將訓練中高價值的樣本挑選出來構建高誤差樣本池，在接下來的訓練中，通過提高這些高價值樣本的選取概率，進而更快地獲得有用的更新區域。由于關于TD error的閾值是人為設置的，若僅僅從高誤差樣本池2中選取訓練樣本，可能導致錯過部分高價值樣本，因此，算法同時也從多樣性樣本池中選擇一定比例的樣本。實驗結果表明，該方法可以提高算法的收斂速度。

4 實驗結果分析

4.1 Pendulum問題

1)實驗描述

為了驗證算法的有效性，本文將DDPG算法和E-DDPG算法用于經典Pendulum問題。圖1給出了Pendulum問題的示意。

圖1 Pendulum問題的示意

一個倒立的鐘擺，擺桿繞中間轉軸隨機擺動。agent的任務是學習到一個策略，使擺桿保持豎直。本文實驗環境是OpenAI gym，狀態是三維的，其中，二維表示鐘擺的位置，一維表示鐘擺的速度。狀態可以表示為

動作是一維的，表示對鐘擺的作用力，取值范圍為[?2,2]。動作可以表示為

獎賞函數可以表示為

其中，等于式(9)的計算值的概率是0.1，等于0的概率是0.9。

2) 實驗設置

實驗運行硬件環境為Inter(R) Xeon(R) CPU E5-2660處理器、NVIDIA GeForce GTX 1060顯卡、16 GB內存；軟件環境為Windows 10操作系統、python 3.5、TensorFlow_GPU-1.4.0。

在該實驗中，DDPG算法收斂需要8.1 h，未引入自模擬度量的E-DDPG算法收斂需要5.2 h，而引入自模擬度量的E-DDPG算法收斂僅需要2.4 h。

3) 實驗分析

DDPG算法、E-DDPG算法應用于經典的Pendulum問題上的性能比較（在實驗過程中，每個算法都獨立執行3 000個情節）如圖2所示，各種算法在不同情節下，目標任務達到終止狀態時的總回報值（回報值是通過目標任務從開始狀態達到終止狀態時總的獎賞值）。其中，橫坐標是情節數，縱坐標是算法執行10次的平均回報值。從圖2可以看出，E-DDPG算法在300個情節時基本收斂。DDPG算法雖然在400個情節時取得較高的回報值，但是還在震蕩并沒有收斂，直到1 200個情節才收斂。因為E-DDPG算法引入了TD error，加大了對具有更高價值的樣本的選取概率，同時因為采用自模擬度量方法更新多樣性樣本池1，使選取的訓練樣本多樣性得到保證，從而進一步加快算法的收斂速度。此外，從圖2還可以看出，兩種算法在收斂后，E-DDPG算法每個情節的回報值震蕩的幅度比DDPG算法的震蕩幅度更小，這充分說明E-DDPG算法的穩定性比DDPG算法更好。

圖2 Pendulum問題中兩種算法的性能比較

引入自模擬度量E-DDPG算法、未引入自摸E-DDPG算法和DDPG算法進行的實驗對比，結果如圖3所示，其中，設置自模擬度量間隔的情節數=30。從圖3可以看出，沒有引入自模擬度量方法的E-DDPG算法在700個情節算法才收斂，引入自模擬度量方法的E-DDPG算法在300個情節算法就收斂，而DDPG算法在1 200個情節才收斂。因為自模擬度量方法使訓練的樣本具有更好的多樣性，提高了訓練的效率，從而加快了訓練的速度。

圖3 Pendulum問題中E-DDPG算法是否引入自模擬度量方法與DDPG算法的實驗對比

圖4 Pendulum問題中E-DDPG算法不同TD Error和DDPG算法的實驗對比

圖5 Pendulum問題中E-DDPG算法不同樣本選取比例和DDPG算法的實驗對比

4.2 MountainCar問題

1) 實驗描述

為了驗證算法的有效性，本文將DDPG算法和E-DDPG算法用于經典的MountainCar問題。圖6給出了MountainCar問題的示意。

圖6 MountainCar問題的示意

曲面表示一個帶有坡度的路面，小車處在坡底，由于動力不足，小車無法直接加速沖上坡頂，因此必須通過前后加速借助慣性到達坡頂，即圖6中右側“星”形標記的位置。本文實驗的環境是OpenAI gym，狀態是二維的，其中，一維表示位置，另一維表示速度，狀態可以表示為

動作是一維的，表示小車的加速度，取值范圍為[?1,1]。動作可以表示為

在情節開始時，給定小車一個隨機的位置和速度，然后進行交互學習。當小車到達目標位置（圖6中的“星”形位置）或當前執行的時間步超過1 000時，情節結束，并開始一個新的情節。當小車到達目標位置時，立即獎賞是100；其他情況下，小車的立即獎賞滿足

2)實驗設置

實驗運行硬件環境為Inter(R) Xeon(R) CPU E5-2660處理器、NVIDIA GeForce GTX 1060顯卡、16 GB內存；軟件環境為Windows 10操作系統、python 3.5、TensorFlow_GPU-1.4.0。

在本實驗中，DDPG算法收斂需要7.5 h，未引入自模擬度量的E-DDPG算法收斂需要4.7 h，而引入自模擬度量的E-DDPG算法收斂僅需要1.6 h。

3) 實驗分析

DDPG算法、E-DDPG算法應用于經典的MountainCar問題上的性能比較（在實驗過程中，每個算法都獨立執行2 000個情節）如圖7所示，各個算法在不同情節下，目標任務達到終止狀態時總的回報值（回報值是通過目標任務從開始狀態達到終止狀態時總的獎賞值）。其中，橫坐標是情節數，縱坐標是算法執行10次的平均回報值。從圖7可以看出，E-DDPG算法在120個情節基本收斂。DDPG算法雖然在220個情節時取得較高的回報值，但是還在震蕩并沒有收斂，直到780個情節才收斂。

圖7 MountainCar問題中兩種算法的性能比較

E-DDPG算法是否引入自模擬度量方法進行的實驗對比如圖8所示，其中，設置自模擬度量間隔的情節數=30。從圖8可以看出，沒有引入自模擬度量方法的E-DDPG算法在470個情節算法才收斂，引入自模擬度量方法的E-DDPG算法在120個情節算法就收斂了，而DDPG算法在780個情節才收斂。這是因為自模擬度量方法使訓練的樣本具有更好的多樣性，提高了訓練的效率，從而加快了訓練的速度。實驗表明，自模擬度量方法能夠加快算法的收斂速度。

圖8 MountainCar問題中E-DDPG算法是否引入自模擬度量方法的實驗比較

圖9 MountainCar問題中E-DDPG算法不同TD Error和DDPG算法的實驗比較

圖10 MountainCar問題中E-DDPG算法不同樣本選取比例和DDPG算法的實驗比較

5 結束語

本文針對DDPG算法在大規模狀態動作空間中存在收斂速度較慢的問題，提出了E-DDPG算法。該算法在深度確定策略梯度算法的基礎上，重新構建兩個新的樣本池——多樣性樣本池和高誤差樣本池。其中，多樣性樣本池主要利用自模擬度量方法對原始樣本池中的樣本相似性進行度量，選擇低相似性樣本，并在學習過程中持續更新；高誤差樣本池主要通過計算時間差分誤差對所選擇的訓練樣本進行排序，選擇具有高價值的高誤差樣本，以提高后續參數更新的有效性。將算法應用到Pendulum問題，從算法性能角度與DDPG算法進行比較。實驗結果表明，E-DDPG算法比DDPG算法收斂速度更快，同時算法的穩定性也更好。針對TD error閾值和多樣性樣本池與高誤差樣本池訓練樣本比例等參數的人工設置不同，對算法性能的影響分別進行了實驗。實驗結果表明，雖然TD error閾值選取和樣本選取比例不同會導致E-DDPG算法性能不一樣，但是與DDPG算法相比還是有較好的效果。

本文主要以Pendulum問題和MountainCar問題作為實驗平臺驗證算法性能，從實驗結果可以看出，算法具有較好的收斂性和穩定性。但是E-DDPG算法中TD error的選取和樣本比例的選取都是人工設置的，且不同的設置參數會對算法收斂性和穩定性產生不同的影響。因此，接下來的工作是進一步分析如何設置TD error和樣本選取比例，讓算法可以獲得最好的收斂性和穩定性，使算法具有更強的通用性。

[1] SUTTON R S, BARTO G A. Reinforcement learning: an introduction[M]. Cambridge: MIT press, 1998.

[2] 朱斐, 劉全, 傅啟明, 等. 一種用于連續動作空間的最小二乘行動者-評論家方法[J]. 計算機研究與發展, 2014, 51(3): 548-558. ZHU F, LIU Q, FU Q M. A least square actor-critic approach for continuous action space[J]. Journal of Computer Research and Development, 2014, 51(3): 548-558.

[3] 孫志軍, 薛磊, 許陽明, 等. 深度學習研究綜述[J]. 計算機應用研究, 2012, 29(8): 2806-2810. SUN Z J, XUE L, XU Y M, et al. Overview of deep learning[J]. Application Research of Computers, 2012, 29(8): 2806-2810.

[4] LECUN Y, BENGIO Y, HINTON G. Deep learning[J]. Nature, 2015, 521(7553): 436-444.

[5] HINTON G E, OSINDERO S, TEH Y W. A fast learning algorithm for deep belief nets[J]. Neural Computation, 2006, 18(7): 1527-1554.

[6] SILVER D, HUANG A, MADDISON C J, et al. Mastering the game of Go with deep neural networks and tree search[J]. Nature, 2016, 529(7587): 484-489.

[7] SILVER D, SCHRITTWIESER J, SIMONYAN K, et al. Mastering the game of go without human knowledge[J]. Nature, 2017, 550(7676): 354-359.

[8] MNIH V, KAVUKCUOFLU K, SILVER D, et al. Playing atari with deep reinforcement learning[C]//Workshops at the 26th Neural Information Processing Systems. 2013.

[9] MNIH V, KAVUKCUOFLU K, SILVER D, et al. Human-level control through deep reinforcement learning[J]. Nature, 2015, 518(7540): 529-533.

[10] WATKINS C J C H. Learning from delayed rewards[J]. Robotics and Autonomous Systems, 1989, 15(4): 233-235.

[11] VAN H V, GUEZ A, SILVER D. Deep reinforcement learning with double q-learning[C]//The AAAI Conference on Artificial Intelligence. 2016.

[12] HASSELT H V. Double Q-learning[C]//The Advances in Neural Information Processing Systems. 2010.

[13] SCHAUL T, QUAN J, ANTONOGLOU I, et al. Prioritized experience replay[C]//The 4th International Conference on Learning Representations. 2016: 322-355.

[14] SUTTON R S, MCALLESTER D, SINGH S, et al. Policy gradient methods for reinforcement learning with function approximation[J]. Advances in Neural Information Processing Systems, 2000, 12: 1057-1063.

[15] LILLICRAP T P, HUNT J J, PRITZEL A, et al. Continuous control with deep reinforcement learning[C]//The 4th International Conference on Learning Representations. 2015.

[16] SILVER D, LEVER G, HEESS N, et al. Deterministic policy gradient algorithms[C]//The International Conference on Machine Learning. 2014.

[17] GIVAN R, DEAN T, GREIG M. Equivalence notions and model minimization in Markov decision processes[J]. Artificial Intelligence, 2003, 147(1-2): 163-223.

[18] FERNS N, PANANGADEN P, PRECUP D. Metrics for finite markov decision processes[C]//The 20th Conference on Uncertainty in Artificial Intelligence. 2004.

Enhanced deep deterministic policy gradient algorithm

CHEN Jianping1,2,3,4, HE Chao1,2,3, LIU Quan5, WU Hongjie1,2,3,4, HU Fuyuan1,2,3,4, FU Qiming1,2,3,4

1. Institute of Electronics and Information Engineering, Suzhou University of Science and Technology, Suzhou 215009, China 2. Jiangsu Province Key Laboratory of Intelligent Building Energy Efficiency, Suzhou University of Science and Technology, Suzhou 215009, China 3. Suzhou Key Laboratory of Mobile Networking and Applied Technologies, Suzhou University of Science and Technology, Suzhou 215009, China 4. Virtual Reality Key Laboratory of Intelligent Interaction and Application Technology of Suzhou, Suzhou University of Science and Technology, Suzhou 215009, China 5. School of Computer Science and Technology, Soochow University, Suzhou 215006, China

With the problem of slow convergence for deep deterministic policy gradient algorithm, an enhanced deep deterministic policy gradient algorithm was proposed. Based on the deep deterministic policy gradient algorithm, two sample pools were constructed, and the time difference error was introduced. The priority samples were added when the experience was played back. When the samples were trained, the samples were selected from two sample pools respectively. At the same time, the bisimulation metric was introduced to ensure the diversity of the selected samples and improve the convergence rate of the algorithm. The E-DDPG algorithm was used to pendulum problem. The experimental results show that the E-DDPG algorithm can effectively improve the convergence performance of the continuous action space problems and have better stability.

deep reinforcement learning, sample ranking, bisimulation metric, temporal difference error

TP391

A

10.11959/j.issn.1000?436x.2018238

陳建平（1963?），男，江蘇南京人，博士，蘇州科技大學教授，主要研究方向為大數據分析與應用、建筑節能、智能信息處理。

何超（1993?），男，江蘇徐州人，蘇州科技大學碩士生，主要研究方向為強化學習、深度學習、建筑節能。

劉全（1969?），男，內蒙古牙克石人，博士，蘇州大學教授、博士生導師，主要研究方向為智能信息處理、自動推理與機器學習。

吳宏杰（1977?），男，江蘇蘇州人，博士，蘇州科技大學副教授，主要研究方向為深度學習、模式識別、生物信息。

胡伏原（1978?），男，湖南岳陽人，博士，蘇州科技大學教授，主要研究方向為模式識別與機器學習。

傅啟明（1985?），男，江蘇淮安人，博士，蘇州科技大學講師，主要研究方向為強化學習、深度學習及建筑節能。

2018?03?22；

2018?08?01

傅啟明，fqm_1@126.com

國家自然科學基金資助項目（No.61502329, No.61772357, No.61750110519, No.61772355, No.61702055, No.61672371, No.61602334, No.61502323）；江蘇省自然科學基金資助項目（No.BK20140283）；江蘇省重點研發計劃基金資助項目（No.BE2017663）；江蘇省高校自然科學研究基金資助項目（No.13KJB520020）；蘇州市應用基礎研究計劃工業部分基金資助項目（No.SYG201422）

The National Natural Science Foundation of China (No.61502329, No.61772357, No.61750110519, No.61772355, No.61702055, No.61672371, No.61602334, No.61502323), The Natural Science Foundation of Jiangsu Province (No.BK20140283), The Key Research and Development Program of Jiangsu Province (No.BE2017663), High School Natural Foundation of Jiangsu Province (No.13KJB520020), Suzhou Industrial Application of Basic Research Program Part (No.SYG201422)