# Practical_RL - Lecture 3 : Model-free

[TOC]

 
 
 
## **Model-free prediction**
 

 
 


 
 

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


 

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

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

 
 

**MDP trajectory :**

 

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

 


 

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

 

 

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) 越接近期望值

 
 

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

 

 
 
 
 
 
 
 

 
 
 
 
 
 
### **Temporal-Difference (時間差分)**

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


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

 
 

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

 

TD 使用 Bellman方程式中的估計方法來估計 value，然後將估計值作為 value 的目標值進行更新

estimated return : $R_{t+1}$ + γ V($S_{t+1}$)

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

 
 

 
 
 
 
TD 與 MC 相比的優點 :

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

 
TD 與 MC 相比的缺點 :

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

 
 
 
**AB Example :**


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

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

 
 

**n-Step Prediction :**

TD 走 n 步


 
 

 
 
### **Temporal-Difference (λ)**

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


 
從上圖可以看出，這是綜合了所有步數的情況，並非直接選擇 n 步 ，而是加入了權重 λ 來綜合所有步數的結果
 

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

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


 


 
- Q-learning 更新 Q-table 的方法是 greedy
 

 
 
 
 
 
 
 
 
參考資料

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