# 李宏毅_ATDL_Lecture_18
###### tags: `Hung-yi Lee` `NTU` `Advance Topics in Deep Learning`
[課程撥放清單](https://www.youtube.com/channel/UC2ggjtuuWvxrHHHiaDH1dlQ/playlists)
## Imitation Learning
[課程連結](https://www.youtube.com/watch?v=rOho-2oJFeA&list=PLJV_el3uVTsPMxPbjeX7PicgWbY7F8wW9&index=18)

### Introduction

Imitation Learning有人又稱為apprenticeship learning、learning by demonstration，但又有人覺得只有Inverse Reinforcement Learning才能稱為apprenticeship learning。learning by demonstration就是人類示範給機器，讓機器去模仿學習。

不同於Reinforcement Learning，Imitation Learning中，機器可以與環境互動，但並不會得到Reward，因此，Imitation Learning並非受到Reward影響，主要還是受到Expert Demonstrates啟發。

使用Imitation Learning主要幾點原因：
1. Reward不好定義
2. 如果Hand-crafted reward可能會造成無法控制的行為，考試要100分是目標，那機器可能學到的是作弊就能100分。

Imitation Learning有三種方法：
1. Behavior Cloning
2. Inverse Reinforcement Learning
3. Generative Adversarial network
### Behavior Cloning

直觀來看，就是要機器複製專家(Expert)的行為，以自駕車為例，我們要搜集很多人類駕駛的行為，可以從行車記錄器取得資料。

訓練資料集的標記自然就是observation所對應的當下行為，上圖為例，人類在看到那種observation的情況下會向前，機器就是學著向前就可以，因此模型Actor(`nn`)的輸入就是observation，輸出就是採取的行為action。

這，就是supervised learning。
### Behavior Cloning

Behavior Cloning會遇到一個問題，就是Expert的samples有限，這會造成遇到非訓練資料中狀況的時候機器的表現不佳。舉例來說，Expert示範轉彎是順順的右轉，但是當初始位置是在過彎一半的地方時機器就會不知道該怎麼做。

一種作法就是給更多資料，給Expert一些平常不會遇到的observation(states)，問他該如何處理，這種作法稱為Dataset Aggregation。

### Behavior Cloning

Dataset Aggregation具體範例說明：
假設現在有一個actor-$\pi_1$，並且用它與環境(environment)互動，如上圖所標示，目前$pi_1$在這個環境中預計走綠色的路線，而車上有一位expert會同時標記這種情況下他會怎麼做。

但是要注意到的是，expert是告訴機器，下一次遇到這種狀況的時候要怎麼走，因此，利用新標記的資料再訓練得到actor-$\pi_2$。

這種作法在自駕車上也許不佳，但其它狀況下或許可行。
### Behavior Cloning

[參考影片](https://www.youtube.com/watch?v=j2FSB3bseek)

Actor在不考慮overfitting情況下完全複製Expert是可以的，但是比較擔心的是Actor的capacity是有限的，有限的情況下對Actor應該學Expert的那一部份所造成的後面結果是影響很大的。

如果有看影片的話，影片中謝爾頓在學中文，他不只說，還學了手勢，但如果他只學到手勢，而忘了怎麼說，那就差異很大了。

這一點在Behavior Cloning中並沒有考慮到，解決這問題的一個方法就是給予不同的錯誤不同的權重，但這部份如果用Supervisor Learning來train Behavior Cloning的話比較難以定義。
### Mismatch

在Behavior Cloning中，你的訓練與測試資料的分佈有可能是不一致的，舉例來說，在Behavior Cloning內，Supervisor learning很簡單的就是輸入$o$，輸出$a$，**但你會看到怎麼樣的Observation是取決於Actor本身的參數**，而actor在學習expert不完全情況下，就會造成兩個Observation的distribution不同。

或許兩個distribution相近，但Observation差異很大，又或許兩個distribution差異甚大，但Observation又相似，這很難判定，也因此另一種方式就出現了，即IRL，Inverse Reinforcement Learning。
### Inverse Reinforcement Learning

Inverse Reinforcement Learning又稱『Inverse Optimal Control』或『Inverse Optimal Planning』，但都是相同的。

名稱上直觀來看，就是將Reinforcement Learning反過來。

RL原始作法：
有一個Agent會與Environment互動，透過互動會得到Reward-$R(\tau)$，$\tau$是環境給的，不是我們所定義的。而$P(s'|s,a)$也是由Environment所提供，在某一個state決定那一個action之後會得到的下一個state。再利用Policy-$\widehat {\pi}$最佳化得到的Reward。

IRL的話則反過來：
我們有一個Policy-$\widehat{\pi}$_{(課程中提到的Policy即Actor)}，也許是一個很會玩遊戲的人，但實際上我們並不知道Policy的參數是長什麼樣子，我們唯一知道的是state與action的對應關係，即$\hat{\tau}$。

從$\hat{\tau}$可以看的出來人類專家在看到什麼樣的state會有什麼樣的action，我們希望這用些資料來反推Reward，這個行為就是Inverse Reinforcement Learning。 Environment Dynamics依然是一個input，它會知道Expert在什麼state會有怎麼樣的action，但不同的是它並不知道採取的action會有多少的Reward。

要注意，它是反推，而不是模仿，根據IRL找出一個Reward function-$R(\tau)$之後，再利用它來找出Policy-$\pi^*$。一個簡單的Reward function就可能可以導致actor有非常複雜的行為，因此，Model Reward function或許會比Model actor還要容易。

IRL就是先推出Reward function，再根據這個Reward function來推出Policy。
### Inverse Reinforcement Learning

這邊快速複習原始RL的作法：
* 給定一個Reward function-$R(\tau)$，裡面有著每一個state對應的action，即$R(\tau)=\sum_{t=1}^Tr(s_t,a_t)$
* $r(s_t,a_t)$即記錄在什麼狀態下有怎麼樣的action會有多少的Reward
* 把整場遊戲所有時間點得到的Reward總合就是$R(\tau)$
* 初始化actor-$\pi$
* 迭代
* 以$\pi$與Environment互動N次，得到N個$\tau$
* $\tau=\{s_1,a_1,r_1,s_2,a_2,r_2...s_T,a_T,r_T\}$
* $R(\tau)=\sum_{t=1}^Tr^T$
* 每次玩可能結果都不一樣，因此取平均，即$\bar{R}_\pi\approx \dfrac{1}{N}\sum_{n=1}^NR(\tau)$
* 更新$\pi$，讓$\bar{R}_\pi$最大化。
* 利用Policy Gradient
* 最終得到可以最大化Reward的$\hat{\pi}$
### Inverse Reinforcement Learning

我們沒有Reward function，手上有的就是$\hat{\pi}$跟拿$\hat{\pi}$玩遊戲的trajectories_(歷程)，大致流程說明如下：
* 手上擁有$R(\tau)$或者是$r(s, a)$
* 給定一個$\hat{\pi}$，裡面有玩N次遊戲的記錄
* 假設手上的$\hat{\pi}$是可以得到最大化Reward的Policy
* 尋找一個Reward function滿足上面的假設
* 即$\bar{R_{\hat{\pi}}}>\bar{R_{\pi}}$
### Ring a bell in your mind?

IRL在某種意涵來說跟Structured Learning相似，以IRL來說，我們要找一個Reward function，其條件為$\bar{R_{\hat{\pi}}}>\bar{R_{\pi}}$，找到Reward function之後再找出Policy讓Reward最大。

在Structured Learning中，我們要找一個evaluation function-$F(x,y)$，input為$x,y$的pair，其$F(x,\hat{y})$是大過所有x,y組成的pair。測試的時候再給定所有的$x,y$看那一組可以讓$F$最大化。

註：$\hat{y}$為實際標記資料
### Review: Structured Perceptron

這邊快速的回顧Structured Learning，假設其evaluation function為$F(x,y)=w\cdot\phi(x,y)$：
* 迭代
* 每次sample一筆資料，看那一個$\widetilde{y}^r$可以讓$F(x,y)$最大
* 如果$\widetilde{y}^r\neq\hat{y}^r$，那就更新參數，以此增加正確的$\hat{y}^r$的evaluation function的值，也減少錯誤的$\widetilde{y}^r$的值。
### IRL v.s. Structured Perceptron

Structured Perceptron中我們假設$F(x, y)$是linear，為$w\cdot\phi(x,y)$，如果在IRL中也可以用相同的定義$\bar{R}_\pi=w\cdot\phi(\pi)$，那就可以用解Structured Perceptron的方式來解IRL。

解法如下：
1. 我們有一個$\tau$，記錄歷程
2. $\bar{R}_\theta$為N個trajectories的平均，即$\dfrac{1}{N}\sum^N_{n=1}R(\tau^n)$
3. 每一個trajectory的Reward為每一個time step的reward總合，因此$R(\tau^n)$可以寫為$\sum_{t=1}^Tr_t$
* 每一個trajectory的長度可能不一樣。
* IRL中，$r_t$我們並不知道，這是由模型參數所決定，被找出來的。
4. 為了讓IRL與Structured Perceptron有關聯，我們定義$r_t=w\cdot f(s_t,a_t)$
* $r_t$為參數vector-$w$與feature vector的內積。
* 參數vector-$w$是我們要解的
* feature vector-$f(s_t,a_t)$是從state與action中抽出vector
* 部份paper並未將$a_t$放在feature vector內，認為只有state與reward有關，與action無關，這由個人定義即可。
5. 將$r_t$帶入，得到$w\cdot\dfrac{1}{N}\sum_{n=1}^N\sum_{t=1}^Tf(s_t,a_t)$
* 參數-$w$在所有的時間點都是一致的，因此放在最外面
* 對所有的trajectory的每一個時間點都抽出一個feature vector，接著平均它們得到一個feature vector再跟參數-$w$做inner product就可以得到我們預期的Reward-$\bar{R}_\pi$_{(簡報為$\theta$，課程中說明應該為$\pi$)}
6. feature vector取決於actor，不同的actor得到的feature vector就不一樣，因此對所有的trajectory的每一個時間點抽出一個feature vector做平均就可以視為對你現在的actor抽一個feature，為$\phi(\pi)$，因此整個數學式可以調整為$w\cdot\phi(\pi)$
7. 接下來就是解argmax的問題，IRL中就是找一個$\pi$讓Reward最大，解法就是利用RL，這意味著每一次迭代你都要做一次RL，因此運算量是非常大的。

### Framework of IRL

實際作法如下：
1. 初始化一個隨機Reward function
2. 依據Reward function找出一個actor-$\pi$
* 因為是隨機生成，因此很笨
* 以RL求解，因此計算量甚大
3. 以actor-$\pi$與Environment互動$N$次，得到trajectory-$\tau_1....\tau_N$
4. Expert-$\hat{\pi}$也與Environment互動$N$次，得到trajectory-$\hat{\tau}_1...\hat{\tau}_N$
* 如果是自駕車，就是記錄人類駕駛在不同情況下有的不同反應
* 如果是機械手臂的話，那就是記錄人抓著手臂去做某一件事情
5. 更新Reward-function，我們希望Expert所期望的Reward是大過現在的actor所期望的Reward，即$\bar{R}_\hat{\pi}>\bar{R}_\pi$
* $\bar{R}_\pi=w\cdot\phi(\pi)$
* 根據$\pi$，把所有trajectory內的state與action成對的取出並計算平均，就可以得到$\phi(\pi)$，再乘上Weight-$w$。
* $r_t=w\cdot f(s_t,a_t)$
* 更新的方式與Structure Perceptron一樣，原始的$w$加上正確的feature-$\phi(\hat{\pi})$並減掉錯誤的feature-$\phi(\pi)$

這邊並非只能帶入Structured Perceptron的概念，如果想要也可以利用Structured SVM。
### GAN v.s. Imitation Learning

GAN也可以結合Imitation Learning，本質上GAN就是要找一個Generator，這個Generator產生的distribution與實際資料的distribution愈接近愈好。

現在假設我們有一個Expert Polyci-$\hat{\pi}$，它與環境互動的時候會產生一堆的trajectory-$\hat{\tau}$，它也是一個distribution。

現在要做的是，訓練一個actor-$\pi$來與環境互動，也會得到trajectory-$\tau$，我們希望actor所output的distribution與$\hat{\tau}$的distribution愈接近愈好。$\tau$可以形成distribution的原因在於environment是有隨機性的，舉例來說，遊戲中相同的畫面你相同的動作，下一步敵人的反應是可能不一樣的。又或者actor本身也可能擁有隨機性。

而我們希望，actor所產生的distribution-$\tau$與expert所產生的distribution-$\hat{\tau}$愈接近愈好。
### GAN for Imitation Learning

實作說明如下：
1. 有一個Expert-$\hat{\pi}$
* 以GAN的角度來看，就當它是實際資料，好比我們用GAN生成影像的時候所擁有的REAL DATA。
* REAL DATA: $\hat{\tau}$
2. 有一個Actor-$\pi$
* 隨機初始，與環境互動得到一堆$\tau$
* 以GAN的角度來看，就是一開始很鳥的Generator，不同的是並非生成很多影像資料，而是生成$\tau$
3. 有一個Discriminator-$D$
* 以trajectory判斷是Expert或是Machine所出的資料
4. 以GAN的方式訓練更新Discriminator
* WGANs也可以
5. 更新Actor的參數
* 即更新Generator的參數來騙過Discriminator
### GAN for Imitation Learning

trajectory-$\tau$是sequence，裡面記錄著每一個state對應的action，然後利用RNN來讀取之後output得分即可。

但實務上可能因為$\tau$的數目較少，因此如果直接將每一個$\tau$都視為一個資料的話會容易造成overfitting，常見作法如下：
1. 將$D(\tau)$拆解為很多$d$的合，即$D(\tau)=\dfrac{1}{T}\sum^T_{t=1}d(s_t,a_t)$
* 每一個$d$也都是一個funtion，input即為一個state與action，而非整個trajectory，僅為trajectory的一個時間點。
* 它判斷在時間點$t$所看到的$s_t$所做的$a_t$所得到的值有多像或多不像Expert的行為
2. 有一個Local Discriminator-$d$
* 它只判斷整個trajectory的某一個時間點
* 把整個trajectory的state、action加總起來，就可以得到$D(\tau)$
3. 判斷$d(s,a)$是否為expert所做，是的話就拉高它的機率，如果是actor的話就降低它的機率
### GAN for Imitation Learning

理論上，只要計算actor的參數對$D(\tau)$期望值的gradient，就可以用這個gradient來更新actor的參數_{(policy gradient)}，actor就會讓$D(\tau)$的期望值變大：
* $\theta^\pi \leftarrow\theta^\pi + \eta\sum^N_{i=1}D(\tau_i)\nabla_{\theta^\pi}logP(\tau_i\vert\pi)$
* $\sum_{i=1}^N$：加總N個目前sample到的trajectory
* $D(\tau_i)$：以Discriminator計算每一個trajectory的$D(\tau_i)$
* $\Delta_{\theta^\pi}logP(\tau_i\vert\pi)$：把$D(\tau_i)$乘上現在的參數對$logP(\tau_i\vert\pi)$的gradient
* $P(\tau_i\vert\pi)$：在actor-$\pi$產生$\tau_i$的機率
* 再把gradient做加總來更新參數

直觀來看，你有一個Discriminator，它會告訴你這個$\tau$是expert還是actor做的，如果discriminator覺得這個$tau$是expert做的，那就增加它未來出現的機率，如果discriminator覺得是actor做的，那就降低它出現的機率。

### Algorithm

以GAN實作Imitation Learning總結：
1. 有一個trajectories-expert-$\hat{\tau}$
2. 初始化Discriminator與actor-$\pi$
3. 每次迭代中：
* 以actor與環境互動N次得到trajectories-$\tau_1...\tau_N$
* 更新discriminator，增加$D(\hat{\tau}_i)$出現的機率並降低$D(\tau_i)$出現的機率
* discriminator定義為$D(\tau)=\dfrac{1}{T}\sum^T_{i=1}d(s_t,a_t)$
* 你也可以自己定義
* 這與IRL中Reward function相同。
* 更新actor
* $\theta^\pi \leftarrow\theta^\pi + \eta\sum^N_{i=1}D(\tau_i)\nabla_{\theta^\pi}logP(\tau_i\vert\pi)$
* 這與IRL中每次都要做一個RL相同

直觀來看，以GAN實作Imitation Learning跟IRL其實說的是同一件事，只是換一個說法而以。
### Recap: Sentence Generation & Chat-bot

之前提過的Sentence Generation & Chat-bot，雖然課程中沒有提到，但事實上它們就是一個解Imitation learning的問題。

以唐詩三百首為例，在Sentence Generation來看：
1. Expert trajectory指的就是詩人所吟的詩，課程範例為床前明月光。
2. trajectory記錄著：
* $(o_1,a_1)$：(\"BOS\",\"床\")
* $(o_2,a_2)$：：(\"床\",\"前\")
* $(o_3,a_3)$：：(\"床前",\"明\")

Imitation Learning中我們並不知道每一個action會有多少reward，我們唯一知道的就是expert是對的，跟著做就是，因此生成的時候我們不需要考慮到reward。

Chat-bot也是類似想法，Expert trajectory中有著對話記錄，state的部份包含著問句-input與每一個state的action。

如果是以Maximum likelihood的話，那實作就是behavior cloning，這會有很多問題，因此現在都以SeqGAN來實作。
### Robot

影片：http://rll.berkeley.edu/gcl/

### Parking Lot Navigation

自駕車如果以RL的做法，對於它的Reward function非常難以定義，倒車要不要扣分?前進、後退的切換要不要扣分?沒延線走要不要扣分?急轉要不要扣分?

因此可以採用Imitation Learning的方法來教導機器。

附圖二是論文的結果，研究題目是停車：
1. 最上面是好的停車路線，四個trajectories(藍線)，最右邊(紅線)是機器執行的結果。
* 結果來看車子停的不錯，雖然車子應該可以從下面直接去停車格，但它尊循expert的作法。
2. 中間是抄捷徑的作法
* 結果可以看的出來機器也學到抄捷徑
3. 最下面是教機器倒車

註：即使是用RL，遲早還是可以將車子停好。
### Path Planning

這是指導機器如何規劃行走的路線，以IRL訓練，兩點之間告訴機器如何行走。

上排範例是告訴機器走正確的道路(上排左圖)，機器會知道走在黑路的道路上(上排中間圖)所得的Reward較大，因此機器規劃的時候可以看的到它是延著道路的。(上排右圖)

下排範例是告訴機器走森林(下排左圖)，因此機器在規劃路線的時候就是往森林走(下排右圖)。

我們可以看的到，相同的圖給機器不同的指導就會得到不同的規劃。
### Third Person Imitation Learning

先前提到拿著機器人的手教導機器人的時候，這時候的機器是第一人稱視角，有人提出了讓機器人以第三人稱視角來訓練。但這會有一個問題，因為機器在看的時候是第三人稱視角，而實際操作的時候是第一人稱視角，這會造成訓練上的困難。
### Third Person Imitation Learning

論文引入了domain adversarial training的概念：
1. Discriminator有兩個input，$O_t,O_{t+4}$，
* $O_{t+4}$可以看成是action
* $O_t$為observation
2. discriminator判斷在這個observation下所採取的action到底是expert還是machine。
* 在Third Person Imitation Learning中，machine與expert所做的本來就差很多
3. 訓練一個`nn`來判斷observation的視角是machine或是expert。
* 得到Domain Label
4. Feature Extractor的中間的某一個hidden layer會往Domain classifier去。
* 決定現在看到的observation是expert或是machine的視角

Feature Extractor一方面希望可以讓discriminator正確的判斷現在這個action是machine所採取的還是expert所採取的，另一方面同時希望騙過domain classifier，讓兩個不同視角的資料通過Feature Extractor的時候可以結合在一起。

:::info
Note:
藍色區塊：Feature Extractor
紅色區塊：Domain Classifier
綠色區塊：Discriminator
:::
:::info
domain adversarial training：
如果有data是來自兩個不同的domain，有一種類似gan的方式可以將兩個不同domain的feature給map在一起。
可參考[上學期課程筆記_ML Lecture 19: Transfer Learning](https://hackmd.io/@shaoeChen/BJKNpmoJN?type=view#Domain-adversarial-training)
:::
### Third Person Imitation Learning

上排是機器觀察時候的視角，下排是機器實際操作的視角。

### Third Person Imitation Learning

兩張圖是玩兩個不同的遊戲，橫座標是訓練迭代次數，不同色的線代表不同方式訓練。