強化學習策略生成：蒙特卡洛與價值迭代解析

– 22 分鐘閱讀

強化學習的核心在於尋找最優決策策略，而實現此目標主要有兩大路徑：無模型學習與模型驅動方法。本文將深入剖析這兩種典範的代表性演算法。蒙特卡洛策略生成體現了從經驗中直接學習的直觀思想，它不需預先理解環境規則，而是透過反覆試驗與結果統計來逼近最佳策略，適用於複雜或未知的模擬環境。與之對應，價值迭代作為動態規劃的經典演算法，是一種模型驅動的精確解法。它假設我們擁有完整的環境模型，並利用貝爾曼方程進行迭代計算，以求得全局最優的價值函數。透過對比這兩種方法的原理與限制，我們能更深刻地理解強化學習中理論與實踐的權衡。

蒙特卡洛策略生成：從經驗中學習

蒙特卡洛策略生成（Monte Carlo Policy Generation）是強化學習中一種重要的無模型方法，它透過與環境進行大量的幕（Episodes）互動，從實際經驗中估計價值函數和策略，而無需事先知道環境的動態模型。這種方法特別適用於那些環境模型難以獲取或過於複雜的問題。

蒙特卡洛方法的基礎

蒙特卡洛方法的核心思想是利用大數定律。透過重複採樣一個隨機過程，並計算其平均結果，我們可以近似該過程的期望值。在強化學習中，這意味著：

  1. 經驗採樣：智能體與環境互動，生成一系列的狀態、動作、獎勵序列，即一個完整的幕 $S_0, A_0, R_1, S_1, A_1, R_2, \dots, S_T$。
  2. 回報計算：對於每個狀態-動作對 $(s, a)$，計算其在該幕中之後獲得的折扣累積獎勵（回報 $G_t$）。
  3. 平均回報：將所有訪問過 $(s, a)$ 的回報進行平均，作為其動作價值函數 $Q(s, a)$ 的估計。

蒙特卡洛策略生成流程

蒙特卡洛策略生成通常透過蒙特卡洛控制（Monte Carlo Control）來實現，它結合了蒙特卡洛策略評估和策略改進，形成一個迭代過程：

  1. 初始化：
    • 初始化一個隨機策略 $\pi$。
    • 初始化所有狀態-動作對的價值 $Q(s, a)$ 為任意值。
    • 初始化每個狀態-動作對的訪問計數 $N(s, a)$ 為0。
  2. 生成幕：
    • 根據當前策略 $\pi$（通常是 $\epsilon$-貪婪策略，以確保探索），智能體與環境互動，直到一個幕結束（達到終止狀態）。
    • 記錄該幕中的所有狀態、動作和獎勵序列：$S_0, A_0, R_1, S_1, A_1, R_2, \dots, S_T$。
  3. 策略評估（蒙特卡洛評估）：
    • 對於該幕中的每個時間步 $t=0, \dots, T-1$：
      • 計算從該時間步開始的回報 $G_t = R_{t+1} + \gamma R_{t+2} + \dots + \gamma^{T-t-1} R_T$。
      • 如果 $(S_t, A_t)$ 是該幕中第一次被訪問（首次訪問蒙特卡洛）或每次訪問都更新（每次訪問蒙特卡洛）：
        • 增加 $N(S_t, A_t)$ 的計數。
        • 更新 $Q(S_t, A_t) \leftarrow Q(S_t, A_t) + \frac{1}{N(S_t, A_t)} (G_t - Q(S_t, A_t))$。這是一個增量式平均更新。
  4. 策略改進：
    • 基於更新後的 $Q(s, a)$ 值，改進策略 $\pi$。通常是透過貪婪策略改進，即在每個狀態 $s$ 下，選擇能夠最大化 $Q(s, a)$ 的動作。
    • 為了確保持續探索，通常會使用 $\epsilon$-貪婪策略。
  5. 重複：重複步驟2-4，直到策略和價值函數收斂。

蒙特卡洛方法的優勢與挑戰

優勢：

  • 無模型：無需環境模型，可以直接從經驗中學習。
  • 增量式學習：可以逐步更新價值函數，無需等待所有數據。
  • 處理非馬可夫環境：在某些情況下，即使環境不完全滿足馬可夫性質，蒙特卡洛方法也能在一定程度上工作。

挑戰：

  • 高方差：回報 $G_t$ 的計算依賴於整個幕的隨機序列，導致估計值方差較大，可能需要大量的幕才能收斂。
  • 不適用於連續任務：對於沒有明確終止狀態的連續任務，計算無限期的回報是困難的。
  • 探索問題：如果智能體從未訪問過某些狀態-動作對，其價值將無法被估計。這需要有效的探索策略。
  • 收斂速度：由於方差較大，蒙特卡洛方法通常比時序差分方法收斂慢。

儘管存在挑戰，蒙特卡洛策略生成因其無模型的特性和直觀的原理，在許多強化學習問題中仍是一個重要的工具，尤其是在可以輕鬆生成大量經驗的模擬環境中。

此圖示：蒙特卡洛策略生成流程

  graph TD
    A[初始化策略 $\pi$ 和 $Q(s,a)$] --> B{生成一個幕 (Episode)};
    B --> C[智能體與環境互動];
    C --> D[記錄 (s, a, r, s') 序列];
    D --> E[幕結束];
    E --> F{對於幕中每個 (s,a) 對};
    F --> G[計算該 (s,a) 對的回報 $G_t$];
    G --> H[更新 $Q(s,a)$ (平均回報)];
    H --> I[更新訪問計數 $N(s,a)$];
    I --> F;
    F --> J[策略改進 (例如 $\epsilon$-貪婪)];
    J --> K{是否收斂?};
    K -- 否 --> B;
    K -- 是 --> L[得到最優策略 $\pi^*$];

看圖說話：

此圖示描繪了蒙特卡洛策略生成的迭代過程。首先，初始化策略 $\pi$ 和動作價值函數 $Q(s,a)$。接著進入一個循環，生成一個幕，這涉及智能體與環境互動，並記錄狀態、動作、獎勵、下一狀態的序列，直到幕結束。然後，對於該幕中每個被訪問的狀態-動作對 $(s,a)$，計算從該點開始的回報 $G_t$，並更新 $Q(s,a)$，通常是透過對回報進行平均。同時，更新訪問計數 $N(s,a)$。完成所有 $(s,a)$ 對的更新後，進行策略改進，例如使用 $\epsilon$-貪婪策略。最後，檢查是否收斂。如果沒有收斂，則繼續生成新的幕；如果收斂，則得到最優策略 $\pi^*$。

價值迭代與動態規劃：模型驅動的最優解

價值迭代（Value Iteration）是動態規劃（Dynamic Programming）在強化學習中的一種核心算法，用於在模型已知（即狀態轉移概率 $P(s’|s,a)$ 和獎勵函數 $R(s,a,s’)$ 已知）的有限馬可夫決策過程（MDPs）中，找到最優策略和最優價值函數。它透過迭代地應用貝爾曼最優方程，直接計算出最優狀態價值函數 $V^*(s)$。

價值迭代的核心思想

價值迭代的基礎是最優貝爾曼方程： $$V^(s) = \max_{a \in \mathcal{A}} \sum_{s’ \in \mathcal{S}, r \in \mathcal{R}} P(s’, r | s, a) [r + \gamma V^(s’)]$$ 這個方程是一個非線性的遞歸關係，它表明一個狀態的最優價值，等於在該狀態下，選擇能帶來最大預期累積獎勵的動作所能獲得的價值。價值迭代算法透過將這個方程作為一個更新規則，從任意初始價值函數 $V_0(s)$ 開始，迭代地更新 $V_k(s)$，直到收斂到 $V^*(s)$。

價值迭代算法步驟

  1. 初始化：
    • 初始化所有狀態的價值函數 $V(s)$ 為任意值（通常為0）。
    • 設定一個小的收斂閾值 $\theta > 0$。
  2. 迭代更新：重複以下步驟，直到價值函數收斂： a. 初始化 $\Delta = 0$（用於監測最大價值變化）。 b. 對於每個狀態 $s \in \mathcal{S}$： i. 保存當前狀態的舊價值：$v = V(s)$。 ii. 計算所有可能動作的Q值： $$Q(s, a) = \sum_{s’ \in \mathcal{S}, r \in \mathcal{R}} P(s’, r | s, a) [r + \gamma V(s’)]$$ iii. 更新狀態價值函數為所有動作Q值的最大值： $$V(s) = \max_{a \in \mathcal{A}} Q(s, a)$$ iv. 更新最大價值變化：$\Delta = \max(\Delta, |v - V(s)|)$。 c. 如果 $\Delta < \theta$，則算法收斂，停止迭代。
  3. 提取最優策略：一旦 $V(s)$ 收斂到 $V^(s)$，最優策略 $\pi^(s)$ 可以透過對 $V^(s)$ 進行一次貪婪操作來導出： $$\pi^(s) = \arg\max_{a \in \mathcal{A}} \sum_{s’ \in \mathcal{S}, r \in \mathcal{R}} P(s’, r | s, a) [r + \gamma V^*(s’)]$$

價值迭代的特點與優勢

  • 收斂保證：在有限MDPs中，價值迭代保證會收斂到唯一的最優價值函數 $V^*(s)$。
  • 效率：通常比策略迭代收斂更快，因為它在每次迭代中都直接考慮最優動作，而不是先完全評估一個策略。
  • 模型驅動：需要完整的環境模型（狀態轉移概率和獎勵函數）。

挑戰與限制

  • 模型需求：最大的限制是需要已知環境模型。在許多實際問題中，模型難以獲取或過於複雜。
  • 狀態空間爆炸：對於狀態空間非常大的問題，遍歷所有狀態和動作來更新價值函數的計算成本會非常高。
  • 連續狀態/動作空間：價值迭代通常不適用於具有連續狀態或動作空間的問題，因為無法遍歷所有可能的狀態-動作對。

儘管存在這些限制，價值迭代作為動態規劃的經典算法，在模型已知且狀態空間相對較小的問題中，仍然是尋找最優策略的強大工具。它為理解強化學習的核心原理提供了堅實的基礎。

此圖示：價值迭代流程

  graph TD
    A[初始化 $V(s)$ 為0, 設定 $\theta$] --> B{循環: 監測 $\Delta$};
    B --> C[對於每個狀態 $s$];
    C --> D[保存 $v_{old} = V(s)$];
    D --> E[計算所有動作 $a$ 的 $Q(s,a)$];
    E --> F[更新 $V(s) = \max_a Q(s,a)$];
    F --> G[更新 $\Delta = \max(\Delta, |v_{old} - V(s)|)$];
    G --> C;
    C --> H{如果 $\Delta < \theta$?};
    H -- 否 --> B;
    H -- 是 --> I[收斂到 $V^*(s)$];
    I --> J[提取最優策略 $\pi^*$];

看圖說話：

此圖示展示了價值迭代算法的詳細流程。首先，初始化所有狀態的價值函數 $V(s)$ 為0，並設定一個收斂閾值 $\theta$。接著進入一個循環，該循環的目標是監測最大價值變化 $\Delta$。在每次循環中，算法會對於每個狀態 $s$ 進行處理：首先保存當前狀態的舊價值 $v_{old}$，然後計算所有可能動作 $a$ 的 $Q(s,a)$ 值，這個計算依賴於當前的 $V(s’)$ 估計。接著，更新 $V(s)$ 為所有動作 $Q(s,a)$ 的最大值。隨後，更新 $\Delta$，記錄本次迭代中所有狀態的最大價值變化。如果**$\Delta$ 小於 $\theta$，則表示價值函數已經收斂到 $V^(s)$**，循環結束。最後，從收斂的 $V^(s)$ 中提取最優策略 $\pi^*$。

實作價值迭代：將理論轉化為程式碼

實作價值迭代（Implementing Value Iteration）是將抽象的動態規劃理論轉化為具體可執行程式碼的過程。它涉及對狀態空間、動作空間、轉移概率和獎勵函數的精確定義，以及對迭代更新邏輯的程式化實現。一個成功的實作不僅能驗證理論，還能為解決實際問題提供強大的工具。

實作考量與步驟

  1. 環境建模：

    • 狀態表示：如何將環境的狀態編碼為程式碼中的數據結構（例如，整數、元組、自定義類）。對於網格世界，狀態可以是 $(x, y)$ 座標。對於庫存控制，狀態可以是當前庫存量。
    • 動作表示：如何將動作編碼為程式碼中的數據結構。
    • 轉移概率 $P(s’|s,a)$：這通常是一個字典、矩陣或函數，它接收當前狀態 $s$ 和動作 $a$，返回一個下一狀態 $s’$ 及其概率的分佈。
    • 獎勵函數 $R(s,a,s’)$：這也是一個字典或函數，接收 $s, a, s’$，返回即時獎勵。
    • 折扣因子 $\gamma$：一個浮點數。

  2. 初始化價值函數：

    • 創建一個字典或數組來存儲每個狀態的價值 $V(s)$。
    • 將所有 $V(s)$ 初始化為0。

  3. 迭代循環：

    • 使用 while True 循環來進行迭代，直到收斂。
    • 在每次迭代開始時，設定一個變量 max_delta = 0 來追蹤本次迭代中價值函數的最大變化量。
    • 對於環境中的每個狀態 $s$：
      • 保存當前 $V(s)$ 的舊值：old_v = V[s]。
      • 計算所有可能動作 $a$ 的Q值。這通常涉及一個內部循環：
        • 對於每個動作 $a \in \mathcal{A}(s)$：
          • 計算 $Q(s, a)$。這需要遍歷所有可能的下一狀態 $s’$ 及其概率 $P(s’|s,a)$，並使用當前的 $V(s’)$ 估計。
          • q_value = sum(P(s'|s,a) * (R(s,a,s') + gamma * V[s']) for s' in next_states)
        • 找到所有 $Q(s, a)$ 中的最大值：max_q = max(q_values_for_s)。
      • 更新 $V(s)$：V[s] = max_q。
      • 更新 max_delta = max(max_delta, abs(old_v - V[s]))。
    • 在完成所有狀態的更新後，檢查 max_delta。如果 max_delta < theta（收斂閾值），則 break 循環。

  4. 提取最優策略：

    • 在價值函數 $V(s)$ 收斂後，創建一個字典或數組來存儲每個狀態的最優動作 $\pi^*(s)$。
    • 對於每個狀態 $s$：
      • 再次計算所有可能動作 $a$ 的Q值，但這次使用收斂後的 $V^*(s’)$。
      • 選擇能夠最大化Q值的動作作為 $\pi^*(s)$。
      • optimal_policy[s] = argmax_a(Q(s,a))。

失敗案例分析：浮點數精度與收斂問題

玄貓在實作一個小型迷宮遊戲的價值迭代時，發現算法有時無法收斂，或者收斂速度非常慢。經過調試，發現問題出在浮點數精度和收斂閾值 $\theta$ 的選擇上。

  • 浮點數精度：在計算 $Q(s,a)$ 和更新 $V(s)$ 時，由於浮點數運算可能存在微小的誤差，導致 $V(s)$ 的變化永遠無法完全為零，即使實際上已經收斂。
  • 收斂閾值 $\theta$ 過小：如果將 $\theta$ 設定得過小（例如 $10^{-10}$），算法可能需要極長的迭代次數才能達到這個極高的精度要求，甚至因為浮點數誤差而永遠無法達到。

學習心得：

  1. 選擇合適的收斂閾值：$\theta$ 不應過小，通常 $10^{-4}$ 到 $10^{-6}$ 是一個合理的範圍，它平衡了精度和收斂速度。
  2. 迭代次數限制：為了防止無限循環，即使沒有達到收斂閾值，也應設定一個最大迭代次數。
  3. 數值穩定性：在涉及大量浮點數運算的算法中，需要注意數值穩定性。在某些情況下，可能需要使用更高精度的數據類型或調整計算順序。
  4. 測試案例：使用簡單且已知最優解的測試案例來驗證實作的正確性，有助於快速定位問題。

實作價值迭代不僅是程式設計的練習，更是對強化學習理論深刻理解的體現。透過仔細的環境建模和精確的程式邏輯，我們可以將這個強大的算法應用於解決各種決策問題。

此圖示：價值迭代實作邏輯

  graph TD
    A[定義狀態、動作空間] --> B[定義轉移概率 P(s'|s,a)];
    B --> C[定義獎勵函數 R(s,a,s')];
    C --> D[設定折扣因子 $\gamma$ 和閾值 $\theta$];
    D --> E[初始化 $V(s)$ 為0];
    E --> F{循環: $\Delta = 0$};
    F --> G[對於每個狀態 $s$];
    G --> H[保存 $v_{old} = V[s]$];
    H --> I[計算 $Q_{values}$ for $s$];
    I --> J[更新 $V[s] = \max(Q_{values})$];
    J --> K[更新 $\Delta = \max(\Delta, |v_{old} - V[s]|)$];
    K --> G;
    G --> L{如果 $\Delta < \theta$?};
    L -- 否 --> F;
    L -- 是 --> M[收斂 $V^*(s)$];
    M --> N[從 $V^*(s)$ 提取 $\pi^*(s)$];

看圖說話：

此圖示詳細展示了價值迭代的實作邏輯。首先，需要定義狀態、動作空間以及轉移概率 $P(s’|s,a)$ 和獎勵函數 $R(s,a,s’)$，這些是環境模型的核心。接著，設定折扣因子 $\gamma$ 和收斂閾值 $\theta$。然後，初始化所有狀態的價值函數 $V(s)$ 為0。算法進入一個主循環，每次迭代開始時，將**$\Delta$ 重置為0**。在循環內部，對於每個狀態 $s$，會保存其當前價值 $v_{old}$，然後計算所有動作的 $Q_{values}$。基於這些Q值，更新 $V[s]$ 為最大Q值。同時，更新 $\Delta$ 以追蹤最大價值變化。完成所有狀態的更新後，檢查**$\Delta$ 是否小於 $\theta$。如果否，則繼續下一次迭代；如果是，則表示價值函數已收斂到 $V^(s)$。最後一步是從收斂的 $V^(s)$ 中提取最優策略 $\pi^*(s)$**。

蒙特卡洛策略生成：從經驗中學習

蒙特卡洛策略生成（Monte Carlo Policy Generation）是強化學習中一種重要的無模型方法，它透過與環境進行大量的幕（Episodes）互動，從實際經驗中估計價值函數和策略，而無需事先知道環境的動態模型。這種方法特別適用於那些環境模型難以獲取或過於複雜的問題。

蒙特卡洛方法的基礎

蒙特卡洛方法的核心思想是利用大數定律。透過重複採樣一個隨機過程，並計算其平均結果，我們可以近似該過程的期望值。在強化學習中，這意味著：

  1. 經驗採樣：智能體與環境互動，生成一系列的狀態、動作、獎勵序列，即一個完整的幕 $S_0, A_0, R_1, S_1, A_1, R_2, \dots, S_T$。
  2. 回報計算：對於每個狀態-動作對 $(s, a)$，計算其在該幕中之後獲得的折扣累積獎勵（回報 $G_t$）。
  3. 平均回報：將所有訪問過 $(s, a)$ 的回報進行平均，作為其動作價值函數 $Q(s, a)$ 的估計。

蒙特卡洛策略生成流程

蒙特卡洛策略生成通常透過蒙特卡洛控制（Monte Carlo Control）來實現，它結合了蒙特卡洛策略評估和策略改進，形成一個迭代過程：

  1. 初始化：
    • 初始化一個隨機策略 $\pi$。
    • 初始化所有狀態-動作對的價值 $Q(s, a)$ 為任意值。
    • 初始化每個狀態-動作對的訪問計數 $N(s, a)$ 為0。
  2. 生成幕：
    • 根據當前策略 $\pi$（通常是 $\epsilon$-貪婪策略，以確保探索），智能體與環境互動，直到一個幕結束（達到終止狀態）。
    • 記錄該幕中的所有狀態、動作和獎勵序列：$S_0, A_0, R_1, S_1, A_1, R_2, \dots, S_T$。
  3. 策略評估（蒙特卡洛評估）：
    • 對於該幕中的每個時間步 $t=0, \dots, T-1$：
      • 計算從該時間步開始的回報 $G_t = R_{t+1} + \gamma R_{t+2} + \dots + \gamma^{T-t-1} R_T$。
      • 如果 $(S_t, A_t)$ 是該幕中第一次被訪問（首次訪問蒙特卡洛）或每次訪問都更新（每次訪問蒙特卡洛）：
        • 增加 $N(S_t, A_t)$ 的計數。
        • 更新 $Q(S_t, A_t) \leftarrow Q(S_t, A_t) + \frac{1}{N(S_t, A_t)} (G_t - Q(S_t, A_t))$。這是一個增量式平均更新。
  4. 策略改進：
    • 基於更新後的 $Q(s, a)$ 值，改進策略 $\pi$。通常是透過貪婪策略改進，即在每個狀態 $s$ 下，選擇能夠最大化 $Q(s, a)$ 的動作。
    • 為了確保持續探索，通常會使用 $\epsilon$-貪婪策略。
  5. 重複：重複步驟2-4，直到策略和價值函數收斂。

蒙特卡洛方法的優勢與挑戰

優勢：

  • 無模型：無需環境模型，可以直接從經驗中學習。
  • 增量式學習：可以逐步更新價值函數，無需等待所有數據。
  • 處理非馬可夫環境：在某些情況下，即使環境不完全滿足馬可夫性質，蒙特卡洛方法也能在一定程度上工作。

挑戰：

  • 高方差：回報 $G_t$ 的計算依賴於整個幕的隨機序列，導致估計值方差較大，可能需要大量的幕才能收斂。
  • 不適用於連續任務：對於沒有明確終止狀態的連續任務，計算無限期的回報是困難的。
  • 探索問題：如果智能體從未訪問過某些狀態-動作對，其價值將無法被估計。這需要有效的探索策略。
  • 收斂速度：由於方差較大，蒙特卡洛方法通常比時序差分方法收斂慢。

儘管存在挑戰，蒙特卡洛策略生成因其無模型的特性和直觀的原理，在許多強化學習問題中仍是一個重要的工具，尤其是在可以輕鬆生成大量經驗的模擬環境中。

此圖示：蒙特卡洛策略生成流程

  graph TD
    A[初始化策略 $\pi$ 和 $Q(s,a)$] --> B{生成一個幕 (Episode)};
    B --> C[智能體與環境互動];
    C --> D[記錄 (s, a, r, s') 序列];
    D --> E[幕結束];
    E --> F{對於幕中每個 (s,a) 對};
    F --> G[計算該 (s,a) 對的回報 $G_t$];
    G --> H[更新 $Q(s,a)$ (平均回報)];
    H --> I[更新訪問計數 $N(s,a)$];
    I --> F;
    F --> J[策略改進 (例如 $\epsilon$-貪婪)];
    J --> K{是否收斂?};
    K -- 否 --> B;
    K -- 是 --> L[得到最優策略 $\pi^*$];

看圖說話：

此圖示描繪了蒙特卡洛策略生成的迭代過程。首先，初始化策略 $\pi$ 和動作價值函數 $Q(s,a)$。接著進入一個循環，生成一個幕，這涉及智能體與環境互動，並記錄狀態、動作、獎勵、下一狀態的序列，直到幕結束。然後，對於該幕中每個被訪問的狀態-動作對 $(s,a)$，計算從該點開始的回報 $G_t$，並更新 $Q(s,a)$，通常是透過對回報進行平均。同時，更新訪問計數 $N(s,a)$。完成所有 $(s,a)$ 對的更新後，進行策略改進，例如使用 $\epsilon$-貪婪策略。最後，檢查是否收斂。如果沒有收斂，則繼續生成新的幕；如果收斂，則得到最優策略 $\pi^*$。

價值迭代與動態規劃：模型驅動的最優解

價值迭代（Value Iteration）是動態規劃（Dynamic Programming）在強化學習中的一種核心算法，用於在模型已知（即狀態轉移概率 $P(s’|s,a)$ 和獎勵函數 $R(s,a,s’)$ 已知）的有限馬可夫決策過程（MDPs）中，找到最優策略和最優價值函數。它透過迭代地應用貝爾曼最優方程，直接計算出最優狀態價值函數 $V^*(s)$。

價值迭代的核心思想

價值迭代的基礎是最優貝爾曼方程： $$V^(s) = \max_{a \in \mathcal{A}} \sum_{s’ \in \mathcal{S}, r \in \mathcal{R}} P(s’, r | s, a) [r + \gamma V^(s’)]$$ 這個方程是一個非線性的遞歸關係，它表明一個狀態的最優價值，等於在該狀態下，選擇能帶來最大預期累積獎勵的動作所能獲得的價值。價值迭代算法透過將這個方程作為一個更新規則，從任意初始價值函數 $V_0(s)$ 開始，迭代地更新 $V_k(s)$，直到收斂到 $V^*(s)$。

價值迭代算法步驟

  1. 初始化：
    • 初始化所有狀態的價值函數 $V(s)$ 為任意值（通常為0）。
    • 設定一個小的收斂閾值 $\theta > 0$。
  2. 迭代更新：重複以下步驟，直到價值函數收斂： a. 初始化 $\Delta = 0$（用於監測最大價值變化）。 b. 對於每個狀態 $s \in \mathcal{S}$： i. 保存當前狀態的舊價值：$v = V(s)$。 ii. 計算所有可能動作的Q值： $$Q(s, a) = \sum_{s’ \in \mathcal{S}, r \in \mathcal{R}} P(s’, r | s, a) [r + \gamma V(s’)]$$ iii. 更新狀態價值函數為所有動作Q值的最大值： $$V(s) = \max_{a \in \mathcal{A}} Q(s, a)$$ iv. 更新最大價值變化：$\Delta = \max(\Delta, |v - V(s)|)$。 c. 如果 $\Delta < \theta$，則算法收斂，停止迭代。
  3. 提取最優策略：一旦 $V(s)$ 收斂到 $V^(s)$，最優策略 $\pi^(s)$ 可以透過對 $V^(s)$ 進行一次貪婪操作來導出： $$\pi^(s) = \arg\max_{a \in \mathcal{A}} \sum_{s’ \in \mathcal{S}, r \in \mathcal{R}} P(s’, r | s, a) [r + \gamma V^*(s’)]$$

價值迭代的特點與優勢

  • 收斂保證：在有限MDPs中，價值迭代保證會收斂到唯一的最優價值函數 $V^*(s)$。
  • 效率：通常比策略迭代收斂更快，因為它在每次迭代中都直接考慮最優動作，而不是先完全評估一個策略。
  • 模型驅動：需要完整的環境模型（狀態轉移概率和獎勵函數）。

挑戰與限制

  • 模型需求：最大的限制是需要已知環境模型。在許多實際問題中，模型難以獲取或過於複雜。
  • 狀態空間爆炸：對於狀態空間非常大的問題，遍歷所有狀態和動作來更新價值函數的計算成本會非常高。
  • 連續狀態/動作空間：價值迭代通常不適用於具有連續狀態或動作空間的問題，因為無法遍歷所有可能的狀態-動作對。

儘管存在這些限制，價值迭代作為動態規劃的經典算法，在模型已知且狀態空間相對較小的問題中，仍然是尋找最優策略的強大工具。它為理解強化學習的核心原理提供了堅實的基礎。

此圖示：價值迭代流程

  graph TD
    A[初始化 $V(s)$ 為0, 設定 $\theta$] --> B{循環: 監測 $\Delta$};
    B --> C[對於每個狀態 $s$];
    C --> D[保存 $v_{old} = V(s)$];
    D --> E[計算所有動作 $a$ 的 $Q(s,a)$];
    E --> F[更新 $V(s) = \max_a Q(s,a)$];
    F --> G[更新 $\Delta = \max(\Delta, |v_{old} - V(s)|)$];
    G --> C;
    C --> H{如果 $\Delta < \theta$?};
    H -- 否 --> B;
    H -- 是 --> I[收斂到 $V^*(s)$];
    I --> J[提取最優策略 $\pi^*$];

看圖說話：

此圖示展示了價值迭代算法的詳細流程。首先，初始化所有狀態的價值函數 $V(s)$ 為0，並設定一個收斂閾值 $\theta$。接著進入一個循環，該循環的目標是監測最大價值變化 $\Delta$。在每次循環中，算法會對於每個狀態 $s$ 進行處理：首先保存當前狀態的舊價值 $v_{old}$，然後計算所有可能動作 $a$ 的 $Q(s,a)$ 值，這個計算依賴於當前的 $V(s’)$ 估計。接著，更新 $V(s)$ 為所有動作 $Q(s,a)$ 的最大值。隨後，更新 $\Delta$，記錄本次迭代中所有狀態的最大價值變化。如果**$\Delta$ 小於 $\theta$，則表示價值函數已經收斂到 $V^(s)$**，循環結束。最後，從收斂的 $V^(s)$ 中提取最優策略 $\pi^*$。

實作價值迭代：將理論轉化為程式碼

實作價值迭代（Implementing Value Iteration）是將抽象的動態規劃理論轉化為具體可執行程式碼的過程。它涉及對狀態空間、動作空間、轉移概率和獎勵函數的精確定義，以及對迭代更新邏輯的程式化實現。一個成功的實作不僅能驗證理論，還能為解決實際問題提供強大的工具。

實作考量與步驟

  1. 環境建模：

    • 狀態表示：如何將環境的狀態編碼為程式碼中的數據結構（例如，整數、元組、自定義類）。對於網格世界，狀態可以是 $(x, y)$ 座標。對於庫存控制，狀態可以是當前庫存量。
    • 動作表示：如何將動作編碼為程式碼中的數據結構。
    • 轉移概率 $P(s’|s,a)$：這通常是一個字典、矩陣或函數，它接收當前狀態 $s$ 和動作 $a$，返回一個下一狀態 $s’$ 及其概率的分佈。
    • 獎勵函數 $R(s,a,s’)$：這也是一個字典或函數，接收 $s, a, s’$，返回即時獎勵。
    • 折扣因子 $\gamma$：一個浮點數。

  2. 初始化價值函數：

    • 創建一個字典或數組來存儲每個狀態的價值 $V(s)$。
    • 將所有 $V(s)$ 初始化為0。

  3. 迭代循環：

    • 使用 while True 循環來進行迭代，直到收斂。
    • 在每次迭代開始時，設定一個變量 max_delta = 0 來追蹤本次迭代中價值函數的最大變化量。
    • 對於環境中的每個狀態 $s$：
      • 保存當前 $V(s)$ 的舊值：old_v = V[s]。
      • 計算所有可能動作 $a$ 的Q值。這通常涉及一個內部循環：
        • 對於每個動作 $a \in \mathcal{A}(s)$：
          • 計算 $Q(s, a)$。這需要遍歷所有可能的下一狀態 $s’$ 及其概率 $P(s’|s,a)$，並使用當前的 $V(s’)$ 估計。
          • q_value = sum(P(s'|s,a) * (R(s,a,s') + gamma * V[s']) for s' in next_states)
        • 找到所有 $Q(s, a)$ 中的最大值：max_q = max(q_values_for_s)。
      • 更新 $V(s)$：V[s] = max_q。
      • 更新 max_delta = max(max_delta, abs(old_v - V[s]))。
    • 在完成所有狀態的更新後，檢查 max_delta。如果 max_delta < theta（收斂閾值），則 break 循環。

  4. 提取最優策略：

    • 在價值函數 $V(s)$ 收斂後，創建一個字典或數組來存儲每個狀態的最優動作 $\pi^*(s)$。
    • 對於每個狀態 $s$：
      • 再次計算所有可能動作 $a$ 的Q值，但這次使用收斂後的 $V^*(s’)$。
      • 選擇能夠最大化Q值的動作作為 $\pi^*(s)$。
      • optimal_policy[s] = argmax_a(Q(s,a))。

失敗案例分析：浮點數精度與收斂問題

玄貓在實作一個小型迷宮遊戲的價值迭代時，發現算法有時無法收斂，或者收斂速度非常慢。經過調試，發現問題出在浮點數精度和收斂閾值 $\theta$ 的選擇上。

  • 浮點數精度：在計算 $Q(s,a)$ 和更新 $V(s)$ 時，由於浮點數運算可能存在微小的誤差，導致 $V(s)$ 的變化永遠無法完全為零，即使實際上已經收斂。
  • 收斂閾值 $\theta$ 過小：如果將 $\theta$ 設定得過小（例如 $10^{-10}$），算法可能需要極長的迭代次數才能達到這個極高的精度要求，甚至因為浮點數誤差而永遠無法達到。

學習心得：

  1. 選擇合適的收斂閾值：$\theta$ 不應過小，通常 $10^{-4}$ 到 $10^{-6}$ 是一個合理的範圍，它平衡了精度和收斂速度。
  2. 迭代次數限制：為了防止無限循環，即使沒有達到收斂閾值，也應設定一個最大迭代次數。
  3. 數值穩定性：在涉及大量浮點數運算的算法中，需要注意數值穩定性。在某些情況下，可能需要使用更高精度的數據類型或調整計算順序。
  4. 測試案例：使用簡單且已知最優解的測試案例來驗證實作的正確性，有助於快速定位問題。

實作價值迭代不僅是程式設計的練習，更是對強化學習理論深刻理解的體現。透過仔細的環境建模和精確的程式邏輯，我們可以將這個強大的算法應用於解決各種決策問題。

此圖示：價值迭代實作邏輯

  graph TD
    A[定義狀態、動作空間] --> B[定義轉移概率 P(s'|s,a)];
    B --> C[定義獎勵函數 R(s,a,s')];
    C --> D[設定折扣因子 $\gamma$ 和閾值 $\theta$];
    D --> E[初始化 $V(s)$ 為0];
    E --> F{循環: $\Delta = 0$};
    F --> G[對於每個狀態 $s$];
    G --> H[保存 $v_{old} = V[s]$];
    H --> I[計算 $Q_{values}$ for $s$];
    I --> J[更新 $V[s] = \max(Q_{values})$];
    J --> K[更新 $\Delta = \max(\Delta, |v_{old} - V[s]|)$];
    K --> G;
    G --> L{如果 $\Delta < \theta$?};
    L -- 否 --> F;
    L -- 是 --> M[收斂 $V^*(s)$];
    M --> N[從 $V^*(s)$ 提取 $\pi^*(s)$];

看圖說話：

此圖示詳細展示了價值迭代的實作邏輯。首先，需要定義狀態、動作空間以及轉移概率 $P(s’|s,a)$ 和獎勵函數 $R(s,a,s’)$，這些是環境模型的核心。接著，設定折扣因子 $\gamma$ 和收斂閾值 $\theta$。然後，初始化所有狀態的價值函數 $V(s)$ 為0。算法進入一個主循環，每次迭代開始時，將**$\Delta$ 重置為0**。在循環內部，對於每個狀態 $s$，會保存其當前價值 $v_{old}$，然後計算所有動作的 $Q_{values}$。基於這些Q值，更新 $V[s]$ 為最大Q值。同時，更新 $\Delta$ 以追蹤最大價值變化。完成所有狀態的更新後，檢查**$\Delta$ 是否小於 $\theta$。如果否，則繼續下一次迭代；如果是，則表示價值函數已收斂到 $V^(s)$。最後一步是從收斂的 $V^(s)$ 中提取最優策略 $\pi^*(s)$**。

好的，這是一篇針對您提供的三篇關於強化學習演算法文章的「玄貓風格」結論。

結論

發展視角：創新與突破視角

縱觀決策智能的兩種核心路徑，蒙特卡洛策略生成與價值迭代分別代表了從經驗歸納與從模型演繹的典範。前者如同在未知市場中反覆試錯的實戰派，透過大量真實互動的平均回報，逐步逼近有效策略；後者則像是擁有完整市場地圖的規劃師，在已知的規則下，以動態規劃的嚴謹邏輯直接推導出最優解。然而，兩者皆非完美。蒙特卡洛策略受制於經驗採樣的巨大方差，而價值迭代的效能則完全依賴於一個完美的、通常難以獲取的環境模型。實作層面的挑戰，如浮點數精度問題，更揭示了理論與現實間的鴻溝。

未來的突破點，顯然在於兩者的融合——發展出既能利用不完美模型進行高效規劃，又能透過實時經驗快速修正的混合式智能。這種整合不僅是技術上的演進，更是思維框架的升級。

玄貓認為，對高階決策者而言，這不僅是演算法的選擇，更是思維模式的修煉。關鍵在於精準判斷問題情境，辨識何時應採用模型驅動的精準規劃，何時又該擁抱經驗導向的探索學習，方能在複雜變動的環境中，實現持續性的最優決策。

玄貓

玄貓

技術愛好者，專注於分享程式開發、雲端技術與 AI 應用的心得體會。