# 李宏毅_ATDL_DRL Lecture 2
###### tags: `Hung-yi Lee` `NTU` `Deep Reinforcement Learning`
[課程撥放清單](https://www.youtube.com/playlist?list=PLJV_el3uVTsODxQFgzMzPLa16h6B8kWM_)
## DRL Lecture 2: Proximal Policy Optimization (PPO)
[課程連結](https://www.youtube.com/watch?v=OAKAZhFmYoI&list=PLJV_el3uVTsODxQFgzMzPLa16h6B8kWM_&index=2)

PPO是OpenAI在強化學習上預設使用的演算法
### On-policy v.s. Off-policy

跟環境互動的agent與訓練的agent同一個的時候，即為On-policy，若否為Off-policy，更白話一點的說法，邊做邊學習的為On-policy，在旁邊透過看別人玩來學習則為Off-policy。

以棋靈王為比喻，阿光自己下自己學，那就是On-policy，如果是佐為下，阿光在旁邊看，那就是Off-policy。
### On-policy $\rightarrow$ Off-policy

課程之前提過的Policy Gradient就是一種On-policy的實作，你有一個actor，它跟環境互動，然後學習更新，這過程中的policy都是同一個，因此為On-policy。

$\nabla \bar{R}_\theta = E_{\tau \sim p_\theta(\tau)} \left[ R(\tau) \nabla \log p_\theta(\tau) \right]$
* 這其中的$E_{\tau \sim p_\theta(\tau)}$是對現在的policy-$\theta$去sample出一個trajectory-$\tau$來計算期望值，因此當你更新參數$\theta$變為$\theta'$之後，那$p_\theta(\tau)$就不對了，這時候你就需要重新sample，之前sample出來的資料已經不能用，也因此課程提過，過程中的資料都只能用一次。
* 這造成Policy Gradient會花很多時間在sample data，因為所有的資料都只能更新參數一次，更新一次之後就要重新sample。

從On-policy調整為Off-policy的好處在於，我們希望可以用一個$\theta'$收集到的資料來訓練$\theta$，這意味著我們可以重覆的利用這些資料來更新$\theta$多次，效率上可以提升不少。

相關的作法可以使用Importance Sampling，這並不僅僅能應用於RL：
* $E_{x \sim p}\left[f(x) \right]$
* 從$p$中sample出$x$來計算$f(x)$的期望值
* $\approx \dfrac{1}{N} \sum^N_{i=1} f(x^i)$
* 沒有辦法對distribution-$p$計算積分，可以用sample的方式，取平均值來近似期望值

目前有一個問題後續會說明，就是無法從$p$來sample資料，因此我們會從$q$來sample，但這並不能套用我們一開始的假設，因為一開始是從$p$來sample資料，因此必需調整：
* $=\int f(x) p(x) dx$
* 對$p(x)$計算積分
* $=\int f(x) \dfrac{p(x)}{q(x)} q(x) dx$
* 分子分母同乘$q(x)$
* $=E_{x \sim q} \left[f(x) \dfrac{p(x)}{q(x)} \right]$
* 調整為從$q$來sample出$x$取期望值
* 需要乘上一個權重$\dfrac{p(x)}{q(x)}$來修正$p,q$兩個distribution之間的差異

### Issue of Importance Sampling

$E_{x \sim p}\left[f(x) \right]=E_{x \sim q} \left[f(x) \dfrac{p(x)}{q(x)} \right]$

兩個random variable，即使mean一樣也不代表variance是一樣的，這可以利用公式計算得到：
* $VAR[X]=E\left[X^2\right]-(E\left[X\right])^2$

簡報上的推導過程可以看的到，兩者之間的Variance是存在著差異$\dfrac{p(x)}{q(x)}$，因此如果$\dfrac{p(x)}{q(x)}$的數值很大，就會造成Variance也非常大。

因此理論上只要sample的次數夠多，從$p$跟從$q$所得的期望值會是一樣的，但如果sample的次數不夠多，就可能會得到非常大的差別。
### Issue of Importance Sampling

$E_{x \sim p}\left[f(x) \right]=E_{x \sim q} \left[f(x) \dfrac{p(x)}{q(x)} \right]$

直觀的用圖示來說明，藍線為$p(x)$的分佈，綠線為$q(x)$的分佈，$f(x)$為紅線。以分佈來說，$p(x)$所sample的點可能多在左邊 ，為負樣本，但$q(x)$所sample的點可能多在右邊，為正樣本。

因此在sample的樣本數不多的情況下，兩者之間的差異會是非常大的。
### On-policy $\rightarrow$ Off-policy

現在，我們要將Importance Sampling的概念應用於Off-policy：
* On-policy
* $\nabla \bar{R}_\theta = E_{\tau \sim p_\theta(\tau)}\left[ R(\tau) \nabla \log p_\theta(\tau)\right]$
* 以$\theta$與環境互動，sample出trajectory-$\tau$並計算期望值
* Off-policy
* $\nabla \bar{R}_\theta = E_{\tau \sim p_{\theta'}(\tau)} \left[ \dfrac{p_\theta(\tau)}{p_{\theta'}(\tau)} R(\tau) \nabla \log p_\theta(\tau) \right]$
* 以$\theta'$與環境互動，這是另一個actor，它的工作是示範給$\theta$看，讓$\theta$知道跟環境互動會發生的狀況，以此訓練$\theta$，這時候的trajectory-$\tau$是由$\theta'$所sample。
* 優點在於可以利用相同的資料更新多次

上面的說明提過Importance Sampling的概念，無法從$p$來sample，永遠可以從其它的分佈來sample，只要乘上權重，也就是$\dfrac{p_\theta(\tau)}{p_{\theta'}(\tau)}$，trajectory-$\tau$由$p_\theta$所sample到的機率除上由$p_{\theta'}$所sample到的機率。
### On-policy $\rightarrow$ Off-policy

課程開始有提到，在做參數更新的時候並非給整個trajectory-$\tau$一樣的分數，而是每個state-action的成對資料分開計算：
* $E_{(s_t, a_t) \sim \pi_\theta} \left[ A^\theta(s_t, a_t) \nabla \log p_\theta(a^n_t \vert s^n_t) \right]$
* 從$\theta$中sample出state, action，計算它的advantage，如果好的就增加出現的機率，不好的就減少。
* On-policy

利用importance sampling調整為Off-policy如下：
* $E_{(s_t, a_t) \sim \pi_{\theta'}} \left[ \dfrac{P_\theta(s_t, a_t)}{P_{\theta'}(s_t, a_t)} A^{\theta'}(s_t, a_t) \nabla \log p_\theta(a^n_t \vert s^n_t) \right]$
* 這邊要注意到的是，advantage function所計算的應該是$\theta'$所估測出來的值，因為現在與環境互動的不是$\theta$，而是$\theta'$

拆解機率的項目如下：
* $E_{(s_t, a_t) \sim \pi_{\theta'}} \left[ \dfrac{P_\theta(a_t \vert s_t)}{P_{\theta'}(a_t \vert s_t)} \dfrac{p_\theta(s_t)}{p_{\theta'}(s_t)} A^{\theta'}(s_t, a_t) \nabla \log p_\theta(a^n_t \vert s^n_t) \right]$
* 假設模型在$\theta$與$\theta'$看到$s_t$的機率是差不多的，因此刪除。
* 另一個想法，$s_t$難以估測，因此無視。

最終得到一個新的object function：
* $J^{\theta'}(\theta) = E_{(s_t, a_t) \sim \pi_{\theta'}} \left[ \dfrac{P_\theta(a_t \vert s_t)}{P_{\theta'}(a_t \vert s_t)} A^{\theta'}(s_t, a_t) \right]$
* 這個推導是來自於$\nabla f(x) = f(x) \nabla \log f(x)$
* 將$p_\theta$視為$f(x)$，課堂上有說明，但推導過程不在畫面上。
* $(\theta)$：要最佳化的參數
* $\theta'$：代表的是用$\theta'$來演示(真正與環境互動)

注意到課程上有提過，importance sample過程中不能讓$\theta$與$\theta'$差異過大，如何避免的方式就是後續會提到的PPO。
### PPO / TRPO

importance sample過程中不能讓$\theta$與$\theta'$兩個distribution差異過大，因此PPO的解法就是在裡面加入一個constrain(約束項)，也就是$\beta KL(\theta, \theta')$：
* $J_{PPO}^{\theta'}(\theta) = J^{\theta'}(\theta) - \beta KL(\theta, \theta')$
* $KL(\theta, \theta')$：兩個model的output的action的KL-divergence，簡單說就是衡量兩者有多相似，我們希望兩個愈像愈好。

不同於TRPO，PPO直接將constrain-$KL(\theta, \theta')$放到要最佳化的式子裡面，接下來利用gradient ascent來最大化。但TRPO是直接將$KL(\theta, \theta')$當做一個額外的constrain，並且$KL(\theta, \theta') < \delta$，這在gradient-based optimization的情況下不好處理。

$KL(\theta, \theta')$並不是指兩個參數之間的距離，而是behavior上的距離，也就是給定相同的state情況下，model output的action之間的差距，model output的action是一個機率分佈，將不同state的output的兩個distribution的KL-divergence平均起來，就是這邊所計算的$KL(\theta, \theta')$。

不考慮參數的距離主要是因為，可能參數的些許變化會對action有不一致的影響，可能很大也可能很小，但我們在意的是action這個行為上的差距，而不是參數，因此只考慮action的距離。

文獻結果來看，PPO對TRPO的效能差不多，但實作上PPO好做的多。
### PPO algorithm

演算法實作如下：
1. 初始化policy的參數$\theta^0$
2. 在每次迭代中：
* 使用$\theta^k$與環境互動，得到一堆{$s_t,a_t$}，計算advantage-$A^{\theta^k}(s_t, a_t)$
* $\theta^k$上一次訓練迭代中得到的actor的參數
* 實作PPO最佳化，以$\theta^k$得到的資料來訓練$\theta$
* 不同於policy gradient只能應用一次資料，這邊可以多次訓練$\theta$
* object function-$J_{PPO}^{\theta^k}(\theta)=J^{\theta^k}(\theta)-\beta KL(\theta, \theta^k)$
* 動態更新$\beta$
* 設置一個可接受的最大、最小$KL(\theta, \theta^k)$，稱為`adative KL penalty`
* 比最大值大，代表懲罰項沒發揮效用，則加大$\beta$
* 比最大值小，代表懲罰項效果太強，則減少$\beta$

### PPO2

PPO因為還要計算KL-divergence因此有點複雜，延申出PPO2，雖然數學式看起來很複雜，但實作起來是簡單的：
$J_{PPO2}^{\theta^k}(\theta) \approx \sum_{s_t, a_t} \min \left( \dfrac{p_\theta(a_t \vert s_t)}{p_{\theta^k}(a_t \vert s_t)} A^{\theta^k}(s_t, a_t), clip\left(\dfrac{p_\theta(a_t \vert s_t)}{p_{\theta^k}(a_t \vert s_t)}, 1 - \epsilon, 1 + \epsilon \right) A^{\theta^k (s_t, a_t)} \right)$
* $\sum_{s_t, a_t}$：summation over state, action的pair
* 數學式由兩個項目所組成，$\min$的作用在於選擇較小的項目
* $clip\left(\dfrac{p_\theta(a_t \vert s_t)}{p_{\theta^k}(a_t \vert s_t)}, 1 - \epsilon, 1 + \epsilon \right)$
* 裡面有三個項目，當第一項小於第二項的時候回傳$1 - \epsilon$，當第一項大於第三項的時候回來$1 + \epsilon$。
* 大概就是WGANs的weight clipping，將值域限制於一個範圍內
* $\epsilon$為超參數

來看組成的第二項，$clip$所處理的部份，見簡報下圖：
* 藍色虛線
* 橫軸為$\dfrac{p_\theta(a_t \vert s_t)}{p_{\theta^k}(a_t \vert s_t)}$
* 縱軸為$clip$的實際輸出
* $clip$的輸出大於$1 + \epsilon$的時候，即輸出$1 + \epsilon$
* $clip$的輸出小於$1 - \epsilon$的時候，即輸出$1 - \epsilon$
* $clip$的輸出介於中間，即直接輸出值

加入組成的第一項：
* 綠色虛線

advantage function-A的輸出影響取值範圍(紅線)，直觀來看：
* 當$A>0$，那代表這個pair是好的，我們會希望增加它出現的機率，也就是讓$p_\theta$愈大愈好，但$p_\theta$與$p_{\theta^k}$的比值不能超過$1 + \epsilon$
* 當$A<0$，那代表這個pair是不好的，我們會希望減少它出現的機率，也就是讓$p_\theta$愈小愈好，但$p_\theta$與$p_{\theta^k}$的比值不能小過$1 - \epsilon$
- [ ] 補圖_::

### Experimental Results

[論文連結_Proximal Policy Optimization Algorithms](https://arxiv.org/abs/1707.06347)

上面是各種方式的實作結果。