tags: reinforcement learning

深度強化學習 Ch3.1 : TD learning

1. 簡介

TD-learning (Temporal-Difference Learning) 是強化學習中很重要的方法類
旗下延伸包含了許多不同的演算法，像 Q-learning、 Sarsa 等。

此方法結合了 [蒙地卡羅方法] 和 [動態規劃] 兩種想法誕生，
因為動態規劃通常會需要一個規律模型，但在強化學習中有太多不確定情況，無法直接取得模型
所以使用了蒙地卡羅方法來做不停地嘗試尋找規律來得出模型。

動態規劃簡介

動態規劃可以將一個問題分解成許多子問題，並找出其解決規律模型

ex : 解階層問題

$n!$ 可以寫成

$a_n=n!=1\ast 2\ast 3\ast ...n$
如果將它進行動態規劃可以發現

$a_2=2!=1\ast 2$

$a_3=3!=a_2\ast 3=1\ast 2\ast 3$
最後可以得到

$a_n=n!=a_{n-1}\ast n$
所以要解決階層問題就不用重算一遍，把之前的

$a_{n-1}$ 值拿出來用就好了

蒙地卡羅方法簡介

蒙地卡羅方法在這邊也可以理解為[試誤學習]
也就是大量的嘗試，在錯誤中學習規律

TD learning 是由以下元素組成 :

• TD Target : 要學習的目標，會希望動作價值函數 Q 可以近似此目標
• TD error : 與 Target 的差距
• Update : 更新 Q 值，也就是演算法本身
  
  

TD learning 又分成兩類型

• On Policy : 會從資料當中學習到同一種策略(
  $\pi$)，再進行改進 ex : Sarsa(
  $\pi$ 為
  $ϵ$ 貪婪策略)
• off Policy : 沒有固定策略，會利用學習到的經驗根據當前狀態推斷出動作的價值，
  也就是其學習到的策略是獨立於訓練資料 ex : Q-learning

---

2. Sarsa 演算法

Sarsa 是 on-Policy 的 TD learning 經典演算法，使用當前回報和下一時刻的估計來計算目標

(1). TD target

動作價值函數 Q 反映了 [ 動作,狀態對 ] 的價值，TD target 就是要估計下一時刻的 Q
並讓現在的 Q 近似預測的 Q，找出預測的 Q 叫做 Target

TD target :

$y_t=r_{t+1}+\gamma \ast Q_{\pi }(s_{t+1},A_{t+1})$

• $r_{t+1}$ : 當前動作得到的 reward
• $s_{t+1}$,
  $A_{t+1}$ : State, Action
• $Q$ : 動作價值函數

解釋 : TD target 就是之後要學習近似的目標

數學推導

數學推導 :

• 因為要計算未來 Q ，先整理一下

  $U_t$ (Return)
  
  $U_t=R_{t+1}+\gamma R_{t+2}+{\gamma }^2{R}_{t+3}...=R_{t+1}+\gamma \ast (R_{t+2}+\gamma R_{t+3}+...)$
  
  $U_t=R_{t+1}+\gamma \ast U_{t+1}$

• 計算動作價值函數
  

  $Q_{\pi }(a_t,s_t)=E(U_t\mid s_t,a_t)=E(R_{t+1}+\gamma U_{t+1}\mid s_t,a_t)$
  
  $Q_{\pi }(a_t,s_t)=E(R_{t+1}\mid s_t,a_t)+E(\gamma U_{t+1}\mid s_t,a_t)$
  
  $Q_{\pi }(a_t,s_t)=E(R_{t+1}\mid s_t,a_t)+\gamma Q_{\pi }(S_{t+1},A_{t+1})$

• 後方的

  $\gamma Q_{\pi }(S_{t+1},A_{t+1})$ 雖然做過期望了，但是 是對
  $S_{t+2},A_{t+2}...$ 執行，
  剩下的
  $S_{t+1},A_{t+1}$ 還是未知所以還可放進
  $a_t,s_t$ 中求期望
  
  $Q_{\pi }(a_t,s_t)=E(R_{t+1}+\gamma Q_{\pi }(S_{t+1},A_{t+1})\mid s_t,a_t)$

• 但要直接求出此期望太過困難(能直接求就不用近似啦!)，所以使用蒙地卡羅近似求期望
  

  $Q_{\pi }(a_t,s_t)⟵y_t=r_{t+1}+\gamma Q_{\pi }(s_{t+1},A_{t+1})$

(2). TD Error

TD error 其實只是 Q 與 TD target 的差距

TD Error :

${\delta }_t=y_t-Q_{\pi }(a_t,s_t)$

• $y_t$ : TD target
• $Q_{\pi }$ : 當前實際 Q 值

(3). Update

這個步驟會更新

$Q_{\pi }$，用當前

$Q_{\pi }$ 減去 error 做更動
通常演算法會直接用此式表示

$Q_{\pi }(a_t,s_t)⟵Q_{\pi }(a_t,s_t)-\alpha \ast {\delta }_t$

$Q_{\pi }(a_t,s_t)⟵Q_{\pi }(a_t,s_t)-\alpha (r_{t+1}+\gamma Q_{\pi }(s_{t+1},A_{t+1})-Q_{\pi }(a_t,s_t))$

• $\alpha$ : 學習率
• 在最左邊的
  $Q_{\pi }(a_t,s_t)$ 是指更新後的 Q，其餘右邊的
  $Q_{\pi }(a_t,s_t)$ 是當前 Q

整個 Sarsa 可以下圖結構表示 (利用未來預測 Q 來影響更新當前 Q)
當 Q 更新越來越大，回饋也就提升。

---

3. Q-Learning

Q-learning 與 Sarsa 的原理非常相似，只差在未來選擇動作

$a_{t+1}$ 時
Sarsa 只有一種選擇策略並做出一動作，
而 Q learning 會選出多個動作，並挑出其中 Q 值最大的動作

(1). TD target

TD target :

$y_t=r_{t+1}+\gamma \ast \underset{a}{max}{Q}^{\ast }(s_{t+1},A)$

• $r_{t+1}$ : 當前動作得到的 reward
• $s_{t+1}$ : 未來的 State
• $A$ : 動作空間
• $Q^{\ast }$ : 最大動作價值函數

數學推導

數學推導 :

• 前面步驟都與 Sarsa 相同，得到此式
  

  $Q_{\pi }(a_t,s_t)=E(R_{t+1}+\gamma Q_{\pi }(S_{t+1},A_{t+1})\mid s_t,a_t)$

• 因為要求多個 action 下的 max 值
  

  $Q^{\ast }(a_t,s_t)=E(R_{t+1}+\gamma Q^{\ast }(S_{t+1},A_{t+1})\mid s_t,a_t)$

• 動作

  $A_{t+1}$ 會取得最大回饋，可以寫成以下公式
  
  $A_{t+1}=\underset{a}{argmax}{Q}^{\ast }(S_{t+1},A)$
  
  $Q^{\ast }(S_{t+1},A_{t+1})=\underset{a}{max}{Q}_{\pi }(S_{t+1},A)$

• 接著代換

  $Q^{\ast }(a_t,s_t)$ 公式
  
  $Q^{\ast }(a_t,s_t)=E(R_{t+1}+\gamma \underset{a}{max}{Q}_{\pi }(S_{t+1},A)\mid s_t,a_t)$

• 使用蒙地卡羅近似求期望
  

  $Q_{\pi }(a_t,s_t)⟵y_t=r_{t+1}+\gamma \underset{a}{max}{Q}_{\pi }(s_{t+1},A)$

(2). TD Error

TD Error :

${\delta }_t=y_t-Q_{\pi }(a_t,s_t)$

• $y_t$ : TD target
• $Q_{\pi }(a_t,s_t)$ : 當前實際 Q 值

(3). Update

$Q_{\pi }(a_t,s_t)⟵Q_{\pi }(a_t,s_t)-\alpha (r_{t+1}+\gamma \underset{a}{max}{Q}_{\pi }(s_{t+1},A)-Q_{\pi }(a_t,s_t))$

• $\alpha$ : 學習率
• $\underset{a}{max}{Q}_{\pi }(s_{t+1},A)$ : 未來狀態預測出的最大動作價值
• 在最左邊的
  $Q_{\pi }(a_t,s_t)$ 是指更新後的 Q，其餘右邊的
  $Q_{\pi }(a_t,s_t)$ 是當前 Q

下圖為 Q-learning 結構，可以看到每使用策略(

$\pi$)找出多個 action 後
再用貪婪策略選出有最大 Q 的動作，利用此期望回饋影響當前 Q

---

Reference

• Temporal-Difference (TD) Learning
• 强化学习基础之TD-learning
• Sarsa算法 (TD Learning 1/3) | Shusen Wang
• Q-Learning算法 (TD Learning 2/3) | Shusen Wang