?PaperWeekly 原創 ·?作者｜李文浩

學校｜華東師范大學博士生

研究方向｜強化學習

本文將介紹 GPS 方法，GPS 方法是由強化學習大牛 Sergey Levine（在最近的 ICLR 2019 發表了 13 篇論文）于 2013 年提出的，目前被作為基礎算法廣泛應用于各種強化學習任務中。

其出發點在于純粹的策略梯度方法在更新參數時不會用到環境模型因而屬于一種無模型強化學習算法，所謂成也蕭何敗也蕭何，雖然這使得策略梯度方法通用性很好，但是由于沒有利用到任何環境的內在屬性，使得其訓練只能完全依靠試錯，效率較低。

基于模型的路徑優化算法（例如 iLQR）方法，能夠充分利用環境模型，從而在利用較少訓練樣本的情況下即可使得算法收斂到局部最優解。

但是路徑優化算法是一個開環方法，在隨機環境下效果較差，雖然能夠通過使用 MPC 方法（基本思想是每次只執行路徑優化算法輸出的第一個時間步的動作）來增加算法的穩定性，但是執行時耗時較長無法適用于實時任務。但是策略梯度方法是一個閉環方法，因而其對于隨即環境的適應能力以及執行耗時上都能達到很好的效果。

因而一個直觀的想法是，能不能將兩者結合起來，用路徑優化算法的輸出結果來指導策略梯度方法的訓練過程，從而提升策略梯度方法的效率呢？GPS 方法正是基于這種思想提出的。

本文主要對早期 GPS 的三篇論文進行了總結（還包括了一些其他論文的相關結論），具體請參閱文末的參考文獻。

文章的結構如下：第一部分將會對最原始的 GPS 方法進行介紹，第二部分將會介紹一個改進版本。注意，這兩種版本的 GPS 算法都必須事先已知環境模型。第三部分將介紹一個在未知環境模型（需要在算法訓練的過程中對環境模型進行局部估計）的情況下也能夠使用的 GPS 算法。

以上三種 GPS 算法均屬于基于模型的強化學習算法（以后我將專門寫一篇文章來介紹基于模型的強化學習算法）。為了方便起見，我將最原始的GPS算法記為 GPS-V1 (ICML 2013) [2]，改進版記為 GPS-V2 (ICML 2014) [3]，最后一個版本記為 GPS-V3 (NIPS 2014) [4]。

GPS-V1

原始版本的 GPS 算法基本思想是首先使用路徑優化算法產生一些訓練數據并加入訓練集中用以指導后續策略梯度方法的訓練。但是策略梯度方法是在線策略算法，只能使用當前策略采樣得到的數據來估計梯度從而更新參數。

為了能夠使用其他策略采樣的數據，這里必須要使用一種技術：重要性采樣。在這里我首先跑一下題來介紹一下重要性采樣。

1.1 重要性采樣

對于一個函數 以及一個概率分布 ，我們想要計算如下統計量：

我們知道，一般估計一個期望值的方法是從變量從屬的概率分布中進行采樣，然后計算均值。但是實際上概率分布 可能非常復雜，我們沒有辦法從其中進行采樣。重要性采樣方法通過從另外一個較為簡單的分布 中采樣出的樣本對以上期望值進行估計：

1.2 基于重要性采樣的策略梯度方法

讓我們回到正題，利用這種方法就可以在估計當前正在學習的策略的梯度時采用其他策略采樣出的樣本：

其中 。從理論上來說 才是期望的無偏估計，這里為了減小訓練時的方差采用了這個特殊值。

但是我們是在其他策略采樣出的樣本分布的基礎上進行新策略的搜索，一旦新策略的樣本分布與采樣樣本分布相距較遠時，無法保證估計梯度的準確性。前面有工作是通過計算重要性權重的方差來判斷新策略的準確性的 [6]，但是對于很長的路徑，重要性權重在大部分地方都為0，方差也很小，但是并不能說明什么問題。

V1 版本的 GPS 算法通過在優化目標上額外加入重要性權重的對數值的方式，來“軟最大化”重要性權重值，畢竟重要性權重越大，代表新策略分布與采樣分布更為接近（但其實在采樣分布概率較小的地方新策略分配一個較大的概率也會使得這個值比較大，所以感覺這種方法還是有很大缺陷的）：

1.3 指導樣本的生成

GPS 系列算法希望使用路徑優化算法生成的指導樣本來引導策略梯度算法往高回報的區域搜索（而非暴力試錯）。在之前的文章中我們講過 iLQR 算法，但是只展開講了確定性情況下的相關知識。

而策略梯度算法的應用場景大部分都是非確定性場景，即使是確定性場景，也會因為噪聲的存在使其實際上同樣是非確定性的。因而，下面我們主要關注非確定性場景下的指導樣本生成。

在非確定性條件下，指導樣本將服從某個概率分布，我們希望這個概率分布滿足以下兩個性質：

各區域的概率密度不要過大（否則會使得重要性權重較小，使得指導樣本對于梯度的貢獻很小）

該分布要盡可能覆蓋高回報區域

GPS-V1 的作者發現，如果指導樣本的分布 是分布 的 I-投影，即最小化如下 KL 散度：

得到的分布 即可滿足以上兩個性質。具體來說，上式右邊第一部分保證了性質 2，右邊第二部分保證了性質 1。那么剩余的問題是分布 的具體形式是什么呢？

GPS-V1 假設分布 是一個高斯分布，這是一個很自然的也是最容易想到的假設。而且如果我們希望能夠用只能解決非隨機環境的路徑優化算法例如 iLQR 來解決隨即環境下的規劃問題的話，只能假設 為高斯分布。

為了能夠直接使用類似 iLQR 算法的路徑優化算法，我們這里再引入另外一個概念或者一個框架，叫做線性可解馬爾科夫決策過程（LMDP）[5]。該框架的核心思想在于，摒棄動作（action）的概念。

智能體在不斷優化其策略的過程中，會通過動作來改變其自身的狀態轉移概率（即在一個狀態下轉移到下一個狀態的概率，策略在不斷優化，那么每個狀態下采取的動作也會變化，因而狀態轉移概率也會發生變化）。那么為何不放棄這一間接的做法，將策略直接定義為狀態轉移概率呢？即:

這就是 LMDP 的核心思想（這部分牽涉的知識較廣，我同樣會之后單獨寫一篇文章來詳細介紹）。在 LMDP 的框架下，其回報函數變成如下形式：

其中 代表學習到的策略（即學習到的狀態轉移概率）， 代表智能體在沒有任何算法控制的情況下的狀態轉移概率。當 表示一個均勻分布時，上式可轉化為：

因而求解一個 LMDP 得到的指導樣本的概率分布是滿足前面提到的兩個性質的。另外，可以證明，當狀態轉移是線性以及回報函數是二次函數的情況下，最優策略可以直接通過 iLQR 算法求解并且求解出的最優策略服從以下高斯分布：

代表確定環境下運用 iLQR 算法得出的最優策略， 代表確定環境下運行 iLQR 算法中的參數，具體參見 iLQR 算法。值得注意的是，由于 LMDP 并沒有動作這一概念，之所以可以得出以上結論，是采用 LMDP 估計 MDP 得出的結論，具體細節我會單獨寫一篇文章細講。

這里得出的結論是什么意思呢？其實就是說在運行 iLQR 算法時，將前向循環中計算最優動作的過程轉化為從以上高斯分布中采樣，然后將優化目標從僅僅最小化（或最大化）損失函數（或回報函數）轉變為同時最大化最優策略的熵即可即可。這樣導出的指導樣本就滿足我們的要求。

還有一個問題是 只有在狀態轉移是線性的情況下才是一個高斯分布，在狀態轉移是非線性的情況下， 是指導樣本分布的一個局部的高斯估計。

由于 GPS 算法需要通過指導樣本來將策略搜索的方向引導向高回報區域（這個高回報區域就是采樣出指導樣本的高斯分布的均值區域），但是這個分布只在指導樣本附近是準確的，離得比較遠就會出現較大誤差，但是策略搜索的區域是任意的，就會出現梯度估計不準確的現象。

以上問題其實已經緩解了，前面提到的改進版的梯度公式中的正則項保證了策略搜索的區域會靠近指導樣本的區域：

1.4 適應性指導樣本分布

我們的策略是用某個特定的函數來進行估計的，而函數的表示能力是有限的（即使是神經網絡，不同網絡層數以及神經元個數都會對網絡的表示能力產生影響。而所謂的通用函數估計器是在神經元個數無限的情況下才成立），那么強行讓學習策略的分布與知道樣本的分布盡可能一致可能會導致一些問題。

考慮下面這種情況：指導樣本是在了解模型的情況下進行決策的，而策略梯度算法是在不知道模型的情況下進行決策的。因而前者除了觀察到的狀態外還利用了環境模型的信息，在相似的觀察下可能會進行差異較大的決策。換句話講，策略函數要嘗試去擬合一些相似輸入產生不同輸出的數據點，這就會使得算法訓練起來十分困難。

目前的算法流程是在算法初始化時就使用 iLQR 算法產生大量的指導樣本，之后就不再產生新的指導樣本了。為了解決以上問題，在策略不斷更新的過程中，重新根據以下這個新的回報函數來運行 iLQR 算法產生新的指導樣本：

通過以上回報函數產生的指導樣本會嘗試產生策略函數能夠產生的樣本分布。

1.5 算法框架

GPS-V1 的整體流程如下圖所示：

這里有幾點細節需要說明。

1. 算法第 6 行選取訓練樣本，其實主要包括以下兩種樣本。第一種，全部的指導樣本；第二種，重要性權重較大的新樣本，權重較大代表與指導樣本更為相似。

2. 第 7 行進行參數更新時，是從上一步最優的參數作為初始點進行更新的。但是有時算法會陷入到局部最優解中，使得在該局部最優解下指導樣本的重要性權重較小，那么指導樣本就對梯度的估計無法產生影響，這樣就會使得算法進一步往更差的方向更新。

為了防止以上問題，這一步的參數更新從兩個不同的初始點開始：第一個初始點就是上一步更新的結果；而第二個則是求得一個使得當前采集到的回報較高的樣本重要性權重最大的參數當作初始化參數。

3. 關于第 11-17 行，具體解釋以下為什么要采取這些操作。當新搜索到的策略比原先的策略要好時，適當減小約束項的權重，這樣可以增大下一步的策略搜索范圍，換句話說就是可以步子邁得大一些。

反之，如果新搜索到的策略比上一步的要差，那么可能目前處于一個局部最優解較多的區域內，或者搜索區域過大使得梯度估計得不準確，這時候應該適當縮小搜索范圍，在更接近指導樣本的區域內搜索。再者，如果這樣還是不能搜索到更好的策略，那么可能就是采樣出的訓練樣本不好，這時候可以嘗試重新采樣。

以上就是 GPS-V1 算法的全部內容。其實在理解 GPS-V1 算法之后，后面兩個版本就很簡單了，因此我下面的內容相對也會少很多。

GPS-V2

作者在 GPS-V1 算法里發現了一個問題，其實 V1 算法也嘗試去解決這個問題但是效果不好，這個問題就是 1.4 節中所描述的問題。

基于模型的路徑優化算法產生的指導樣本，不基于模型的策略梯度方法有時候并不能擬合出來，就像在上一節中講到的那樣，策略梯度算法觀察不到一些通過模型才能反應出來的因素。這樣會使得對于復雜問題學習出來的樣本分布并不能與指導樣本分布符合的很好。

GPS-V2 從另外一個角度解決了上述問題，即完全拋棄了策略梯度步驟，直接讓策略通過對指導樣本進行監督學習得出，并且在路徑優化算法更新時考慮到與當前策略的距離并且嘗試使得這個距離盡可能小。通過這樣一種迭代更新的流程來使得兩者最終匹配。

上述思想其實 GPS-V1 部分的 1.4 節已經考慮到了，但是是通過改變回報函數的方式達到的。GPS-V2 通過一種更直接的方式來建模，并拋棄了策略梯度部分，通過更加魯棒的監督學習來學習策略，使得算法更新更為穩定。

具體來說，GPS-V2 求解以下優化問題：

其中第一個和第二個約束在路徑優化算法運行的過程中已經默認保證了，實際我們只需要考慮第三個約束。注意優化目標就是 GPS-V1 中提到的 I-projection，只不過這里沒有展開。我們采用拉格朗日乘子法（或者擴展拉格朗日乘子法）將上述問題轉化為一個無約束優化問題：

而對于上述優化問題，我們可以采用對偶梯度下降法（DGD，或者交替方向乘子法，ADMM）分別更新三部分的參數。而對偶變量通過以下公式更新：

可以看出更新 其實就是在采用路徑優化算法，更新 時就是在做監督學習。最后給出算法流程：

GPS-V3

其實我覺得最實用的還是 V3 版本的 GPS 算法，因為對于大部分現實問題，環境模型對與算法設計者來說都是未知的。但是前兩個版本的 GPS 算法都假設環境模型是已知的（這樣才能運行路徑優化算法）。

GPS-V3 算法嘗試解決事先未知環境模型場景下的相關問題，其實其基本思想也很直接，未知模型那我就估計模型，只不過全局模型肯定是很難估計準確的，而且要采用類似 iLQR 這種路徑優化算法要對模型進行線性近似，因而更加不可能采用全局模型了。

GPS-V3 通過估計局部模型來緩解上述問題，但是采用局部模型又會引入類似 GPS-V1 這樣的問題，在搜索區域距離當前樣本過遠時，算法誤差就會較大，因而 GPS-V3 在 GPS-V2 的基礎上再加了一個約束來解決這個問題。

具體來說，GPS-V1 是解決如下優化問題來產生指導樣本的：

然后我們先轉回到最原始 iLQR 算法的優化目標，不過因為這個時候我們是用估計的局部模型來運行該算法的，我們加上如下KL散度的約束來使得搜索范圍不會離當前樣本太遠：

接下來同樣采用拉格朗日乘子法（或者擴展拉格朗日乘子法）將其轉變為無約束問題：

將上式中的 KL 散度展開：

和 GPS-V1 的優化問題對比，我們可以發現一個優秀的巧合，我們只需要對上式兩邊除以 ，并將回報函數轉變一下：

就可以直接采用 GPS-V1 一樣的方法產生指導樣本。再將 GPS-V2 算法引入進來：

對于上式同樣采用 GPS-V2 一樣的 DGD 方法（或者 ADMM 算法）求解即可。具體流程如下：

這里需要再提一點，關于估計局部模型采用的方法。由于局部模型是一個高斯分布，我們其實只要去估計其均值即可（方差設定為 ）。而均值又是個線性函數，其實只要估計兩個梯度即可：

因而可以用簡單的線性回歸方法。當然，對于較復雜的問題，一般會采用貝葉斯線性回歸，選用高斯過程、深度網絡或者高斯混合模型作為貝葉斯先驗（這部分有機會我也會展開講一講）。

總結

最后，我引用 [1] 中的一段文字來總結 GPS 算法的核心思想：

Since each trajectory-centric teacher only needs to solve the task from a single initial state, it is faced with a much easier problem. The final policy is trained with supervised learning, which allows us to use a nonlinear, high-dimensional representation for this final policy, such as a multilayer neural network, in order to learn complex behaviors with good generalization.

A key component in guided policy search is adaptation between the trajectories produced by the teacher and the final policy. This adaptation ensures that, at convergence, the teacher does not take actions that the final policy cannot reproduce.

This is realized by an alternating optimization procedure, which iteratively optimizes the policy to match each teacher, while the teachers adapt to gradually match the behavior of the final policy.

參考文獻

[1] Zhang, Marvin, et al. "Learning deep neural network policies with continuous memory states." 2016 IEEE International Conference on Robotics and Automation (ICRA). IEEE, 2016.

[2] Levine, Sergey, and Vladlen Koltun. "Guided policy search." International Conference on Machine Learning. 2013.

[3] Levine, Sergey, and Vladlen Koltun. "Learning complex neural network policies with trajectory optimization." International Conference on Machine Learning. 2014.

[4] Levine, Sergey, and Pieter Abbeel. "Learning neural network policies with guided policy search under unknown dynamics." Advances in Neural Information Processing Systems. 2014.

[5] Dvijotham, Krishnamurthy, and Emanuel Todorov. "Inverse optimal control with linearly-solvable MDPs." Proceedings of the 27th International Conference on Machine Learning (ICML-10). 2010.

[6] Jie, Tang, and Pieter Abbeel. "On a connection between importance sampling and the likelihood ratio policy gradient." Advances in Neural Information Processing Systems. 2010.

????

現在，在「知乎」也能找到我們了

進入知乎首頁搜索「PaperWeekly」

點擊「關注」訂閱我們的專欄吧

關于PaperWeekly

PaperWeekly 是一個推薦、解讀、討論、報道人工智能前沿論文成果的學術平臺。如果你研究或從事 AI 領域，歡迎在公眾號后臺點擊「交流群」，小助手將把你帶入 PaperWeekly 的交流群里。

總結

以上是生活随笔為你收集整理的漫谈强化学习中的引导搜索策略的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。