李宏毅_ATDL_DRL Lecture 2

tags: Hung-yi Lee NTU Deep Reinforcement Learning

課程撥放清單

DRL Lecture 2: Proximal Policy Optimization (PPO)

課程連結

PPO是OpenAI在強化學習上預設使用的演算法

On-policy v.s. Off-policy

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

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

On-policy

$\to$ Off-policy

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

$\mathrm{\nabla }{\overline{R}}_{\theta }=E_{\tau \sim p_{\theta }(\tau )}[R(\tau )\mathrm{\nabla }\log p_{\theta }(\tau )]$

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

從On-policy調整為Off-policy的好處在於，我們希望可以用一個

${\theta }^{\prime }$收集到的資料來訓練

$\theta$，這意味著我們可以重覆的利用這些資料來更新

$\theta$多次，效率上可以提升不少。

相關的作法可以使用Importance Sampling，這並不僅僅能應用於RL：

• $E_{x\sim p}[f(x)]$
  • 從
    $p$中sample出
    $x$來計算
    $f(x)$的期望值
• $\approx {\displaystyle \frac{1}{N}}\sum _{i=1}^{N}f(x^i)$
  • 沒有辦法對distribution-
    $p$計算積分，可以用sample的方式，取平均值來近似期望值

目前有一個問題後續會說明，就是無法從

$p$來sample資料，因此我們會從

$q$來sample，但這並不能套用我們一開始的假設，因為一開始是從

$p$來sample資料，因此必需調整：

• $=\int f(x)p(x)dx$
  • 對
    $p(x)$計算積分
• $=\int f(x){\displaystyle \frac{p(x)}{q(x)}}q(x)dx$
  • 分子分母同乘
    $q(x)$
• $=E_{x\sim q}[f(x){\displaystyle \frac{p(x)}{q(x)}}]$
  • 調整為從
    $q$來sample出
    $x$取期望值
  • 需要乘上一個權重
    ${\displaystyle \frac{p(x)}{q(x)}}$來修正
    $p,q$兩個distribution之間的差異

Issue of Importance Sampling

$E_{x\sim p}[f(x)]=E_{x\sim q}[f(x){\displaystyle \frac{p(x)}{q(x)}}]$

兩個random variable，即使mean一樣也不代表variance是一樣的，這可以利用公式計算得到：

• $VAR[X]=E\left[X^2\right]-(E\left[X\right]{)}^2$

簡報上的推導過程可以看的到，兩者之間的Variance是存在著差異

${\displaystyle \frac{p(x)}{q(x)}}$，因此如果

${\displaystyle \frac{p(x)}{q(x)}}$的數值很大，就會造成Variance也非常大。

因此理論上只要sample的次數夠多，從

$p$跟從

$q$所得的期望值會是一樣的，但如果sample的次數不夠多，就可能會得到非常大的差別。

Issue of Importance Sampling

$E_{x\sim p}[f(x)]=E_{x\sim q}[f(x){\displaystyle \frac{p(x)}{q(x)}}]$

直觀的用圖示來說明，藍線為

$p(x)$的分佈，綠線為

$q(x)$的分佈，

$f(x)$為紅線。以分佈來說，

$p(x)$所sample的點可能多在左邊 ，為負樣本，但

$q(x)$所sample的點可能多在右邊，為正樣本。

因此在sample的樣本數不多的情況下，兩者之間的差異會是非常大的。

On-policy

$\to$ Off-policy

現在，我們要將Importance Sampling的概念應用於Off-policy：

• On-policy
  • $\mathrm{\nabla }{\overline{R}}_{\theta }=E_{\tau \sim p_{\theta }(\tau )}[R(\tau )\mathrm{\nabla }\log p_{\theta }(\tau )]$
  • 以
    $\theta$與環境互動，sample出trajectory-
    $\tau$並計算期望值
• Off-policy
  • $\mathrm{\nabla }{\overline{R}}_{\theta }=E_{\tau \sim p_{{\theta }^{\prime }}(\tau )}[{\displaystyle \frac{p_{\theta }(\tau )}{p_{{\theta }^{\prime }}(\tau )}}R(\tau )\mathrm{\nabla }\log p_{\theta }(\tau )]$
  • 以
    ${\theta }^{\prime }$與環境互動，這是另一個actor，它的工作是示範給
    $\theta$看，讓
    $\theta$知道跟環境互動會發生的狀況，以此訓練
    $\theta$，這時候的trajectory-
    $\tau$是由
    ${\theta }^{\prime }$所sample。
  • 優點在於可以利用相同的資料更新多次

上面的說明提過Importance Sampling的概念，無法從

$p$來sample，永遠可以從其它的分佈來sample，只要乘上權重，也就是

${\displaystyle \frac{p_{\theta }(\tau )}{p_{{\theta }^{\prime }}(\tau )}}$，trajectory-

$\tau$由

$p_{\theta }$所sample到的機率除上由

$p_{{\theta }^{\prime }}$所sample到的機率。

On-policy

$\to$ Off-policy

課程開始有提到，在做參數更新的時候並非給整個trajectory-

$\tau$一樣的分數，而是每個state-action的成對資料分開計算：

• $E_{(s_t,a_t)\sim {\pi }_{\theta }}[A^{\theta }(s_t,a_t)\mathrm{\nabla }\log p_{\theta }(a_t^n|s_t^n)]$
  • 從
    $\theta$中sample出state, action，計算它的advantage，如果好的就增加出現的機率，不好的就減少。
  • On-policy

利用importance sampling調整為Off-policy如下：

• $E_{(s_t,a_t)\sim {\pi }_{{\theta }^{\prime }}}[{\displaystyle \frac{P_{\theta }(s_t,a_t)}{P_{{\theta }^{\prime }}(s_t,a_t)}}{A}^{{\theta }^{\prime }}(s_t,a_t)\mathrm{\nabla }\log p_{\theta }(a_t^n|s_t^n)]$
  • 這邊要注意到的是，advantage function所計算的應該是
    ${\theta }^{\prime }$所估測出來的值，因為現在與環境互動的不是
    $\theta$，而是
    ${\theta }^{\prime }$

拆解機率的項目如下：

• $E_{(s_t,a_t)\sim {\pi }_{{\theta }^{\prime }}}[{\displaystyle \frac{P_{\theta }(a_t|s_t)}{P_{{\theta }^{\prime }}(a_t|s_t)}}{\displaystyle \frac{p_{\theta }(s_t)}{p_{{\theta }^{\prime }}(s_t)}}{A}^{{\theta }^{\prime }}(s_t,a_t)\mathrm{\nabla }\log p_{\theta }(a_t^n|s_t^n)]$
  • 假設模型在
    $\theta$與
    ${\theta }^{\prime }$看到
    $s_t$的機率是差不多的，因此刪除。
  • 另一個想法，
    $s_t$難以估測，因此無視。

最終得到一個新的object function：

• $J^{{\theta }^{\prime }}(\theta )=E_{(s_t,a_t)\sim {\pi }_{{\theta }^{\prime }}}[{\displaystyle \frac{P_{\theta }(a_t|s_t)}{P_{{\theta }^{\prime }}(a_t|s_t)}}{A}^{{\theta }^{\prime }}(s_t,a_t)]$
  • 這個推導是來自於
    $\mathrm{\nabla }f(x)=f(x)\mathrm{\nabla }\log f(x)$
  • 將
    $p_{\theta }$視為
    $f(x)$，課堂上有說明，但推導過程不在畫面上。
  • $(\theta )$：要最佳化的參數
  • ${\theta }^{\prime }$：代表的是用
    ${\theta }^{\prime }$來演示(真正與環境互動)

注意到課程上有提過，importance sample過程中不能讓

$\theta$與

${\theta }^{\prime }$差異過大，如何避免的方式就是後續會提到的PPO。

PPO / TRPO

importance sample過程中不能讓

$\theta$與

${\theta }^{\prime }$兩個distribution差異過大，因此PPO的解法就是在裡面加入一個constrain(約束項)，也就是

$\beta KL(\theta ,{\theta }^{\prime })$：

• $J_{PPO}^{{\theta }^{\prime }}(\theta )=J^{{\theta }^{\prime }}(\theta )-\beta KL(\theta ,{\theta }^{\prime })$
  • $KL(\theta ,{\theta }^{\prime })$：兩個model的output的action的KL-divergence，簡單說就是衡量兩者有多相似，我們希望兩個愈像愈好。

不同於TRPO，PPO直接將constrain-

$KL(\theta ,{\theta }^{\prime })$放到要最佳化的式子裡面，接下來利用gradient ascent來最大化。但TRPO是直接將

$KL(\theta ,{\theta }^{\prime })$當做一個額外的constrain，並且

$KL(\theta ,{\theta }^{\prime })<\delta$，這在gradient-based optimization的情況下不好處理。

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

$KL(\theta ,{\theta }^{\prime })$。

不考慮參數的距離主要是因為，可能參數的些許變化會對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({\displaystyle \frac{p_{\theta }(a_t|s_t)}{p_{{\theta }^k}(a_t|s_t)}}{A}^{{\theta }^k}(s_t,a_t),clip({\displaystyle \frac{p_{\theta }(a_t|s_t)}{p_{{\theta }^k}(a_t|s_t)}},1-ϵ,1+ϵ)A^{{\theta }^k(s_t,a_t)})$

• $\sum _{s_t,a_t}$：summation over state, action的pair
• 數學式由兩個項目所組成，
  $min$的作用在於選擇較小的項目
• $clip({\displaystyle \frac{p_{\theta }(a_t|s_t)}{p_{{\theta }^k}(a_t|s_t)}},1-ϵ,1+ϵ)$
  • 裡面有三個項目，當第一項小於第二項的時候回傳
    $1-ϵ$，當第一項大於第三項的時候回來
    $1+ϵ$。
    • 大概就是WGANs的weight clipping，將值域限制於一個範圍內
  • $ϵ$為超參數

來看組成的第二項，

$clip$所處理的部份，見簡報下圖：

• 藍色虛線
• 橫軸為
  ${\displaystyle \frac{p_{\theta }(a_t|s_t)}{p_{{\theta }^k}(a_t|s_t)}}$
• 縱軸為
  $clip$的實際輸出
• $clip$的輸出大於
  $1+ϵ$的時候，即輸出
  $1+ϵ$
• $clip$的輸出小於
  $1-ϵ$的時候，即輸出
  $1-ϵ$
• $clip$的輸出介於中間，即直接輸出值

加入組成的第一項：

• 綠色虛線

advantage function-A的輸出影響取值範圍(紅線)，直觀來看：

• 當
  $A>0$，那代表這個pair是好的，我們會希望增加它出現的機率，也就是讓
  $p_{\theta }$愈大愈好，但
  $p_{\theta }$與
  $p_{{\theta }^k}$的比值不能超過
  $1+ϵ$
• 當
  $A<0$，那代表這個pair是不好的，我們會希望減少它出現的機率，也就是讓
  $p_{\theta }$愈小愈好，但
  $p_{\theta }$與
  $p_{{\theta }^k}$的比值不能小過
  $1-ϵ$

• 補圖_::

Experimental Results

論文連結_Proximal Policy Optimization Algorithms

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