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

###### tags: `reinforcement learning` # 深度強化學習 Ch3.1 : TD learning ## 1. 簡介 TD-learning (Temporal-Difference Learning) 是強化學習中很重要的方法類旗下延伸包含了許多不同的演算法，像 Q-learning、 Sarsa 等。此方法結合了 [蒙地卡羅方法] 和 [動態規劃] 兩種想法誕生，因為動態規劃通常會需要一個規律模型，但在強化學習中有太多不確定情況，無法直接取得模型所以使用了蒙地卡羅方法來做不停地嘗試尋找規律來得出模型。 :::spoiler :secret:動態規劃簡介 :::warning 動態規劃可以將一個問題分解成許多子問題，並找出其解決規律模型 :::info ex : 解階層問題 $n!$ 可以寫成 $a_n=n!=1*2*3*...n$ 如果將它進行動態規劃可以發現 $a_2=2!=1*2$ $a_3=3!=a_2 * 3=1*2*3$ 最後可以得到 $a_n=n!=a_{n-1}*n$ 所以要解決階層問題就不用重算一遍，把之前的 $a_{n-1}$ 值拿出來用就好了 ::: :::spoiler :secret:蒙地卡羅方法簡介 :::warning 蒙地卡羅方法在這邊也可以理解為[試誤學習] 也就是大量的嘗試，在錯誤中學習規律 ::: ::: TD learning 是由以下元素組成 : - ==**TD Target**== : 要學習的目標，會希望動作價值函數 Q 可以近似此目標 - ==**TD error**== : 與 Target 的差距 - ==**Update**== : 更新 Q 值，也就是演算法本身 TD learning 又分成兩類型 - **On Policy** : 會從資料當中學習到同一種策略($\pi$)，再進行改進 **ex : Sarsa($\pi$** 為 $\epsilon$ 貪婪策略) - **off Policy** : 沒有固定策略，會利用學習到的經驗根據當前狀態推斷出動作的價值，也就是其學習到的策略是獨立於訓練資料 ex : Q-learning --- ## 2. Sarsa 演算法 Sarsa 是 on-Policy 的 TD learning 經典演算法，使用當前回報和下一時刻的估計來計算目標 ### (1). TD target 動作價值函數 Q 反映了 [ 動作,狀態對 ] 的價值，TD target 就是要估計下一時刻的 Q 並讓現在的 Q 近似預測的 Q，找出預測的 Q 叫做 Target :::warning **TD target : $y_t = r_{t+1}+{\gamma}*Q_{\pi}(s_{t+1}, A_{t+1})$** - $r_{t+1}$ : 當前動作得到的 reward - $s_{t+1}$, $A_{t+1}$ : State, Action - $Q$ : 動作價值函數解釋 : TD target 就是之後要學習近似的目標 ::: :::spoiler :secret:**數學推導** :::info **數學推導** : - 因為要計算未來 Q ，先整理一下 $U_t$ (Return) $U_t=R_{t+1}+{\gamma}R_{t+2}+{\gamma}^2R_{t+3}... =R_{t+1}+{\gamma}*(R_{t+2}+{\gamma}R_{t+3}+...)$ $U_t=R_{t+1}+{\gamma}*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)\longleftarrow y_t=r_{t+1}+{\gamma}Q_{\pi}(s_{t+1},A_{t+1})$ ::: ::: ### (2). TD Error TD error 其實只是 Q 與 TD target 的差距 :::warning **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 做更動通常演算法會直接用此式表示 :::warning $Q_{\pi}(a_t,s_t)\longleftarrow Q_{\pi}(a_t,s_t)-{\alpha}*{\delta}_t$ **$Q_{\pi}(a_t,s_t)\longleftarrow 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$ : 學習率 - :bangbang: 在最左邊的 $Q_{\pi}(a_t,s_t)$ 是指更新後的 Q，其餘右邊的 $Q_{\pi}(a_t,s_t)$ 是當前 Q ::: 整個 Sarsa 可以下圖結構表示 (利用未來預測 Q 來影響更新當前 Q) 當 Q 更新越來越大，回饋也就提升。 ![](https://i.imgur.com/uPtrGu5.jpg =350x400) --- ## 3. Q-Learning Q-learning 與 Sarsa 的原理非常相似，只差在未來選擇動作 $a_{t+1}$ 時 Sarsa 只有一種選擇策略並做出一動作，而 Q learning 會選出多個動作，並挑出其中 Q 值最大的動作 ### (1). TD target :::warning **TD target : $y_t = r_{t+1}+{\gamma}*\mathop{max}\limits_{a}Q^{*}(s_{t+1}, A)$** - $r_{t+1}$ : 當前動作得到的 reward - $s_{t+1}$ : 未來的 State - $A$ : 動作空間 - $Q^*$ : 最大動作價值函數 ::: :::spoiler :secret:**數學推導** :::info **數學推導** : - 前面步驟都與 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^*(a_t,s_t)=E(R_{t+1}+{\gamma}Q^*(S_{t+1},A_{t+1})\mid s_t,a_t)$ - 動作 $A_{t+1}$ 會取得最大回饋，可以寫成以下公式 $A_{t+1}=\mathop{argmax}\limits_{a}Q^*(S_{t+1},A)$ $Q^*(S_{t+1},A_{t+1}) =\mathop{max}\limits_{a}Q_{\pi}(S_{t+1},A)$ - 接著代換 $Q^*(a_t,s_t)$ 公式 $Q^*(a_t,s_t)=E(R_{t+1}+{\gamma}\mathop{max}\limits_{a}Q_{\pi}(S_{t+1},A)\mid s_t,a_t)$ - 使用蒙地卡羅近似求期望 $Q_{\pi}(a_t,s_t)\longleftarrow y_t=r_{t+1}+{\gamma}\mathop{max}\limits_{a}Q_{\pi}(s_{t+1},A)$ ::: ::: ### (2). TD Error :::warning **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 :::warning **$Q_{\pi}(a_t,s_t)\longleftarrow Q_{\pi}(a_t,s_t)-{\alpha}(r_{t+1}+{\gamma}\mathop{max}\limits_{a}Q_{\pi}(s_{t+1}, A)-Q_{\pi}(a_t,s_t))$** - $\alpha$ : 學習率 - $\mathop{max}\limits_{a}Q_{\pi}(s_{t+1}, A)$ : 未來狀態預測出的最大動作價值 - :bangbang: 在最左邊的 $Q_{\pi}(a_t,s_t)$ 是指更新後的 Q，其餘右邊的 $Q_{\pi}(a_t,s_t)$ 是當前 Q ::: 下圖為 Q-learning 結構，可以看到每使用策略($\pi$)找出多個 action 後再用貪婪策略選出有最大 Q 的動作，利用此期望回饋影響當前 Q ![](https://i.imgur.com/wfCgyvI.jpg =400x400) --- Reference - [Temporal-Difference (TD) Learning](https://towardsdatascience.com/temporal-difference-learning-47b4a7205ca8) - [强化学习基础之TD-learning](https://zhuanlan.zhihu.com/p/75622421) - [Sarsa算法 (TD Learning 1/3) | Shusen Wang](https://www.youtube.com/watch?v=-cYWdUubB6Q) - [Q-Learning算法 (TD Learning 2/3) | Shusen Wang](https://www.youtube.com/watch?v=Ymy2w3DGn2U)