CS234 Winter 2026 第二講假設世界模型已知，回答怎麼算出最好的 policy。先把 MDP 加上 policy 變回 MRP，用 Bellman backup 迭代評估 policy；再用 policy iteration 交替評估與改進，並證明每一輪都不會變差，最多 |A|^|S| 輪就停。另一條路是 value iteration：直接重複套用 Bellman 最佳化運算子，因為它在 γ < 1 時是 contraction，所以一定收斂。最後補上 finite horizon：這時最好的 policy 通常會隨剩餘步數改變。
HW6 Problem 2（15 分）給你一張 4×5 的 Gridworld：動作會打滑、獎勵在離開格子時才拿到。你要在 notebook 裡寫 policy evaluation、policy iteration 與 value iteration 各一步，再觀察折扣因子 γ 怎麼改變策略，最後反問「這樣建模機器人任務合理嗎」。環境規則全部已知，所以這是規劃，還不是學習。
第 21 講把隨機序列決策寫成已知 dynamics 的 MDP，以 Bellman backup 定義 value 與 Q-value，再用 value iteration 或 policy iteration 求最佳 policy。
動態規劃先精確定義子問題，再用 optimal substructure 寫 recurrence，最後依相依順序填表；Bellman–Ford 以 edge 數分層，Floyd–Warshall 則以允許的中繼頂點分層。
Lecture 13 把動態規劃整理成五步：選 state、寫 transition、填表、回復解、再優化實作。LCS 是 O(mn)，兩種背包都是 O(nW) 的擬多項式時間，樹上最大權重獨立集則能在 O(|V|) 完成。