# 李宏毅_ATDL_DRL Lecture 1
###### tags: `Hung-yi Lee` `NTU` `Deep Reinforcement Learning`
[課程撥放清單](https://www.youtube.com/playlist?list=PLJV_el3uVTsODxQFgzMzPLa16h6B8kWM_)
## DRL Lecture 1: Policy Gradient (Review)
[課程連結](https://www.youtube.com/watch?v=z95ZYgPgXOY&list=PLJV_el3uVTsODxQFgzMzPLa16h6B8kWM_)
Policy Gradient的進階版，Proximal Policy Optimization(PPO)，這在OpenAI是預設的演算法。
### DeepMind

[影片連結](https://www.youtube.com/watch?v=gn4nRCC9TwQ)

影片中可以看到機器人在失誤過程中學習。
### OpenAI

[影片連結](https://openai.com/blog/openai-baselines-ppo/)

機器人的目標是拿到紅色的球，過程中它會不斷的被白色的球攻擊。
### Basic Components

這邊先複習Policy Gradient。

在RL內有三個component：
* Actor
* Env
* Reward Function

其中Env與Reward Function是無法控制的，屬於事先給定，只有Actor是我們可以調整的，透過調整Policy來提高得到的Reward。
### Policy of Actor

Policy-$\pi$決定Actor的行為，所謂的Policy就是給定一個外界的輸入，然後輸出決定Actor現在應該執行的行為。如果以`nn`來實作，那它的參數就是$\theta$。

以`nn`來實作：
* input就是機器目前看到什麼，如果是電玩那就是遊戲的畫面，可以是matrix，也可以是vector
* output就是機器看到畫面之後決定要採取的行為
* 假設可以採取的行為有三個，那機器的輸出就是三個行為的機率
### Example: Playing Video Game

以遊戲為例：
* 首先actor目到一個遊戲畫面
* $s_1$
* 機器看到畫面之後決定採取第一個action
* $a_1$
* 採取一個action之後決定得到多少reward
* $r_1=0$
* 接下來機器看到下一個畫面
* $s_2$
* 決定開火
* $a_2$
* 得到reward
* $r_2=5$

整個過程一直循環，直到遊戲結束，一場遊戲稱為『episode』，整個遊戲過程的reward以$R$來表示，即$R=\sum_{t=1}^Tr_t$，actor的目的就是得到最大的reward。
### Actor, Environment, Reward

Env本身也可以視為一個function。

以圖形化來瞭解整個RL的過程，Env的output做為Actor的input，Actor的output再做為Env的input...一直到得到結束的訊號，將整個過程的input、output串起來即為**Trajectory**，$\tau=\left\{s_1,a_1,s_2,a_2,...,s_T,a_T\right\}$

在actor的參數$\theta$給定的情況下，可以計算某一個trajectory發生的機率：
* $p_\theta(\tau)=p(s_1)p_\theta(a_1 \vert s_1)p(s_2 \vert s_1,a_1)p_\theta(a_2 \vert s_2)p(s_3 \vert s_2,a_2)...$
* $=p(s_1)\prod_{t=1}^T p_\theta(a_t \vert s_t)p(s_{t+1} \vert s_t,a_t)$

機率取決於Env與Actor，其中$p(s_{t+1} \vert s_t,a_t)$代表Env，這項通常無法控制，可以控制的是$p_\theta(a_t \vert s_t)$，這取決於actor的參數$\theta$
### Actor, Environment, Reward

Reward function根據在某個state-$s$採取什麼樣的action-$a$會得到多少reward-$r$，將一場trajectory-$\tau$的reward加總即為$R(\tau)=\sum^T_{t=1}r_t$。

我們要的就是調整actor的參數$\theta$來讓$R$的值愈大愈好，但因為Actor本身是有隨機性的，即使相同的state可能得到的action也不一樣，因此$R$本身是一個random variable，你無法計算它，能計算的只有它的期望值：
* $\bar{R}_\theta=\sum_\tau R(\tau)p_\theta(\tau)=E_{\tau \sim p_\theta(\tau)}\left[R(\tau)\right]$
* 在給定$\theta$的情況下$R$的期望值是多少
* 窮舉所有可能的trajectory-$\tau$，根據$\theta$計算某一個$\tau$出現的機率，計算這個$\tau$的total reward，再weighted fair這個$\tau$出現的機率，就是期望值
* 從$p_\theta(\tau)$這個分佈中sample一個trajectory-$\tau$，計算$R(\tau)$的期望值

### Policy Gradient

知道期望值怎麼計算之後就可以利用Gradient Ascent來最大化reward function，只是單純在更新參數的時候由減調整為加。

$\bar{R}_\theta=\sum_\tau R(\tau)p_\theta(\tau)$，那$\nabla \bar{R}_\theta$該如何解：
* $\nabla \bar{R}_\theta = \sum_\tau R(\tau) \nabla p_\theta(\tau)$
* 只有$p_\theta$是與$\theta$有關，因此gradient是寫在這$\nabla p_\theta$
* $R(\tau)$並不需要是可微的
* $=\sum_\tau R(\tau) p_\theta(\tau) \dfrac{\nabla p_\theta(\tau)}{p_\theta(\tau)}$
* 分子分母同乘$p_\theta(\tau)$
* $=\sum_\tau R(\tau) p_\theta(\tau) \nabla \log p_\theta(\tau)$
* 公式：$\nabla f(x) = f(x) \nabla \log f(x)$
* 對某一個function計算gradient公式
* $E_{\tau \sim p_\theta(\tau)}\left[R(\tau) \nabla \log p_\theta(\tau)\right]$
* 因為有針對$R(\tau)$與$\nabla \log p_\theta(\tau)$做weighted fair $p_\theta(\tau)$，因此可以寫成期望值的型式
* 從$p_\theta(\tau)$這個分佈中sample出一個$\tau$計算$R(\tau) \nabla \log p_\theta(\tau)$，然後對所有可能的$\tau$做計算
* $\approx \dfrac{1}{N} \sum^N_{n=1} R(\tau^n) \nabla \log p_\theta(\tau^n)$
* 因為無法窮舉所有的可能，因此以sample的方式計算平均值
* $=\dfrac{1}{N} \sum^N_{n=1} \sum^{T_n}_{t=1} R(\tau^n) \nabla \log p_\theta(a^n_t \vert s^n_t)$
* $p_\theta(\tau^n)$是可以計算的，它包含兩個，一個環境Env，一個是Agent，而對Env做計算是沒有用的，因為Env與$\theta$無關。真正會計算的只有$\log p_\theta(a^n_t \vert s^n_t)$
* $(a^n_t \vert s^n_t)$是整個trajectory內的某一個時間點的成對資料(pair)，如果這個pair會導致整個trajectory的reward變大，那就要增加它出現的機率，反之則減少。
### Policy Gradient

實作上就是套入稍早所提到的公式計算即可：
* $\theta \leftarrow \theta + \eta \nabla \bar{R}_\theta$
* $\nabla \bar{R}_\theta=\dfrac{1}{N} \sum^N_{n=1} \sum^{T_n}_{t=1} R(\tau^n) \nabla \log p_\theta(a^n_t \vert s^n_t)$

首先要先收集很多$s,a$的成對資料：
* 拿Agent與環境互動，得到一堆的遊戲記錄
* $\tau^n: (s^n_t, a^n_t), R(\tau^n)$
* state是有隨機性的，相同的state不見得會有相同的action
* 將收集到的資料帶入公式，計算梯度
* 計算log probability-$\log p_\theta(a^n_t \vert s^n_t)$，然後取gradient-$\nabla$，然後乘上weight，即這場遊戲的reward-$R(\tau^n)$
* 更新模型
* 重新收集資料
* ....

一般Policy Gradient對收集到的資料就只會用到一次，下次更新的時候並不會再用到。
### Implementation

實作上幾個小細節分享：
1. 把它想成是一個分類問題
2. input image(state)，output action
3. 搜集的訓練資料要有input，output的成對資料
4. 目標並不是要判斷有什麼物件在image內，而是看到這張image要採取什麼樣的行為

一般分類問題的object function都是最小化cross-entropy，相對的也就是最大化log likelihood：
$\dfrac{1}{N} \sum_{n=1}^N \sum_{t=1}^{T_n} \log p_\theta(a^n_t \vert s_t^n) \rightarrow \dfrac{1}{N} \sum_{n=1}^N \sum_{t=1}^{T_n} \nabla \log p_\theta(a^n_t \vert s_t^n)$

而RL問題中與分類問題唯一的不同就是前面加了一個權重，要注意，這個權重-$R(\tau^n)$是整場遊戲的reward，而不是當下某一個state採取某一個action所得到的reward：
$\dfrac{1}{N} \sum_{n=1}^N \sum_{t=1}^{T_n} R(\tau^n) \log p_\theta(a^n_t \vert s_t^n) \rightarrow \dfrac{1}{N} \sum_{n=1}^N \sum_{t=1}^{T_n} R(\tau^n) \nabla \log p_\theta(a^n_t \vert s_t^n)$
### Tip 1: Add a Baseline

$\nabla \bar{R}_\theta \approx \dfrac{1}{N} \sum_{n=1}^N \sum_{t=1}^{T_n} R(\tau^n) \nabla \log p_\theta(a^n_t \vert s_t^n)$

前面有說明過，直觀來看這個數學式就是讓某個state所採取的action如果讓reward變大(正向的reward)，那出現的機率就提高，反之就減少。但某些情況下是不會有負向的reward，這時候給model的訊息就是每一個action出現的機率都提升。

這看起來似乎沒有什麼問題，因為過程中還會計算權重$R(\tau^n)$，權重大的就上升多，權重小的就上升少，而機率的總合就是一而以，因此權重大的就上升，權重小的就下降。但，實務上我們是sample，因此某些action可能是不會被sample到的，簡報為例，action-a可能是從沒被sample到的，它的機率會因此而下降，但它可能是一個好的action，只是運氣不好一直沒有被sample到。

要預防這種情況的發生，就是在式子裡減掉一項『b-baseline』：
$\nabla \bar{R}_\theta \approx \dfrac{1}{N} \sum_{n=1}^N \sum_{t=1}^{T_n} (R(\tau^n) - b) \nabla \log p_\theta(a^n_t \vert s_t^n)$

加入baseline這個項目之後，就可以讓輸出的值有正有負，設置上可以取期望值(平均)-$b \approx E \left[(\tau)\right]$
### Tip2: Assign Suitable Credit

$\nabla \bar{R}_\theta \approx \dfrac{1}{N} \sum_{n=1}^N \sum_{t=1}^{T_n} (R(\tau^n) - b) \nabla \log p_\theta(a^n_t \vert s_t^n)$

根據上面的數學式可以發現到，在某一個trajectory內的所有action所得到的weight都是相同的$(R(\tau^n) - b)$，這顯然是不公平的，因為action有好有壞，整場遊戲所得的reward低，並不代表整場遊戲的action都是不好，反之也不代表整場遊戲的action都是好的，因此我們希望可以更細項的針對action來給予權重。

簡報範例，假設每一個trajectory都只有三個state就結束：
* 左邊整場遊戲總得reward=5+0+(-2)=+3
* 整場遊戲的所得來自於第一個action，與其它兩個action無關，甚至有可能是因為第二個action才導致失誤，造成第三個action所得是-2
* 三個action都乘上權重+3
* 右邊整場遊戲總得reward=(-5)+0+(-2)=-7
* 整場遊戲的失分來自於第一個action，與其它兩個action無關，甚至有可能是因為第二個action才導致回穩，造成第三個action所得是-2
* 三個action都乘上權重-7

如果我們調整讓每一個action的權重與上一個action的reward無關，只跟它以後的action有關：
* $\nabla \bar{R}_\theta \approx \dfrac{1}{N} \sum_{n=1}^N \sum_{t=1}^{T_n} (\sum^{T_n}_{t'=t}r^n_{t'} - b) \nabla \log p_\theta(a^n_t \vert s_t^n)$
* $\sum^{T_n}_{t'=t}r^n_{t'}$：計算某一個時間點$t$之後的reward總合

這樣調整之後，只計算某一個時間點之後的reward，就能代表某一個action執行之後的結果究竟是不是好的，調整之後的範例第二、第三個action的權重就通通是-2。這樣就能突顯出某一個action對整個結果的影響是好還是壞：
* 左邊的範例
* 第一個action讓後續遊戲得到+3，因此權重為+3
* 第二個action讓後續遊戲得到-2，因此權重為-2
* 第三個action權重為最終結果-2
* 右邊的範例
* 第一個action讓後續遊戲得到-7，因此權重為-7
* 第二個action讓後續遊戲得到-2，因此權重為-2
* 第三個action權重為最終結果-2
### Tip2: Assign Suitable Credit

更進一步的調整，雖然某一個action可以造成後續的影響，但愈後面它所擁有的影響力就愈少，因此會再加入一個項目$\gamma^{t'-t}$來減少對後面action所得的reward的影響。($\gamma$設置為小於1的數值，也許0.9，愈後面就想成每次都打9折，對100個action之後的影響就是100次9折)，因此數學式修正如下：
* $\nabla \bar{R}_\theta \approx \dfrac{1}{N} \sum_{n=1}^N \sum_{t=1}^{T_n} (\sum^{T_n}_{t'=t} \gamma^{t'-t} r^n_{t'} - b) \nabla \log p_\theta(a^n_t \vert s_t^n)$

$b$的部份較為複雜，後續課程會提到，稍微調整式子，將原始$R(\tau^n) - b)$的項目以$A^\theta(s_t,a_t)$來表示，統稱為Advantage Function：
* $\nabla \bar{R}_\theta \approx \dfrac{1}{N} \sum_{n=1}^N \sum_{t=1}^{T_n} (A^\theta(s_t,a_t)) \nabla \log p_\theta(a^n_t \vert s_t^n)$
* $A^\theta(s_t,a_t)$：在某一個state-$s_t$執行某一個action-$a_t$，相較於其它可能的action，現在執行的這一個有多好。
* $A^\theta$，其$\theta$代表用目前參數為$\theta$的model與環境互動
* 通常可以由一個`nn`來估測，即critic，後續課程提到。