# 李宏毅_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 ![](https://i.imgur.com/K6cRnki.png) 跟環境互動的agent與訓練的agent同一個的時候,即為On-policy,若否為Off-policy,更白話一點的說法,邊做邊學習的為On-policy,在旁邊透過看別人玩來學習則為Off-policy。 以棋靈王為比喻,阿光自己下自己學,那就是On-policy,如果是佐為下,阿光在旁邊看,那就是Off-policy。 ### On-policy $\rightarrow$ Off-policy ![](https://i.imgur.com/R9f3ZDL.png) 課程之前提過的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 ![](https://i.imgur.com/AytYtDS.png) $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 ![](https://i.imgur.com/xJbSjcA.png) $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 ![](https://i.imgur.com/lt9BxFm.png) 現在,我們要將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 ![](https://i.imgur.com/seddowf.png) 課程開始有提到,在做參數更新的時候並非給整個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 ![](https://i.imgur.com/93jhsOG.png) 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 ![](https://i.imgur.com/X5DN5jv.png) 演算法實作如下: 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 ![](https://i.imgur.com/G4FVSN7.png) 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 ![](https://i.imgur.com/kkMuIzf.png) [論文連結_Proximal Policy Optimization Algorithms](https://arxiv.org/abs/1707.06347) 上面是各種方式的實作結果。