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