第一次接觸強(qiáng)化學(xué)習(xí)的人往往會被“智能體與環(huán)境交互”“獎勵信號”“探索與利用”這些概念吸引覺得像是在訓(xùn)練一個有靈性的活物。但真正開始啃算法時會發(fā)現(xiàn)第一個能完整推導(dǎo)、親手實現(xiàn)、可視化收斂過程的反而是“動態(tài)規(guī)劃”這個聽著有點古老的詞。這一講的核心其實就一句話在環(huán)境模型完全已知的前提下怎么系統(tǒng)地把每個狀態(tài)的價值估準(zhǔn)再從價值里反推出最優(yōu)策略。它是強(qiáng)化學(xué)習(xí)課程里最接近傳統(tǒng)算法的一講也是后面所有無模型方法的理論地基。這篇內(nèi)容適合三類人看正在跟著課程自學(xué)、對貝爾曼方程還有點懵的同學(xué)已經(jīng)能跑一些深度學(xué)習(xí)框架、但回到底層迭代邏輯反而含糊的工程師以及準(zhǔn)備算法崗面試、想快速把“策略迭代和價值迭代的聯(lián)系與區(qū)別”講清楚的人。我盡量不堆公式把每一步背后的“為什么”也一起說了。1. 先從“已知模型”說起動態(tài)規(guī)劃站在什么位置1.1 強(qiáng)化學(xué)習(xí)四大類方法的分水嶺強(qiáng)化學(xué)習(xí)方法通常被粗分成四類動態(tài)規(guī)劃、蒙特卡洛方法、時序差分學(xué)習(xí)、策略梯度方法。這四者不是互相替代的關(guān)系而是沿一條“對模型依賴程度”的光譜依次排列。動態(tài)規(guī)劃DP假設(shè)環(huán)境轉(zhuǎn)移概率和獎勵函數(shù)完全已知通過迭代計算精確的價值函數(shù)。蒙特卡洛方法MC不需要模型讓智能體完整跑完一條軌跡用實際回報的平均值估計價值。時序差分方法TD也不需要模型但只需走一步就能更新估計把下一狀態(tài)的估計值當(dāng)作“部分真相”來用。策略梯度方法PG直接在策略參數(shù)空間里搜索最優(yōu)方向繞開值函數(shù)估計這個中間層。這個分水嶺就是“環(huán)境動力學(xué)是否已知”。有模型時你面對的是一個可解析計算的馬爾可夫決策過程無模型時你只能靠和環(huán)境交互獲得樣本。動態(tài)規(guī)劃之所以被擺在第一講是因為它把“價值函數(shù)的定義”“貝爾曼方程”“迭代收斂”這些底層骨架先立起來后面所有方法幾乎都在用不同手段逼近同一個方程。1.2 為什么動態(tài)規(guī)劃值得認(rèn)真學(xué)一遍很多人覺得現(xiàn)在工業(yè)界誰還手寫動態(tài)規(guī)劃環(huán)境模型基本都是未知的這個方向已經(jīng)過時了。這個觀點我不同意。原因有三點第一貝爾曼方程是幾乎所有強(qiáng)化學(xué)習(xí)算法的數(shù)學(xué)底座。無論是 DQN 的損失函數(shù)還是 TD(0) 的更新公式本質(zhì)上都在嘗試滿足同一條遞推關(guān)系。把 DP 弄懂后面看任何算法論文都不會覺得公式是在變魔術(shù)。第二動態(tài)規(guī)劃的迭代過程是最直觀的“收斂演示”。你寫一遍策略評估循環(huán)觀察價值矩陣從亂跳、到緩慢變化、再到穩(wěn)定不再動這一步對“強(qiáng)化學(xué)習(xí)到底在優(yōu)化什么”的理解比看一百張網(wǎng)絡(luò)結(jié)構(gòu)圖都有用。第三很多實際問題本身就是動態(tài)規(guī)劃問題。比如機(jī)器人路徑規(guī)劃里的 Dijkstra 算法本質(zhì)上是價值迭代的特殊形式再比如某些運籌學(xué)里的庫存管理問題轉(zhuǎn)移概率可以建模直接用策略迭代就能求出最優(yōu)策略。這門課并不是教你死記一個過時算法而是教你一套“自舉式更新”的思維范式。動態(tài)規(guī)劃在強(qiáng)化學(xué)習(xí)里有兩大經(jīng)典內(nèi)容策略迭代和價值迭代。這兩者共享同一個基礎(chǔ)組件——策略評估也就是把一個固定策略下的價值函數(shù)算到收斂。2.1 貝爾曼方程先搞清楚“價值”到底是什么定義一個策略 π 下的狀態(tài)價值函數(shù) Vπ(s)它表示從狀態(tài) s 出發(fā)按照策略 π 行動之后獲得的期望折扣回報。折扣因子 γ 表示未來的回報相對現(xiàn)在要打幾折γ ∈ [0, 1)。于是有Vπ(s) E[ Rt1 γ·Vπ(St1) | St s ]用人話說就是當(dāng)前狀態(tài)的得分等于“邁出這一步立刻拿到的獎勵”加上“下個狀態(tài)在打折扣后的價值”。很多初學(xué)者卡在這一步是因為不理解為什么 Vπ(s) 同時出現(xiàn)在等式兩邊。這里其實是把“一個無窮長序列的求和”變成了“一條關(guān)于 Vπ 自身的方程”。由于 Vπ(s) 是未知的且等式右側(cè) Vπ(St1) 也是未知的所以不能直接解只能通過迭代逼近。生活類比你評估一個區(qū)域的房產(chǎn)價值心里其實是在反復(fù)自我對齊——這間房的價值取決于周邊房的價值而周邊房的價值又反過來參考它。當(dāng)整個小區(qū)所有房子的評估都自洽時這套評估才算穩(wěn)定了。狀態(tài)價值能算出來之后進(jìn)一步定義動作價值 Qπ(s, a)表示在狀態(tài) s 先執(zhí)行動作 a之后按策略 π 行動的期望回報。它的更新公式是Qπ(s, a) Σ_s p(s | s, a) · [ r γ·Vπ(s) ]這個字段后面會頻繁用到策略改進(jìn)步驟里需要它來比較“哪個動作更好”。2.2 策略評估一次迭代到底在算什么策略評估的目標(biāo)是給定策略 π求出 Vπ。做法是迭代更新Vk1(s) Σ_a π(a | s) · Σ_s p(s | s, a) · [ r γ·Vk(s) ]這一步對策略 π 下可能選到的每個動作求期望再對可能到達(dá)的每個后繼狀態(tài)求期望。Vk 第 k 輪估計傳到 Vk1 第 k1 輪形成一次掃描。實際操作時人們很少真的讓 Vk 完全收斂而是設(shè)一個閾值 ε當(dāng) max_s |Vk1(s) - Vk(s)| ε 時停止。課程里常用 ε 1e-3 或 1e-4想拿到更精確的比較就設(shè)小一點。2.3 策略改進(jìn)既然價值清楚了就朝著更好的方向走有了一組相對準(zhǔn)確的 Vπ下一步是為每個狀態(tài)選擇一個“看起來更好”的動作。這里用貪心策略對每個狀態(tài) s選使 Qπ(s, a) 最大的動作π(s) argmax_a Σ_s p(s | s, a) · [ r γ·Vπ(s) ]之所以敢直接貪心背后的依據(jù)是策略改進(jìn)定理如果策略 π 在每一步都選擇了一個不差于 π 的動作那么 Vπ(s) ≥ Vπ(s) 對每個狀態(tài)成立。也就是說局部貪心不會把整體帶壞這給了迭代循環(huán)一個安全的下界。課程里最常舉的例子是格柵世界智能體在 4x4 網(wǎng)格里移動每步獎勵為 -1到達(dá)左上角或右下角終止。讀者可以手推一遍從一個均勻隨機(jī)策略開始評估兩步、改進(jìn)一次、再評估兩步就能看到價值逐漸從周圍往終點蔓延。3. 策略迭代與價值迭代兩種收斂路線的選擇3.1 策略迭代先評估到準(zhǔn)再改進(jìn)策略策略迭代的循環(huán)形式很簡單隨機(jī)初始化策略 π0。策略評估用迭代法算出當(dāng)前策略的 Vπ。策略改進(jìn)基于 Vπ 對每個狀態(tài)貪心選動作得到 π。若 π ≠ π則把 π 更新為 π回到步驟2否則輸出 π。這個流程的優(yōu)點很明顯每次改進(jìn)之間策略是質(zhì)量較高的迭代次數(shù)通常很少。對于規(guī)?？山獾沫h(huán)境比如狀態(tài)不超過幾萬個策略迭代往往比價值迭代更快收斂。缺點是每輪評估本身需要多次掃描單輪成本高。3.2 價值迭代省去顯式策略的簡化版價值迭代把策略評估壓縮成一步直接將貝爾曼最優(yōu)方程作為更新目標(biāo)Vk1(s) max_a Σ_s p(s | s, a) · [ r γ·Vk(s) ]它不從某個初始策略開始而是直接收斂到最優(yōu)價值函數(shù)最后再從 V* 反推最優(yōu)策略?？梢赃@樣理解價值迭代把“評估后改進(jìn)”的兩個階段合并成了“每次掃描時直接盯著最優(yōu)值更新”相當(dāng)于在每一步都對策略做了隱式改進(jìn)。它的單輪掃描開銷低代碼也精簡但需要更多輪次達(dá)到穩(wěn)定尤其在獎勵稀疏、折扣因子接近 1 的時候。3.3 怎么選一張對比表說清楚對比維度策略迭代價值迭代每輪是否包含顯式策略有策略評估循環(huán)以策略穩(wěn)定為收斂判據(jù)無顯式策略循環(huán)以價值變化閾值為收斂判據(jù)單輪計算成本較高需評估多次較低一次貝爾曼最優(yōu)更新收斂所需輪數(shù)較少較多實現(xiàn)難度稍復(fù)雜簡單直接適用狀態(tài)規(guī)模中小規(guī)模、模型可用中大規(guī)模、需要簡單實現(xiàn)常見誤用場景環(huán)境模型頻繁變化重算代價高γ 接近 1、獎勵非常稀疏時收斂極慢個人體會如果環(huán)境規(guī)模不大、離線求解一次就好策略迭代往往更“省總時間”如果要寫一個在線模塊、每步都要快速更新價值表價值迭代更順手。不要迷信哪一種兩者本質(zhì)是一個問題的兩面。4. 配套實操從零寫一個格柵世界的動態(tài)規(guī)劃4.1 實驗環(huán)境設(shè)定與狀態(tài)動作定義這一講配的模擬項目通常叫“格柵世界”我用的是一個經(jīng)典 4x4 版本。環(huán)境參數(shù)如下狀態(tài)16 個網(wǎng)格編號 0 到 15其中 0 和 15 是終止?fàn)顟B(tài)。動作4 個方向上、下、左、右試圖越界時停留在原地。獎勵每走一步得到 -1直到進(jìn)入終止?fàn)顟B(tài)。折扣因子γ 1課程演示常用但理論上終止?fàn)顟B(tài)價值固定為 0。這個環(huán)境小到可以打印價值矩陣看著數(shù)值慢慢變化非常適合理解更新公式。4.2 核心代碼價值迭代實現(xiàn)課程配套代碼比較精簡我通常會讓學(xué)生把價值迭代單獨寫一遍不要只跑現(xiàn)成庫。下面是一份能直接運行的參考版本雙數(shù)組和 in-place 的順序問題我會在后面章節(jié)詳細(xì)解釋。import numpy as np # 環(huán)境定義 n_rows, n_cols 4, 4 n_states n_rows * n_cols n_actions 4 # up, down, left, right terminals [0, 15] def is_terminal(s): return s in terminals def step(s, a): 返回 (next_state, reward)若越界則原地停留但獲得 -1 獎勵。 r, c s // n_cols, s % n_cols if is_terminal(s): return s, 0 if a 0: # up r max(r - 1, 0) elif a 1: # down r min(r 1, n_rows - 1) elif a 2: # left c max(c - 1, 0) elif a 3: # right c min(c 1, n_cols - 1) return r * n_cols c, -1 def greedy_policy_from_values(V, gamma1.0): 根據(jù)價值表 V 貪心生成策略。 policy np.zeros(n_states, dtypeint) for s in range(n_states): if is_terminal(s): continue q_vals [] for a in range(n_actions): s_next, r step(s, a) q_vals.append(r gamma * V[s_next]) policy[s] int(np.argmax(q_vals)) return policy def value_iteration(gamma1.0, theta1e-4, max_iter1000): V np.zeros(n_states) for it in range(max_iter): delta 0.0 for s in range(n_states): if is_terminal(s): continue v V[s] q_vals [] for a in range(n_actions): s_next, r step(s, a) q_vals.append(r gamma * V[s_next]) V[s] max(q_vals) delta max(delta, abs(v - V[s])) if delta theta: print(fConverged at iteration {it 1}) break policy greedy_policy_from_values(V, gamma) return V, policy V_star, pi_star value_iteration() print(Optimal value matrix:) print(V_star.reshape((n_rows, n_cols))) print(Optimal policy matrix (0:up, 1:down, 2:left, 3:right):) print(pi_star.reshape((n_rows, n_cols)).astype(int))這段代碼里有兩個細(xì)節(jié)值得注意終止?fàn)顟B(tài)直接跳過更新價值固定為 0。若忘了加這一步終止?fàn)顟B(tài)會反復(fù)被周圍狀態(tài)拉高導(dǎo)致價值矩陣自激發(fā)散。更新時用的 V[s_next] 來自當(dāng)前輪的舊表雙數(shù)組等下一輪才把新值統(tǒng)一覆蓋。實現(xiàn)時如果直接原地改 V 數(shù)組相當(dāng)于用部分新值參與計算收斂行為會不同。4.3 收斂判據(jù)與可視化檢查運行時程序會打印類似Converged at iteration 6 Optimal value matrix: [[ 0. -1. -2. -3.] [-1. -2. -3. -2.] [-2. -3. -2. -1.] [-3. -2. -1. 0.]]這個結(jié)果符合預(yù)期從任意格子出發(fā)最少要走 6 步左右才能到達(dá)終點的方向上價值恰好是負(fù)的步數(shù)。策略矩陣也基本指向能最快到達(dá)終點的方向。實際操作中我建議再加一個可視化把每一輪迭代的最大變化量 delta 打印出來觀察它是否單調(diào)遞減。如果出現(xiàn)反復(fù)很大的波動先別急著調(diào)參數(shù)檢查一下終止?fàn)顟B(tài)跳步和折扣因子是否寫對這類問題往往是環(huán)境實現(xiàn)的小錯誤導(dǎo)致的而不是算法本身的問題。5. 常見問題與排查技巧實錄5.1 收斂閾值與最大迭代次數(shù)的平衡很多人把閾值調(diào)到特別小比如 1e-8結(jié)果在 4x4 格柵世界這種規(guī)模上還能跑一旦換成 20x20 或更復(fù)雜環(huán)境程序很久不出結(jié)果。經(jīng)驗做法是先設(shè) θ1e-3 跑一遍看趨勢再根據(jù)業(yè)務(wù)需求收緊。同時一定要設(shè)置最大迭代次數(shù)防止因為環(huán)境設(shè)計有缺陷或 γ1 時長期不滿足收斂條件而卡死。還有一種情況是 γ 非常接近 1比如 0.99加上獎勵很稀疏、狀態(tài)鏈很長這時候價值迭代可能要幾萬輪才能收斂。解決辦法是在迭代輪數(shù)上設(shè)上限同時中途打印 delta 下降率如果幾百輪下來 delta 幾乎不動但價值還在緩慢變化要考慮是不是折扣因子過大導(dǎo)致的“長尾傳播”正?，F(xiàn)象。5.2 雙數(shù)組更新與原地更新的差異課程第 4 講最容易出現(xiàn)理解的偏差就是“為什么代碼里有人把 V 復(fù)制了一份有人直接原地改”。雙數(shù)組同步方式第 k1 輪的所有更新統(tǒng)一參考第 k 輪的 V 數(shù)組不動原始數(shù)組更新完成后一起覆蓋。價值迭代課內(nèi)的標(biāo)準(zhǔn)寫法常是這個。in-place異步方式第 k1 輪計算一個狀態(tài)時可能已經(jīng)用到了本輪的新值。這種方式收斂通常明顯更快因為信息傳播更高效。格柵世界樣本里雙數(shù)組能讓你清楚看到每次迭代的“擴(kuò)散邊界”適合學(xué)習(xí)。實際工程項目我推薦 in-place迭代輪數(shù)可以省 30% 到 50%。唯一要注意的是迭代順序會輕微影響中間結(jié)果但收斂終點相同。5.3 模型已知這個假設(shè)在實踐里意味著什么“已知模型”聽起來很簡單但工程里做一個精確的轉(zhuǎn)移概率映射表并不便宜。比如應(yīng)用在工業(yè)機(jī)器人抓取場景狀態(tài)是關(guān)節(jié)角度和工件位置動作是連續(xù)力矩想寫清楚 p(s | s, a) 幾乎是無法完成的任務(wù)。正因如此后面幾講才引入了蒙特卡洛和時序差分這類無模型方法。它們的思想就是既然沒法手寫環(huán)境模型那就讓智能體通過與真實環(huán)境交互來“收集代替轉(zhuǎn)移概率的樣本”。理解了這層遞進(jìn)關(guān)系整門課程的主線就很清楚了——動態(tài)規(guī)劃是那個“假設(shè)什么都給你算好的演算稿”后面的方法則一步步把假設(shè)松開。嚴(yán)格意義上動態(tài)規(guī)劃屬于“有模型”強(qiáng)化學(xué)習(xí)課程里通常把它看作理論起點。如果你將來做規(guī)劃控制方向它依然能直接用到如果做游戲 AI 或推薦系統(tǒng)更多價值在于幫助你理解后續(xù)算法的推導(dǎo)而不是直接調(diào)用動態(tài)規(guī)劃。5.4 動態(tài)規(guī)劃的后續(xù)影子模型預(yù)測控制與深層強(qiáng)化學(xué)習(xí)動態(tài)規(guī)劃的價值不止于這門課本身。在機(jī)器人控制里廣泛使用的模型預(yù)測控制會在一個很短時間窗里反復(fù)做類似的規(guī)劃求解用到的正是動態(tài)規(guī)劃的分層決策思想。在深度強(qiáng)化學(xué)習(xí)里基于模型的強(qiáng)化學(xué)習(xí)也正逐漸回歸因為人們發(fā)現(xiàn)純粹無模型方法在樣本效率上始終不夠于是又把環(huán)境預(yù)估模型和規(guī)劃式求解重新?lián)炱饋怼Ａ硗獠呗缘摹霸u估——改進(jìn)”循環(huán)在深度強(qiáng)化學(xué)習(xí)中演化成了 Actor-Critic 框架Critic 負(fù)責(zé)價值評估Actor 負(fù)責(zé)策略提升兩者交替更新本質(zhì)上還是動態(tài)規(guī)劃那套循環(huán)結(jié)構(gòu)。只是把“查表更新”換成了“梯度下降”把“真實模型”換成了“經(jīng)驗回放”。如果有余力建議把 DDPG 或 PPO 的算法結(jié)構(gòu)圖攤開對照動態(tài)規(guī)劃的循環(huán)來讀很多模塊設(shè)計會突然變清晰。個人體會是動態(tài)規(guī)劃就像下棋時的把整盤棋擺在面前推演能算得很準(zhǔn)但現(xiàn)實更多時候只能走一步看一步。把這一講的迭代思想徹底消化后后續(xù)所有內(nèi)容都是在問同一個問題“如果環(huán)境不能全知我該靠什么信息來代替那張狀態(tài)遷移表”帶著這個問題去學(xué)后面的課程推進(jìn)會順暢很多。