強化學習進階
- 本文主要講解
- 動態規劃法（Dynamic Programming DP）
- 蒙特卡洛法（Monte Carlo MC）
- 時序差分法（Temporal Difference TD）
1. 動態規劃法
1.1 動態規劃概念
-
動態規劃核心思想：
- 其核心思想在于復雜問題的最優解劃分為多個小問題的最優解的求解問題，就像遞歸一樣，且子問題的最優解會被儲存起來重復利用。
-
動態規劃方法在強化學習中使用：
- 在已知狀態轉移概率和獎勵函數的前提下，通過反復更新值函數，找到最優策略的方法
1.2 動態規劃法的使用
-
動態規劃的前提：
-
環境是一個已知的馬爾可夫決策過程（MDP），必須知道：
-
狀態集合 S \mathcal{S} S
-
動作集合 A \mathcal{A} A
-
狀態轉移概率： P ( s ′ ∣ s , a ) P(s'|s,a) P(s′∣s,a)
-
獎勵函數： R ( s , a , s ′ ) R(s,a,s') R(s,a,s′)
-
-
在強化學習中，我們的目標是最大化累計獎勵。
- 相當于當知道獎勵函數和狀態轉換函數時，便可以根據下一個狀態的價值來更新當前狀態的價值
- 即可以把計算下一個可能狀態的價值當成一個子問題，而把計算當前狀態的價值看做當前問題
-
DP 的核心思想是：
- 把求解整個最優策略的問題，分解為求解每個狀態最優值的子問題。
-
這就符合動態規劃的精髓：最優子結構 + 重疊子問題。
-
1.2.1 方法一：策略迭代
1.2.1.1 策略評估（Policy Evaluation）
-
給定一個策略 π \pi π，估計每個狀態 s s s 的值函數 V π ( s ) V^\pi(s) Vπ(s)
-
公式如下（貝爾曼期望方程）：
V π ( s ) = ∑ a π ( a ∣ s ) ∑ s ′ P ( s ′ ∣ s , a ) [ R ( s , a , s ′ ) + γ V π ( s ′ ) ] V^\pi(s) = \sum_a \pi(a|s) \sum_{s'} P(s'|s,a) [R(s,a,s') + \gamma V^\pi(s')] Vπ(s)=a∑?π(a∣s)s′∑?P(s′∣s,a)[R(s,a,s′)+γVπ(s′)]- 用這個公式反復更新所有狀態的 V π ( s ) V^\pi(s) Vπ(s)，直到收斂。
1.2.2.2 策略改進（Policy Improvement）
-
有了 V π ( s ) V^\pi(s) Vπ(s) 之后，我們可以生成一個“更貪心”的策略。
-
做法：對每個狀態 s s s，選擇能使 Q π ( s , a ) Q^\pi(s,a) Qπ(s,a) 最大的動作：
KaTeX parse error: Can't use function '$' in math mode at position 2: $?\pi'(s) = \arg\…- 也就是：讓策略盡可能選“更高價值”的動作。
1.2.2.3 策略迭代（Policy Iteration）
-
將上面兩個步驟交替執行：
-
初始化一個策略 π \pi π
-
重復直到收斂：
-
策略評估：根據當前策略估算 V π ( s ) V^\pi(s) Vπ(s)
-
策略改進：更新策略 π ← π ′ \pi \leftarrow \pi' π←π′
-
-
-
最終會收斂到一個最優策略 π ? \pi^* π?。
1.2.2.4 算法流程圖
初始化 π
重復：1. 用 DP 做策略評估（多個循環直到 V 收斂）2. 用貪心策略改進 π ← π'
直到 π 不再變化
1.2.2 方法二：值迭代
-
不顯式做策略評估，而是直接用 Bellman 最優方程迭代值函數
-
核心公式：
V ( s ) ← max ? a ∑ s ′ P ( s ′ ∣ s , a ) [ R ( s , a , s ′ ) + γ V ( s ′ ) ] V(s) \leftarrow \max_a \sum_{s'} P(s'|s,a) [R(s,a,s') + \gamma V(s')] V(s)←amax?s′∑?P(s′∣s,a)[R(s,a,s′)+γV(s′)]- 每一步就朝著最優值推進，不需要再等策略完全評估完成。
-
算法流程圖
初始化 V(s) 隨便設 重復直到收斂：對每個 s：V(s) ← max_a Σ_s' P(s'|s,a) [R + γ V(s')] 最終通過 V 生成最優策略 π*(s) = argmax_a ...
1.3 方法的優缺點
-
優點
-
收斂快、穩定性強
- 利用完整的模型計算，可以精確推導價值函數的收斂。
-
可得最優策略
- 理論上保證找到最優值函數和策略。
-
結構清晰
- 策略評估+策略改進，邏輯明確，適合 理論推導和分析。
-
-
缺點
-
必須知道模型
- 很多實際問題中，環境狀態轉移和獎勵函數是未知的，無法使用 DP。
-
計算量大，不適合大規模狀態空間
- 每次更新都需要對所有狀態和動作進行遍歷計算。
-
不能從真實交互中學習
- 只能在離線已知模型上操作，不適合實際交互式學習。
-
-
以下是從參考文章中補充的數學推導
2. 蒙特卡洛法
2.1 蒙特卡洛方法概述
-
概念
- 蒙特卡洛(monte carlo，簡稱MC)方法，也稱為統計模擬方法，就是通過大量的隨機樣本來估算或近似真實值，比如近似估算圓的面經、近似定積分、近似期望、近似隨機梯度
-
強化學習中的應用
-
類似上面的例子，用蒙特卡洛方法來估計一個策略在一個馬爾可夫決策過程中的狀態價值。
-
考慮到一個狀態的價值是它的期望回報，我們用策略在MDP上采樣很多條序列，然后計算從這個狀態出發的回報，再求其期望： V π ( s ) = E π [ G t ∣ S t = s ] = 1 N ∑ i = 1 N G t ( i ) V_\pi (s) = E_\pi [G_t|S_t = s] = \frac{1}{N} \sum_{i=1}^{N}G_{t}^{(i)} Vπ?(s)=Eπ?[Gt?∣St?=s]=N1?∑i=1N?Gt(i)?
-
通俗定義
- 蒙特卡洛方法是通過多次試驗采樣完整軌跡，然后用這些軌跡中的實際回報來估計狀態或動作的價值，從而改進策略。
-
2.2 蒙特卡洛方法使用
2.2.1 策略評估階段
-
在這一步，我們只是評估當前策略 π \pi π 的效果，不改變它。
-
流程如下：
-
固定策略 π \pi π，用它與環境交互，采樣多次軌跡。
-
從每條軌跡中收集回報 G t G_t Gt?，估計每個狀態 s s s 或狀態-動作對 ( s , a ) (s, a) (s,a) 的價值（即 V ( s ) V(s) V(s) 或 Q ( s , a ) Q(s, a) Q(s,a)）。
-
此階段策略是人為設定或初始定義的，不會改變。
-
-
舉例
- 「每次都往右走多一點」是當前策略，那你就照這個策略模擬很多次，把每個點走后的總收益 G t G_t Gt? 記錄下來，用于評價“這套策略好不好”。
2.2.2 策略改進階段
-
用估計的價值函數，來更新策略
-
這個階段，我們根據估計出來的值函數來調整策略：
-
方法一：貪婪策略改進（Greedy）
-
如果我們有了動作價值函數 Q ( s , a ) Q(s,a) Q(s,a)，那么我們可以對策略這樣更新： π ′ ( s ) = arg ? max ? a Q ( s , a ) \pi'(s) = \arg\max_a Q(s, a) π′(s)=argmaxa?Q(s,a)
-
也就是說，在每個狀態 s s s 中，選擇價值最高的動作作為新的策略。
-
-
方法二：ε-貪婪策略改進（探索+利用）
-
因為純貪婪可能陷入局部最優，MC 通常使用 ε-貪婪策略：
-
以 1 ? ε 1 - \varepsilon 1?ε 的概率選擇最優動作；
-
以 ε \varepsilon ε 的概率隨機選一個動作，鼓勵探索。
-
-
就是增加一個參數來控制
-
2.3 方法的優缺點
-
優點
-
不需要知道模型
- 可以從與環境的交互中直接學習，適用于模型未知的情況。
-
簡單直觀
- 基于“真實經驗軌跡”估算期望回報，更貼近現實過程。
-
適合非馬爾可夫任務的評估
- 如果任務不是嚴格的 MDP，MC 也能處理。
-
-
缺點
-
必須等一整條軌跡結束才能學習（Delayed update）
- 不能在線更新，每次更新都要等 episode 結束，不適合無限期任務。
-
高方差
- 一條軌跡可能包含很多隨機性，導致估計不穩定。
-
效率低
- 需要大量完整軌跡才能得到準確估計，收斂速度慢。
-
3. 時序差分法
- 時序差分法是一種結合了動態規劃（DP）和蒙特卡洛（MC）方法優點的學習方法：
- 它像 MC 一樣從經驗中學習，但像 DP 一樣每一步就更新價值函數
3.1 方法的核心思想
-
在一個狀態 s t s_t st?，執行一個動作 a t a_t at?，然后觀察到獎勵 r t + 1 r_{t+1} rt+1? 和下一個狀態 s t + 1 s_{t+1} st+1?。
-
用以下公式更新當前狀態價值：
V ( s t ) ← V ( s t ) + α ? [ R t + 1 + γ V ( s t + 1 ) ? 時序差分目標 ? V ( s t ) ] ? 時序差分誤差?TD?Error V(s_t) \leftarrow V(s_t) + \alpha \cdot \underbrace{[\overbrace {R_{t+1} + \gamma V(s_{t+1})}^{\text{時序差分目標}} - V(s_t)]}_{\text{時序差分誤差 TD Error}} V(st?)←V(st?)+α?時序差分誤差?TD?Error [Rt+1?+γV(st+1?) ?時序差分目標??V(st?)]??-
α \alpha α：學習率（多快學新信息）
-
γ \gamma γ：折扣因子
-
T D E r r o r = 目標值 ? 當前估計 TD\ Error = \text{目標值} - \text{當前估計} TD?Error=目標值?當前估計
-
-
通俗理解：
- 原來以為這一步能拿5分，現在從下一個狀態估計來看其實是7分，那我就修正一下對當前狀態的估計
-
以下是參考文章對于公式的講解
-
3.2 方法流程
-
以TD(0)為評估策略
-
初始化狀態價值函數 V ( s ) V(s) V(s)
-
從起始狀態開始與環境交互（執行當前策略）
-
每走一步：
-
得到當前狀態 s s s、獎勵 r r r、下一狀態 s ′ s' s′
-
用上述 TD 公式更新 V ( s ) V(s) V(s)
-
-
不斷重復以上過程，直到收斂
-
-
三種方法對比
- MC的做法相當于一條道走到黑 沒走個10公里不回頭
- DP相當于所有道比如10條道 每條道都走個1公里 不錯過任何一條可能成為最好道的可能，最后10條道都走完1公里后才返回匯報/反饋
- TD則相當于先選一條道走個1公里即返回匯報/反饋，之后再走下一條道的1公里
參考文章
)
