# DRL 介紹

### 簡介
  本人主要依據[李弘毅老師的 DRL 課程](https://www.youtube.com/watch?v=z95ZYgPgXOY&list=PLJV_el3uVTsODxQFgzMzPLa16h6B8kWM_&index=1)，搭配其他網路上的資料與論文，撰寫出這篇 DRL 入門介紹。

## Reinforcement Learning (RL) 介紹
  首先我們先來看最基本的 RL 架構。如下圖所示，一個 RL 架構包含 Agent (又稱 actor)、Environment、State (又稱 observation)、Reward 和 Action。我們考慮在時槽 $n$ 時，Agent 會根據上一個時間的 Reward $r[n-1]$ 和這個時間的 State $s[n]$ 來當作輸入，透過一個 Policy $\pi$ 來決定這個時間的 action $a[n]$，這個 policy $\pi$ 就是你要訓練的網路，假設目前網路訓練的參數為 $\theta$。而 environment 會根據 action $a[n]$ 來給出這個時間的 Reward $r[n]$ 並回傳給 Agent，environment 也會更新 State 成 $s[n+1]$。


註: 為甚麼 state 又稱 observation? 有些人認為 state 是模型最真實的狀態，而我們用來訓練的資料只是我們從外界觀察到模型的變化過程，state 往往無法被觀察到或難以被定義出來，因此稱這個觀察為 observation。這裡提到很重要的一點：「observation 是我們從外界觀察到模型的變化過程」，因此你如何定義 observation 可以跟你的真實狀態越接近，那模型就越接近真實的模型。

  我們稱一個互動過程為一個 episode，舉例可能是下一盤棋、玩一場遊戲等等。假設一個 episode 耗費的時間為 $N$，那 Agent 的目標就是要最大化

$$R=\sum^{N}_{n=1}r[n]$$

  一個 trajectory $\tau$ 可以被定義為一段時間 $N$ 內的所有 state 跟 action，而我們可以定義產生這個 $\tau$ 的機率為

\begin{equation}
p_{\theta}(\tau)=p(s[1])\prod_{n=1}^{N}p_{\theta}(a[n]|s[n])p(s[n+1]|s[n],a[n])
\end{equation}

其中 $p_{\theta}(a[n]|s[n])$ 是 Agent 可以決定的 action，而 $p(s[n+1]|s[n],a[n])$ 是 environment 決定的 state。接著我們用 $R(\tau)=\sum^{N}_{n=1}r[n]$ 表示一個給定的 $\tau$ 的 reward，由於 $\tau$ 是一個隨機變數，因此 reward 也是一個隨機變數。因此我們要最大化的是 reward 的期望值:

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

那做法就是對 $\overline{R}_{\theta}$ 做 gradient 來求最大值 :

\begin{align*}
\nabla \overline{R}_{\theta}
&= \sum_{\tau}R(\tau)\nabla p_{\theta}(\tau) \\
&= \sum_{\tau}R(\tau)p_{\theta}(\tau)\frac{\nabla p_{\theta}(\tau)}{p_{\theta}(\tau)}\\
&= \sum_{\tau}R(\tau)p_{\theta}(\tau)\nabla\log(p_{\theta}(\tau))\\
&= E_{\tau\sim p_{\theta}(\tau)}[R(\tau)\nabla\log(p_{\theta}(\tau))]\\
&\approx \frac{1}{M}\sum^{M}_{m=1}R(\tau^m)\nabla\log(p_{\theta}(\tau^m))\\
&= \frac{1}{M}\sum^{M}_{m=1}\sum^{N_m}_{n=1}R(\tau^m)\nabla\log(p_{\theta}(a^m[n]|s^m[n]))
\end{align*}

其中近似是因為我們沒辦法求出所有 $\tau$，因此用蒙地卡羅方法撒點來求出近似期望值，第六個等號是因為 $p(s[n+1]|s[n],a[n])$ 跟 $\theta$ 沒有關係，所以微分會不見。直觀概念就是若因這個 state 產生的 action 可以讓 reward 變大，那我們就要增加這個執行的機率。這邊要注意的是：「每個 $n$ 最終乘上的 weight 是這次 episode 的 reward，並不是當下時間的 reward。」

  在實作上，有以下幾點可以注意：
1. 每次更新完 $\theta$ ，我們都會需要重新 sample 很多 trajectories。
2. 由於 reward 可能一直都是正的，因此我們在算 gradient 時可以把 reward 減掉一個 baseline $b$，有點像中間值的概念，讓 reward 可以有正有負，這樣可以避免有些 action 因為沒有被 sample 到，經過權重調整且正規化後，這個 action 反而被選到的機率被降低。整題來說可以改寫為

$$\nabla \overline{R}_{\theta}=\frac{1}{M}\sum^{M}_{m=1}\sum^{N_m}_{n=1}(R(\tau^m)-b)\nabla\log(p_{\theta}(a^m[n]|s^m[n])) $$

3. 由於當下的行動跟之前的行動應該是無關的，如果都乘上同一個 reward 其實不公平，因此比較公平的算法是當下的 action 應該乘上他發生的時間以後計算出來的 weight。此外，我們會在乘上一個 $\gamma$ 來代表這個這個 action 對未來步驟的影響力 (discount)，時間越久，這個影響力越小。具體來說可以寫成：

$$\nabla \overline{R}_{\theta}=\frac{1}{M}\sum^{M}_{m=1}\sum^{N_m}_{n=1}(\sum^{N_m}_{n'=n}\gamma^{n'-n}r^{m}_{n'}-b)\nabla\log(p_{\theta}(a^m[n]|s^m[n])) $$

其中 $A^{\theta}(s[n],a[n])=\sum^{N_m}_{n'=n}\gamma^{n'-n}r^{m}_{n'}-b$ 其實就是我們的 advantage function，代表在某一個 state 時，這個 action 相較其他的 action 有多好。(可以由 critic 評估)

## On policy v.s. Off policy

  前面我們說到若要使用 DRL 的方法，為了避免計算期望值，我們必須要每次更新都 sample 一堆資料，這樣是耗時且浪費資源的。為此，科學家們想出一種 Off policy 的方法來解決此問題。而我們前面提到的其實是 On policy 的方法，這兩種方法的說明如下：
* On policy：要學習的 agent 自己跟環境的互動來學習。
* Off policy：要學習的 agent 透過觀察其他 agent 跟環境互動的來學習。

這種 Off policy 的方法令要學習的 agent 透過觀察其他 agent 跟環境的互動來學習。想當然耳我們會對更新公式做出一些修改，然而這些修改剛好解決了我們要在每個步驟取樣一堆點的問題，以下我會依序講解。

### Importance Sampling

  首先，我們介紹 Importance Sampling，回想上一章講的：「我們要從某 $p$ 分布取樣，將取樣後的值帶入某個函數，並算出這個函數的期望值，但這個值算不出來，因此我們用蒙地卡羅撒點近似平均值。」但 Importance Sampling 告訴我們可以不用一定要從 $p$ 分布取樣，也可以從任意 $q$ 分布取樣，之後再乘上一個 weight 便會就會跟從 $p$ 取出來的點一樣。具體數學式如下：

$$
E_{\tau\sim p_{\theta}(\tau)}[R(\tau)]= \int R(\tau)p_{\theta}(\tau)d\tau=\int R(\tau)\frac{p_{\theta}(\tau)}{q_{\theta}(\tau)}q_{\theta}(\tau)d\tau=E_{\tau\sim q_{\theta}(\tau)}[R(\tau)\frac{p_{\theta}(\tau)}{q_{\theta}(\tau)}]
$$
其中可以看出 $\frac{p_{\theta}(\tau)}{q_{\theta}(\tau)}$ 便是要乘上的 weight。因此，我們的 gradient 更新公式便可以寫為：

$$
\nabla \overline{R}_{\theta}= E_{\tau\sim p_{\theta}(\tau)}[R(\tau)\nabla\log(p_{\theta}(\tau))]=E_{\tau\sim p_{\theta'}(\tau)}[\frac{p_{\theta}(\tau)}{p_{\theta'}(\tau)}R(\tau)\nabla\log(p_{\theta'}(\tau))]
$$
其中 $p_{\theta'}(\tau)$ 便是我們要取樣的分佈，只要在第一次做取樣就好。由於我們每個步驟都會更新 $\theta$，所以 weight $,\frac{p_{\theta}(\tau)}{p_{\theta'}},$ 絕對會變，也因此可以一直使用第一次取樣的資料來訓練。

  接著再回到 Advantage 的形式，我們可以推導出：

\begin{align*}
\nabla \overline{R}_{\theta}
&= E_{(s[n],a[n]\sim\pi_{\theta})}[\sum^{N_m}_{n=1}A^{\theta}(s[n],a[n])\nabla\log(p_{\theta}(a[n]|s[n])) \\
&= E_{(s[n],a[n]\sim\pi_{\theta'})}[\sum^{N_m}_{n=1}\frac{p_{\theta}(s[n],a[n])}{p_{\theta'}(s[n],a[n])}A^{\theta'}(s[n],a[n])\nabla\log(p_{\theta}(a[n]|s[n]))\\
&= E_{(s[n],a[n]\sim\pi_{\theta'})}[\sum^{N_m}_{n=1}\frac{p_{\theta}(a[n]|s[n])}{p_{\theta'}(a[n]|s[n])}\frac{p_{\theta}(s[n])}{p_{\theta'}(s[n])}A^{\theta'}(s[n],a[n])\nabla\log(p_{\theta}(a[n]|s[n]))\\
&= E_{(s[n],a[n]\sim\pi_{\theta'})}[\sum^{N_m}_{n=1}\frac{p_{\theta}(a[n]|s[n])}{p_{\theta'}(a[n]|s[n])}A^{\theta'}(s[n],a[n])\nabla\log(p_{\theta}(a[n]|s[n]))\\
\end{align*}

其中第四個等式是因為 $p_{\theta}(s[n])$ 跟 $p_{\theta'}(s[n])$ 可以視為一樣的分佈。此時我們便推導完 off policy 的 gradient 了，以下在做幾點說明：
1. 由微分式子我們可以在推回 objective function 為：
\begin{equation}
J^{\theta'}(\theta)=E_{(s[n],a[n]\sim\pi_{\theta'})}[\sum^{N_m}_{n=1}\frac{p_{\theta}(a[n]|s[n])}{p_{\theta'}(a[n]|s[n])}A^{\theta'}(s[n],a[n])]
\end{equation}
2. 雖然我們可以推導出 importance sampling 後的分佈的期望值與原分佈的期望值相同，但我們卻無法保證它們的變異數一樣。若變異數差太多，會造成機率分佈差太多，也就是訓練出來的模型跟原模型會不匹配。

### PPO

  上一小節我們講到若被 importance sampling 的分佈與原分佈差太多，則訓練出來的模型跟原模型會不匹配。而 Proximal Policy Optimization (PPO) 演算法就是在處理這個問題。他在原目標函數中加了一個限制，使訓練出來的模型跟原模型不會差太多，具體數學如下：
\begin{equation}
J^{\theta'}_{PPO}(\theta)=J^{\theta'}(\theta)-\beta KL(\theta,\theta')
\end{equation}
其中 $KL(\theta,\theta')$ 其實也不太好算，因此之後還有延伸出一個 PPO2 演算法，不用算 $KL(\theta,\theta')$，更容易實作，有興趣可以去看李老師的影片。

## Q-Learning

  一個不直接參與決定 action ，但會評價其他 agent 的 agent 我們稱為 critic，而被評價的 agent 我們可以稱為 actor。critic 會根據狀態 $s[n]$ 來給出這個 actor 使用的 policy $\pi$ 在時間 $n$ 之後的價值 $V^{\pi}(s[n])$。從定義上來看，他是一種 off policy。有一些方法可以用來設計 $\pi$ 的價值函數 $V^{\pi}(s[n])$ ，包含 Monte-Carlo (MC) 方法跟 Temporal-difference (TD) 方法。

  MC 方法是先讓 actor 跟環境互動，產生一組 state 和他們對應的 cumulated reward，之後讓 $V^{\pi}(s[n])$ 網路去學習不同 state 和他們可以得到的分數，這樣就可以學出 Policy $\pi$，這個學法可以用回歸的方式學習。

  TD 方法一樣是先讓 actor 跟環境互動，產生一組 state 和他們對應的 cumulated reward。之後讓 $V^{\pi}(s[n])$ 網路去學習輸入 $s[n]$ 跟 $s[n+1]$ 得到的分數會差 $r[n]=V^{\pi}(s[n])-V^{\pi}(s[n+1])$，這樣就可以學出 Policy $\pi$，這個學法可以用回歸的方式學習。

  此外，我們介紹一種類似價值函數的 Q-function $Q^{\pi}(s[n],a[n])$，只不過它的輸入變成 state 跟 action。Q-function 的方法一樣是先讓 actor 跟環境互動，產生一組 state 、根據 $\pi$ 的對應 action 和他們對應的 cumulated reward。之後用類似 TD 的方式，讓 Q-function 網路去學習 $s[n]$ 跟 $a[n]$ 與 $s[n+1]$ 跟 $\pi(s[n+1])$ 之間的差 $r[n]=Q^{\pi}(s[n],a[n])-Q^{\pi}(s[n+1],\pi(s[n+1]))$，這樣就可以學出 Q-function。

  總之，假設我們現在有一個 actor 擁有 policy $\pi$，讓其跟環境互動一下我們可以得到很多組狀態跟分數。我們將這些資料拿來訓練 Q-function $Q^{\pi}(s[n],a[n])$。接著我們在找出可以使 $Q^{\pi}(s[n],a[n])$ 在不同 state 最大化的 action，並將其拿來當作我們的新策略 $\pi'$，此策略可以保證 $V^{\pi'}(s[n])>V^{\pi}(s[n])$。接著在替換掉舊策略 $\pi$，然後再不斷重複便可以得到最佳策略。如下圖所示：


  但實作上要注意的是，有可能我們在訓練 Q-function 時，有一些 state 跟 action 並沒有被使用到。為了更全面的試出所有可能的 action，我們在找 action 時不一定會根據 policy 來找，目前較普遍的有兩種做法，包括 Epsilon Greedy 跟 Boltzmann Exploartion：
1. Epsilon Greedy 的作法是設定一個 $1-\epsilon$ 當作選 policy 選的 action 的機率，反之則隨機選 action。通常我們會將 $\epsilon$ 隨時間遞減：

\begin{align}
a=
\begin{cases}
\underset{a}{argmax} Q(s,a), & (1-\epsilon)*100\%\\
0, & \text{otherwise}\\
\end{cases}
\end{align}

2. Boltzmann Exploartion 則是將所有某個 state 所有可能的 action 去做正歸化求出機率，接著隨機 sample 出 action。也就是 Q-value 越高就越有機會被 sample，但 Q-value 小也會有機會被 sample 到：

$$
P(a|s)=\frac{\exp(Q(s,a))}{\sum_a \exp(Q(s,a))}
$$

### Replay Buffer
  通常我們會設一個 buffer 來收集資料，而 Q-function 在訓練的時候就一次從 buffer 裡面拿一個 batch 的資料量進來訓練。這邊講一個比較玄的事情，就是 buffer 內不一定都是要是 policy $\pi$ 跟環境互動過的結果，也可以是以前的 policy 跟環境互動的結果。雖然聽下來推翻了我們 Q-learning 講的所有東西，我們變成要找一個比未知的 policy 還要好的 policy $\pi'$，但理論跟模擬都可以證明這個新 policy $\pi'$ 一定比舊 policy $\pi$ 還要好。會這樣做的好處是可以增加多樣性，並且用 replay buffer 可以讓我們減少當下要跟環境互動的次數，主要的資料都是過去的經驗。演算法可以參考以下圖片：


## Advantage Actor-Critic

  在前幾章我們有講到：

$$\nabla \overline{R}_{\theta}=\frac{1}{M}\sum^{M}_{m=1}\sum^{N_m}_{n=1}(\sum^{N_m}_{n'=n}\gamma^{n'-n}r^{m}_{n'}-b)\nabla\log(p_{\theta}(a^m[n]|s^m[n])) $$

但由於模型的隨機性，我們的 $G^m[n]=\sum^{N_m}_{n'=n}\gamma^{n'-n}r^{m}_{n'}$ 是非常不穩定的。因此，結合上述所學，我們將 $G^m[n]$ 替換成 $E[G^m[n]]=Q^{\pi_{\theta}}(s^m[n],a^m[n])$。而上式的 b 我們就以 $V^{\pi_{\theta}}(s^m[n])$ 取代，因為 $V^{\pi_{\theta}}(s^m[n])$ 就是 $Q^{\pi_{\theta}}(s^m[n],a^m[n])$ 的期望值。我們令 $Q^{\pi_{\theta}}(s^m[n],a^m[n])=E[r^m[n]+V^{\pi_{\theta}}(s^m[n+1])]\approx r^m[n]+V^{\pi_{\theta}}(s^m[n+1])$，此時 $Q^{\pi_{\theta}}(s^m[n],a^m[n])$ 會因為 $r^m[n]$ 而有一點不穩定，但怎麼樣也比 $G^m[n]$ 的不穩定來的好。所以我們的 Advantage 可以寫為
$$
A^{\theta}(s[n])=r^m[n]+V^{\pi_{\theta}}(s^m[n+1])-V^{\pi_{\theta}}(s^m[n])
$$
  因此，Advantage Actor-Critic 的流程圖如下所示，只是將學習 Q-function 改成學習 V-function 而已。


  在做訓練 V-function 時有一個小技巧是「加一個提高輸出 entropy 的限制」，這個限制可以使得在 exploration 時更全面。

## 結語
  這個網頁算是整理了 DRL 的基本介紹，但並沒有包含所有李宏毅老師授課的內容，有一些比較細節的，像是 Q-learning advanced tips (裡面有 DQN)、Q-learning continuous action、sparse reward (很難獲得 reward 怎麼辦) 跟 limitation learning 等等，大家有興趣可以在自行去觀看影片。