---
# System prepended metadata

title: 'Practical_RL - Lecture 3 : Model-free'

---

# Practical_RL - Lecture 3 : Model-free 


[TOC]

&emsp;
&emsp;
&emsp;
## **Model-free prediction**
&emsp;
![](https://i.imgur.com/PigY6Zk.png)


&emsp;
&emsp;


![](https://i.imgur.com/obmLCWB.png)



&emsp;
&emsp;

有些環境可以藉由 MDP 建構出來 : 

![](https://i.imgur.com/z6lQxeq.png)


&emsp;


但有些環境可能會發生如下的情況 : 

- MDP model is unknown, but experience can be sampled
- MDP model is known, but is too big to use, except by samples
&emsp;
:::info
**p ( $s_{t+1}$ | $s_t$ , $a_t$ ) 是未知的**
:::

&emsp;
&emsp;

**MDP trajectory :**

&emsp;
![](https://i.imgur.com/nTWYZ39.png)

Trajectory is a sequence of
- states  ( s )
- actions ( a )
- rewards ( r )

&emsp;

![](https://i.imgur.com/yRD5oqP.png)

&emsp;

### **Monte-Carlo : 基於隨機取樣的方法進行計算學習** 

&emsp;
![](https://i.imgur.com/JRqjIL1.png)

&emsp;

1. 選擇一個狀態 $s_t$
2. 每次 episode 出現 $s_t$ 後便開始計算累積獎勵 $G_t$
3. $s_t$ 出現總次數 N(s) ，  總獎勵值 S(s) ← S(s) + $G_t$
4. 價值函數 : V(s) = S(s)/N(s)
5. 根據大數法則 ( large numbers )，當 N(s) → ∞ ， V(s) 越接近期望值


&emsp;
&emsp;
![](https://i.imgur.com/utqtpIJ.png)

&emsp;
&emsp;
&emsp;
**Incremental mean(累進更新平均值) :**

&emsp;
![](https://i.imgur.com/YWzNH6j.png)

&emsp;
&emsp;
![](https://i.imgur.com/nZ2UNmc.png)
&emsp;
&emsp;
&emsp;
&emsp;
&emsp;
![](https://i.imgur.com/lcFYVpE.png)

&emsp;
&emsp;
&emsp;
&emsp;
&emsp;
&emsp;
### **Temporal-Difference (時間差分)**

&emsp;
在 MC 方法中 ， V(s)的更新為 :

![](https://i.imgur.com/0W3n6Hi.png)

$G_t$ 為累積獎勵，可知 MC 方法每次更新都須完成一整個 episode

&emsp;
&emsp;

在 TD 方法中 ， V(s)的更新為 : 

![](https://i.imgur.com/kJBKGqu.png)
&emsp;
 
TD 使用 Bellman方程式中的估計方法來估計 value，然後將估計值作為 value 的目標值進行更新

estimated return : $R_{t+1}$ + &gamma; V($S_{t+1}$)

$R_{t+1}$ + &gamma; V($S_{t+1}$) 稱為 TD target ， $δ_t$ = $R_{t+1}$ + &gamma; V($S_{t+1}$) - V ($S_t$) 稱為 TD error

&emsp;
&emsp;
![](https://i.imgur.com/OpVrCPl.png)

&emsp;
&emsp;
&emsp;
&emsp;
TD 與 MC 相比的優點 :

:::info 
- 每一步都可以更新，也就是 online learning，學習較快
- 不須完成一整個 eposide，可以應用於沒有結果的狀況，應用範圍廣
:::

&emsp;
TD 與 MC 相比的缺點 :

:::danger
TD target是估計值，這會導致更新得到的 value 與實際是有誤差的
:::

&emsp;
&emsp;
&emsp;
**AB Example :**

![](https://i.imgur.com/ofgARi2.png)

應用 MC 算法，也就是跑完一整個 episode，並且狀態 A 只出現過一次。 
V(A) = 0，V(B) = 6/8
&emsp;

應用 TD 算法，由于狀態 A 的後繼有狀態 B，所以狀態 A 的價值可通過狀態 B 的價值來計算 。然後從經驗可知 ，A 到 B 的轉移機率是100%，且 A 狀態的即時獎勵是 0 ，而且沒有衰減，因此 A 狀態的價值會等於 B 狀態的價值 ， V(A) = V(B) = 3/4 。






&emsp;
&emsp;

**n-Step Prediction :**

 TD 走 n 步 

![](https://i.imgur.com/bB6jauZ.png)

&emsp;
&emsp;
![](https://i.imgur.com/wejUYZM.png)

&emsp;
&emsp;
### **Temporal-Difference (λ)**

&emsp;
n 為多少時，預測的效果會最好 ?
&emsp;

![](https://i.imgur.com/CGzZBMR.png)

&emsp;
從上圖可以看出，這是綜合了所有步數的情況，並非直接選擇 n 步 ，而是加入了權重 λ 來綜合所有步數的結果
&emsp;
![](https://i.imgur.com/fj3RY4B.png)

從 (1−λ)^n-1^ 可知，每一步的權重都會漸漸衰減。即是距離狀態 s 越遠的，權重就越小。
&emsp;
### **Q-Learning** 

Q-Learning 的 Q 就是 action-values Q(s, a)

![](https://i.imgur.com/disSPXa.png)

&emsp;
![](https://i.imgur.com/cbhzAu9.png)


![](https://i.imgur.com/2fq4ySk.png)

&emsp;
- Q-learning 更新 Q-table 的方法是 greedy
&emsp;
![](https://i.imgur.com/3MmECKO.png)





&emsp;
&emsp;
&emsp;
&emsp;
&emsp;
&emsp;
&emsp;
&emsp;
參考資料 

https://yadi.sk/i/54qWKtDB3NDeuh
http://www0.cs.ucl.ac.uk/staff/d.silver/web/Teaching_files/MC-TD.pdf
http://www0.cs.ucl.ac.uk/staff/d.silver/web/Teaching_files/control.pdf
https://blog.csdn.net/liweibin1994/article/details/79111536
https://blog.csdn.net/songrotek/article/details/51381873