最近在整理電腦文件，看到一份當(dāng)初給同事講解TRPO算法原理時寫的PPT，感覺要比先前那篇寫的更加清楚明白，加之這幾天剛好在復(fù)習(xí)RL相關(guān)的知識，然后便將PPT的內(nèi)容加上我比當(dāng)時更加深入的理解，整理成了這篇文章，分享給大家。

策略梯度方法及其缺點

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

agent觀察到一個環(huán)境狀態(tài) $s_t$
可以計算 $J(\theta)$ 關(guān)于策略函數(shù)參數(shù) $\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))$
當(dāng)然，上式子中的 $Q_\pi(s_t,a)$ 和 $V_\pi(s_t)$ 是未知的，我們可以使用一個參數(shù)為 $w$ 的神經(jīng)網(wǎng)絡(luò) $v_w(s)$ 來近似 $V_\pi(s)$ ，而 $Q_\pi(s,a)$ 我們可以使用走完一整個episode后的真實回報 $G_t$ ，或者使用 $r_t + v_w(s_{t+1})$ 來近似，這樣我們就得到了隨機梯度 $g(\theta)$
在通過梯度上升最大化 $J(\theta)$ 的參數(shù) $\theta$ , 其中 $\alpha$ 為學(xué)習(xí)率
$\theta \leftarrow \theta + \alpha g(\theta)$
這種方法的缺點也是顯而易見的，因為強化學(xué)習(xí)環(huán)境的變化往往非常大，也導(dǎo)致Value的方差比普通的深度學(xué)習(xí)數(shù)據(jù)要大的多，很難選擇到一個合適的學(xué)習(xí)率 $\alpha$ 可以保障更新參數(shù)之后的價值比現(xiàn)在的好，一旦選擇了這個更不好的策略進行采樣學(xué)習(xí)，再次更新的參數(shù)會更差，因此很容易導(dǎo)致越學(xué)越差，一直無法收斂。

價值崩潰

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

Trust Region Policy Optimization

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

我們用 $\pi_\theta$ 來表示參數(shù)為 $\theta$ 的策略函數(shù)，那么TRPO的參數(shù)更新方式可以表示為：
$\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)$ 是原始策略梯度最大化目標(biāo) $J(\theta)$ 在 $\overline{D}_{KL}(\theta || \theta_k) \leq\delta$ 限制范圍內(nèi)的近似:
$\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)勢函數(shù)，表示選擇動作 $a$ 所帶來的優(yōu)勢，直觀上看，如果 $A< 0$ 說明動作 $a$ 不好，應(yīng)該降低 $a$ 的概率，于是應(yīng)該減小動作 $a$ 的概率，那么 $\frac{\pi_\theta(a|s)}{\pi_{\theta_k}(a|s)}$ 應(yīng)該小于1，越接近0越好，正好符合 $\mathcal{L}{(\theta_k , \theta)}$ 的最大化，反之亦成立，因此從直觀上看，這個替代的目標(biāo)函數(shù)是符合要求的。但是這個替代函數(shù)到底是怎么來的呢？
其實非常簡單，我們只需要對 $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)勢函數(shù)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)化目標(biāo)，但是要怎么來解這個帶約束的優(yōu)化問題呢？其實就是參考了 Trust Region 算法的求解過程，這也是TRPO這個算法名字的由來。

Trust Region

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

第一步，我們定義參數(shù) $\theta_k$ 的鄰域 $\mathcal{N}(\theta_k，\theta)$ , $\theta$ 是該鄰域內(nèi)的點，滿足 $\theta$ 和 $\theta_k$ 比較接近，常見的方式就是保證：

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

找鄰域內(nèi)的相似函數(shù)

第二步，在鄰域 $\mathcal{N}(\theta_k，\theta)$ 內(nèi)求 $\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$

領(lǐng)域內(nèi)求最大值

第三步，重復(fù)上面兩步，直到收斂：

迭代

TRPO的更新過程

顯然TRPO算法的訓(xùn)練過程就是在策略梯度方法的基礎(chǔ)上，套用了Trust Region 。

在鄰域 $\mathcal{N}(\theta_k,~\theta)$ 內(nèi)找到 $J(\theta)$ 的近似函數(shù) $\mathcal{L}(\theta_k,\theta)$
我們使?蒙特卡洛來作為期望的近似，使?當(dāng)前策略 $\pi_{\theta_k}$ 來和環(huán)境交互，除了記錄transition之外，還記錄每一步的 $\pi(s,a)$ ,就可以得到公式中的 $\frac{\pi_\theta(a|s)}{\pi_{\theta_k}(a|s)}$ ,另外用一個神經(jīng)網(wǎng)絡(luò)來近似 $V_\pi$ , 利用TD算法可以求出公式中的Advantage，這樣近似函數(shù)就找到了，另外我們使用 $\pi_\theta$ 和 $\pi_{\theta_k}$ 的平均KL散度來增加這個約束。
但是從理論上來說，上面所說的TRPO更新十分難求，于是需要做進一步的近似。
我們使用泰勒級數(shù)來估計 $\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$
如果我們只使用這個結(jié)果，算法將精確計算自然策略梯度。但是這樣有一個問題，由于泰勒展開式引入了近似誤差，可能會導(dǎo)致不滿足KL散度的約束，或者實際提高了相應(yīng)動作的優(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)$ 是回溯系數(shù)， $j$ 是 $\pi_{\theta_{k+1}}$ 滿足KL散度約束并產(chǎn)生正向替代優(yōu)勢的最小非負整數(shù)。
另外，當(dāng)神經(jīng)網(wǎng)絡(luò)有數(shù)百萬個參數(shù)時，計算和存儲矩陣 $H^{-1}$ 的代價是很大的。TRPO通過使?共軛梯度算法計算 $Hx=g$ 來避免求解 $x=H^{-1}g$ .這樣我們就可以只??個函數(shù)來計算 $Hx$ ,從而避免直接存儲整個矩陣 .(其實這個?法跟梯度下降有點像)。
沿著更新方程迭代直到收斂...

Proximal Policy Optimization

看了上面的更新過程，我們其實就會發(fā)現(xiàn)，當(dāng)我們使用神經(jīng)網(wǎng)絡(luò)來近似策略時，參數(shù)非常多，TRPO的二階解法計算量會非常大，于是就有了后來的PPO算法。它們的動機是完全一樣的，就是為了讓當(dāng)前策略上進行有效更新時不至于導(dǎo)致Value的崩潰。PPO算法可以看作時TRPO的一階近似，它的試用范圍更廣、計算效率更高、更容易實現(xiàn)，并且從OpenAI的經(jīng)驗上來看，至少效果是不比TRPO差的。PPO也成為了SOTA強化學(xué)習(xí)算法中最常用的之一。

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

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

實踐證明，PPO-Clip這種暴力的方式反而更有效，因此現(xiàn)在主流的PPO用的都是PPO-Clip，因此，本文也就只講PPO-Clip的原理和實現(xiàn)。

PPO-Clip的目標(biāo)函數(shù)可以改寫為：
$\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)))$
這個公式非常復(fù)雜，我們將其拆解成兩種情況來看...
當(dāng)優(yōu)勢A大于0：，說明動作a是好的，于是應(yīng)該讓 $\frac{\pi_\theta(a|s)}{\pi_{\theta_k}(a|s)}$ 大于1且范圍內(nèi)越大越好，當(dāng) $\frac{\pi_\theta(a|s)}{\pi_{\theta_k}(a|s)} > 1 + \epsilon$ 時就截取到 $1 + \epsilon$ , 否則取原值 $\frac{\pi_\theta(a|s)}{\pi_{\theta_k}(a|s)}$ .
當(dāng)優(yōu)勢A小于等于0：，說明動作a是不好的，于是應(yīng)該讓 $\frac{\pi_\theta(a|s)}{\pi_{\theta_k}(a|s)}$ < 1且范圍內(nèi)越小越好，當(dāng) $\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īng)該是取max，但是因為A是負的，于是又變成了取min，這樣就剛好對應(yīng)上面的公式。

然后價值網(wǎng)絡(luò)和策略網(wǎng)絡(luò)的設(shè)計方式和普通的actor-critic并沒有區(qū)別，分別用td算法來有優(yōu)化value網(wǎng)絡(luò)，用梯度上升來優(yōu)化policy網(wǎng)絡(luò)訓(xùn)練即可。

GAE

另外值得一提的還有g(shù)eneralized advantage estimator算法，因為我們一般在實現(xiàn)PPO的時候并不會用最原始的Advantage function，而是GAE，GAE實際上就是multi-step td的Advantage的指數(shù)加權(quán)移動平均，正如multi-step的td算法比one-step的會好，gae可以讓優(yōu)勢估計更加平滑和穩(wěn)定，因為GAE的效果更好，因此在后期GAE版本的TRPO和PPO才是標(biāo)準(zhǔn)的實現(xiàn)。

參考Multi-step TD target的思想，我們將 $V$ 作為狀態(tài)價值的近似，折扣系數(shù)為 $\gamma$ ,定義 $\delta_t^V=r_t+ \gamma V(s_{t+1}) - V(s_t)$ , 則n步的Adventage的 $\hat{A}_t^{(n)}$ 估計應(yīng)該是這樣的：
$\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ù)測值的情況下，數(shù)值優(yōu)化算法上有一種很常見的作法，就是取附近值的指數(shù)加權(quán)移動平均，這便是GAE了，我們將加權(quán)系數(shù)設(shè)置為 $\lambda$ :
$\hat{A}_t^{GAE(\gamma, \lambda)} = (1-\lambda)(\hat{A}_t^{(1)}+ \lambda \hat{A}_t^{(2)} + \lambda^2\hat{A}_t^{(3)}+...)$
當(dāng) $\lambda = 0$ 時， $\hat{A}_t = \delta_t$ ，相當(dāng)于one-step的TD。
當(dāng) $\lambda = 1$ 時， $\hat{A}_t = \sum^{\inf}_{l=0}\gamma^l\delta_{t+l}$ ，相當(dāng)于玩完整局菜更新的Reinforce。
這個權(quán)重系數(shù) $\lambda$ 就是用來控制取多少步的，比如 $\lambda =0.5$ , 此時 $\lambda^2 \approx \frac{1}{e} \approx 0.35$ 很小，我們可以認為平均了2步，再設(shè)大一些就會多取幾步。