强化学习动态规划：策略迭代与值迭代原理及实现-北京尧图网络

1. 从“查表”到“迭代”动态规划到底在强化学习里扮演什么角色很多人第一次接触强化学习脑子里浮现的都是神经网络、梯度下降、各种复杂的策略优化。但如果你把时间倒回这门学科刚起步的年代会发现最核心的求解工具其实非常朴素——动态规划。它不依赖任何函数逼近也不需要采样只要你能把问题写成一个马尔可夫决策过程并且状态空间和动作空间都足够小它就能给你算出精确的最优策略。我刚开始学这块的时候也有个误解觉得动态规划就是个“老古董”实际项目里根本用不上。后来做了一些小规模的调度和路径规划问题才发现动态规划给出的解往往是最好的基准线。你后面用Q-learning也好用策略梯度也好最终效果好不好拿动态规划的结果一对比就清楚了。它就像一把尺子量的是你的算法到底偏离最优解有多远。这篇文章我打算把动态规划在强化学习里的两个核心算法——策略迭代和值迭代——从头到尾拆一遍。不是那种教科书式的公式罗列而是把我自己推导时卡住的地方、写代码时踩过的坑、以及为什么这么设计的原因都讲清楚。适合已经了解MDP基本概念、但还没真正动手实现过动态规划的读者。如果你连状态、动作、回报这些词都还陌生建议先补一下基础再来看不然容易卡在中间。先说结论动态规划的核心思想就一句话——用贝尔曼方程把一个大问题拆成一层层的小问题然后反复迭代直到收敛。听起来简单但魔鬼全在细节里。2. 贝尔曼方程动态规划能跑起来的唯一支点2.1 为什么必须先把贝尔曼方程吃透动态规划之所以能用在强化学习上根本原因在于价值函数满足贝尔曼方程。这个方程的本质是一个递归关系当前状态的价值等于你采取某个动作后获得的即时回报加上折扣后下一个状态的价值期望。用大白话说就是一个位置好不好取决于从这儿出发能拿到多少即时好处以及下一步能走到多好的位置。这个递归结构让“全局最优”这个问题变成了“每一步都做对”的问题。贝尔曼方程有两种形式分别对应状态价值和动作价值状态价值函数 V(s)从状态s出发按照策略π行动能获得的期望回报。动作价值函数 Q(s,a)从状态s出发先执行动作a之后按照策略π行动能获得的期望回报。这两个函数之间的关系是理解后面所有算法的关键。V(s)等于在s下对所有动作的Q(s,a)按策略概率加权求和而Q(s,a)等于即时回报加上折扣后所有可能下一状态的V的期望。我当初学的时候最大的困惑是这两个函数到底哪个先算后来想明白了——它们互相依赖所以动态规划的做法就是先随便猜一个然后反复迭代让它们互相逼近直到不再变化。2.2 贝尔曼最优方程和普通贝尔曼方程的区别这里有个容易混淆的点。普通贝尔曼方程描述的是“给定策略π下的价值”而贝尔曼最优方程描述的是“在所有可能策略中最优的那个价值是多少”。区别体现在动作选择上普通贝尔曼方程对动作做加权平均按π的概率而最优贝尔曼方程直接取最大值。这个“取最大”的操作就是贪心策略的来源。注意取最大值这个操作看起来简单但它引入了一个非线性因素。这也是为什么动态规划需要反复迭代——因为max操作让方程不再有闭式解只能一步步逼近。2.3 折扣因子γ到底在调节什么折扣因子γ0到1之间控制的是未来回报的权重。γ越接近0智能体越短视只看眼前利益γ越接近1智能体越有远见愿意为长期回报牺牲即时收益。但γ还有一个容易被忽略的作用它决定了价值函数的数值范围。如果即时回报的最大绝对值是R_max那么任何状态的价值都不会超过R_max/(1-γ)。这个性质在数值计算时很有用可以帮你判断迭代是否已经收敛到合理范围。我在实际调参时发现γ设成0.9到0.99之间通常比较合理。太低会导致策略过于短视太高则会让价值函数收敛变慢而且数值容易变得很大。具体选多少要看你问题的“视野”有多长——如果完成一个任务需要几十步γ至少得0.95以上。3. 策略迭代先评估再改进循环往复3.1 策略评估的完整推导过程策略迭代的第一步是策略评估给定一个策略π算出这个策略下每个状态的价值V_π(s)。做法很简单就是把贝尔曼方程当成一个迭代更新公式V_{k1}(s) Σ_a π(a|s) [ R(s,a) γ Σ_{s} P(s|s,a) V_k(s) ]这个公式的意思是新的价值估计等于“按当前策略选动作每个动作的即时回报加上折扣后下一状态旧价值的期望”的加权和。实际操作时我们初始化V(s)0或者任意值然后反复用这个公式更新所有状态的价值直到V的变化量小于某个阈值比如1e-6。这里有个细节更新顺序会影响收敛速度。如果按状态编号顺序更新后面的状态会用上前面刚更新的值这叫“异步更新”通常比同步更新所有状态用旧值算新值收敛更快。我在代码里一般直接用异步更新省事又高效。3.2 策略改进贪心为什么能保证不退化策略评估完成后我们有了每个状态的V值。接下来做策略改进对每个状态选择那个能让Q值最大的动作。新策略π(s) argmax_a [ R(s,a) γ Σ_{s} P(s|s,a) V(s) ]这里有个重要的理论保证新策略一定不比旧策略差。也就是说对任意状态sV_{π}(s) ≥ V_π(s)。这个叫策略改进定理。为什么因为如果你在每个状态都选了当前V下最好的动作那至少不会比原来按π选动作差。如果所有状态都选不出更好的动作了那说明π已经是最优策略。我当初对这个定理的理解卡了很久后来用反证法想通了假设存在某个状态s新策略的价值比旧策略低那说明在s下按π选的动作比贪心动作更好但这与贪心动作的定义矛盾。所以新策略不可能更差。3.3 策略迭代的收敛条件和终止判断策略迭代的流程是评估→改进→再评估→再改进直到策略不再变化。终止条件就是策略改进后所有状态的动作选择都和上一轮一样。这时候策略已经稳定再迭代下去也不会变了。但实际写代码时判断“策略不再变化”比判断“价值不再变化”更直接。因为价值可能因为数值精度问题一直在微小波动但策略早就稳定了。提示策略评估不需要做到完全收敛。实践中评估迭代几次就够了因为策略改进会纠正评估的误差。这种“不精确评估”的策略迭代通常收敛更快。3.4 一个手算例子4x4网格世界假设有一个4x4的网格左上角是起点右下角是终点每走一步回报-1走到终点回报0γ1。动作有上下左右四个方向撞墙则留在原地。用策略迭代求解初始策略可以随便设比如所有状态都往右走。第一轮评估后靠近终点的状态价值会变高因为离终点近负回报少。然后策略改进会让这些状态指向终点方向。几轮之后所有状态都会指向一条最短路径。这个例子虽然简单但能帮你直观感受动态规划的工作方式。我建议你拿张纸手算一遍比看十遍公式都管用。4. 值迭代把评估和改进揉成一步4.1 值迭代和策略迭代的本质区别值迭代的思路更直接我不维护显式的策略直接迭代最优价值函数。更新公式是V_{k1}(s) max_a [ R(s,a) γ Σ_{s} P(s|s,a) V_k(s) ]对比策略迭代的评估公式你会发现值迭代把“按π加权求和”换成了“取最大值”。这一步就把策略评估和策略改进合并了——因为取最大值本身就意味着在改进策略。值迭代每轮只做一次更新而策略迭代每轮要做多次评估加一次改进。所以值迭代通常更快尤其是状态空间大的时候。但值迭代也有代价它不显式维护策略所以中间过程你看不到策略长什么样。如果你需要观察策略的演化过程策略迭代更直观。4.2 值迭代的收敛性怎么保证值迭代的收敛性依赖于贝尔曼最优算子是压缩映射这个性质。简单说每次迭代后价值函数和最优价值函数的差距会缩小到原来的γ倍。因为γ1所以反复迭代一定会收敛。这个压缩性质也给出了收敛速度的估计如果初始误差是E迭代k轮后误差不超过γ^k * E。所以γ越小收敛越快γ越接近1收敛越慢。我在实际跑值迭代时通常设最大迭代次数1000阈值1e-6。大部分小规模问题几百轮就收敛了。如果超过1000轮还没收敛要么是γ太接近1要么是问题本身有环比如某些状态之间可以无限循环需要检查模型定义。4.3 同步更新和异步更新的选择值迭代也有同步和异步两种更新方式。同步更新每轮用上一轮的V值计算所有状态的新V值然后统一替换。实现简单但需要额外空间存旧值。异步更新按顺序遍历状态每个状态直接用最新的V值更新。收敛更快空间更省。我一般用异步更新因为代码写起来更简洁而且实测收敛速度确实快不少。但异步更新的收敛性证明比同步复杂不过实践中基本没问题。注意异步更新时遍历顺序会影响结果。如果按状态编号顺序遍历可能会导致某些状态被“过度更新”。一个常见的做法是随机打乱顺序或者按某种优先级排序比如优先更新价值变化大的状态。4.4 值迭代的代码实现框架下面是一个值迭代的伪代码框架用Python风格写def value_iteration(states, actions, transition, reward, gamma, theta1e-6): V {s: 0 for s in states} while True: delta 0 for s in states: v_old V[s] v_new max( sum(transition(s, a, s_next) * (reward(s, a, s_next) gamma * V[s_next]) for s_next in states) for a in actions ) V[s] v_new delta max(delta, abs(v_old - v_new)) if delta theta: break # 提取最优策略 policy {} for s in states: policy[s] max(actions, keylambda a: sum( transition(s, a, s_next) * (reward(s, a, s_next) gamma * V[s_next]) for s_next in states )) return V, policy这段代码的核心就是两层循环外层判断收敛内层遍历所有状态做max操作。提取策略时再遍历一次选Q值最大的动作。实际写的时候要注意transition和reward函数的设计直接影响性能。如果状态多最好用矩阵或张量预存转移概率和回报避免每次循环都查字典。5. 动态规划的边界它能做什么不能做什么5.1 动态规划的三个硬性前提动态规划在强化学习里能用的前提非常苛刻模型完全已知你必须知道转移概率P(s|s,a)和回报函数R(s,a,s)。如果不知道动态规划直接没法用。状态空间有限且不大因为要对所有状态做遍历状态数太多比如连续状态就不可行。马尔可夫性质成立下一状态只依赖当前状态和动作与历史无关。这三个条件缺一个动态规划就用不了。这也是为什么实际项目里更多用采样方法如Q-learning——因为采样方法不需要模型也能处理连续状态。但动态规划的价值在于它给出了理论上的最优解。你可以用它来验证采样方法的收敛性或者在小规模问题上做基准测试。5.2 维数灾难状态爆炸怎么破动态规划最大的敌人是维数灾难。假设你有10个维度每个维度10个取值状态空间就是10^10根本存不下。解决思路有几条状态聚合把相似状态合并减少状态数。但会损失精度。函数逼近用参数化函数表示价值函数而不是查表。这就是深度强化学习的思路。采样不遍历所有状态只采样一部分。这就是蒙特卡洛和时序差分方法。动态规划本身没法解决维数灾难但它是理解这些高级方法的基石。你只有先搞懂精确解怎么求才能理解近似解在近似什么。5.3 动态规划和蒙特卡洛、时序差分的关系这三者的关系可以用一句话概括动态规划用模型和自举蒙特卡洛用采样和完整回报时序差分用采样和自举。动态规划需要模型用下一状态的估计值更新当前状态自举。蒙特卡洛不需要模型用完整回合的实际回报更新。时序差分不需要模型用下一状态的估计值更新自举。时序差分可以看成动态规划和蒙特卡洛的结合体。它既有动态规划的自举特性又有蒙特卡洛的无模型特性。理解了动态规划时序差分就很好理解了。我在学习路径上建议先手推动态规划再写代码实现然后对比蒙特卡洛和时序差分。这样一路下来整个强化学习的脉络就清晰了。6. 实操中容易踩的坑和调试技巧6.1 收敛阈值设多少才合适阈值设太大结果不精确设太小迭代次数暴增。我的经验是如果回报量级在1左右阈值设1e-6到1e-8比较合适。如果回报量级很大比如几千阈值要按比例放大。可以先跑一次看delta的变化曲线找一个明显变平的拐点。另外不要只看delta还要看策略是否稳定。有时候delta已经很小了但策略还在微调。这时候多跑几轮更保险。6.2 价值函数初始化的影响理论上动态规划对初始值不敏感因为压缩映射保证收敛到唯一不动点。但实践中好的初始化能显著减少迭代次数。一个常用技巧是用问题的启发式信息初始化V。比如在网格世界里可以用到终点的曼哈顿距离的负值作为初始V。这样一开始就离最优解不远收敛更快。如果没有任何先验信息全零初始化就行。不要用随机初始化因为随机值可能让前几轮迭代波动很大。6.3 策略迭代中评估轮数怎么定策略迭代的评估步骤不需要做到完全收敛。我通常设一个较小的最大迭代次数比如10到20轮或者用较松的阈值比如1e-3。原因很简单评估不精确没关系策略改进会纠正。而且下一轮评估会基于改进后的策略重新算误差不会累积。但要注意如果评估轮数太少策略改进可能选错动作。一个折中方案是前几轮策略迭代用较少的评估轮数后面逐渐增加。6.4 怎么验证动态规划结果的正确性验证方法有几种小规模暴力枚举如果状态和动作很少可以枚举所有策略找最优的。对比动态规划结果。策略稳定性检查最优策略下每个状态的动作是否都是贪心动作。如果不是说明还没收敛。贝尔曼误差检查计算每个状态的贝尔曼误差左边V(s)减去右边max Q(s,a)如果都接近零说明收敛。我一般用第二种和第三种结合。先看策略是否稳定再看贝尔曼误差是否够小。两个都满足基本就没问题了。7. 从动态规划到深度强化学习的自然延伸动态规划虽然在实际项目中直接用的场景不多但它的思想贯穿了整个强化学习。你后面遇到的几乎所有算法都能在动态规划里找到影子。比如DQN里的目标网络本质上是在模仿动态规划的自举更新只是用神经网络代替了查表。再比如策略梯度里的优势函数其实就是在估计动态规划里的Q值和V值之差。我个人的学习体会是动态规划是强化学习的“内功”。你不需要在实际项目里天天用它但如果不理解它后面学什么都是浮在表面。尤其是当你调参调不动、算法不收敛的时候回到动态规划想一想往往能找到问题的根源。如果你现在正在学强化学习我建议你至少手写一遍策略迭代和值迭代的代码在一个小规模问题上跑通。这个过程花不了太多时间但能帮你建立非常扎实的直觉。后面再学Q-learning、SARSA、DQN你会发现很多东西都是水到渠成的。最后分享一个我常用的调试技巧当你的算法不收敛时先在一个极小的状态空间比如3个状态、2个动作上跑动态规划看看最优解长什么样。然后让你的算法在同样的问题上跑对比结果。如果动态规划能收敛而你的算法不能问题一定出在算法实现或超参上而不是问题本身。这个对比法帮我省了很多排查时间。

强化学习动态规划：策略迭代与值迭代原理及实现

相关推荐

Python数据处理：用pandas DataFrame替代字典循环实现高效查询

从困惑度到语义重构：科学降AI率的完整路径

Visual Studio解决方案文件深度解析：.sln、.csproj与协作规范

更多资讯

戴森球计划工厂蓝图库：7128 份蓝图，三步导入、分阶段选型

如何在10分钟内让笔记本跑起Qwen3-8B_rai_1.8.0_npu_4K：Ryzen AI NPU快速部署教程

5分钟上手tf_efficientnet_b3.ap_in1k：用5行代码搭建1000类图像分类器（新手保姆级教程）

如何挑选EfficientNet？efficientnet_b5.sw_in12k_ft_in1k与B0-B7全系列参数性能对比

无名杀网页版：本地部署的免费在线三国杀，两行命令开局

多线程：Thread类基本用法

今日更新

电商智能运营体系从0到1：架构设计、落地步骤与避坑指南

压缩空气储能与热网热惯性联合优化调度：热电联产系统建模与求解

若依框架AI代码生成不稳定？用Agent Skill三层结构+五步法搞定

本周精选

金融AI落地指南：从调研报告到技术选型与工程实践

大模型上下文成本与注意力优化技术深度解析——为何O(n²)平方复杂度无法被常规优化消除｜TaoToken 统一 Key 通道实测

基于GMM的语音识别系统原理与MATLAB实现详解

本月热门

我发现了一个新思路：用 Remotion + Claude Code 像写代码一样自动化生成短视频

Windows下 Codex 中 Chrome 和 Computer Use 插件不可用问题排查及解决参考方式：TaoToken 统一 Key 配置与验证

2026 大模型集体涨价：用 Python 做企业 Token 成本测算与选型避坑（附配置）

读完文章，想聊聊您的网站？