第三章 政策梯度及 PPO 算法

Policy Gradient

Policy Gradient

在 reinforcement learning 中有 3 個components，一個

actor

，一個

environment

，一個

reward function

。

讓機器玩 video game 時，

• actor 做的事情就是去操控遊戲的搖杆， 比如說向左、向右、開火等操作；
• environment 就是遊戲的主機， 負責控制遊戲的畫面負責控制說，怪物要怎麼移動， 你現在要看到什麼畫面等等；
• reward function 就是當你做什麼事情，發生什麼狀況的時候，你可以得到多少分數， 比如說殺一隻怪獸得到 20 分等等。

同樣的概念用在圍棋上也是一樣的，

• actor 就是 alpha Go，它要決定下哪一個位置；
• environment 就是對手；
• reward function 就是按照圍棋的規則， 赢就是得一分，輸就是負一分等等。

在 reinforcement learning 裡面，environment 跟 reward function 不是你可以控制的，environment 跟 reward function 是在開始學習之前，就已經事先給定的。你唯一能做的事情是調整 actor 裡面的 policy，使得 actor 可以得到最大的 reward。Actor 裡面會有一個 policy， 這個 policy 決定了 actor 的行為。Policy 就是給一個外界的輸入，然後它會輸出 actor 現在應該要執行的行為。

• Policy 一般寫成 $\pi$。假設你是用 deep learning 的技術來做 reinforcement learning 的話，policy 就是一個 network。Network 裡面就有一堆參數， 我們用 $\theta$ 來代表 $\pi$ 的參數。
• Network 的 input 就是現在 machine 看到的東西，如果讓 machine 打電玩的話，machine 看到的東西就是遊戲的畫面。Machine 看到什麼東西，會影響你現在 training 到底好不好 train。舉例來說，在玩遊戲的時候， 也許你覺得遊戲的畫面，前後是相關的，也許你覺得說，你應該讓你的 policy，看從遊戲初始到現在這個時間點，所有畫面的總和。你可能會覺得你要用到 RNN 來處理它，不過這樣子會比較難處理。要讓你的 machine，你的 policy 看到什麼樣的畫面， 這個是你自己決定的。讓你知道說給機器看到什麼樣的遊戲畫面，可能是比較有效的。
• Output 的就是機器要采取什麼樣的行為。

上圖就是具體的例子，

• policy 就是一個 network；
• input 就是遊戲的畫面，它通常是由 pixels 所組成的；
• output 就是看看說有哪些選項是你可以去執行的，output layer 就有幾個 neurons。

假設你現在可以做的行為有 3 個，output layer 就是有 3 個 neurons。每個 neuron 對應到一個可以采取的行為。Input 一個東西後，network 就會給每一個可以采取的行為一個分數。接下來，你把這個分數當作是機率。 actor 就是看這個機率的分布，根據這個機率的分布，決定它要采取的行為。比如說 70% 會走 left，20% 走 right，10% 開火等等。機率分布不同，actor 采取的行為就會不一樣。

接下來用一個例子來說明 actor 是怎麼樣跟環境互動的。 首先 actor 會看到一個遊戲畫面，我們用 $s_1$ 來表示這個遊戲畫面，它代表遊戲初始的畫面。接下來 actor 看到這個遊戲的初始畫面以後，根據它内部的 network，根據它内部的 policy 來決定一個 action。假設它現在決定的 action 是向右，它決定完 action 以後，它就會得到一個 reward ，代表它采取這個 action 以後得到的分數。

我們把一開始的初始畫面記作 $s_1$， 把第一次執行的動作記作 $a_1$，把第一次執行動作完以後得到的 reward 記作 $r_1$。不同的書會有不同的定義，有人會覺得說這邊應該要叫做 $r_2$，這個都可以，你自己看得懂就好。Actor 決定一個的行為以後， 就會看到一個新的遊戲畫面，這邊是 $s_2$。然後把這個 $s_2$ 輸入給 actor，這個 actor 決定要開火，然後它可能殺了一隻怪，就得到五分。這個 process 就反複地持續下去，直到今天走到某一個 timestamp 執行某一個 action，得到 reward 之後， 這個 environment 決定這個遊戲結束了。比如說，如果在這個遊戲裡面，你是控制綠色的船去殺怪，如果你被殺死的話，遊戲就結束，或是你把所有的怪都清空，遊戲就結束了。

一場遊戲叫做一個

episode(回合)

或者

trial(試驗)

。把這個遊戲裡面，所有得到的 reward 都總合起來，就是

total reward

，我們稱其為

return(回報)

，用 R 來表示它。Actor 要想辦法去 maximize 它可以得到的 reward。

首先，

environment

是一個

function

，遊戲的主機也可以把它看作是一個 function，雖然它不一定是 neural network，可能是 rule-based 的規則，但你可以把它看作是一個 function。這個 function，一開始就先吐出一個 state，也就是遊戲的畫面，接下來你的 actor 看到這個遊戲畫面 $s_1$ 以後，它吐出 $a_1$，然後 environment 把 $a_1$ 當作它的輸入，然後它再吐出 $s_2$，吐出新的遊戲畫面。Actor 看到新的遊戲畫面，再采取新的行為 $a_2$，然後 environment 再看到 $a_2$，再吐出 $s_3$。這個 process 會一直持續下去，直到 environment 覺得說應該要停止為止。

在一場遊戲裡面，我們把 environment 輸出的 $s$ 跟 actor 輸出的行為 $a$，把這個 $s$ 跟 $a$ 全部串起來， 叫做一個

Trajectory

，如下式所示。

每一個 trajectory，你可以計算它發生的機率。假設現在 actor 的參數已經被給定了話，就是 $\theta$。根據 $\theta$，你其實可以計算某一個 trajectory 發生的機率，你可以計算某一個回合，某一個 episode 裡面， 發生這樣子狀況的機率。

怎麼算呢，如上式所示。在假設 actor 的參數就是 $\theta$ 的情況下，某一個 trajectory $\tau$ 的機率就是這樣算的，你先算 environment 輸出 $s_1$ 的機率，再計算根據 $s_1$ 執行 $a_1$ 的機率，這是由你 policy 裡面的 network 參數 $\theta$ 所決定的， 它是一個機率，因為你的 policy 的 network 的 output 是一個 distribution，actor 是根據這個 distribution 去做 sample，決定現在實際上要采取的 action是哪一個。接下來 environment 根據 $a_1$ 跟 $s_1$ 産生 $s_2$，因為 $s_2$ 跟$s_1$ 還是有關系的，下一個遊戲畫面，跟前一個遊戲畫面通常還是有關系的，至少要是連續的， 是以給定前一個遊戲畫面 $s_1$ 和現在 actor 采取的行為 $a_1$，就會産生 $s_2$。

這件事情可能是機率，也可能不是機率，這個取決于 environment，就是主機它内部設定是怎樣。看今天這個主機在決定，要輸出什麼樣的遊戲畫面的時候，有沒有機率。因為如果沒有機率的話，這個遊戲的每次的行為都一樣，你隻要找到一條 path 就可以過關了，這樣感覺是蠻無聊的 。是以遊戲裡面，通常是還是有一些機率的，你做同樣的行為，給同樣的前一個畫面， 下次産生的畫面不見得是一樣的。Process 就反複繼續下去，你就可以計算一個 trajectory $s_1$,$a_1$, $s_2$ , $a_2$ 出現的機率有多大。

這個機率取決于兩部分，

• 一部分是

  environment 的行為

  ， environment 的 function 它内部的參數或内部的規則長什麼樣子。 $p(s_{t+1}|s_t,a_t)$這一項代表的是 environment， environment 這一項通常你是無法控制它的，因為那個是人家寫好的，你不能控制它。
• 另一部分是

  agent 的行為

  。你能控制的是 $p_\theta(a_t|s_t)$。給定一個 $s_t$， actor 要采取什麼樣的 $a_t$ 會取決于你 actor 的參數 $\theta$， 是以這部分是 actor 可以自己控制的。随着 actor 的行為不同，每個同樣的 trajectory， 它就會有不同的出現的機率。

在 reinforcement learning 裡面，除了 environment 跟 actor 以外， 還有

reward function

。Reward function 根據在某一個 state 采取的某一個 action 決定說現在這個行為可以得到多少的分數。 它是一個 function，給它 $s_1$，$a_1$，它告訴你得到 $r_1$。給它 $s_2$ ，$a_2$，它告訴你得到 $r_2$。 把所有的 $r$ 都加起來，我們就得到了 $R(\tau)$ ，代表某一個 trajectory $\tau$ 的 reward。在某一場遊戲裡面， 某一個 episode 裡面，我們會得到 R。我們要做的事情就是調整 actor 内部的參數 $\theta$， 使得 R 的值越大越好。 但實際上 reward 并不隻是一個 scalar，reward 其實是一個 random variable，R 其實是一個 random variable。 因為 actor 在給定同樣的 state 會做什麼樣的行為，這件事情是有随機性的。environment 在給定同樣的 observation 要采取什麼樣的 action，要産生什麼樣的 observation，本身也是有随機性的。是以 R 是一個 random variable，你能夠計算的，是它的期望值。你能夠計算的是說，在給定某一組參數 $\theta$ 的情況下，我們會得到的 R 的期望值是多少。

這個期望值的算法如上式所示，窮舉所有可能的 trajectory $\tau$， 每一個 trajectory $\tau$ 都有一個機率。比如 $\theta$ 是一個很強的 model， 那它都不會死。如果有一個 episode 很快就死掉了， 它的機率就很小；如果有一個 episode 都一直沒有死， 那它的機率就很大。根據你的 $\theta$， 你可以算出某一個 trajectory $\tau$ 出現的機率，接下來你計算這個 $\tau$ 的 total reward 是多少。 Total reward weighted by 這個 $\tau$ 出現的機率，對所有的 $\tau$ 進行求和，就是期望值。給定一個參數，你會得到的期望值。

我們還可以寫成上式那樣，從 $p_{\theta}(\tau)$ 這個 distribution sample 一個 trajectory $\tau$，然後計算 $R(\tau)$ 的期望值，就是你的 expected reward。 我們要做的事情就是 maximize expected reward。

怎麼 maximize expected reward 呢？我們用的是

gradient ascent

，因為要讓它越大越好，是以是 gradient ascent。Gradient ascent 在 update 參數的時候要加。要進行 gradient ascent，我們先要計算 expected reward $\bar{R}$ 的 gradient 。我們對 $\bar{R}$ 取一個 gradient，這裡面隻有 $p{\theta}(\tau)$ 是跟 $\theta$ 有關，是以 gradient 就放在 $p{\theta}(\tau)$ 這個地方。$R(\tau)$ 這個 reward function 不需要是 differentiable，我們也可以解接下來的問題。舉例來說，如果是在 GAN 裡面，$R(\tau)$ 其實是一個 discriminator，它就算是沒有辦法微分，也無所謂，你還是可以做接下來的運算。

取 gradient之後，我們背一個公式：

我們可以對 $\nabla p{\theta}(\tau)$ 使用這個公式，然後會得到 $\nabla p{\theta}(\tau)=p{\theta}(\tau) \nabla \log p{\theta}(\tau)$。

接下來， 分子分母，上下同乘$p_{\theta}(\tau)$，然後我們可以得到下式：

然後如下式所示， 對 $\tau$ 進行求和，把 $R(\tau)$ 和 $\log p{\theta}(\tau)$ 這兩項 weighted by $ p{\theta}(\tau)$， 既然有 weighted by $p{\theta}(\tau)$，它們就可以被寫成這個 expected 的形式。也就是你從 $p{\theta}(\tau)$ 這個 distribution 裡面 sample $\tau$ 出來， 去計算 $R(\tau)$ 乘上 $\nabla\log p_{\theta}(\tau)$，然後把它對所有可能的 $\tau$ 進行求和，就是這個 expected value 。

實際上這個 expected value 沒有辦法算，是以你是用 sample 的方式來 sample 一大堆的 $\tau$。你 sample $N$ 筆 $\tau$， 然後你去計算每一筆的這些 value，然後把它全部加起來，最後你就得到你的 gradient。你就可以去 update 你的參數，你就可以去 update 你的 agent，如下式所示。

注意 $p{\theta}(\tau)$ 裡面有兩項，$p(s{t+1}|s_t,a_t)$ 來自于 environment，$p\theta(a_t|s_t)$ 是來自于 agent。 $p(s{t+1}|s_t,a_t)$ 由環境決定進而與 $\theta$ 無關，是以 $\nabla \log p(s{t+1}|s_t,a_t) =0 $。是以 $\nabla p{\theta}(\tau)= \nabla \log p{\theta}\left(a{t}^{n} | s_{t}^{n}\right)$。

你可以非常直覺的來了解這個部分，也就是在你 sample 到的 data 裡面， 你 sample 到，在某一個 state $s_t$ 要執行某一個 action $a_t$， 這個 $s_t$ 跟 $a_t$ 它是在整個 trajectory $\tau$ 的裡面的某一個 state and action 的 pair。

• 假設你在 $s_t$ 執行 $a_t$，最後發現 $\tau$ 的 reward 是正的， 那你就要增加這一項的機率，你就要增加在 $s_t$ 執行 $a_t$ 的機率。
• 反之，在 $s_t$ 執行 $a_t$ 會導緻$\tau$ 的 reward 變成負的， 你就要減少這一項的機率。

這個怎麼實作呢？ 你用 gradient ascent 來 update 你的參數，你原來有一個參數 $\theta$ ，把你的 $\theta$ 加上你的 gradient 這一項，那當然前面要有個 learning rate，learning rate 其實也是要調的，你可用 Adam、RMSProp 等方法對其進行調整。

我們可以套下面這個公式來把 gradient 計算出來:

實際上，要套上面這個公式， 首先你要先收集一大堆的 s 跟 a 的 pair，你還要知道這些 s 跟 a 在跟環境互動的時候，你會得到多少的 reward。 這些資料怎麼收集呢？你要拿你的 agent，它的參數是 $\theta$，去跟環境做互動， 也就是拿你已經 train 好的 agent 先去跟環境玩一下，先去跟那個遊戲互動一下， 互動完以後，你就會得到一大堆遊戲的紀錄，你會記錄說，今天先玩了第一場，在第一場遊戲裡面，我們在 state $s_1$ 采取 action $a_1$，在 state $s_2$ 采取 action $a_2$ 。

玩遊戲的時候是有随機性的，是以 agent 本身是有随機性的，在同樣 state $s_1$，不是每次都會采取 $a_1$，是以你要記錄下來。在 state $s_1^1$ 采取 $a_1^1$，在 state $s_2^1$ 采取 $a_2^1$。整場遊戲結束以後，得到的分數是$R(\tau^1)$。你會 sample 到另外一筆 data，也就是另外一場遊戲。在另外一場遊戲裡面，你在 state $s_1^2$ 采取 $a_1^2$，在 state $s_2^2$ 采取 $a_2^2$，然後你 sample 到的就是 $\tau^2$，得到的 reward 是 $R(\tau^2)$。

你就可以把 sample 到的東西代到這個 gradient 的式子裡面，把 gradient 算出來。也就是把這邊的每一個 s 跟 a 的 pair 拿進來，算一下它的 log probability 。你計算一下在某一個 state 采取某一個 action 的 log probability，然後對它取 gradient，然後這個 gradient 前面會乘一個 weight，weight 就是這場遊戲的 reward。 有了這些以後，你就會去 update 你的 model。

Update 完你的 model 以後。你要重新去收集 data，再 update model。這邊要注意一下，一般 policy gradient sample 的 data 就隻會用一次。你把這些 data sample 起來，然後拿去 update 參數，這些 data 就丢掉了。接着再重新 sample data，才能夠去 update 參數， 等一下我們會解決這個問題。

接下來講一些實作細節。實作方法是這個樣子，把它想成一個分類的問題，在 classification 裡面就是 input 一個 image，然後 output 決定說是 10 個 class 裡面的哪一個。在做 classification 時，我們要收集一堆 training data，要有 input 跟 output 的 pair。

在實作的時候，你就把 state 當作是 classifier 的 input。 你就當在做 image classification 的 problem，隻是現在的 class 不是說 image 裡面有什麼 objects。 現在的 class 是說，看到這張 image 我們要采取什麼樣的行為，每一個行為就是一個 class。比如說第一個 class 叫做向左，第二個 class 叫做向右，第三個 class 叫做開火。

這些訓練的資料從哪裡來的呢？ 做分類的問題時，要有 input 和正确的 output。 這些訓練資料是從 sampling 的 process 來的。假設在 sampling 的 process 裡面，在某一個 state，你 sample 到你要采取 action a， 你就把這個 action a 當作是你的 ground truth。你在這個 state，你 sample 到要向左。 本來向左這件事機率不一定是最高， 因為你是 sample，它不一定機率最高。假設你 sample 到向左，在 training 的時候 你叫告訴 machine 說，調整 network 的參數， 如果看到這個 state，你就向左。在一般的 classification 的 problem 裡面，其實你在 implement classification 的時候， 你的 objective function 都會寫成 minimize cross entropy，其實 minimize cross entropy 就是 maximize log likelihood。

做 classification 的時候，objective function 就是 maximize 或 minimize 的對象， 因為我們現在是 maximize likelihood 是以其實是 maximize， 你要 maximize 的對象，如下式所示:

像這種 loss function。你可在 TensorFlow 裡 call 現成的 function，它就會自動幫你算。 然後你就可以把 gradient 計算出來，這是一般的分類問題。RL 唯一不同的地方是 loss 前面乘上一個 weight，這個是整場遊戲的時候得到的 total reward R， 它并不是在 state s 采取 action a 的時候得到的 reward。 你要把你的每一筆 training data，都 weighted by 這個 R。然後你用 TensorFlow 或 PyTorch 去幫你算 gradient 就結束了，跟一般 classification 差不多。

Tips

這邊有一些在實作的時候，你也許用得上的 tip。

Tip 1: Add a Baseline

第一個 tip 是 add 一個 baseline。 如果 given state s 采取 action a 會給你整場遊戲正面的 reward，就要增加它的機率。如果 state s 執行 action a，整場遊戲得到負的 reward，就要減少這一項的機率。

但在很多遊戲裡面， reward 總是正的，就是說最低都是 0。比如說打乒乓球遊戲， 你的分數就是介于 0 到 21 分之間，是以這個 R 總是正的。假設你直接套用這個式子， 在 training 的時候，告訴 model 說，不管是什麼 action 你都應該要把它的機率提升。 在理想上，這麼做并不一定會有問題。因為雖然說 R 總是正的，但它正的量總是有大有小，你在玩乒乓球那個遊戲裡面，得到的 reward 總是正的，但它是介于 0~21分之間，有時候你采取某些 action 可能是得到 0 分，采取某些 action 可能是得到 20 分。

假設你有 3 個 action a/b/c 可以執行，在某一個 state 有 3 個 action a/b/c可以執行。根據這個式子，你要把這 3 項的機率， log probability 都拉高。 但是它們前面 weight 的這個 R 是不一樣的。 R 是有大有小的，weight 小的，它上升的就少，weight 多的，它上升的就大一點。 因為這個 log probability，它是一個機率，是以action a、b、c 的和要是 0。 是以上升少的，在做完 normalize 以後， 它其實就是下降的，上升的多的，才會上升。

這個是一個理想上的狀況，但是實際上，我們是在做 sampling 就本來這邊應該是一個 expectation， summation over 所有可能的 s 跟 a 的 pair。 但你真正在學的時候，當然不可能是這麼做的，你隻是 sample 了少量的 s 跟 a 的 pair 而已。 因為我們做的是 sampling，有一些 action 可能從來都沒有 sample 到。在某一個 state1，雖然可以執行的 action 有 a/b/c 3 個，但你可能隻 sample 到 action b，你可能隻 sample 到 action c，你沒有 sample 到 action a。但現在所有 action 的 reward 都是正的，是以根據這個式子，它的每一項的機率都應該要上升。你會遇到的問題是，因為 a 沒有被 sample 到，其它 action 的機率如果都要上升，a 的機率就下降。 是以 a 不一定是一個不好的 action， 它隻是沒被 sample 到。但隻是因為它沒被 sample 到， 它的機率就會下降，這個顯然是有問題的，要怎麼解決這個問題呢？你會希望你的 reward 不要總是正的。

為了解決 reward 總是正的這個問題，你可以把 reward 減掉一項叫做 b，這項 b 叫做 baseline。你減掉這項 b 以後，就可以讓 $R(\tau^n)-b$ 這一項， 有正有負。 是以如果得到的 total reward $R(\tau^n)$ 大于 b 的話，就讓它的機率上升。如果這個 total reward 小于 b，就算它是正的，正的很小也是不好的，你就要讓這一項的機率下降。 如果$R(\tau^n)<b$ ， 你就要讓這個 state 采取這個 action 的分數下降 。這個 b 怎麼設呢？一個最簡單的做法就是， 你把 $\tau^n$ 的值取 expectation， 算一下 $\tau^n$的平均值。

這是其中一種做法， 你可以想想看有沒有其它的做法。

是以在 implement training 的時候，你會不斷地把 $R(\tau)$ 的分數記錄下來 然後你會不斷地去計算 $R(\tau)$ 的平均值， 你會把這個平均值，當作你的 b 來用。 這樣就可以讓你在 training 的時候， $\nabla \log p{\theta}\left(a{t}^{n} | s_{t}^{n}\right)$ 乘上前面這一項， 是有正有負的，這個是第一個 tip。

Tip 2: Assign Suitable Credit

第二個 tip：給每一個 action 合适的 credit。什麼意思呢，如果我們看今天下面這個式子的話，

我們原來會做的事情是，在某一個 state，假設你執行了某一個 action a，它得到的 reward ，它前面乘上的這一項 $R(\tau^n)-b$。

隻要在同一個 episode 裡面，在同一場遊戲裡面， 所有的 state 跟 a 的 pair，它都會 weighted by 同樣的 reward term，這件事情顯然是不公平的，因為在同一場遊戲裡面 也許有些 action 是好的，有些 action 是不好的。 假設整場遊戲的結果是好的， 并不代表這個遊戲裡面每一個行為都是對的。若是整場遊戲結果不好， 但不代表遊戲裡面的所有行為都是錯的。是以我們希望可以給每一個不同的 action 前面都乘上不同的 weight。每一個 action 的不同 weight， 它反映了每一個 action 到底是好還是不好。

舉個例子， 假設這個遊戲都很短，隻有 3~4 個互動， 在 $s_a$ 執行 $a_1$ 得到 5 分。在 $s_b$ 執行 $a_2$ 得到 0 分。在 $s_c$ 執行 $a_3$ 得到 -2 分。 整場遊戲下來，你得到 +3 分，那你得到 +3 分 代表在 state $s_b$ 執行 action $a_2$ 是好的嗎？并不見得代表 state $s_b$ 執行 $a_2$ 是好的。因為這個正的分數，主要來自于在 state $s_a$ 執行了 $a_1$，跟在 state $s_b$ 執行 $a_2$ 是沒有關系的，也許在 state $s_b$ 執行 $a_2$ 反而是不好的， 因為它導緻你接下來會進入 state $s_c$，執行 $a_3$ 被扣分，是以整場遊戲得到的結果是好的， 并不代表每一個行為都是對的。

如果按照我們剛才的講法，整場遊戲得到的分數是 3 分，那到時候在 training 的時候， 每一個 state 跟 action 的 pair，都會被乘上 +3。 在理想的狀況下，這個問題，如果你 sample 夠多就可以被解決。因為假設你 sample 夠多，在 state $s_b$ 執行 $a_2$ 的這件事情，被 sample 到很多。就某一場遊戲，在 state $s_b$ 執行 $a_2$，你會得到 +3 分。 但在另外一場遊戲，在 state $s_b$ 執行 $a_2$，你卻得到了 -7 分，為什麼會得到 -7 分呢？ 因為在 state $s_b$ 執行 $a_2$ 之前， 你在 state $s_a$ 執行 $a_2$ 得到 -5 分，-5 分這件事可能也不是在 $s_b$ 執行 $a_2$ 的錯，這兩件事情，可能是沒有關系的，因為它先發生了，這件事才發生，是以它們是沒有關系的。

在 state $s_b$ 執行 $a_2$ 可能造成的問題隻有會在接下來 -2 分，而跟前面的 -5 分沒有關系的。但是假設我們今天 sample 到這項的次數夠多，把所有發生這件事情的情況的分數通通都集合起來， 那可能不是一個問題。但現在的問題就是，我們 sample 的次數是不夠多的。在 sample 的次數不夠多的情況下，你要給每一個 state 跟 action pair 合理的 credit，你要讓大家知道它合理的 contribution。怎麼給它一個合理的 contribution 呢？ 一個做法是計算這個 pair 的 reward 的時候，不把整場遊戲得到的 reward 全部加起來，隻計算從這一個 action 執行以後所得到的 reward。因為這場遊戲在執行這個 action 之前發生的事情是跟執行這個 action 是沒有關系的， 是以在執行這個 action 之前得到多少 reward 都不能算是這個 action 的功勞。跟這個 action 有關的東西， 隻有在執行這個 action 以後發生的所有的 reward 把它加起來，才是這個 action 真正的 contribution。是以在這個例子裡面，在 state $s_b$ 執行 $a_2$ 這件事情，也許它真正會導緻你得到的分數應該是 -2 分而不是 +3 分，因為前面的 +5 分 并不是執行 $a_2$ 的功勞。實際上執行 $a_2$ 以後，到遊戲結束前， 你隻有被扣 2 分而已，是以它應該是 -2。那一樣的道理，今天執行 $a_2$ 實際上不應該是扣 7 分，因為前面扣 5 分，跟在 $s_b$ 這個 state 執行 $a_2$ 是沒有關系的。在 $s_b$ 這個 state 執行 $a_2$，隻會讓你被扣兩分而已，是以也許在 $s_b$ 這個 state 執行 $a_2$， 你真正會導緻的結果隻有扣兩分而已。如果要把它寫成式子的話是什麼樣子呢？如下式所示。

本來的 weight 是整場遊戲的 reward 的總和。那現在改成從某個時間 $t$ 開始，假設這個 action 是在 t 這個時間點所執行的，從 $t$ 這個時間點，一直到遊戲結束所有 reward 的總和，才真的代表這個 action 是好的還是不好的。

接下來再更進一步，我們把未來的 reward 做一個 discount，由此得到的回報被稱為

Discounted Return(折扣回報)

。為什麼要把未來的 reward 做一個 discount 呢？因為雖然在某一個時間點，執行某一個 action，會影響接下來所有的結果，有可能在某一個時間點執行的 action，接下來得到的 reward 都是這個 action 的功勞。但在比較真實的情況下， 如果時間拖得越長，影響力就越小。 比如說在第二個時間點執行某一個 action， 那我在第三個時間點得到的 reward 可能是在第二個時間點執行某個 action 的功勞，但是在 100 個 timestamp 之後，又得到 reward，那可能就不是在第二個時間點執行某一個 action 得到的功勞。 是以我們實際上在做的時候，你會在 R 前面乘上一個

discount factor

$\gamma$， $\gamma \in [0,1] $ ，一般會設個 0.9 或 0.99，

• $\gamma = 0$ : 隻關心即時獎勵；
• $\gamma = 1$ : 未來獎勵等同于即時獎勵。

如果 time stamp $t'$ 越大，它前面就乘上越多次的 $\gamma$，就代表說現在在某一個 state $s_t$， 執行某一個 action $a_t$ 的時候，它真正的 credit 是在執行這個 action 之後所有 reward 的總和，而且你還要乘上 $\gamma$。

舉一個例子， 你就想成說，這是遊戲的第 1、2、3、4 回合，那你在遊戲的第二回合的某一個 $s_t$ 你執行 $a_t$，它真正的 credit 得到的分數應該是，假設你這邊得到 +1 分 這邊得到 +3 分，這邊得到 -5 分，它的真正的 credit，應該是 1 加上一個 discount 的 credit 叫做 $\gamma$ 乘上 3，再加上 $\gamma^2$ 乘上 -5。

如果大家可以接受這樣子的話， 實際上就是這麼 implement 的。這個 b 可以是 state-dependent 的，事實上 b 它通常是一個 network 估計出來的，它是一個 network 的 output。

把 $R-b$ 這一項合起來，我們統稱為

advantage function

， 用

A

來代表 advantage function。Advantage function 是 dependent on s and a，我們就是要計算的是在某一個 state s 采取某一個 action a 的時候，advantage function 有多大。

在算 advantage function 時，你要計算 $\sum{t^{\prime}=t}^{T{n}} r_{t^{\prime}}^{n}$ ，你需要有一個互動的結果。你需要有一個 model 去跟環境做互動，你才知道接下來得到的 reward 會有多少。這個 advantage function 的上标是 $\theta$，$\theta$ 就是代表說是用 $\theta$ 這個 model 跟環境去做互動，然後你才計算出這一項。從時間 t 開始到遊戲結束為止，所有 r 的加和減掉 b，這個就叫 advantage function。

Advantage function 的意義就是，假設我們在某一個 state $s_t$ 執行某一個 action $a_t$，相較于其他可能的 action，它有多好。它在意的不是一個絕對的好，而是相對的好，即

相對優勢(relative advantage)

。因為會減掉一個 b，減掉一個 baseline， 是以這個東西是相對的好，不是絕對的好。 $A^{\theta}\left(s{t}, a{t}\right)$ 通常可以是由一個 network estimate 出來的，這個 network 叫做 critic。

REINFORCE: Monte Carlo Policy Gradient

蒙特卡洛可以了解為算法完成一個 episode 之後，再拿這個 episode 的資料來去 learn 一下，做一次更新。因為我們已經拿到了一整個 episode 的資料的話，也能夠拿到每一個 step 的 reward，我們可以很友善地去計算每個 step 的未來總收益，就是我們的期望，就是我們的回報 $G_t$ 。$G_t$ 是我們的未來總收益，$G_t$ 代表是從這個 step 後面，我能拿到的收益之和是多少。$G_1$是說我從第一步開始，往後能夠拿到多少的收益。$G_2$ 是說從第二步開始，往後一共能夠拿到多少的收益。

相比蒙特卡洛還是一個 episode 更新一次這樣子的方式，時序差分就是每個 step 都更新一下。每走一步，我就更新下，這樣的更新頻率會更高一點。它拿的是 Q-function 來去近似地表示我的未來總收益 $G_t$。

舉個例子來解釋時序差分強化學習和蒙特卡洛強化學習的差別，

• 時序差分強化學習是指在不清楚馬爾可夫狀态轉移機率的情況下，以采樣的方式得到不完整的狀态序列，估計某狀态在該狀态序列完整後可能得到的收益，并通過不斷地采樣持續更新價值。
• 蒙特卡洛強化學習則需要經曆完整的狀态序列後，再來更新狀态的真實價值。

例如，你想獲得開車去公司的時間，每天上班開車的經曆就是一次采樣。假設今天在路口 A 遇到了堵車，

• 時序差分強化學習會在路口 A 就開始更新預計到達路口 B、路口 C $\cdots \cdots$, 以及到達公司的時間；
• 而蒙特卡洛強化學習并不會立即更新時間，而是在到達公司後，再修改到達每個路口和公司的時間。

時序差分強化學習能夠在知道結果之前就開始學習，相比蒙特卡洛強化學習，其更快速、靈活。

我們介紹下政策梯度最簡單的也是最經典的一個算法

REINFORCE

。REINFORCE 用的是回合更新的方式。它在代碼上的處理上是先拿到每個 step 的 reward，然後計算每個 step 的未來總收益 $G_t$ 是多少，然後拿每個 $G_t$ 代入公式，去優化每一個 action 的輸出。是以編寫代碼時會有這樣一個函數，輸入每個 step 拿到的 reward，把這些 reward 轉成每一個 step 的未來總收益。因為未來總收益是這樣計算的：

上一個 step 和下一個 step 的未來總收益可以有這樣子的一個關系。是以在代碼的計算上，我們就是從後往前推，一步一步地往前推，先算 $G_T$，然後往前推，一直算到 $G_1$ 。

REINFORCE 的僞代碼主要看最後四行，先産生一個 episode 的資料，比如 $(s_1,a_1,G_1),(s_2,a_2,G_2),\cdots,(s_T,a_T,G_T)$。然後針對每個 action 來計算梯度。 在代碼上計算時，我們要拿到神經網絡的輸出。神經網絡會輸出每個 action 對應的機率值，然後我們還可以拿到實際的 action，把它轉成 one-hot 向量乘一下，我們可以拿到 $\ln \pi(A_t|S_t,\theta)$ 。

手寫數字識别是一個經典的多分類問題，就是輸入一張手寫數字的圖檔，經過神經網絡輸出的是各個分類的一個機率。目的是希望輸出的這個機率的分布盡可能地去貼近真實值的機率分布。因為真實值隻有一個數字 9，你用這個 one-hot 向量的形式去給它編碼的話，也可以把這個真實值了解為一個機率分布，9 的機率就是1，其他的機率就是 0。神經的網絡輸出一開始可能會比較平均，通過不斷地疊代，訓練優化之後，我會希望 9 輸出的機率可以遠高于其他數字輸出的機率。

如上圖所示，就是提高 9 對應的機率，降低其他數字對應的機率，讓神經網絡輸出的機率能夠更貼近這個真實值的機率分布。我們可以用

交叉熵(Cross Entropy)

來去表示兩個機率分布之間的差距。

我們看一下它的優化流程，就是怎麼讓這個輸出去逼近這個真實值。它的優化流程就是将圖檔作為輸入傳給神經網絡，神經網絡會判斷這個圖檔屬于哪一類數字，輸出所有數字可能的機率，然後再計算這個交叉熵，就是神經網絡的輸出 $Y_i$ 和真實的标簽值 $Y_i'$ 之間的距離 $-\sum Y{i}^{\prime} \cdot \log \left(Y{i}\right)$。我們希望盡可能地縮小這兩個機率分布之間的差距，計算出來的 cross entropy 可以作為這個 loss 函數傳給神經網絡裡面的優化器去優化，去自動去做神經網絡的參數更新。

類似地，policy gradient 預測每一個狀态下面應該要輸出的這個行動的機率，就是輸入狀态 $s_t$，然後輸出動作的機率，比如 0.02，0.08，0.09。實際上輸出給環境的動作是随機選了一個 action，比如說我選了右這個 action，它的 one-hot 向量就是 0，0，1。我們把神經網絡的輸出和實際動作帶入 cross entropy 的公式就可以求出輸出的機率和實際的動作之間的差距。但這個實際的動作 $a_t$ 隻是我們輸出的真實的 action，它并不一定是正确的 action，它不能像手寫數字識别一樣作為一個正确的标簽來去指導神經網絡朝着正确的方向去更新，是以我們在這裡會需要乘以一個獎勵回報 $G_t$。這個獎勵回報相當于是對這個真實 action 的評價，$G_t$ 具體越大，未來總收益越大，說明目前輸出的這個真實的 action 就越好，這個 loss 就越需要重視。如果 $G_t$ 越小，那就說明做這個 action $a_t$ 并沒有那麼的好，loss 的權重就要小一點，優化力度就小一點。通過這個和那個手寫輸入識别的一個對比，我們就知道為什麼 loss 會構造成這個樣子。

實際上我們在計算這個 loss 的時候，我們要拿到那個 $\ln \pi(A_t|S_t,\theta)$。我就拿我實際執行的這個動作，先取個 one-hot 向量，然後再拿到神經網絡預測的動作機率，這兩個一相乘，我就可以拿到算法裡面的那個 $\ln \pi(A_t|S_t,\theta)$。這個就是我們要構造的 loss。因為我們會拿到整個 episode 的所有的軌迹，是以我們可以對這一條整條軌迹裡面的每個 action 都去計算一個 loss。把所有的 loss 加起來之後，我們再扔給那個 adam 的優化器去自動更新參數就好了。

上圖是 REINFORCE 的流程圖。首先我們需要一個 policy model 來輸出動作機率，輸出動作機率後，我們用 sample 函數去得到一個具體的動作，然後跟環境互動過後，我們可以得到一整個 episode 的資料。拿到 episode 資料之後，我再去執行一下 learn() 函數，在 learn() 函數裡面，我就可以拿這些資料去構造 loss function，扔給這個優化器去優化，去更新我的 policy model。

PPO

From On-policy to Off-policy

在講 PPO 之前，我們先講一下 on-policy 和 off-policy 這兩種 training 方法的差別。 在 reinforcement learning 裡面，我們要 learn 的就是一個 agent。

• 如果要 learn 的 agent 跟和環境互動的 agent 是同一個的話， 這個叫做

  on-policy(同政策)

  。
• 如果要 learn 的 agent 跟和環境互動的 agent 不是同一個的話， 那這個叫做

  off-policy(異政策)

  。

比較拟人化的講法是如果要學習的那個 agent，一邊跟環境互動，一邊做學習這個叫 on-policy。 如果它在旁邊看别人玩，通過看别人玩來學習的話，這個叫做 off-policy。

為什麼我們會想要考慮 off-policy ？讓我們來想想 policy gradient。Policy gradient 是 on-policy 的做法，因為在做 policy gradient 時，我們需要有一個 agent、一個 policy 和一個 actor。這個 actor 先去跟環境互動去搜集資料，搜集很多的 $\tau$，根據它搜集到的資料，會按照 policy gradient 的式子去 update policy 的參數。是以 policy gradient 是一個 on-policy 的 algorithm。

PPO 是 policy gradient 的一個變形，它是現在 OpenAI 預設的 reinforcement learning 的 algorithm。

問題是上面這個 update 的式子中的 $E{\tau \sim p{\theta}(\tau)}$ 應該是你現在的 policy $\theta$ 所 sample 出來的 trajectory $\tau$ 做 expectation。一旦 update 了參數，從 $\theta$ 變成 $\theta'$ ，$p_\theta(\tau)$這個機率就不對了，之前 sample 出來的 data 就變的不能用了。是以 policy gradient 是一個會花很多時間來 sample data 的 algorithm，你會發現大多數時間都在 sample data，agent 去跟環境做互動以後，接下來就要 update 參數。你隻能 update 參數一次。接下來你就要重新再去 collect data， 然後才能再次update 參數。

這顯然是非常花時間的，是以我們想要從 on-policy 變成 off-policy。 這樣做就可以用另外一個 policy， 另外一個 actor $\theta'$ 去跟環境做互動。用 $\theta'$ collect 到的 data 去訓練 $\theta$。假設我們可以用 $\theta'$ collect 到的 data 去訓練 $\theta$，意味着說我們可以把 $\theta'$ collect 到的 data 用非常多次，我們可以執行 gradient ascent 好幾次，我們可以 update 參數好幾次， 都隻要用同一筆 data 就好了。因為假設 $\theta$ 有能力學習另外一個 actor $\theta'$ 所 sample 出來的 data 的話， 那 $\theta'$ 就隻要 sample 一次，也許 sample 多一點的 data， 讓 $\theta$ 去 update 很多次，這樣就會比較有效率。

Importance Sampling

具體怎麼做呢？這邊就需要介紹

importance sampling

的概念。假設你有一個 function $f(x)$，你要計算從 p 這個 distribution sample $x$，再把 $x$ 帶到 $f$ 裡面，得到 $f(x)$。你要該怎麼計算這個 $f(x)$ 的期望值？假設你不能對 p 這個distribution 做積分的話，那你可以從 p 這個 distribution 去 sample 一些 data $x^i$。把 $x^i$ 代到 $f(x)$ 裡面，然後取它的平均值，就可以近似 $f(x)$ 的期望值。

現在有另外一個問題，我們沒有辦法從 p 這個 distribution 裡面 sample data。假設我們不能從 p sample data，隻能從另外一個 distribution q 去 sample data，q 可以是任何 distribution。我們不能夠從 p 去 sample data，但可以從 q 去 sample $x$。我們從 q 去 sample $x^i$ 的話就不能直接套下面的式子。

因為上式是假設你的 $x$ 都是從 p sample 出來的。是以做一個修正，修正是這樣子的。期望值$E_{x \sim p}[f(x)]$其實就是$\int f(x) p(x) dx$，我們對其做如下的變換：

我們就可以寫成對 q 裡面所 sample 出來的 x 取期望值。我們從 q 裡面 sample x，然後再去計算 $f(x) \frac{p(x)}{q(x)}$，再去取期望值。是以就算我們不能從 p 裡面去 sample data，隻要能夠從 q 裡面去 sample data，然後代入上式，你就可以計算從 p 這個 distribution sample $x$ 代入 $f$ 以後所算出來的期望值。

這邊是從 q 做 sample，是以從 q 裡 sample 出來的每一筆 data，你需要乘上一個 weight 來修正這兩個 distribution 的差異，weight 就是 $\frac{p(x)}{q(x)}$。$q(x)$ 可以是任何 distribution，唯一的限制就是 $q(x)$ 的機率是 0 的時候，$p(x)$ 的機率不為 0，不然這樣會沒有定義。假設 $q(x)$ 的機率是 0 的時候，$p(x)$ 的機率也都是 0 的話，那這樣 $p(x)$ 除以 $q(x)$是有定義的。是以這個時候你就可以 apply importance sampling 這個技巧。你就可以從 p 做 sample 換成從 q 做 sample。

Importance sampling 有一些 issue。雖然理論上你可以把 p 換成任何的 q。但是在實作上， p 和 q 不能差太多。差太多的話，會有一些問題。什麼樣的問題呢？

雖然上式成立。但上式左邊是 $f(x)$ 的期望值，它的 distribution 是 p，上式右邊是 $f(x) \frac{p(x)}{q(x)}$ 的期望值，它的 distribution 是 q。如果不是算期望值，而是算 variance 的話。這兩個 variance 是不一樣的。兩個 random variable 的 mean 一樣，并不代表它的 variance 一樣。

我們可以代一下方差的公式：

$\operatorname{Var}{x \sim p}[f(x)]$ 和 $\operatorname{Var}{x \sim q}\left[f(x) \frac{p(x)}{q(x)}\right]$ 的差别在第一項是不同的， $\operatorname{Var}{x \sim q}\left[f(x) \frac{p(x)}{q(x)}\right]$ 的第一項多乘了$\frac{p(x)}{q(x)}$，如果$\frac{p(x)}{q(x)}$ 差距很大的話， $\operatorname{Var}{x \sim q}\left[f(x) \frac{p(x)}{q(x)}\right]$的 variance 就會很大。是以雖然理論上它們的 expectation 一樣，也就是說，你隻要對 p 這個 distribution sample 夠多次，q 這個 distribution sample 夠多，你得到的結果會是一樣的。但是假設你 sample 的次數不夠多，因為它們的 variance 差距是很大的，是以你就有可能得到非常大的差别。

舉個例子，當 $p(x)$ 和 $q(x)$ 差距很大的時候，會發生什麼樣的問題。假設藍線是 $p(x)$ 的distribution，綠線是 $q(x)$ 的 distribution，紅線是 $f(x)$。如果我們要計算$f(x)$的期望值，從 $p(x)$ 這個 distribution 做 sample 的話，那顯然 $E_{x \sim p}[f(x)]$ 是負的，因為左邊那塊區域 $p(x)$ 的機率很高，是以要 sample 的話，都會 sample 到這個地方，而 $f(x)$ 在這個區域是負的， 是以理論上這一項算出來會是負。

接下來我們改成從 $q(x)$ 這邊做 sample，因為 $q(x)$ 在右邊這邊的機率比較高，是以如果你 sample 的點不夠的話，那你可能都隻 sample 到右側。如果你都隻 sample 到右側的話，你會發現說，算 $E{x \sim q}\left[f(x) \frac{p(x)}{q(x)}\right]$這一項，搞不好還應該是正的。你這邊 sample 到這些點，然後你去計算它們的 $f(x) \frac{p(x)}{q(x)}$ 都是正的，是以你 sample 到這些點都是正的。 你取期望值以後，也都是正的。為什麼會這樣，因為你 sample 的次數不夠多，因為假設你 sample 次數很少，你隻能 sample 到右邊這邊。左邊這邊雖然機率很低，但也不是沒有可能被 sample 到。假設你今天好不容易 sample 到左邊的點，因為左邊的點，$p(x)$ 和 $q(x)$ 是差很多的， 這邊 $p(x)$ 很小，$q(x)$ 很大。今天 $f(x)$ 好不容易終于 sample 到一個負的，這個負的就會被乘上一個非常大的 weight ，這樣就可以平衡掉剛才那邊一直 sample 到 positive 的 value 的情況。最終你算出這一項的期望值，終究還是負的。但前提是你要 sample 夠多次，這件事情才會發生。但有可能 sample 不夠，$E{x \sim p}[f(x)]$ 跟 $E_{x \sim q}\left[f(x) \frac{p(x)}{q(x)}\right]$ 就有可能有很大的差距。這就是 importance sampling 的問題。

現在要做的事情就是把 importance sampling 用在 off-policy 的 case。把 on-policy training 的 algorithm 改成 off-policy training 的 algorithm。怎麼改呢，之前我們是拿 $\theta$ 這個 policy 去跟環境做互動，sample 出 trajectory $\tau$，然後計算 $R(\tau) \nabla \log p_{\theta}(\tau)$。

現在我們不用 $\theta$ 去跟環境做互動，假設有另外一個 policy $\theta'$，它就是另外一個actor。它的工作是他要去做demonstration，$\theta'$ 的工作是要去示範給$\theta$ 看。它去跟環境做互動，告訴 $\theta$ 說，它跟環境做互動會發生什麼事。然後，借此來訓練$\theta$。我們要訓練的是 $\theta$ ，$\theta'$ 隻是負責做 demo，負責跟環境做互動。

我們現在的 $\tau$ 是從 $\theta'$ sample 出來的，是拿 $\theta'$ 去跟環境做互動。是以 sample 出來的 $\tau$ 是從 $\theta'$ sample 出來的，這兩個distribution 不一樣。但沒有關系，假設你本來是從 p 做 sample，但你發現你不能夠從 p 做sample，是以我們不拿$\theta$ 去跟環境做互動。你可以把 p 換 q，然後在後面這邊補上一個 importance weight。現在的狀況就是一樣，把 $\theta$ 換成 $\theta'$ 後，要補上一個 importance weight $\frac{p{\theta}(\tau)}{p{\theta^{\prime}}(\tau)}$。這個 importance weight 就是某一個 trajectory $\tau$ 用 $\theta$ 算出來的機率除以這個 trajectory $\tau$，用 $\theta'$ 算出來的機率。這一項是很重要的，因為今天你要 learn 的是 actor $\theta$ 和 $\theta'$ 是不太一樣的。$\theta'$ 會見到的情形跟 $\theta$ 見到的情形不見得是一樣的，是以中間要做一個修正的項。

Q: 現在的 data 是從 $\theta'$ sample 出來的，從 $\theta$ 換成 $\theta'$ 有什麼好處呢？

A: 因為現在跟環境做互動是 $\theta'$ 而不是 $\theta$。是以 sample 出來的東西跟 $\theta$ 本身是沒有關系的。是以你就可以讓 $\theta'$ 做互動 sample 一大堆的 data，$\theta$ 可以 update 參數很多次，一直到 $\theta$ train 到一定的程度，update 很多次以後，$\theta'$ 再重新去做 sample，這就是 on-policy 換成 off-policy 的妙用。

實際在做 policy gradient 的時候，我們并不是給整個 trajectory $\tau$ 都一樣的分數，而是每一個 state-action 的 pair 會分開來計算。實際上 update gradient 的時候，我們的式子是長這樣子的。

我們用 $\theta$ 這個 actor 去 sample 出 $s_t$ 跟 $a_t$，sample 出 state 跟 action 的 pair，我們會計算這個 state 跟 action pair 它的 advantage， 就是它有多好。$A^{\theta}\left(s{t}, a{t}\right)$就是 accumulated 的 reward 減掉 bias，這一項就是估測出來的。它要估測的是，在 state $s_t$ 采取 action $a_t$ 是好的，還是不好的。那接下來後面會乘上 $\nabla \log p{\theta}\left(a{t}^{n} | s{t}^{n}\right)$，也就是說如果 $A^{\theta}\left(s{t}, a_{t}\right)$是正的，就要增加機率， 如果是負的，就要減少機率。

那現在用了 importance sampling 的技術把 on-policy 變成 off-policy，就從 $\theta$ 變成 $\theta'$。是以現在 $s_t$、$a_t$ 是$\theta'$ ，另外一個actor 跟環境互動以後所 sample 到的data。 但是拿來訓練要調整參數是 model $\theta$。因為 $\theta'$ 跟 $\theta$ 是不同的 model，是以你要做一個修正的項。這項修正的項，就是用 importance sampling 的技術，把 $s_t$、$a_t$ 用 $\theta$ sample 出來的機率除掉$s_t$、$a_t$ 用 $\theta'$ sample 出來的機率。

這邊 $A^{\theta}(s_t,a_t)$ 有一個上标 $\theta$，$\theta$ 代表說這個是 actor $\theta$ 跟環境互動的時候所計算出來的 A。但是實際上從 $\theta$ 換到 $\theta'$ 的時候，$A^{\theta}(s_t,a_t)$ 應該改成 $A^{\theta'}(s_t,a_t)$，為什麼？A 這一項是想要估測說現在在某一個 state 采取某一個 action，接下來會得到 accumulated reward 的值減掉 base line 。你怎麼估 A 這一項，你就會看在 state $s_t$，采取 action $a_t$，接下來會得到的 reward 的總和，再減掉 baseline。之前是 $\theta$ 在跟環境做互動，是以你觀察到的是 $\theta$ 可以得到的 reward。但現在是 $\theta'$ 在跟環境做互動，是以你得到的這個 advantage， 其實是根據 $\theta'$ 所 estimate 出來的 advantage。但我們現在先不要管那麼多， 我們就假設這兩項可能是差不多的。

那接下來，我們可以拆解 $p{\theta}\left(s{t}, a{t}\right)$ 和 $p{\theta'}\left(s{t}, a{t}\right)$，即

于是我們得到下式：

然後這邊需要做一件事情是，假設 model 是 $\theta$ 的時候，你看到$s_t$ 的機率，跟 model 是$\theta'$ 的時候，你看到$s_t$ 的機率是差不多的，即$p{\theta}(s_t)=p{\theta'}(s_t)$。因為它們是一樣的，是以你可以把它删掉，即

為什麼可以假設它是差不多的。舉例來說，會看到什麼 state 往往跟你會采取什麼樣的action 是沒有太大的關系的。比如說你玩不同的 Atari 的遊戲，其實你看到的遊戲畫面都是差不多的，是以也許不同的 $\theta$ 對 $s_t$ 是沒有影響的。但是有一個更直覺的理由就是這一項到時候真的要你算，你會算嗎？因為想想看這項要怎麼算，這一項你還要說我有一個參數$\theta$，然後拿$\theta$ 去跟環境做互動，算$s_t$ 出現的機率，這個你根本很難算。尤其是你如果 input 是image 的話， 同樣的 $s_t$ 根本就不會出現第二次。你根本沒有辦法估這一項， 是以幹脆就無視這個問題。

但是 $p{\theta}(a_t|s_t)$很好算。你手上有 $\theta$ 這個參數，它就是個 network。你就把$s_t$ 帶進去，$s_t$ 就是遊戲畫面，你把遊戲畫面帶進去，它就會告訴你某一個 state 的 $a_t$ 機率是多少。我們其實有個 policy 的 network，把 $s_t$ 帶進去，它會告訴我們每一個 $a_t$ 的機率是多少。是以 $\frac{p{\theta}\left(a{t} | s{t}\right)}{p{\theta^{\prime}}\left(a{t} | s_{t}\right)}$ 這一項，你隻要知道$\theta$ 和 $\theta'$ 的參數就可以算。

現在我們得到一個新的 objective function。

式(1)是 gradient，其實我們可以從 gradient 去反推原來的 objective function。這邊有一個公式

我們可以用這個公式來反推 objective function，要注意一點，對 $\theta$ 求梯度時，$p{\theta^{\prime}}(a{t} | s{t})$ 和 $A^{\theta^{\prime}}\left(s{t}, a_{t}\right)$ 都是常數。

是以實際上，當我們 apply importance sampling 的時候，要去 optimize 的那一個 objective function 就長這樣子，我們把它寫作 $J^{\theta^{\prime}}(\theta)$。為什麼寫成 $J^{\theta^{\prime}}(\theta)$ 呢，這個括号裡面那個 $\theta$ 代表我們要去 optimize 的那個參數。$\theta'$ 是說我們拿 $\theta'$ 去做 demonstration，就是現在真正在跟環境互動的是 $\theta'$。因為 $\theta$ 不跟環境做互動，是 $\theta'$ 在跟環境互動。

然後你用 $\theta'$ 去跟環境做互動，sample 出 $s_t$、$a_t$ 以後，你要去計算 $s_t$ 跟 $a_t$ 的 advantage，然後你再去把它乘上 $\frac{p{\theta}\left(a{t} | s{t}\right)}{p{\theta^{\prime}}\left(a{t} | s{t}\right)}$。$\frac{p{\theta}\left(a{t} | s{t}\right)}{p{\theta^{\prime}}\left(a{t} | s{t}\right)}$ 是好算的，$A^{\theta^{\prime}}\left(s{t}, a{t}\right)$ 可以從這個 sample 的結果裡面去估測出來的，是以 $J^{\theta^{\prime}}(\theta)$ 是可以算的。實際上在 update 參數的時候，就是按照式(1) 來 update 參數。

PPO

我們可以把 on-policy 換成 off-policy，但 importance sampling 有一個 issue，如果 $p{\theta}\left(a{t} | s{t}\right)$ 跟 $p{\theta'}\left(a{t} | s{t}\right)$ 差太多的話，這兩個 distribution 差太多的話，importance sampling 的結果就會不好。怎麼避免它差太多呢？這個就是

Proximal Policy Optimization (PPO)

在做的事情。它實際上做的事情就是這樣，在 off-policy 的方法裡要 optimize 的是 $J^{\theta^{\prime}}(\theta)$。但是這個 objective function 又牽涉到 importance sampling。在做 importance sampling 的時候，$p{\theta}\left(a{t} | s{t}\right)$ 不能跟 $p{\theta'}\left(a{t} | s{t}\right)$差太多。你做 demonstration 的 model 不能夠跟真正的 model 差太多，差太多的話 importance sampling 的結果就會不好。我們在 training 的時候，多加一個 constrain。這個 constrain 是 $\theta$ 跟 $\theta'$ output 的 action 的 KL divergence，簡單來說，這一項的意思就是要衡量說 $\theta$ 跟 $\theta'$ 有多像。

然後我們希望在 training 的過程中，learn 出來的 $\theta$ 跟 $\theta'$ 越像越好。因為如果 $\theta$ 跟 $\theta'$ 不像的話，最後的結果就會不好。是以在 PPO 裡面有兩個式子，一方面是 optimize 本來要 optimize 的東西，但再加一個 constrain。這個 constrain 就好像那個 regularization 的 term 一樣，在做 machine learning 的時候不是有 L1/L2 的 regularization。這一項也很像 regularization，這樣 regularization 做的事情就是希望最後 learn 出來的 $\theta$ 不要跟 $\theta'$ 太不一樣。

PPO 有一個前身叫做 TRPO，TRPO 的式子如下式所示。

它與 PPO 不一樣的地方 是 constrain 擺的位置不一樣，PPO是直接把 constrain 放到你要 optimize 的那個式子裡面，然後你就可以用 gradient ascent 的方法去 maximize 這個式子。但 TRPO 是把 KL divergence 當作 constrain，它希望 $\theta$ 跟 $\theta'$ 的 KL divergence 小于一個$\delta$。如果你是用 gradient based optimization 時，有 constrain 是很難處理的。

PPO 是很難處理的，因為它是把 KL divergence constrain 當做一個額外的 constrain，沒有放 objective 裡面，是以它很難算。是以不想搬石頭砸自己的腳的話， 你就用 PPO 不要用 TRPO。看文獻上的結果是，PPO 跟 TRPO 可能 performance 差不多，但 PPO 在實作上比 TRPO 容易的多。

Q: KL divergence 到底指的是什麼？

A: 這邊我是直接把 KL divergence 當做一個 function，input 是 $\theta$ 跟 $\theta'$，但我的意思并不是說把 $\theta$ 或 $\theta'$ 當做一個distribution，算這兩個distribution 之間的距離，我不是這個意思。所謂的 $\theta$ 跟 $\theta'$ 的距離并不是參數上的距離，而是 behavior 上的距離。

假設你有一個 model，有一個 actor 它是 $\theta$，你有另外一個 actor 的參數是 $\theta'$ ，所謂參數上的距離就是你算這兩組參數有多像。我今天所講的不是參數上的距離， 而是它們行為上的距離。就是你先帶進去一個 state s，它會對這個 action 的 space output 一個 distribution。假設你有 3 個 actions，3 個可能的 actions 就 output 3 個值。那今天所指的 distance 是 behavior distance。也就是說，給同樣的 state 的時候，輸出 action 之間的差距。這兩個 actions 的 distribution 都是一個機率分布。是以就可以計算這兩個機率分布的 KL divergence。把不同的 state output 的這兩個 distribution 的 KL divergence 平均起來才是我這邊所指的兩個 actor 間的 KL divergence。你可能說怎麼不直接算這個 $\theta$ 或 $\theta'$ 之間的距離，甚至不要用 KL divergence 算，L1 跟 L2 的 norm 也可以保證 $\theta$ 跟 $\theta'$ 很接近。在做 reinforcement learning 的時候，之是以我們考慮的不是參數上的距離，而是 action 上的距離，是因為很有可能對 actor 來說，參數的變化跟 action 的變化不一定是完全一緻的。有時候你參數小小變了一下，它可能 output 的行為就差很多。或是參數變很多，但 output 的行為可能沒什麼改變。是以我們真正在意的是這個actor 的行為上的差距，而不是它們參數上的差距。是以在做 PPO 的時候，所謂的 KL divergence 并不是參數的距離，而是 action 的距離。

我們來看一下

PPO1

的 algorithm。它先 initial 一個 policy 的參數 $\theta^0$。然後在每一個 iteration 裡面呢，你要用參數 $\theta^k$，$\theta^k$ 就是你在前一個 training 的 iteration得到的 actor 的參數，你用 $\theta^k$ 去跟環境做互動，sample 到一大堆 state-action 的pair。

然後你根據 $\theta^k$ 互動的結果，估測一下$A^{\theta^{k}}\left(s{t}, a{t}\right)$。然後你就 apply PPO 的 optimization 的 formulation。但跟原來的policy gradient 不一樣，原來的 policy gradient 隻能 update 一次參數，update 完以後，你就要重新 sample data。但是現在不用，你拿 $\theta^k$ 去跟環境做互動，sample 到這組 data 以後，你可以讓 $\theta$ update 很多次，想辦法去 maximize objective function。這邊 $\theta$ update 很多次沒有關系，因為我們已經有做 importance sampling，是以這些experience，這些 state-action 的 pair 是從 $\theta^k$ sample 出來的沒有關系。$\theta$ 可以 update 很多次，它跟 $\theta^k$ 變得不太一樣也沒有關系，你還是可以照樣訓練 $\theta$。

在 PPO 的 paper 裡面還有一個

adaptive KL divergence

。這邊會遇到一個問題就是 $\beta$ 要設多少，它就跟那個regularization 一樣。regularization 前面也要乘一個 weight，是以這個 KL divergence 前面也要乘一個 weight，但 $\beta$ 要設多少呢？是以有個動态調整 $\beta$ 的方法。

• 在這個方法裡面呢，你先設一個 KL divergence，你可以接受的最大值。然後假設你發現說你 optimize 完這個式子以後，KL divergence 的項太大，那就代表說後面這個 penalize 的 term 沒有發揮作用，那就把 $\beta$ 調大。
• 那另外你定一個 KL divergence 的最小值。如果發現 optimize 完上面這個式子以後，KL divergence 比最小值還要小，那代表後面這一項的效果太強了，你怕他隻弄後面這一項，那 $\theta$ 跟 $\theta^k$ 都一樣，這不是你要的，是以你這個時候你叫要減少 $\beta$。

是以 $\beta$ 是可以動态調整的。這個叫做

adaptive KL penalty

。

如果你覺得算 KL divergence 很複雜。有一個

PPO2

。PPO2 要去 maximize 的 objective function 如下式所示，它的式子裡面就沒有 KL divergence 。

這個式子看起來有點複雜，但實際 implement 就很簡單。我們來實際看一下說這個式子到底是什麼意思。 min 這個 operator 做的事情是第一項跟第二項裡面選比較小的那個。第二項前面有個 clip function，clip 這個 function 的意思是說，在括号裡面有 3 項，如果第一項小于第二項的話，那就 output $1-\varepsilon$ 。第一項如果大于第三項的話，那就output $1+\varepsilon$。 $\varepsilon$ 是一個 hyper parameter，你要 tune 的，你可以設成 0.1 或 設 0.2 。 假設這邊設 0.2 的話，如下式所示

如果$\frac{p{\theta}\left(a{t} | s{t}\right)}{p{\theta^{k}}\left(a{t} | s{t}\right)}$算出來小于 0.8，那就當作 0.8。如果算出來大于 1.2，那就當作1.2。

我們先看一下下面這項這個算出來到底是什麼的東西。

上圖的橫軸是 $\frac{p{\theta}\left(a{t} | s{t}\right)}{p{\theta^{k}}\left(a{t} | s{t}\right)}$，縱軸是 clip function 實際的輸出。

• 如果 $\frac{p{\theta}\left(a{t} | s{t}\right)}{p{\theta^{k}}\left(a{t} | s{t}\right)}$ 大于$1+\varepsilon$，輸出就是 $1+\varepsilon$。
• 如果小于 $1-\varepsilon$， 它輸出就是 $1-\varepsilon$。
• 如果介于 $1+\varepsilon$ 跟 $1-\varepsilon$ 之間， 就是輸入等于輸出。

• $\frac{p{\theta}\left(a{t} | s{t}\right)}{p{\theta^{k}}\left(a{t} | s{t}\right)}$ 是綠色的線；
• $\operatorname{clip}\left(\frac{p{\theta}\left(a{t} | s{t}\right)}{p{\theta^{k}}\left(a{t} | s{t}\right)}, 1-\varepsilon, 1+\varepsilon\right)$ 是藍色的線；
• 在綠色的線跟藍色的線中間，我們要取一個最小的。假設前面乘上的這個 term A，它是大于0 的話，取最小的結果，就是紅色的這一條線。

如果 A 小于0 的話，取最小的以後，就得到紅色的這一條線。 這一個式子雖然看起來有點複雜，實作起來是蠻簡單的，因為這個式子想要做的事情就是希望 $p{\theta}(a{t} | s{t})$ 跟$p{\theta^k}(a{t} | s{t})$，也就是你拿來做 demonstration 的 model， 跟你實際上 learn 的 model，在 optimize 以後不要差距太大。那你要怎麼讓它做到不要差距太大呢？

如果 A 大于 0，也就是某一個 state-action 的pair 是好的。那我們希望增加這個 state-action pair 的機率。也就是說，我們想要讓 $p{\theta}(a{t} | s{t})$ 越大越好，但它跟 $p{\theta^k}(a{t} | s{t})$ 的比值不可以超過 $1+\varepsilon$。如果超過 $1+\varepsilon$ 的話，就沒有 benefit 了。紅色的線就是我們的 objective function，我們希望 objective 越大越好，我們希望 $p{\theta}(a{t} | s{t})$ 越大越好。但是$\frac{p{\theta}\left(a{t} | s{t}\right)}{p{\theta^{k}}\left(a{t} | s_{t}\right)}$隻要大過 $1+\varepsilon$，就沒有 benefit 了。

是以今天在 train 的時候，當 $p{\theta}(a{t} | s{t})$ 被 train 到 $\frac{p{\theta}\left(a{t} | s{t}\right)}{p{\theta^{k}}\left(a{t} | s_{t}\right)}$大于 $1+\varepsilon$ 時，它就會停止。

假設 $p{\theta}(a{t} | s{t})$ 比 $p{\theta^k}(a{t} | s{t})$ 還要小，那我們的目标是要讓 $p{\theta}(a{t} | s_{t})$ 越大越好。

• 假設這個 advantage 是正的，我們希望 $p{\theta}(a{t} | s{t})$ 越大越好。假設這個 action 是好的，我們當然希望這個 action 被采取的機率越大越好。是以假設 $p{\theta}(a{t} | s{t})$ 還比 $p{\theta^k}(a{t} | s_{t})$ 小，那就盡量把它挪大，但隻要大到 $1+\varepsilon$ 就好。
• 負的時候也是一樣，如果某一個 state-action pair 是不好的，我們希望把 $p{\theta}(a{t} | s{t})$ 減小。如果 $p{\theta}(a{t} | s{t})$ 比$p{\theta^k}(a{t} | s{t})$ 還大，那你就盡量把它壓小，壓到$\frac{p{\theta}\left(a{t} | s{t}\right)}{p{\theta^{k}}\left(a{t} | s_{t}\right)}$是$1-\epsilon$ 的時候就停了，就不要再壓得更小。

這樣的好處就是， 你不會讓 $p{\theta}(a{t} | s{t})$ 跟 $p{\theta^k}(a{t} | s{t})$ 差距太大。要實作這個東西，很簡單。

上圖是 PPO 跟其它方法的比較。Actor-Critic 和 A2C+Trust Region 方法是 actor-critic based 的方法。PPO 是紫色線的方法，這邊每張圖就是某一個 RL 的任務，你會發現說在多數的 cases 裡面，PPO 都是不錯的，不是最好的，就是第二好的。