1. 动态规划在强化学习里的特殊地位逃不掉的一课我见过不少刚接触强化学习的人翻开教材看到动态规划这一章就直接跳过去。原因也很简单这一章没有神经网络、没有试错、没有智能体与环境交互的画面感反而满屏都是全状态扫描、贝尔曼方程、线性方程组看起来跟智能两个字的距离比深度学习还远。但说实话这个判断成本很高。动态规划这个名称多少有点误导它既不是字面意义上的动态也不是单一的规划算法而是一类用递推关系拆解问题、用子问题的最优解组装全局最优解的方法。你在经典算法里写过的01背包、最短路径、最小硬币问题本质都在做同一件事。到了强化学习里被递推的对象换成了价值函数递推关系由马尔可夫决策过程的贝尔曼方程给出。这里有个容易被忽略的事实贝尔曼方程是整个强化学习理论的地基而动态规划是唯一一种不依赖采样、直接把贝尔曼方程当作方程组来求解的范式。说得再直白一点Q-learning、深度Q网络、离线强化学习各种算法收敛之后逼近的仍然是一张Q表或价值函数动态规划则能在你不与环境交互的情况下用完整的模型把这张表精确算出来。这个精确是采样型算法永远给不了的。所以这篇内容不设门槛只要你用过Python且大致知道状态、动作、奖励、折扣这几个词是什么意思就能跟下来。你会看到策略迭代和价值迭代是怎么从零开始把最优策略算出来的也会看到一个完整的代码例子和几处只有自己跑一遍才会发现的问题。这些经验基本不会出现在教科书里。2. 先把符号打通回报、价值函数与贝尔曼方程2.1 回报不是一段路程总和而是不断衰减的未来强化学习里最核心的对象不是奖励本身而是回报。t时刻的回报G_t定义为未来所有折扣奖励之和G_t R_t γ R_{t1} γ² R_{t2} ...γ是折扣因子取值0到1。这个公式的含义值得仔细琢磨一下同样是10分奖励马上拿走比十分钟后拿走更值钱。为什么要有折扣三个理由一是数学上保证无穷级数收敛尤其面对无限时域任务二是模仿现实中的时间成本现在的钱比未来的钱更实际三是引入可调节的远视程度γ越接近1智能体越愿意为了远期收益牺牲眼前利益。在强化学习里策略π描述的是在状态s下做什么动作的规则。给定一个策略从状态s出发后续能获得的期望回报就是状态价值V_π(s)。如果把状态动作绑定在一起从状态s执行动作a开始获得的期望回报就是动作价值Q_π(s, a)。2.2 贝尔曼方程的核心思想今天的价值由明天的价值决定V和Q最漂亮的性质是它们满足递推关系。状态价值可以拆成两部分V_π(s) Σ_a π(a|s) Σ_{s} P(s|s, a)[r γ V_π(s)]用大白话翻译就是当前状态的价值 所有可能动作的加权平均(按策略概率) ×动作后立即获得的奖励 下一个状态价值的折扣值。这看起来像一个循环定义——用V_π(s)定义V_π(s)而s又可能回到s本身。但这正是递推的精髓它把计算无限时间尺度上的总回报这个无从下手的求和转化为一个每个状态一个方程的线性方程组。这里能解释为什么很多学强化学习的人对DP感到陌生贝尔曼方程要求的输入是P(s|s, a)——状态转移概率。这意味着你必须先知道世界的动力学模型才能写出这个方程。而大多数入门教程一上来就讲Q-learning恰恰不需要这个模型所以大部分人第一次见到贝尔曼方程时并不理解它为什么重要。V和Q之间还有一层换算关系Q(s, a) Σ_{s} P(s|s, a)[r γ V(s)]而做完动作a之后如果策略是确定性选择最优动作V(s)就该等于所有Q(s, a)里最大的那个。这组关系是动态规划所有后续推演的原点。2.3 把最优写进方程贝尔曼最优性方程如果存在一个最优策略π*它对应的价值V*会满足贝尔曼最优性方程V*(s) max_a Σ_{s} P(s|s, a)[r γ V*(s)]注意右边从期望变成了最大。这意味着智能体不是把所有动作按策略概率加权而是每次都选择让自己后续价值最大的那个动作。这张方程看似只比期望方程多了一个max但性质完全不同期望方程对应一个具体策略求解出来是评估最优性方程直接求的是控制解出来就是最优价值函数而最优策略就是那个在每个状态下让V*(s)最大化的动作。这个区分是动态规划中最容易被搞混的点策略评估在算V_π策略改进在求π*两者合起来才是控制问题的完整解。一句话记住它评估解决这个策略有多好控制解决怎么找到最好的策略。3. 策略迭代评估与改进组成的双轮传动3.1 策略评估把方程组当作迭代来解假设我们手里有一个策略π想算出它的价值函数V_π。贝尔曼期望方程对每个状态都成立理论上直接解一个|S|元的线性方程组就行。状态空间很小时这个思路可行比如5×5的网格世界有25个状态解25元方程组并不难受。但一旦状态到几千几万线性代数解法就变味了稀疏矩阵迭代法更实用。动态规划的经典做法不是解方程组而是用迭代逼近。从任意初始V_0开始反复套用V_{k1}(s) Σ_a π(a|s) Σ_{s} P(s|s, a)[r γ V_k(s)]这个操作的效果是每一轮都用上一轮的V_k计算出新的V_{k1}直到相邻两次的差足够小。因为γ1这个迭代序列会单调收敛到真实价值函数。收敛速度由γ决定γ越接近0收敛越快γ0.9时每次迭代误差约缩小到前一次的0.9倍。工程上有个后来做DP一定会遇到的细节完全收敛往往没必要。策略评估只是为策略改进服务的中间过程只要价值函数大致能反映相对优劣就可以提前停止评估、直接进入改进阶段。这种评估一轮就改进一轮的折中模式叫modified policy iteration能省掉大量无谓扫描。我在后面的经验章会细说。3.2 策略改进为什么贪心在理论上不会亏有了V_π怎么从旧策略改进到新策略答案是每个状态都选择当前Q值最大的动作π(s) argmax_a Σ_{s} P(s|s, a)[r γ V_π(s)]听起来这就是个朴素的贪心。但在强化学习里这个贪心有一个漂亮的保证如果π按上述方式取那么对于所有状态V_π(s) ≥ V_π(s)一定成立。也就是说每一步改进都不会倒退只会持平或更好。为什么直观的逻辑是对状态s来说新策略选择了能带来最大下一状态价值的动作而这个最大不会小于旧策略在该状态下所有动作的加权期望因此单看一步新策略在s上就已经不比旧策略差。由于改进是全局同步进行的这个优势会通过贝尔曼递推向所有可到达的状态传播。你可以把它理解成一个团队里每个人都被换成了在当前岗位上最合适的人整个团队的整体产出只可能上升或持平不可能变差。3.3 双轮传动直到不动点策略迭代的完整循环是给定一个初始策略通常均匀随机。策略评估迭代计算V_π直到收敛。策略改进按V_π做贪心得到新策略π。如果π π说明已经到达最优策略停止否则回到第2步。站在更高的视角看这个循环里的每一步都在向不动点靠近评估收敛于策略π的价值改进把策略推向针对当前价值最优的新策略两个步骤交替直到策略不再变化。因为有限MDP的策略数量是有限的且每轮改进不会让价值下降这个过程保证在有限步内终止。这里的复杂度值得估算一下。每轮策略评估中对 |S| 个状态、|A| 个动作、每个动作最多 |S| 个后继状态一次的完整扫描成本是O(|S|²|A|)。这是DP类算法最让人头疼的计算量来源——状态空间稍微长大一点成本急剧上升。所以DP在实际应用中一直偏爱状态空间小、结构清晰的系统这是我后面要反复强调的边界。4. 价值迭代把两步合并成一步策略迭代是完备的但它有一个明显的笨拙之处每轮改进之前都要先把整个策略评估到接近收敛。可我们要的只是哪个动作更好精确的价值其实没那么重要——更聪明的方法是让价值估计跟着策略一起进化而不是等策略完全定下来再去算价值。由此引出一个更优雅的算法价值迭代。它的更新规则异常简洁V_{k1}(s) max_a Σ_{s} P(s|s, a)[r γ V_k(s)]把它和策略评估公式对比区别只有一个策略评估里的Σ_a π(a|s)被换成了max_a。这个替换意义深远。策略评估是按给定策略做加权平均价值迭代则是每次都选最好的动作。在价值迭代里评估和改进不再分开发生每一次扫描都同时完成这两件事。你不需要显式维护策略策略只是价值函数算出来之后的附属产物只要V收敛到V*最优策略就是argmax那一行直接导出即可。实现代码通常还比策略迭代更短因为少了一层for循环。为什么V_k一定会收敛到V*这里有一个非常漂亮的数学性质上面这条更新规则可以写成V ← TV其中算子T称为贝尔曼最优性算子。这个算子是一个γ-压缩映射意思是||TV₁ - TV₂||_∞ ≤ γ ||V₁ - V₂||_∞压缩映射的意义在于每做一次映射两个价值函数之间的距离至少缩小到原来的γ倍。因此反复施加算子序列V_k会像一条被反复折短的毛线一样不断靠近唯一的不动点——而这个不动点恰恰就是贝尔曼最优性方程的解V*。这个证明框架虽然抽象但体现了为什么只要γ严格小于1价值迭代就一定收敛。收敛速度由γ直接决定γ0.9时每轮误差缩小约10倍需要22轮γ0.99则需要230轮。所以γ并不是一个很随意就能设的参数它直接影响算法的迭代成本。5. 策略迭代 vs 价值迭代两种选择背后的工程逻辑对比维度策略迭代价值迭代迭代单元评估改进交替进行单轮扫描同时完成评估与改进收敛速度策略改进次数少适合状态数中等每轮改进较小可能需要很多轮每轮成本需要完整评估循环成本高一轮扫描O(|S|²|A|)对初始值的敏感度对初始策略敏感迭代轮数少对初始价值敏感但一般都能收敛实现复杂度两套循环逻辑稍长实现简单几行搞定典型场景状态空间有限且模型精确状态爆炸前的中小问题、教学演示很多人以为价值迭代一定比策略迭代好其实未必。策略迭代虽然每轮贵但改进的幅度大收敛所需的轮数通常少得多价值迭代每轮便宜但几何级数收缩的特点让它可能走很多轮才磨到最优附近。同样是1000个状态的环境策略迭代可能10轮以内就稳定价值迭代可能要几百轮甚至上千轮。当然状态空间一旦变大两者都无能为力这就是下一章要聊的边界。实际项目里我更推荐折中方案每轮策略评估只做有限几次扫描不等完全收敛就做改进。这个方案融合了两者的长处——评估成本被压到很低同时每轮还能保留策略层面明显前进的幅度。许多经典强化学习教材没有强调这一点但它是把DP从玩具问题推向真实问题的一个重要技巧。6. DP的隐性前提它到底缺什么6.1 模型是命根子转移概率和奖励函数动态规划从头到尾都在使用P(s|s, a)和R(s, a, s)这两个输入。这让DP天然分为两类预测问题给定策略求V_π。控制问题不求给定策略直接找最优策略。两次操作都离不开同样的材料完整的环境模型。这也是DP与传统学习类算法的分水岭。一个不知道转移概率的智能体不可能手写贝尔曼方程它只能通过与环境的交互采样数据用统计推断去估计价值函数。Q-learning就是这条路线上的典型例子它看起来像是无模型的价值迭代——没有模型时用采样均值替代期望用一次次试错逼近贝尔曼最优方程的解。6.2 灾难后果状态空间的诅咒DP的复杂度里有个令人绝望的平方项O(|S|²|A|)。这意味着状态数翻一倍计算量翻四倍翻四倍计算量翻十六倍。20×20400个状态的网格已经接近千万次级操作三维机器人网格动辄上万状态会让DP直接变成一个天文数字。再加上每个状态都要完整扫描这条约束DP连偷懒的空间都没有。采样型强化学习可以靠随机探索集中在概率较高的状态区域DP没有这个能力它对所有状态一视同仁。这也是为什么DP在实际工程项目里很少成为主角而深度强化学习能火起来——函数近似让价值函数的表示成本不再随状态数指数膨胀。但从另一个角度看很多系统仍然把DP当作核心计算引擎。经典控制里的线性二次调节器、车辆巡航的燃油最优控制、机械臂在低维任务空间里的轨迹规划、船舶调度中的动力优化只要有精确模型且状态维度可以压到个位数DP给出的结果依旧是最可靠的基准解。想在低维世界找最优解动态规划不应该是被绕过的章节而应该是首先想到的工具。7. 动手实践Gambler问题的完整流程7.1 赌徒问题的设定为了看DP如何落地用Sutton书里经典的Gambler问题来做实验。设定很简单赌徒手里有s美元s1,2,...,99目标赢到100美元每局他可以下注a美元a不能超过min(s, 100-s)。假设赌局硬币正面朝上的概率是p0.4不利赌局赢了就多a美元输了就少a美元到0美元破产到100美元任务完成达到这两个状态游戏结束。这是一个标准的有限MDP状态s1..99动作a1..min(s, 100-s)终止状态是0和100。因为赢的概率不满0.5直觉上保守下注等运气和激进全押赌一把的选择并不直观最终的最优策略并不简单非常考验算法。7.2 价值迭代代码不用任何强化学习框架纯Python就能跑通核心代码只有20多行import numpy as np goal 100 # 目标金额 p_head 0.4 # 硬币正面概率不利情况 theta 1e-4 # 收敛阈值 v np.zeros(goal 1) # 状态价值v[0]v[100]0 终止状态 policy np.zeros(goal 1, dtypeint) while True: delta 0.0 for s in range(1, goal): # 跳过终止状态 old_v v[s] best_value 0.0 best_action 0 # 可选下注额范围不超过当前资金也不超过离目标的距离 for a in range(1, min(s, goal - s) 1): val p_head * v[s a] (1 - p_head) * v[s - a] if val best_value: best_value val best_action a v[s] best_value policy[s] best_action delta max(delta, abs(old_v - v[s])) if delta theta: break需要注意几个细节终止状态的价值必须设为0并跳过更新动作的下界从1开始因为下注0没有意义动作的上界是min(s, goal-s)保证赌徒赢了不超出目标、输了不会导致负资产。7.3 结果解读三峰策略的反直觉之处跑完之后把policy画出来横轴是当前资金s纵轴是最优下注额a会看到一个非常有趣的三峰形状。资金在25以下时下注全部资金25到50之间下注50-s50到75之间下注s-50超过75之后下注100-s。这个策略一开始反直觉为什么不是全押到底因为它稳的不是单局而是整个过程的期望回报。用0.4的赢率小步快跑可以多次尝试单局输光概率被分散全押则一次失败就归零。而价值迭代通过贝尔曼方程把这些概率路径完整地编码进了价值函数最终算出来的策略看起来聪明其实只是方程一贯的推论。这个例子非常有说明力它在训练DP时也帮我建立了一个直觉——价值函数不是黑箱输出的数字它就是未来回报的期望在人脑里可以画出来的概率地图。你理解了这张地图就理解了Q-learning里那张Q表在收敛后到底在表达什么。7.4 如果换一个更直观的环境网格世界如果Gambler的概率选得不够直观网格世界是更好的入门。假设一个5×5的网格左上角是起点右下角是目标其他格子有随机奖励比如一个格子-1表示代价一个格子10表示金币智能体可以上下左右移动。状态数只有25个价值迭代算出来的每个格子的价值就是从这格出发按最优策略走未来还能拿到的期望回报。跑到最后把每个格子的最优动作标记成箭头就能得到一张完整的策略图能看得见的最优路径就是这样的。这种可视化的价值其实是很难从公式里感受出来的。8. 从DP出发理解整个RL家族TD、Q-learning、离线和深度方法的关系很多教程把DP、蒙特卡洛、时序差分并列提出让人误以为它们是互不相关的几种算法。实际上它们共享同一套贝尔曼方程骨架区别只在于对期望计算的处理方式。动态规划已知模型用全状态扫描精确计算期望不需要数据。蒙特卡洛未知模型用完整回合的实际回报样本估计价值。时序差分未知模型用当前估计值自举加实时奖励更新一步一更新。Q-learning本质上就是用采样的方式执行价值迭代。价值迭代里更新的公式是v(s) max_a Σ P[r γv(s)]Q-learning把期望换成了当前的Q估计值和一个实时采样到的(s, a, r, s)思路完全一脉相承。把这个油门一直踩到底配上多层神经网络当函数近似器就是Deep Q-Network再把数据改成从固定数据集读取、不与环境交互就成了离线强化学习的框架比如现在讨论度很高的IQL这类方法虽然名字叫隐式Q学习但它优化的仍然是贝尔曼方程那套价值函数约束。图强化学习和深度强化学习的热度可以理解为价值函数本身是定义在状态空间上的函数当状态带有图结构时比如分子、路网用图网络去做函数近似是很自然的选择。联邦深度强化学习解决的数据分布问题只是换了一种训练模式。多个方向的进阶都只是换怎么表达和近似价值函数底层要逼近的贝尔曼不动点没有变。所以说把DP这一章吃透相当于拿到一张整个强化学习世界的地图。后面所有算法再花哨也是在地图上的某条路径上做工程改进。9. 实操中的坑与经验从数值精度到工程选择9.1 终止状态不是小事我第一次写Gambler问题时忘了把v[0]和v[100]锁死为0结果价值一直在两个终止状态间振荡。原因是终止状态不该参与更新一旦它们被更新等于奖励会从边界流回内部导致价值函数出现鬼影。处理办法就是直接跳过终止状态并强制清零。这个坑在网格世界、迷宫问题里都会出现凡是DP实现第一步先检查终止状态是否被正确隔离。9.2 收敛判据的取值经验θ取1e-4在多数小问题上够用但如果γ接近0.99价值量级变得很大θ要相应缩小。否则很容易出现数值上停下来了策略还没稳定的情况。更稳的做法是同时监控策略变化每轮记录策略是否发生变化策略连续几轮不变通常比价值差值更早给出收敛信号判断时优先以策略稳定为准。另外收敛阈值太苛刻没有意义。价值函数每一次迭代的误差上界和γ/(1-γ)有关暴力压到1e-8在小问题上浪费时间在稍大的问题上可能导致根本不收敛。我的习惯是先跑一版看价值量级再定θ价值量级10以内用1e-4量级100以上用1e-5或更小。9.3 高斯-赛德尔式更新免费的加速标准价值迭代用的是全同步更新先用旧的V_k算完全部新值再一起替换。实际实现时可以改成就地更新——算出一个新V(s)立即覆盖旧值后续状态计算直接使用最新值。这种异步DP也叫高斯-赛德尔式更新在多数情况下能把收敛轮数压缩30%-50%代码改动却只有一行赋值顺序的区别。原理也不难理解较新的信息更逼近真实价值传递给下游状态时误差更小。9.4 热启动的价值策略迭代和价值迭代都可以利用热启动上一次任务算好的价值函数直接作为新一轮迭代的初始值模型微调后重新计算时能省掉大量预热轮次。这在实际工程里非常实用比如机械臂任务中目标位置小幅变化、车队巡航的坡度参数变化热启动能把原本几百轮的价值迭代压到几十轮。但要注意如果环境变化太大比如目标从远到近翻转热启动可能把旧的最优解当作初始偏向反而需要更多轮次来纠偏此时不如随机初始化来得干净。9.5 DP什么时候该用、什么时候该果断放弃我的应用标准越来越简单有精确模型、转移概率可算、状态空间撑死在几万个以内DP就是首选状态维度一旦超过五六个并且需要连续表示DP基本无法落地直接转向函数近似、深度强化学习或者采样型方法。很多人在这中间犹豫不决浪费大量时间调一个已经超纲的问题。DP还有一个很实际的价值常被低估作为标准答案生成器。训练一个深度强化学习智能体前在小规模简化版本上用DP算出最优价值和最优策略你手里就有了一张可对照的标准答案表。模型训练完之后拿DP的结果做对比能快速判断是环境建模问题还是策略学习问题。我的工作流里DP始终没有离开工具箱只是从主角变成了裁判。动态规划的价值不在于它的公式有多深奥而在于它用一个极其干净的递推框架把强化学习的目标函数和最优策略牢牢钉在了数学的可计算地基上。真正动手跑一遍Gambler问题亲眼看到三峰策略从贝尔曼方程里长出来你会对后面所有的深度强化学习算法获得一个更坚实、更少被迷惑的理解。