# 李宏毅_ML_Lecture_23-1
###### tags: `Hung-yi Lee` `NTU` `Machine Learning`
[課程撥放清單](https://www.youtube.com/channel/UC2ggjtuuWvxrHHHiaDH1dlQ/playlists)
ML Lecture 23-1: Deep Reinforcement Learning
[課程連結](https://www.youtube.com/watch?v=W8XF3ME8G2I&list=PLJV_el3uVTsPy9oCRY30oBPNLCo89yu49&index=33)
### Scenario of Reinforcement Learning

談Reinforcement Learning之前要先瞭解：
* Agent
* Environment
* Observation
* 常見用語為State
* 意指Environment的狀態，為Machine所看到的東西
* Action
* Machine做的事情
* 與Environment互動來影響Environment
* Reward
* Machine在Action之後會對Environment造成影響並得到Reward

舉例來說，Machine看到一杯水，並打翻它，那就得到一個負值報酬，而因為水已經被打翻了，因此下一個時間點所看到的就是水被打翻的狀態，這時候它決定把地擦乾淨，因此得到一個正值報酬。

機器學習的目標就是根據過去的經驗讓Reward被最大化的Action。
### Learning to paly Go

以AlphaGO為例
1. 機器的Observation(State)就是棋盤
* 棋盤用19x19的Matrix來描述它
2. 接著它take一個Action
* 即落子的位置
3. 在圍棋中Environment就是對手，落子的位置影響對手的反應。
4. 機器看到下一個Observation，再決定它的Action，又影響Environment....

在這個案例子，多數情況下Action之後的Reward是0，只有在最後才知道輸(-1)或贏(1)，那時候才能決定Reward，因此它的困難點在於如何讓機器在只有少數情況下才會有Reward的情形中去發現正確的Action。
### Learning to paly Go - Supervised v.s. Reinforcement

如果是利用Supervised Learning，那就是看到什麼盤勢來決定下一子怎麼落子，雖然可以利用棋譜來學會下棋，但可能不是最強的，這種學習方式就像是Machine從一個老師身上學到如何下棋。

但利用Reinforcement的話卻不是這樣，它是從過去的經驗來學習怎麼下棋，沒有人教它。

在圍棋這個任務中，機器需要大量的訓練資料，也許下個三千萬盤棋之後它才會變的厲害，也因為沒有人可以跟電腦下三千萬盤，因此AlphaGo的做法是讓機器互下。
### Learning a chat-bot - Supervised v.s. Reinforcement

應用於Chat-bot上的話，Supervised會教機器聽到一句之後的下一句如何回覆，而Reinforcement不是，它會胡亂說到最後讓人爆氣，它就知道剛才可能有錯，但它也不知道是那一句錯，但慢慢的它真的就自己學習的到。
### Learning a chat-bot - Reinforcement Learning

作法上就是採用Alpha Go的方式，讓兩個機器人自己去胡亂對話。
### Learning a chat-bot - Reinforcement Learning

但一個問題在於，兩個機器人胡亂說了一堆之後你也不知道到底說的好不好，因此要從幾百、千萬中對話中評核也是一個問題，未來或許有人會利用GAN，讓Discriminator來判斷對話像不像人，以此做為Reward。
### More applicaitons

也可以應用在交互式對話，使用者問了一個問題，機器反問想問的是否為某一個問題，以此來取得Reward，只是機器只要問一個問題就是一個Negative Reward，因為這造成了人的困擾。
### More applications

### Example: Playing Video Game

目前強化學習最常應用在電玩領域中，這時候Agent跟遊戲內的AI並不相同，因為Agent的角色跟人一樣，以看到的內容為主。

後續會以小蜜蜂為例說明。
### Example: Playing Video Game

Scenario如下：
1. Machine看到畫面($S_1$)，即畫面中的Pixel
* 這個畫面就是Observation(State)
* Matrix，三維的tensor
2. Machine決定Action
* 每次Action之後得到Reward
* $a_1$:right
* Reward:0
* 因為單純的向右
* Action之後影響Environment
* Environment會有Random變化，但這個變化跟Machine take Action是沒有關係的
* 像畫面中外星人射出子彈，這跟Action無關
3. Machine看到畫面($S_2$)，即向右一步之後的畫面
* $a_2$: 射擊
* 成功射殺，Reward:5
4. $S_3$為少一隻外星人的畫面

這個程序一直進行下去...
### Example: Playing Video Game

程式會一直執行到$a_T$的時候，$r_T$進入另外的State，一個terminal state，代表遊戲結束。

遊戲的開始到結束稱為一個episode，機器學習的就是如何在一個episode中Maximize Reward。
### Difficulties of Reinforcement Learning

強化學習的難處有幾點：
1. Reward的出現是有延遲的
* 小蜜蜂為例，只有在射擊的時候才會得到Reward，如果機器只學如何射擊的話，就不會左右移動了，但左右移動卻可以幫助機器在未來得到Reward。
* Agent的任何行為都會影響看到的東西，因此Agent要學會探索世界
* 如果小蜜蜂不射擊就永遠不知道射擊可以得到Reward。
### Outline

目前強化學習分成兩大塊：
1. Policy-based
* 訓練一個負責做事的Actor
3. Value-based
* 訓練一個不做事的Critic

兩個加起來就是Actor-Critic，課程中就會說明A3C_{(Asynchronous Advantage Actor-Critic)}

AlphaGo裡面涵蓋了policy-based、value-based、model-based

Model-based: 對未來事件的理解，預測未來會發生什麼事，這種方式應用於棋類遊戲比較有用，電玩應用上沒見到較好的範例，棋類雖然未來狀況多，但還是可以窮舉，但電玩的話比較難以窮舉。
### To learn deep reinforcement learning...

### Machine Learning - Looking for a Function

Reinforcement Learning也是Machine Learing的一種，做的事情也是找一個Function，Actor。

Actor就是一個Function：
* input：機器看到的Observation
* output：機器要採取的Action

利用Reward來協助找到這個Function，也就是Actor。

符號約定：
$\pi$:表示Actor，部份文獻稱為Policy
### Three Steps for Deep Learning

強化學習三步驟：
1. 定義function
* NN決定function space
* Actor可以是一個NN
* 如果Actor是NN，那就是Deep Reinforcement Learning
2. 決定function的好壞
* 衡量Actor的好壞
3. 選擇最好的Actor
* 利用Gradient Ascent

### Neural network as Actor

假設我們用NN來當做Actor：
* Input就是機器看到的Observation，就是一堆Pixel，用一個vector或matrix來描述
* 理論上使用CNN
* Output就是要採取的Action
* 有幾個可以採取的Action，Output就有幾個Dimension

以小蜜蜂為例，它的Output就會有三個Dimension(左移、右移、射擊)，Input就直接利用CNN將Observation輸入，最後輸出每一個Action的分數。

Policy Gradient通常假設Actor_(Policy)是Stochastic_(隨機)，意思就是，Policy的Output是機率，上圖為例，即是70%會left，20%會right，10%會fire。

部份時候採用Stochastic是有好處的，如果Actor是deterministic，那就可能跟小叮噹一樣一直出石頭。

後續的課程都假設Actor為Stochastic

相較於傳統作法使用table來記錄Observation與Action的對應，利用NN的優點在於它可以舉一反三，即使沒有看過的畫面，最終還是會有一個輸出。
### Goodness of Actor

在Supervised Learning中決定好壞的方式就是定義Loss，然後最小化Cost Function。
### Goodness of Actor

強化學習中定義Actor的好壞也是類似的方式，Actor就是一個NN，它的參數是$\theta$，因此我們用$\pi_\theta$來表示Actor

* Actor:$\pi_\theta$
* 一個Actor就是一個function
* input：$S$
* Actor看到的Observation
* $R_\theta$：遊戲結束之後的Total Reward
* $r_1+r_2...+r_T$
* Total Reward就是我們要Maximize的對象
* 並非優化每一個step

即使相同的Actor，不同的episode也會有不同的結果_{(每次的$R_\theta$不同)}，理由如下：
1. Actor採Stochastic，即使看到相同場景、相同參數也會採取不同的Action，因此每次得到的$R_\theta$也不同
2. 遊戲本身的隨機性，即使採取相同的Action，每次看到的Observation也不一樣，因此，$R_\theta$本身是一個Random-Variable

我們要做的並不是最大化某一次遊戲得到的$R_\theta$，而是$R_\theta$的期望值，$\bar{R}_\theta$。拿同一個Actor玩了N次遊戲之後，我們希望$\bar{R}_\theta$愈大愈好。

這個期望值，就是用來衡量Actor的好壞。

符號約定：
$\bar{R}_\theta$：Actor的期望值
### Goodness of Actor

期望值的計算方式：
* 一場遊戲就是一個$\tau$
* $\tau$為sequence，包含Observation、看到Observation之後的Action、Action之後的Reward....
* $R(\tau)$代表這個trajectory_(軌跡)在這場遊戲中最終得到的Total Reward
* 加總所有的$r$
* 使用某一個Actor玩遊戲的時候，每一個$\tau$都會有一個出現的機率
* $\tau$代表某一種可能的從遊戲開始到結束的過程，這過程有千千百百種
* i.e. 某個較弱的Actor都會自己去吃子彈，那會看到這個Actor的每一個$\tau$都會自己控制去吃子彈自殺
* 每一個遊戲出現的過程都可以用機率來描述它，即$P(\tau|\theta)$
* 當Actor的參數是$\theta$的時候，這個$\tau$(遊戲過程)出現的機率

期望值$\bar{R}_\theta=\sum_\tau R(\tau)P(\tau|\theta)$
* 即加總所有可能的$\tau$(遊戲過程)
* $\tau$的所有可能性難以窮舉，但我們假設可以窮舉
* 每一個$\tau$都有它的機率$P(\tau|\theta)$跟它的Reward$R(\tau)$
* 相乘之後加總，就可以得到這個Actor的期望Reward

實際上窮舉是不可能的，因此我們讓Actor去玩N場遊戲_{(代表擁有N筆訓練資料)}，玩N場遊戲就像是從$P(\tau|\theta)$sample出N個$\tau$，如果某個$\tau$機率特別大，那它就很容易被取出。

最後將N個$\tau$的Reward計算出來平均，所得的值就可以近似我們的期望函數。
### Gradient Ascent

我們的目標函數(Objective Function)就是找一個參數來最大化$\bar{R}_\theta$，解法就是利用Gradient Ascent_{(因為我們要最大化)}。

作法如下：
1. 隨機初始$\theta^0$
2. 計算使用$\theta^0$的Actor，$\theta^0$對$\bar{R}_{\theta^0}$的微分
3. 更新參數得到$\theta^1$
4. 計算$\theta^1$對$\bar{R}_{\theta^1}$的微分
5. 更新參數得到$\theta^2$
6. .....
### Gradient Ascent

因為$R(\tau)$對$\bar{R}_{\theta}$沒有影響，只需要計算$P(\tau|\theta)$，因此即使$R(\tau)$是不可微的也不影響，因為本來就不會計算它的微分。即使$R(\tau)$根本是個黑盒子，我們只知道它最終會給我們一個Reward。

推導過程如下：
$\nabla\bar{R}_\theta=\sum_\tau R(\tau)\nabla P(\tau|\theta)=\sum_\tau R(\tau)P(\tau|\theta)\dfrac{\nabla P(\tau|\theta)}{P(\tau|\theta)}$
* 基本上這並沒有讓數學式不同，只是為了轉換過程使用，因為分子分母加入了$P(\tau|\theta)$

$\sum_\tau R(\tau)P(\tau|\theta)\dfrac{\nabla P(\tau|\theta)}{P(\tau|\theta)}=\sum_\tau R(\tau)P(\tau|\theta)\nabla logP(\tau|\theta)$
* 轉換如方框所示

之前提過，當看到紅框處的部份，我們可以將它視為Sampling，因此可以看成利用$\theta$玩N次遊戲得到$\tau^1...\tau^N$，因此近似如下：
$\dfrac{1}{N}\sum^N_{n=1}R(\tau^n)\nabla logP(\tau^n|\theta)$
### Gradient Ascent

$\nabla logP(\tau^n|\theta)$

$P(\tau|\theta)=$
$p(s_1)$：遊戲開始畫面出現的機率
$p(a_1|s_1,\theta)$：根據$\theta$在$s_1$會有一定的機率採用$a_1$
$p(r_1,s_2|s_1,a_1)$：根據在$s_1$採取$a_1$，你得到了$r_1$然後跳到$s_2$
$p(a_2|s_2,\theta)$：根據$s_2$採取$a_1$，這取決於$\theta$
$p(r_2,s_3|s_2,a_2)$：看到$s_2,a_2$得到$r_2, s_3$
$=p(s_1)\prod_{t=1}^Tp(a_t|s_t,\theta)p(r_t,s_{t+1}|s_t,a_t)$

其中兩項底線畫起的部份是與Actor無關，僅紅線底項是有關的
### Gradient Ascent

$\nabla logP(\tau^n|\theta)$

$P(\tau|\theta)=p(s_1)\prod_{t=1}^Tp(a_t|s_t,\theta)p(r_t,s_{t+1}|s_t,a_t)$
將所得數學式取log，如下：
$logP(\tau|\theta)=logp(s_1)+\sum^T_{t=1}logp(a_t|s_t,\theta)+logp(r_t,s_{t+1}|s_t,a_t)$

接著對$\theta$做Gradient，與$\theta$無關的項目就可以直接忽略，如下：
$\nabla logP(\tau|\theta)=\sum^T_{t=1}\nabla logp(a_t|s_t,\theta)$
### Gradient Ascent

最終，$\bar{R}_\theta$就接近於取N個$\tau$，每一個$\tau$都計算出它的Reward，再乘上每一個$\tau$出現的機率的log的Gradient，如下：
$\nabla \bar{R}_\theta \approx \dfrac{1}{N}\sum_{n=1}^NR(\tau^n)\nabla logP(\tau^n|\theta)$

其中$\nabla logP(\tau^n|\theta)$可以視為加總在這個$\tau$內所有採取過的Action的機率取log的Gradient，如下：
$\sum_{t=1}^{T_n}\nabla logp(a_t^n|S_t^n,\theta)$

再調整順序之後得到最終的數學式如下：
$\dfrac{1}{N}\sum_{n=1}^N\sum_{t=1}^{T_n}R(\tau^n)\nabla logp(a_t^n|s_t^n,\theta)$
* $\nabla logp(a_t^n|s_t^n,\theta)$：在資料集中，根據Model計算$s^n_t$這個State中，我們曾經採取$a^n_t$這個Action的機率取log計算梯度
* $R(\tau^n)$：在$s^n_t$採取$a^n_t$的遊戲中得到的Total Reward。
* 這邊計算是整個遊戲中所產生的Reward，而不是採取該Action所得到的Reward。
* 這麼做的原因在於，如果僅考慮該Action的Reward，那機器只會一直射擊而不會左右移動，因為只有射擊才會得到Reward。

直觀來看，在$\tau^n$的過程中，在$s^n_t$採取$a^n_t$，我們希望得到的Reward是一個正值，而且這個機率$p(a_t^n|s_t^n)$愈大愈好，因此我們會更新模型，讓機器在$s^n_t$的時候採取$a^n_t$的機率愈大愈好。

相反的，如果在$s^n_t$採取$a^n_t$得到的是一個負Reward，那我們就會希望後續在相同的Observation(State)的時候它採取$a^n_t$的機率愈小愈好。
### Gradient Ascent

$\nabla logp(a_t^n|s_t^n,\theta)=\dfrac{\nabla p(a_t^n|s_t^n,\theta)}{p(a_t^n|s_t^n,\theta)}$

機率在取log之後得到數學式如上，對於取log原因說明如下：
* 在相同的Observation情況下，因為Actor是Stochastic，因此即使相同的Observation也不會採取相同的Action，有三次決定採取Action-b-Reward:1，一次採取Action-a-Reward:2，即使Action-a所得Reward為2較高，但是我們所計算的是加總所有出現的結果_{(結果就是b出現的次數較多)}，因此機器後續取樣的時候會偏好於Action-b。
* 除掉機率就如同做Normalization，當某一個Action出現機率較高，那它所除掉的值就較大，更新之後機器就不會偏好於出現機率較高的Action。
### Add a Baseline

理論來說，如果Reward皆為正數不會構成問題，假設某一個State可以採取三個Action，而三個Action得到的Reward皆為正，但所得有多有少，有大有小，假設a、c的$R(\tau)$較大，而b較小，在更新之後，ac出現的機率還是會較大b來的大。

但實作中，我們是隨機取樣，某一個Action是有可能不被採樣到，因此機器永遠不知道它的$R(\tau)$有多大，在更新之後它的機率自然就會減少，而被採取到的就會增加。

因此我們希望$R(\tau)$是有正負值，而不是單純的正值，作法上，可以直接將$R(\tau)$減掉一個bias-b-baseline，意思就是你的$R(\tau)$必須大過這個baseline，那它得到的才會是正值，它的Action機率才會增加，沒超過就得到負值，機率就減少，這樣就不會造成單純沒有被取樣到的機率減少。