CS 294: Deep Reinforcement Learning（11）

01-24

Berkeley深度強化學習的中文筆記（10）：Advanced Policy Gradient：TRPO, PPO

這節也會討論與第六節：策略梯度（Policy Gradient）相似的想法，但會用不同的推導思路，來推導出更加efficient，表現穩定提升的演算法：NPG，TRPO以及PPO。

作為最後一節筆記，在最後會總結一下之前學過的4種RL思想。

損失函數和Improvement Theory：

RL的目標是最大化策略得到的獎勵總和，即策略的期望return（帶有discount $gamma$ ）：

常用的Monte Carlo思想和Policy Gradient思想是：根據當前的策略 $pi_{old}$ 進行sample，根據sample到的路徑，通過優化某一目標函數，來提升策略，即提升 $eta(pi)$ 。（在之前的Policy Gradient演算法中，以 $eta(pi)$ 為目標，直接計算其梯度，採用梯度下降法）

首先我們可以證明一個有用的等式：

利用 $A^{pi_{old}}(s,a)=E_{s$ 即可證明。

如果令 $ho_{pi}(s)=(P(s_0=s)+gamma P(s_1=s)+…)$ ，可得到更簡便的表達：

$qquadlarge eta(pi)=eta(pi_{old})+E_{s sim pi,asim pi}[A^{pi_{old}}]$

現在要利用這個等式來找到一個目標函數，作為優化目標，能夠通過 $pi_{old}$ 進行sample來提升策略（其實就是採用重要性採樣importance sampling，off-policy RL中常用）：

$qquadlarge eta(pi)=eta(pi_{old})+E_{s sim pi,asim pi_{old}}[frac{pi(a|s)}{pi_{old}(a|s)}A^{pi_{old}}]$

但還需要改變s的分布，才能用 $pi_{old}$ 進行sample得到上式的無偏估計。

為此不如直接定義一個代替的目標函數 $L_{pi_{old}}(pi)$ ，來代替 $eta(pi)$ （忽略s的分布改變）：（下式少加了常數 $eta(pi_{old})$ ，但對優化無影響）

這樣的 $L_{pi_{old}}(pi)$ 是實際估計的（用 $pi_{old}$ 進行sample即可），而且可以看到L的性質： $L_{pi_{ heta_{old}}}(pi_{ heta_{old}})=eta(pi_{ heta_{old}})$ ，以及

也就是說在 $pi_{old}$ 局部 $L_{pi_{ heta_{old}}}(pi_{ heta})$ 和 $eta(pi_{ heta})$ 行為是一樣的，但是步長增大的話就會有差別（即兩者的一階泰勒展開一樣，高階就有差別）。之前的Policy Gradient就是對 $L_{pi_{ heta_{old}}}(pi_{ heta})$ 一階的梯度下降，也就是說只能在局部是保持 $eta$ 增長的，步長稍大一些，就不能保證了。

（步長大時，用 $L_{pi_{ heta_{old}}}(pi_{ heta})$ 代替 $eta(pi_{ heta})$ 變得不準確，這是由忽略s的分布改變導致的）

Improvement Theory：為了解決這個問題，有theory能給出 $L_{pi_{ heta_{old}}}(pi_{ heta})$ 和 $eta(pi_{ heta})$ 差異的界限：

( $epsilon=max A(s,a)$ )這樣給出了 $eta(pi_{ heta})$ 的一個下界，同時可以看到當 $pi$ 取 $pi_{old}$ 時不等式右邊為 $eta(pi_{ heta_{old}})$ ，因此如果不等式右邊能保持增加的話，就能保證 $eta(pi_{ heta})$ 的單調提升。

實際優化：

上述theory已經給出理論保障，只需優化： $large L_{pi_{old}}(pi)-Cmax_sKL[pi_{old}(cdot|s),pi(cdot|s)]$

在實際操作過程中：

用 $pi_{old}$ 進行sample得到的路徑來估計 $L_{pi_{old}}(pi)$ ：

$hat L_{pi_{old}}(pi)=sum_nfrac{pi(a_n|s_n)}{pi_{old}(a_n|s_n)}hat A^{pi_{old}}_n$ 如果只需要計算在 $pi_{old}$ 處的梯度的話，

可以簡單寫成： $Large hat L_{pi_{old}}(pi)=sum_nlogpi(a_n|s_n)hat A_n$

使用平均KL散度更佳： $overline{KL}_{pi_{old}}(pi)= E_{ssimpi_{old}}[KL[pi_{old}(cdot|s),pi(cdot|s)]]$

實際用sample來估計： $sum_nKL[pi_{old}(cdot|s_n),pi(cdot|s_n)]$

對於常數C，如果用理論中的C的話，那麼步長太小，太保守了，常用的處理方法有兩種：

Natural policy gradient and PPO：使用定長或可調節的C
TRPO：將優化問題轉化為在KL限制下的有限制的優化問題

接下來會對上述兩種方法進行深入討論

自然策略梯度 Natural Policy Gradient：

要解決之前的優化問題： $max_{ heta}L_{pi_{ heta_{old}}}(pi_{ heta})-Coverline{KL}_{pi_{ heta_{old}}}(pi_{ heta})$ ，

對 $L_{pi_{ heta_{old}}}$ 在 $pi_{old}$ 處做一階展開，對 $overline{KL}_{pi_{ heta_{old}}}$ 做二階展開（因為 $L_{pi_{ heta_{old}}}$ 的二階導相比 $overline{KL}_{pi_{ heta_{old}}}$ 很小，而 $overline{KL}_{pi_{ heta_{old}}}$ 的一階導為0）：

對於這個二次優化問題，是有唯一的最優點： $heta- heta_{old}=frac{1}{C}F^{-1}g$

出於計算複雜度的考慮，不能直接求Hessian矩陣F的逆。但是如果上過數值代數之類課程的，應該知道很多能解這個線性方程組（二次優化與線性方程組自然等價）的數值方法，其中最為流行的就是共軛梯度法conjugate gradient（CG）了。CG詳細演算法可以在任何一本數值代數或優化演算法上找到，其介於梯度下降和牛頓法之間，不需要直接計算Hessian矩陣，只需要優化函數的一階導信息。

詳細地說，CG演算法能近似解決 $x=A^{-1}b$ （牛頓法結果）：在k步內，CG能在 $b,Ab,A^2b,...,A^{k-1}b$ 張成的子空間中找到 $frac{1}{2}xAx^T-xb$ 在子空間中的最小值。
而且CG演算法不需要實際生成完整的A矩陣，只需要能形成矩陣A與向量v相乘的函數： $v o Av$ 即可。
在這個具體應用中，也就是不需要計算出 $H=F=frac{partial^2}{partial^2 heta}overline{KL}_{pi_{ heta_{old}}}|_{ heta= heta_{old}}$ ，只需要給任意一個向量v（和 $heta$ 維數一樣），能計算 $v o Hv$ 即可
具體實現就是（tensorflow）：分兩次求導：

vector = tf.placeholder([dim_theta]) gradient = tf.grad(kl, theta) gradient_vector_product = tf.sum( gradient * vector ) hessian_vector_product = tf.grad(gradient_vector_product, theta)

其計算複雜度只有一階導的2倍左右，但如果直接計算H，需要d倍複雜度

將上述過程總結可以得到

Natural Policy Gradient演算法：

其中常數C可以設置為常數，或者根據KL調節，而估計Advantage函數 $hat A_n$ ，可以用之前A3C的方法（第六節），也可以用GAE（generalized advantage estimation）（第九節最後）

TRPO：Trust Region Policy Optimization

對於之前的無限制優化問題： $max_{ heta}L_{pi_{ heta_{old}}}(pi_{ heta})-Coverline{KL}_{pi_{ heta_{old}}}(pi_{ heta})$ ，

可以考慮相關的有限制優化問題： $max_{ heta}L_{pi_{ heta_{old}}}(pi_{ heta})$ 服從 $overline{KL}_{pi_{ heta_{old}}}(pi_{ heta})ledelta$ ，

那麼解決有限制優化問題就近似解決了無限制優化問題，（這個也是合理的，因為KL散度是大於0的，那麼最大化上式就需要KL儘可能小（比如小於能容忍的較小的常數 $delta$ ），然後最大化 $L_{pi_{ heta_{old}}}(pi_{ heta})$ ，即轉化為了有限制優化問題）

變為有限制優化問題的好處是：超參數 $delta$ 比C要好確定，實際只需要取一個比較小的常數即可。而且這個有限制優化問題，能採取更大的步長，更快速訓練。

對於上述的有限制優化問題可以用Lagrange Multiplier方法按照以下步驟求解：

1. 對 $L_{pi_{ heta_{old}}}$ 做一階展開，對 $overline{KL}_{pi_{ heta_{old}}}$ 做二階展開：

$egin{equation} max_{ heta}g( heta- heta_{old}), \ subject to frac{1}{2}( heta- heta_{old})^TF( heta- heta_{old})ledelta end{equation}$

2. 做有限制優化問題的Lagrangian函數： $qquad L( heta,lambda)=g( heta- heta_{old})-frac{lambda}{2}(( heta- heta_{old})^TF( heta- heta_{old})-delta)$

3. 用之前說的CG演算法得到二次逼近的最優點： $heta- heta_{old}=frac{1}{lambda}F^{-1}g$

4. 為了滿足限制條件（KKT條件），需要更新方向s步長滿足： $frac{1}{2}s^TFs=delta$

因此對於之前得到的更新方向 $s_{unscaled}=F^{-1}g$ ，需要rescale它的步長：

$qquadlarge s=sqrt{frac{2delta}{s_{unscaled}^TFs_{unscaled}}}s_{unscaled}$

5. 線性搜索：上一步得到了等式約束的更新方向s，對於不等式約束（而且是凸函數），那麼只需要在方向s內進行線性搜索即可：使用步長 $s,s/2,s/4,...$ 直到優化目標 $max_{ heta}L_{pi_{ heta_{old}}}(pi_{ heta})$ 有提升

將上述步驟用演算法表示就是：

TRPO演算法：

更多細節在15年paper《Trust Region Policy Optimization》中。

PPO：「Proximal」 Policy Optimization

在17年的paper：《Proximal Policy Optimization Algorithms》中：

實際上可以對Natural Policy Gradient演算法做點改進和近似，得到更簡單點的演算法：

優化目標還是： $max_{ heta}hat L_{pi_{ heta_{old}}}(pi_{ heta})-eta overline{KL}_{pi_{ heta_{old}}}(pi_{ heta})$ ，

但是只進行梯度下降優化，而非牛頓法或CG的類似二階的方法，即會求解 $hat L_{pi_{ heta_{old}}}(pi_{ heta})-etaoverline{KL}_{pi_{ heta_{old}}}(pi_{ heta})$ 的一階導數

PPO演算法：

與Natural Policy Gradient不同的是其可以根據KL來調節KL散度在Loss中的權重 $eta$ ，而且只需要求一階梯度即可。在實驗中，PPO的表現能和TRPO差不多。（實際上，這種根據KL來調節的思想在homework4中也體現了：根據KL來調節學習率）

有一個小細節：之前說對KL散度在 $heta_{old}$ 處的一階導數為0，而PPO只做一階導數的話，那KL項不就不起作用了？實際上，PPO演算法中在收集到一個batch的data後會對 $hat L_{pi_{ heta_{old}}}(pi_{ heta})-etaoverline{KL}_{pi_{ heta_{old}}}(pi_{ heta})$ 做多步的SGD，而且在這過程中， $heta_{old}$ 保持不變，因此除了第一步的SGD，之後的KL梯度都不為0。

在論文中還提出了另一個Loss function：clipping loss

容易看出這是policy gradient的一個下界，也能一定程度地保證更新後的 $heta$ 與 $heta_{old}$ 相差不大，而且在連續控制實驗中，取得最好效果（ $epsilon=0.2$ ）

實驗結果：

總體來說，TRPO或PPO演算法比A2C演算法在連續控制（較簡單的輸入）上能表現得更好，但是在高維的圖像輸入的Atari Game上，TRPO或PPO演算法並沒有顯示出優勢。

我自己做了一個簡單的試驗：https://github.com/futurebelongtoML/RL_experiment/blob/master/TRPO_cartpole.py（基於homework4）

在完全一樣的設置下，TRPO（黃色）能比A2C（藍色）更快學到成果。

總結：

這一節從等式： $eta(pi)=eta(pi_{old})+E_{s sim pi,asim pi}[A^{pi_{old}}]$ 出發，以policy gradient的思路，想要在原有策略 $pi_{old}$ 基礎上提升策略。為了能用 $pi_{old}$ 進行sample，引入替代目標函數 $L_{pi_{old}}(pi)=E_{s sim pi_{old},asim pi_{old}}[frac{pi(a_n|s_n)}{pi_{old}(a_n|s_n)}hat A^{pi_{old}}_n]$ ，但是 $L_{pi_{ heta_{old}}}$ 只和真正目標 $eta(pi)$ 在局部一致，當步長增大，就無法保證 $L_{pi_{ heta_{old}}}$ 是一個有效目標。

為了解決這個問題，提出了improvement theory： $large eta(pi) ge L_{pi_{old}}(pi)-Cmax_sKL[pi_{old}(cdot|s),pi(cdot|s)]$ ，

有了這個下界之後，就只需要優化不等式右邊就能保證 $eta(pi)$ 的提升。

在實際優化時，可以分為兩種方法：

Natural Policy Gradient：優化 $max_{ heta}L_{pi_{ heta_{old}}}(pi_{ heta})-Coverline{KL}_{pi_{ heta_{old}}}(pi_{ heta})$ ，用對優化目標做二次逼近，得到牛頓法更新步： $heta- heta_{old}=frac{1}{C}F^{-1}g$ ，考慮到計算複雜性，採用近似的二階優化方法：共軛梯度法（CG），而且使用了小trick，不需要直接求出Hessian矩陣，只需要能計算 $v o Hv$ 即可
PPO：「Proximal」 Policy Optimization：優化 $max_{ heta}hat L_{pi_{ heta_{old}}}(pi_{ heta})-Coverline{KL}_{pi_{ heta_{old}}}(pi_{ heta})$ ，只進行一階的SGD，但會根據KL大小來改變KL項權重C。
TRPO：優化 $max_{ heta}L_{pi_{ heta_{old}}}(pi_{ heta})$ 服從 $overline{KL}_{pi_{ heta_{old}}}(pi_{ heta})ledelta$ ，轉化為有限制優化問題，採用Lagrange Multiplier方法，在規劃更新方向 $s_{unscaled}=F^{-1}g$ ，並進行線性搜索。好處是超參數 $delta$ 比C要好確定，且能採用較大步長。

Natural Policy Gradient這類方法比一般的Policy Gradient方法，能夠保證 $eta(pi)$ 單調增長，有更好的收斂性質，因此更加穩定，而且效率更高。

強化學習各種方法總結和一些Open Problem

到目前為止，我們已經學習了很多的強化學習演算法，從第一節的imitation learning到這節的TRPO，這些演算法的總體思路可以分為四種：

模仿學習imitation learning，將監督學習直接應用到RL環境中，根據有指導的事例進行學習，需要大量有標記的樣本。
有模型學習model-based RL，根據收集到的數據建立模型，然後根據model，可以用動態規劃dynamic programming直接求解或指導策略，需要環境模型比較簡單，而且要選好環境模型（NN，GP等），但比較data-efficient。
無模型學習model-free RL中的Q-learning（以及Saras），思路是要學習到正確的值函數，然後根據值函數就能容易確定策略（greedy），由於Q-learning是off-policy的（用來sample的策略與bootstrap的策略可以不同），而且是on-line的（每行動一步都會更新值函數），因此可以用replay memory，大大提升了其效率。
無模型學習model-free RL中的policy gradient，思路是直接學習策略函數，而不依賴值函數（雖然actor-critic會利用值函數），是on-policy和off-line的，gradient estimator的方差比較大，但能與非同步asynchronous處理很好結合來加快速度，能處理連續動作的情況和部分觀測情況，而且有時候策略本身會比環境模型和值函數更為簡單，更容易建模些。同時與Q-learning相比本身帶有exploration，不需要-greedy，因此能夠產生更好的策略。

其中後三個方法能用一個high-level的示意圖表示它們的三個主要過程：

根據當前策略在交互環境中sample路徑 -> 調整環境模型/優化值函數 -> 提升策略，如此循環。

各種主要演算法的效率比較（根據達到穩定的步數），可以從下圖看出：

雖然圖中有些演算法應用在不同任務中，沒有可比性，但是已經能大概說明各自效率。

現在已經有很多很好的演算法了，它們主要要解決且還有待解決的是三個方面的problem：

穩定性stability
效率efficiency
規模scale

穩定性不光指演算法的收斂性，而且是演算法關於超參數（比如學習率，網路模型）的穩定性，因為如果演算法對超參數比較敏感的話，會需要很長時間進行調參。解決方法是希望演算法有更好的收斂性質，比如DQN中的replay memory破壞數據間的聯繫和target net，以及TRPO演算法能保證return單調上升。或者演算法能夠自動調參，如Q-Prop演算法。

至於效率，上面那張圖已經說明了各種演算法的效率，可以根據實際情況進行選擇各類演算法，比如在現實環境中，一般用model-based的演算法比較好，在複雜的模擬環境中可以用DQN或A3C。至於想要加快速率，DQN中的replay memory和A3C的非同步處理起到重要作用。而Q-Prop將policy gradient與off-policy結合加快速率。此外可以利用之前的數據知識來加快學習過程：RL2: Fast reinforcement learning via slow reinforcement learning和Learning to reinforcement learning。（也稱為meta learning，元學習）

要處理大規模的RL，比如AlphaGo，現實情形，那會遇到很多有變數的情形，就需要強大的泛化能力generalization，能在多任務中泛化策略，能用之前的經驗和知識來提升當前策略。這方面有很多好的paper，列在Lecture的slide中。