# 李宏毅_ATDL_DRL Lecture 3
###### tags: `Hung-yi Lee` `NTU` `Deep Reinforcement Learning`
[課程撥放清單](https://www.youtube.com/playlist?list=PLJV_el3uVTsODxQFgzMzPLa16h6B8kWM_)
## DRL Lecture 3: Q-learning (Basic Idea)
[課程連結](https://www.youtube.com/watch?v=o_g9JUMw1Oc&list=PLJV_el3uVTsODxQFgzMzPLa16h6B8kWM_&index=3)
### Critic

Q-learning是value-based，訓練的並不是policy，而是critic。critic本身並不會有直接的行為，而是評價現在的行為actor-$\pi$有多好或多不好。

假設actor為$\pi$，以這個$\pi$與環境互動，假設這個actor-$\pi$看到某一個state-$s$，接下來一直到遊戲結束所累積的reward(cumulated reward)的期望值有多大，即為state value function-$V^\pi(s)$。

$V^\pi(s)$：
* input state-$s$
* output scalar

畫面上兩個遊戲範例：
* 左圖：遊戲初期，因此預期的reward會比較大
* 右圖：怪已不多，因此預期的reward會比較小

Critic的output有多大取決於state-$s$與actor-$\pi$，因此，一個critic一定綁定一個actor，因為它衡量的是actor的好壞，而不是state。
### Critic

以棋靈王為例，以前佐為教阿光要下小馬步飛，但現在要阿光下大馬步飛，這是因為能力的不同。因此，如果阿光是actor的話，以前的阿光下大馬步飛，那critic所評估出來的reward會是不好的，但現在是變強的阿光做為actor，一樣下大馬步飛，critic所評估出來的reward反而會是好的。

這邊要說明的是，state value function是取決於你的actor，當actor改變的時候，state value function的output也會跟著變。
### How to estimate $V^\pi(s)$

要估測$V^\pi(s)$有兩種方式，其中一種為Monte-Carlo(MC) based approach：
* 讓actor與環境互動給critic看
* 當actor看到$s_a$，接下來所得到的cumulated reward-$G_a$有多大
* 當actor看到$s_b$，接下來所得到的cumulated reward-$G_b$有多大
* MC-based需要每次計算所有reward-$G$的總合，因此要遊戲結束才能做統計，遊戲時間太長的話可能收搜到的資料不多，也過於花費時間。

實際上我們並沒有辦法掃過所有的state，但$V^\pi(s)$是一個`nn`，因此即使是沒有看過的state，模型還是會給出一個值。在已經知道真正output的情況下，我們會希望$V^\pi(s)$的output愈接近$G$愈好，很明顯的這是一個迴歸問題。

### How to estimate $V^\pi(s)$

另一種估測$V^\pi(s)$為Temporal-difference(TD) approach：
* 不需要整個遊戲結束，只需要$\left\{ s_t, a_t, r_t, s_{t+1} \right\}$
* $V^\pi(s_t)=V^\pi(s_{t+1})+r_t$
* 這個時步所得的cumulated reward會是下一個時步的cumulated reward加上這個時步所得的reward
* 將$s_t$的output-$v^\pi(s_t)$減掉$s_{t+1}$的output-$V^\pi(s_{t+1})$的值愈接近$r_t$愈好
### MC v.s. TD

MC與TD的差別：
* MC的variance較大
* 遊戲本身有隨機性，因此$G_a$可以想成是一個random variable
* 相同的$s_a$所得到的$G_a$是不一樣的，而且每次所得的值差異也很大，因為$G_a$是很多不同時步的reward的總合
* TD的variance較小
* 有隨機性的是$r$，因為相同的$s_t$所得到的reward不一定是相同的，但這個隨機性只在$r$而不像MC是整個$G$
* state value function-$V$不見得估測的準，如果不準的話所得到結果也不一定是好的

後續會說明到MC、TD合併的版本。
### MC v.s. TD

範例是有一個actor-$\pi$與環境互動八次得到的遊戲結果，以此估測state vaule：
* $V^\pi(s_b)=\dfrac{3}{4}$
* 以記錄來看，八次出現$s_b$總共得到六分，因此為$\dfrac{6}{8}$
* $V^\pi(s_b)=???? 0? \dfrac{3}{4}?$
* Monte-Carlo：$V^\pi(s_a)=0$
* 因為遊戲得到的reward為0
* Temporal-difference：$V^\pi(s_a)=\dfrac{3}{4}$
* $V^\pi(s_a)=V^\pi(s_b) + r$

這邊可以看的出來，MC、TD兩種方法所估測出來的結果是不一樣的，即使是相同的資料集。
### Another Critic

另一種作法為Q-function，State-action value function-$Q^\pi(s, a)$：
* 不同於State value function僅考慮state，Q-function，考慮了state與action的pair
* 在某一個state採取某一個action，假設使用actor-$\pi$的情況下，其cumulated reward的期望值有多少
* 需要注意的是，actor-$\pi$在看到state-$s$的時候，它採取的action不一定是$a$，但在Q-function的假設是，在state-$s$，強制執行action-$a$，然後以actor-$\pi$一直玩下去所得到的期望值才是$Q^\pi(s, a)$

Q-function有兩種的表示方式：
1. input state-action pair output scalar
2. input state output multi value，但這必需在action為discrete的情況下才可以，這時候的Q value所代表的是執行不同action所得到的reward。
### State-action value function

[論文連結_MnihEtAlHassibis15NatureControlDeepRL.pdf](https://web.stanford.edu/class/psych209/Readings/MnihEtAlHassibis15NatureControlDeepRL.pdf)

上面的桌球範例：
1. 圖一說明，這個時間點所執行的三個動作(不動、上、下)一直到遊戲結束所預期得到的reward都不差多
2. 圖二說明，球已經彈上去了，要向上才會有reward
3. 圖三與圖二一樣，如果不向上接球，那就得不到reward
4. 圖四因為球彈回去了，而且已經贏了，因此那一個action都一樣
### Another Way to use Critic: Q-Learning

表面上Q-function只能用來評估actor的好壞，但實際上有Q-function就可以實作RL，就可以決定要採取的action。

假設有一個初始actor-$\pi$，很爛，隨機都沒有關係，與環境互動之後收集很多資料，接下來learn一個actor-$\pi$的Q-value($Q^\pi(s,a)$)來衡量actor-$\pi$在某一個state強制某一個action接下來會得到的expected reward。

只要能夠學習一個policy-$pi$的Q-function就保證可以找到一個新的policy-$\pi'$，而且$\pi'$一定比原來的$\pi$還要好。這樣的循環一直下去就可以讓policy愈來愈好。
### Q-Learning

這邊說明剛才的為什麼一定找的到更好的$\pi'$：
* 什麼叫做比較好?
* 對同一個state-$s$而來$\pi$的value function一定小於$\pi'$的value function
* 如何決定$\pi'$?
* 依據$\pi'(s)=arg \max_a Q^\pi(s, a)$
* 假設已經訓練出$\pi$的Q-function，在state-$s$的時候，將所有可能的action-$a$都帶入，看那一個action可以讓Q-function的output最大
* 要注意到，Q-function的定義，在state-$s$的時候，policy-$\pi$並不一定會採取action-$a$。因此在某一個state-$s$的時候要強制採取某一個action-$a$，然後用$\pi$繼續互動下去，得到的expected reward。
* 再次強調，在state-$s$不一定會採取action-$a$。因此在$\pi'$在state-$s$所採取的action-$a$與$\pi$不一定一樣，但$\pi'$所採取的action會得到較大expected reward。

因此，實際上並沒有一個policy叫做$\pi'$，$\pi'$其實是由Q-function所推出來，並沒有另一個`nn`來決定$\pi'$怎麼interaction，只需要Q-function就可以找出$\pi'$

後續會再說明如果action是continous的解法。

### Q-Learning

這邊證明為什麼上述作法可以得到較好的結果。

* $\pi'(s)=arg \max_a Q^\pi(s, a)$
* $V^{\pi'}(s) \geq V^\pi(s)$
* 對同一個state而言，$V^{\pi'}$一定比$V^\pi$還要大

* $V^\pi(s) = Q^\pi(s, \pi(s)) \leq \max_a Q^\pi(s, a) = Q^\pi(s, \pi'(s))$
* $Q^\pi(s, \pi(s))$是選擇某一個action，而$\max_a Q^\pi(s, a)$是選擇最大值的action
* $\max_a Q^\pi(s, a) = Q^\pi(s, \pi'(s))$，因為$\pi'(s)=arg \max_a Q^\pi(s, a)$

* $V^\pi(s) \leq Q^\pi(s, \pi'(s))$
* 在某一個state，按照policy-$\pi$一路做下去所得到的reward一定會小於等於不按$\pi$所給的方向。好比只有在第一步state-$s$按$\pi'$的方向走，其餘就按$\pi$的指示走，雖然只有一步之差，但得到的reward還是會比完全依照$\pi$所得的reward還要大
* $=E\left[ r_{t+1} + V^\pi(s_{t+1}) \vert s_t=s, a_t=\pi'(s_t) \right]$
* 在state-$s_t$按照policy-$\pi'$所採取的action-$a_t$，得到reward-$r_{t+1}$，然後跳到state-$s_{t+1}$，state-$s_{t+1}$根據actor-$\pi$所估測出來的value，即$V^\pi(s_{t+1})$
* 這邊的$r_{t+1}$意指$r_t$，即這個action所得到的reward
* $\leq E\left[ r_{t+1} + Q^\pi(s_{t+1}, \pi'(s_{t+1})) \vert s_t=s, a_t=\pi'(s_t) \right]$
* 上面有提到$V^\pi(s)$一定小於等於$Q^\pi(s, \pi'(s))$，也就是一直根據$\pi$所得的reward一定是比其中一步跟著$\pi'$所得的reward還要小。
* $=E\left[ r_{t+1} + r_{t+2} + V^\pi(s_{t+2}) \vert \cdots \right]$
* $\leq E\left[ r_{t+1} + r_{t+2} + Q^\pi(s_{t+1}, \pi'(s_{t+2})) \vert \cdots \right]$
* $\leq V^\pi(s)$

這邊要說明的是，可以估測某一個policy的Q-function，接下來就一定可以找的到另一個policy-$\pi'$，它一定比原來的policy-$\pi$還要更好
### Target Network

後續說明Q-learning的tip

使用Q-learning的時候會應用到TD的概念：
假設現在收集到一個data，在stata-$s_t$的時候採取action-$a_t$而得到reward-$r_t$，接著跳到state-$s_{t+1}$，而根據Q-function我們知道，$Q^\pi(s_t, a_t)=r_t + Q^\pi(s_{t+1}, \pi(s_{t+1}))$，也就是$s_t$與$s_{t+1}$中間差了一個$r_t$，這概念與TD是一樣的。

但實務上在訓練的時候會發現，這樣的function不好訓練。如果這是一個regression問題的話，$Q^\pi(s_t, a_t)$是output，而目標(target)$r_t + Q^\pi(s_{t+1}, \pi(s_{t+1}))$是會變動的。如果硬要將兩個model一起訓練不是問題，兩個$Q^\pi$是一樣的模型，只要將結果加在一起就可以，但這樣的訓練方式是不穩定的，因為你要fit的target是不斷變動的。

因此，訓練的時候可以將其中一個$Q^\pi$固定住(通常為$s_{t+1}$固定)，過程中不更新它的參數，而這個被固定參數的模型即稱為『Target Network』，它負責產生target給另一個模型去fit。

因為Target Network參數固定，因此它的output也是固定的，即$r_t + Q^\pi(s_{t+1}, \pi(s_{t+1}))$是固定的。那對另一個模型而言就是一個很單純的regression的問題，訓練幾次迭代之後再用這個模型去替換掉Target Network。
### Exploration

使用Q-function的時候，其Policy是完成取決於Q-function：
* $a=arg \max_a Q(s,a)$，給定一個state，窮舉所有的action，看那一個action得到的Q value最大就採用它，這與Policy Gradient是不同的，Policy Gradient的output是隨機的，從distribution中sample出一個action

這種方式並不好，因為要估測某一個state採取的action得到的Q-value有多少必需要你在那個state採取過那個action才估測的出來，如果不是那是無法估測的。雖然如果使用`nn`的話可能比較不會有這種問題，但如果你的state-action pair是一個table，沒看過就估不出值的話，那就沒有值了。

舉例來說，一開始所有的action的Q value都是0，剛好在state-$s$的其中一個action-$a_2$剛好sample過，得到的結果是正值，這時候$Q(s, a_2)$會比其它的action選擇來的好，那之後就只會sample到action-$a_2$，因為$arg \max$就永遠是它。

這問題有兩個方法可以解：
* Epsilon Greddy
* 設置一個$\epsilon$，通常是一個很小的值，有$1 - \epsilon$的機率是採$arg \max$的方式執行，有$\epsilon$的機率採隨機
* 實作上$\epsilon$會隨著時間遞減，因為一開始還不是那麼確定怎麼樣的action是好的，因此隨著時間增長遞減
* Boltzmann Exploration
* 這方法比較像是Policy Gradient，根據Q-value定義一個probability distribution，假設某一個action的Q value愈大代表它愈好，那我們採取這個action的機率就要越高，只是偶爾也會試一下那些Q-value較不好的action
* Q-value有正有負，因此要弄成機率就先取exponential再做normalize，以此做為sample action的機率
* $P(a \vert s)=\dfrac{exp(Q(s, a))}{\sum_a exp(Q(s, a))}$
* Q是一個`nn`，一開始可能每一個action的output值都是差不多的，因此$Q(s, a)$在一開始會比較是uniform
### Replay Buffer

我們有某一個policy-$\pi$與環境互動，然後收集互動的資料，每一筆資料記錄著$s_t, a_t, r_t, s_{t+1}$，接下來將這些資料通通放置於Reply Buffer。

Reply Buffer裡面的experience可能是來自於不同的policy，可能每一個policy保存一萬筆，而你的Reply Buffer只能保存五萬筆，每次滿了就將舊的資料丟棄。

訓練的時候就直接從Buffer中取batch_size的資料出來更新Q-function，這麼做的時候變成是一個off-policy的作法，原本Q所觀察的是$\pi$的某一個action的value，但實際上Q所觀察的資料並不通通是來自於$\pi$，是很多不同$\pi$的experience，這麼做的好處有兩個，第一，在做RL的時候最花時間的部份通常在與環境互動並取得資料，使用Reply Buffer可以減少互動次數。第二，訓練`nn`的時候，每一個batch裡面的資料愈diverse愈好。

### Typical Q-Leraning Algorithm

* 初始化兩個`nn`，Q-function，以及target network-$\hat{Q}$，並且讓$\hat{Q}=Q$
* 每一個episode(每一次互動)
* 每一個互動過程中
* 得到一個state-$s_t$，根據Q-function採取某一個action-$a_t$(記得Exploration)
* 得到reward-$r_t$，跳到state-$s_{t+1}$
* 收集到一筆資料{$s_t, a_t, r_t, s_{t+1}$}，保存到buffer
* 如果buffer滿了，就把舊資料刪掉
* 從buffer sample batch_size的資料$\left\{s_i, a_i, r_i, s_{i+1} \right\}$
* 依sample出來的資料計算target，$y=r_i + max_a \hat{Q}(s_{i+1}, a)$
* $a$，就是看那一個action可以讓$\hat{Q}$的值最大
* 更新Q-function的參數，讓$Q(s_i, a)$的output愈接近$y$愈好，這是一個regression的問題
* 每$C$次的更新就讓$\hat{Q}=Q$