深入理解TRPO和PPO算法

最近在整理電腦文件劈猪，看到一份當初給同事講解TRPO算法原理時寫的PPT昧甘，感覺要比先前那篇寫的更加清楚明白，加之這幾天剛好在復習RL相關的知識战得，然后便將PPT的內容加上我比當時更加深入的理解充边，整理成了這篇文章，分享給大家常侦。

策略梯度方法及其缺點

相對于Value Based的方法浇冰，基于策略梯度的強化學習方法的很明顯的優(yōu)勢是它可以直接去學習Policy本身，這樣學習速度會更快聋亡，并且更關鍵的是它可以用于連續(xù)動作空間的情況肘习。
它的基本思想是通過最大化狀態(tài)價值來更新策略函數的參數，即最大化目標函數 $J(\theta) = \mathbb{E}_S[V_\pi(s)]$ ,其中 $\theta$ 為策略函數的參數坡倔，具體的優(yōu)化過程如下：

agent觀察到一個環(huán)境狀態(tài) $s_t$
可以計算 $J(\theta)$ 關于策略函數參數 $\theta$ 的梯度 $g(\theta)$
$g(\theta) = \frac{\partial V_\pi(s_t)}{\partial \theta} =\frac{\partial \mathbb{E}_A[\pi_\theta(A|s_t)Q_\pi(s_t,A)] }{\partial \theta} = \mathbb{E}[\frac{\partial log\pi_\theta(A|s_t)}{\partial \theta} Q_\pi(s_t,A)] = \mathbb{E}[\frac{\partial log\pi_\theta(A|s_t)}{\partial \theta} (Q_\pi(s_t,A) - V_\pi(s_t))]$
基于策略 $\pi_\theta$ 隨機采樣一個動作 a,求隨機梯度
$g(\theta) = \frac{\partial log\pi_\theta(a|s)}{\partial \theta} (Q_\pi(s_t,a) - V_\pi(s_t))$
當然漂佩，上式子中的 $Q_\pi(s_t,a)$ 和 $V_\pi(s_t)$ 是未知的脖含，我們可以使用一個參數為 $w$ 的神經網絡 $v_w(s)$ 來近似 $V_\pi(s)$ ，而 $Q_\pi(s,a)$ 我們可以使用走完一整個episode后的真實回報 $G_t$ 投蝉，或者使用 $r_t + v_w(s_{t+1})$ 來近似养葵，這樣我們就得到了隨機梯度 $g(\theta)$
在通過梯度上升最大化 $J(\theta)$ 的參數 $\theta$ , 其中 $\alpha$ 為學習率
$\theta \leftarrow \theta + \alpha g(\theta)$
這種方法的缺點也是顯而易見的，因為強化學習環(huán)境的變化往往非常大瘩缆，也導致Value的方差比普通的深度學習數據要大的多关拒，很難選擇到一個合適的學習率 $\alpha$ 可以保障更新參數之后的價值比現在的好，一旦選擇了這個更不好的策略進行采樣學習咳榜，再次更新的參數會更差夏醉，因此很容易導致越學越差，一直無法收斂涌韩。

價值崩潰

對于怎么選擇這個合適的學習率是一個相當棘手的問題畔柔，然而不愧是Shulman博士，并沒有糾結于表面上的學習率臣樱，而是從問題的本質出發(fā)靶擦，從而另辟蹊徑給出了TRPO的解決方案。（P.S. 這就是馬斯克所謂的第一性原理的實踐案例吧~）

Trust Region Policy Optimization

TRPO算法盡量通過能提高狀態(tài)價值的方式來更新策略雇毫。它通過在新舊策略之間增加約束玄捕，將整個參數空間的變化限制在一個小范圍之內，從而避免了錯誤決策導致Value的崩塌棚放，盡可能的保持快速而單調的提升枚粘。

我們用 $\pi_\theta$ 來表示參數為 $\theta$ 的策略函數，那么TRPO的參數更新方式可以表示為：
$\theta_{k+1} = \argmax_\theta\mathcal{L}(\theta_k ~,\theta) \\ ~~ ~~ ~~ ~~ ~~ ~~~~ ~~ ~~~~ ~~ ~~~ ~~~~ s.t. ~\overline{D}_{KL}(\theta || \theta_k) \leq\delta$
這里的 $\mathcal{L}(\theta_k , \theta)$ 是原始策略梯度最大化目標 $J(\theta)$ 在 $\overline{D}_{KL}(\theta || \theta_k) \leq\delta$ 限制范圍內的近似:
$\mathcal{L}{(\theta_k 飘蚯， \theta)} = \mathbb{E}[\frac{\pi_\theta(a|s)}{\pi_{\theta_k}(a|s)} A_{\pi_{\theta_k}}(s,a)]$
其中 $A_{\pi_{\theta_k}}(s,a)$ 是優(yōu)勢函數馍迄，表示選擇動作 $a$ 所帶來的優(yōu)勢，直觀上看局骤，如果 $A< 0$ 說明動作 $a$ 不好攀圈，應該降低 $a$ 的概率，于是應該減小動作 $a$ 的概率峦甩，那么 $\frac{\pi_\theta(a|s)}{\pi_{\theta_k}(a|s)}$ 應該小于1赘来，越接近0越好，正好符合 $\mathcal{L}{(\theta_k , \theta)}$ 的最大化凯傲，反之亦成立犬辰，因此從直觀上看，這個替代的目標函數是符合要求的泣洞。但是這個替代函數到底是怎么來的呢忧风？
其實非常簡單，我們只需要對 $J(\theta)$ 做一點微小的變換：
$\begin{align} J(\theta) = \mathbb{E}_s[V_\pi(s)] &= \mathbb{E}_s[\mathbb{E}_a[Q_\pi(s,a)]] \\ &= \mathbb{E}_s[ \sum_{a\sim\theta_k}\pi_\theta(a|s)Q_{\pi_{\theta_k}}(s,a)] \\ &= \mathbb{E}_s[ \sum_{a\sim\theta_k} \pi_{\theta_k}(a|s) \frac{\pi_\theta(a|s)}{\pi_{\theta_k}(a|s)}Q_{\pi_{\theta_k}}(s,~a)] \\ &= \mathbb{E}_{s,a}[ \frac{\pi_\theta(a|s)}{\pi_{\theta_k}(a|s)}Q_{\pi_{\theta_k}}(s,a)] \\ 引入優(yōu)勢函數A \\ &= \mathbb{E}_{s,a}[ \frac{\pi_\theta(a|s)}{\pi_{\theta_k}(a|s)}A_{\pi_{\theta_k}}(s,a)] = \mathcal{L}{(\theta_k , \theta)} \end{align}$
雖然推出了優(yōu)化目標球凰，但是要怎么來解這個帶約束的優(yōu)化問題呢狮腿？其實就是參考了 Trust Region 算法的求解過程，這也是TRPO這個算法名字的由來呕诉。

Trust Region

我們先來看一下Trust Region算法是怎么來最大化目標函數 $J(\theta)$ 的缘厢，TRPO用的也是同樣的方法。

第一步甩挫，我們定義參數 $\theta_k$ 的鄰域 $\mathcal{N}(\theta_k贴硫，\theta)$ , $\theta$ 是該鄰域內的點，滿足 $\theta$ 和 $\theta_k$ 比較接近伊者，常見的方式就是保證：

$|| \theta - \theta_k ||_2 < \delta$
$\overline{D}_{KL}(\theta || \theta_k) < \delta$
然后我們在這個鄰域內找到 $J(\theta)$ 的相似函數 $\mathcal{L}(\theta_k , \theta)$

找鄰域內的相似函數

第二步英遭，在鄰域 $\mathcal{N}(\theta_k，\theta)$ 內求 $\mathcal{L}(\theta_k , \theta)$ 的最大值：
$\theta_{k+1} = \argmax_\theta\mathcal{L}(\theta_k ~,\theta) \\ ~~ ~~ ~~ ~~ ~~ ~~~ ~ ~~ ~~~~ ~~ ~~ ~~ ~~ ~ ~~ s.t. ~\overline{D}_{KL}(\theta || \theta_k) \leq\delta$

領域內求最大值

第三步亦渗，重復上面兩步挖诸，直到收斂：

迭代

TRPO的更新過程

顯然TRPO算法的訓練過程就是在策略梯度方法的基礎上，套用了Trust Region 法精。

在鄰域 $\mathcal{N}(\theta_k,~\theta)$ 內找到 $J(\theta)$ 的近似函數 $\mathcal{L}(\theta_k,\theta)$
我們使?蒙特卡洛來作為期望的近似多律，使?當前策略 $\pi_{\theta_k}$ 來和環(huán)境交互，除了記錄transition之外搂蜓，還記錄每一步的 $\pi(s,a)$ ,就可以得到公式中的 $\frac{\pi_\theta(a|s)}{\pi_{\theta_k}(a|s)}$ ,另外用一個神經網絡來近似 $V_\pi$ , 利用TD算法可以求出公式中的Advantage狼荞，這樣近似函數就找到了，另外我們使用 $\pi_\theta$ 和 $\pi_{\theta_k}$ 的平均KL散度來增加這個約束帮碰。
但是從理論上來說相味，上面所說的TRPO更新十分難求，于是需要做進一步的近似殉挽。
我們使用泰勒級數來估計 $\mathcal{L}$ 和 $KL$ 散度的均值丰涉，將 $\mathcal{L}$ 展開到一階，KL散度展開到二階:
$\mathcal{L}(\theta_k,\theta) \approx g^T(\theta-\theta_k) \\ \overline{D}_{KL}{(\pi_{\theta_k}, \pi_\theta)} \approx \frac{1}{2} (\theta -\theta_k)^T H(\theta-\theta_k)$
就得到了這樣一個近似的優(yōu)化問題：
$\theta_{k+1} = \argmax_\theta g^T(\theta-\theta_k) \\ ~~ ~~ ~~ ~~ ~~ ~~ ~~ ~~ ~~ ~~ ~~ ~~ ~~ ~~ ~~ ~~ ~~ ~~ s.t. \frac{1}{2} (\theta -\theta_k)^T H(\theta-\theta_k)$
最大化
這個近似問題可以?拉格朗?對偶?法解析求解：
$\theta_{k+1} = \theta_k + \sqrt{\frac{2\delta}{g^TH^{-1}g}}H^{-1}g$
如果我們只使用這個結果此再，算法將精確計算自然策略梯度昔搂。但是這樣有一個問題，由于泰勒展開式引入了近似誤差输拇，可能會導致不滿足KL散度的約束摘符，或者實際提高了相應動作的優(yōu)勢，于是TRPO對這個更新規(guī)則增加了一個修改策吠，稱之為回溯線搜索：
$\theta_{k+1} = \theta_k +\alpha^j \sqrt{\frac{2\delta}{g^TH^{-1}g}}H^{-1}g$
其中 $\alpha \in (0, 1)$ 是回溯系數逛裤， $j$ 是 $\pi_{\theta_{k+1}}$ 滿足KL散度約束并產生正向替代優(yōu)勢的最小非負整數。
另外猴抹，當神經網絡有數百萬個參數時带族，計算和存儲矩陣 $H^{-1}$ 的代價是很大的。TRPO通過使?共軛梯度算法計算 $Hx=g$ 來避免求解 $x=H^{-1}g$ .這樣我們就可以只??個函數來計算 $Hx$ ,從而避免直接存儲整個矩陣 .(其實這個?法跟梯度下降有點像)蟀给。
沿著更新方程迭代直到收斂...

Proximal Policy Optimization

看了上面的更新過程蝙砌，我們其實就會發(fā)現阳堕，當我們使用神經網絡來近似策略時，參數非常多择克，TRPO的二階解法計算量會非常大恬总，于是就有了后來的PPO算法。它們的動機是完全一樣的肚邢，就是為了讓當前策略上進行有效更新時不至于導致Value的崩潰壹堰。PPO算法可以看作時TRPO的一階近似，它的試用范圍更廣骡湖、計算效率更高贱纠、更容易實現，并且從OpenAI的經驗上來看响蕴，至少效果是不比TRPO差的谆焊。PPO也成為了SOTA強化學習算法中最常用的之一。

PPO主要有兩種變體：PPO-Penalty 和 PPO-Clip 换途。

PPO-Penalty修改了KL散度的約束方式懊渡，它不再添加硬約束，而是通過在目標函數中加入KL散度的正則項的方式來處理約束問題军拟。
PPO-Clip 則刪除了約束剃执，直接使用強制剪裁的暴力方式來讓 $\theta$ 的更新保持在一定范圍之內。

實踐證明，PPO-Clip這種暴力的方式反而更有效，因此現在主流的PPO用的都是PPO-Clip始藕，因此俏竞，本文也就只講PPO-Clip的原理和實現寄狼。

PPO-Clip的目標函數可以改寫為：
$\mathcal{L}(s, a,\theta_k, \theta) = min(\frac{\pi_\theta(a|s)}{\pi_{\theta_k}(a|s)} A_{\pi_{\theta_k}}(s,a) , clip( \frac{\pi_\theta(a|s)}{\pi_{\theta_k}(a|s)}, 1-\epsilon, 1+ \epsilon) A_{\pi_{\theta_k}}(s,a)))$
這個公式非常復雜，我們將其拆解成兩種情況來看...
當優(yōu)勢A大于0：，說明動作a是好的，于是應該讓 $\frac{\pi_\theta(a|s)}{\pi_{\theta_k}(a|s)}$ 大于1且范圍內越大越好遣耍，當 $\frac{\pi_\theta(a|s)}{\pi_{\theta_k}(a|s)} > 1 + \epsilon$ 時就截取到 $1 + \epsilon$ , 否則取原值 $\frac{\pi_\theta(a|s)}{\pi_{\theta_k}(a|s)}$ .
當優(yōu)勢A小于等于0：，說明動作a是不好的炮车，于是應該讓 $\frac{\pi_\theta(a|s)}{\pi_{\theta_k}(a|s)}$ < 1且范圍內越小越好舵变，當 $\frac{\pi_\theta(a|s)}{\pi_{\theta_k}(a|s)} < 1 - \epsilon$ ，則截取到 $1 - \epsilon$ 瘦穆，否則 $\frac{\pi_\theta(a|s)}{\pi_{\theta_k}(a|s)}$ 纪隙，此時應該是取max，但是因為A是負的扛或，于是又變成了取min绵咱，這樣就剛好對應上面的公式。

然后價值網絡和策略網絡的設計方式和普通的actor-critic并沒有區(qū)別熙兔，分別用td算法來有優(yōu)化value網絡悲伶，用梯度上升來優(yōu)化policy網絡訓練即可艾恼。

GAE

另外值得一提的還有generalized advantage estimator算法，因為我們一般在實現PPO的時候并不會用最原始的Advantage function拢切，而是GAE蒂萎，GAE實際上就是multi-step td的Advantage的指數加權移動平均秆吵，正如multi-step的td算法比one-step的會好淮椰，gae可以讓優(yōu)勢估計更加平滑和穩(wěn)定，因為GAE的效果更好纳寂，因此在后期GAE版本的TRPO和PPO才是標準的實現主穗。

參考Multi-step TD target的思想，我們將 $V$ 作為狀態(tài)價值的近似毙芜，折扣系數為 $\gamma$ ,定義 $\delta_t^V=r_t+ \gamma V(s_{t+1}) - V(s_t)$ , 則n步的Adventage的 $\hat{A}_t^{(n)}$ 估計應該是這樣的：
$\begin{align} \hat{A}_t^{(1)} &= \delta_t^V = -V(s_t)+r_t+\gamma V(s_{t+1}) \\ \hat{A}_t^{(2)} &= \delta_t^V + \gamma \delta_{t+1}^V = -V(s_t)+r_t+ \gamma r_{t+1} +\gamma^2 V(s_{t+2}) \\ \hat{A}_t^{(3)} &= \delta_t^V + \gamma \delta_{t+1}^V + \gamma^2 \delta_{t+2}^V = -V(s_t)+r_t+ \gamma r_{t+1} + \gamma^2 r_{t+2} +\gamma^3 V(s_{t+3}) \\ ... \\ \hat{A}_t^{(k)} &= \sum^{k-1}_{l=0}\gamma^l\delta_{t+l}^V = -V(s_t)+r_t+\gamma r_{t+1} + ... + \gamma^{k-1}r_{t+k-1}+ \gamma^kV(s_{t+k})\\ \end{align}$
但是我們到底選幾步的優(yōu)勢是最好的呢忽媒？又是否存在這樣一個最好的n呢？
在不知道選哪個預測值的情況下腋粥，數值優(yōu)化算法上有一種很常見的作法晦雨，就是取附近值的指數加權移動平均，這便是GAE了隘冲，我們將加權系數設置為 $\lambda$ :
$\hat{A}_t^{GAE(\gamma, \lambda)} = (1-\lambda)(\hat{A}_t^{(1)}+ \lambda \hat{A}_t^{(2)} + \lambda^2\hat{A}_t^{(3)}+...)$
當 $\lambda = 0$ 時闹瞧， $\hat{A}_t = \delta_t$ ，相當于one-step的TD展辞。
當 $\lambda = 1$ 時奥邮， $\hat{A}_t = \sum^{\inf}_{l=0}\gamma^l\delta_{t+l}$ ，相當于玩完整局菜更新的Reinforce罗珍。
這個權重系數 $\lambda$ 就是用來控制取多少步的洽腺，比如 $\lambda =0.5$ , 此時 $\lambda^2 \approx \frac{1}{e} \approx 0.35$ 很小，我們可以認為平均了2步覆旱，再設大一些就會多取幾步蘸朋。

總結

PPO通過on-policy的方式訓練隨機策略，這意味它通過最新版本的隨機策略來對環(huán)境進行采樣扣唱，但是實際分布式采樣和訓練的時候往往有策略更新的延遲的情況藕坯，因此也可以算作是有點off-policy的...

基礎實現的代碼可以參考我教程中的實現tutorials/ppo ，不過請注意画舌，這個單worker的版本僅用于學習基本的原理堕担，實際并沒有什么用，真正有用的請參考進階版中的多worker實現曲聂。

參考

Trust Region Policy Optimization, Schulman et al. 2015
Approximately Optimal Approximate Reinforcement Learning, Kakade and Langford 2002
Proximal Policy Optimization Algorithms, Schulman et al. 2017
High Dimensional Continuous Control Using Generalized Advantage Estimation, Schulman et al. 2016
Emergence of Locomotion Behaviours in Rich Environments, Heess et al. 2017
Trust Region Policy Optimization, spinningup.openai

最后編輯于：2022.03.01 22:55:06

?著作權歸作者所有,轉載或內容合作請聯(lián)系作者

人面猴
序言：七十年代末霹购，一起剝皮案震驚了整個濱河市，隨后出現的幾起案子朋腋，更是在濱河造成了極大的恐慌齐疙，老刑警劉巖膜楷，帶你破解...
沈念sama閱讀 206,126評論 6贊 481
死咒
序言：濱河連續(xù)發(fā)生了三起死亡事件，死亡現場離奇詭異贞奋，居然都是意外死亡赌厅，警方通過查閱死者的電腦和手機，發(fā)現死者居然都...
沈念sama閱讀 88,254評論 2贊 382
救了他兩次的神仙讓他今天三更去死
文/潘曉璐我一進店門轿塔，熙熙樓的掌柜王于貴愁眉苦臉地迎上來特愿，“玉大人，你說我怎么就攤上這事勾缭∽嵴希” “怎么了？”我有些...
開封第一講書人閱讀 152,445評論 0贊 341
道士緝兇錄：失蹤的賣姜人
文/不壞的土叔我叫張陵俩由，是天一觀的道長毒嫡。經常有香客問我，道長幻梯，這世上最難降的妖魔是什么兜畸？我笑而不...
開封第一講書人閱讀 55,185評論 1贊 278
?港島之戀（遺憾婚禮）
正文為了忘掉前任，我火速辦了婚禮碘梢，結果婚禮上咬摇，老公的妹妹穿的比我還像新娘。我一直安慰自己痘系，他們只是感情好菲嘴，可當我...
茶點故事閱讀 64,178評論 5贊 371
惡毒庶女頂嫁案：這布局不是一般人想出來的
文/花漫我一把揭開白布。她就那樣靜靜地躺著汰翠，像睡著了一般龄坪。火紅的嫁衣襯著肌膚如雪。梳的紋絲不亂的頭發(fā)上复唤，一...
開封第一講書人閱讀 48,970評論 1贊 284
城市分裂傳說
那天健田，我揣著相機與錄音，去河邊找鬼佛纫。笑死妓局，一個胖子當著我的面吹牛，可吹牛的內容都是我干的呈宇。我是一名探鬼主播好爬，決...
沈念sama閱讀 38,276評論 3贊 399
雙鴛鴦連環(huán)套：你想象不到人心有多黑
文/蒼蘭香墨我猛地睜開眼，長吁一口氣：“原來是場噩夢啊……” “哼甥啄！你這毒婦竟也來了存炮？” 一聲冷哼從身側響起，我...
開封第一講書人閱讀 36,927評論 0贊 259
萬榮殺人案實錄
序言：老撾萬榮一對情侶失蹤，失蹤者是張志新（化名）和其女友劉穎穆桂，沒想到半個月后宫盔，有當地人在樹林里發(fā)現了一具尸體，經...
沈念sama閱讀 43,400評論 1贊 300
?護林員之死
正文獨居荒郊野嶺守林人離奇死亡享完，尸身上長有42處帶血的膿包…… 初始之章·張勛以下內容為張勛視角年9月15日...
茶點故事閱讀 35,883評論 2贊 323
?白月光啟示錄
正文我和宋清朗相戀三年灼芭，在試婚紗的時候發(fā)現自己被綠了。大學時的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片般又。...
茶點故事閱讀 37,997評論 1贊 333
活死人
序言：一個原本活蹦亂跳的男人離奇死亡彼绷，死狀恐怖，靈堂內的尸體忽然破棺而出倒源，到底是詐尸還是另有隱情苛预，我是刑警寧澤，帶...
沈念sama閱讀 33,646評論 4贊 322
?日本核電站爆炸內幕
正文年R本政府宣布笋熬，位于F島的核電站，受9級特大地震影響腻菇，放射性物質發(fā)生泄漏胳螟。R本人自食惡果不足惜，卻給世界環(huán)境...
茶點故事閱讀 39,213評論 3贊 307
男人毒藥：我在死后第九天來索命
文/蒙蒙一筹吐、第九天我趴在偏房一處隱蔽的房頂上張望糖耸。院中可真熱鬧，春花似錦丘薛、人聲如沸嘉竟。這莊子的主人今日做“春日...
開封第一講書人閱讀 30,204評論 0贊 19
一樁弒父案洋侨，背后竟有這般陰謀
文/蒼蘭香墨我抬頭看了看天上的太陽舍扰。三九已至，卻和暖如春希坚，著一層夾襖步出監(jiān)牢的瞬間边苹，已是汗流浹背。一陣腳步聲響...
開封第一講書人閱讀 31,423評論 1贊 260
情欲美人皮
我被黑心中介騙來泰國打工裁僧，沒想到剛下飛機就差點兒被人妖公主榨干…… 1. 我叫王不留个束，地道東北人。一個月前我還...
沈念sama閱讀 45,423評論 2贊 352
代替公主和親
正文我出身青樓聊疲，卻偏偏與公主長得像茬底，于是被迫代替她去往敵國和親。傳聞我的和親對象是個殘疾皇子获洲，可洞房花燭夜當晚...
茶點故事閱讀 42,722評論 2贊 345