做强化学习这两年最常被朋友问起的一个问题是书上讲的动态规划和LeetCode刷的“动态规划”到底是不是一回事其实两者共享同一个数学内核但落地场景完全不同。算法题里的DP解决的是“递推状态转移”问题而强化学习里的动态规划是一套在已知环境模型下求解最优策略的系统化方法。很多人入门RL时都卡在这里因为它既不像监督学习那样直接调包训练也不像进化算法那样随机搜索它需要你先理解MDP马尔可夫决策过程、价值函数、贝尔曼方程这一整套理论然后再把理论转成真正能跑出结果的代码。这篇文章我打算用一次完整的网格世界实战把强化学习中的动态规划掰开揉碎。从理论推导讲到策略迭代与价值迭代的实现再聊到为什么真实场景不能直接套DP、以及现代RL算法里DP思想的继承方式。读完你至少能自己复现一个价值迭代求解器也能看懂为什么DQN、PPO这些算法的理论推导里总是绕不开那几个DP递推式。1. 在强化学习里“动态规划”到底指什么1.1 先分清两个“动态规划”平时刷题碰到的动态规划核心是“最优子结构 重叠子问题”通过缓存中间结果避免重复计算。强化学习里的动态规划字面含义更贴近Bellman本人最初的定义把一个多阶段决策问题拆成一系列单阶段子问题每个子问题的解都依赖于后续状态的估计值。换句话说它是“利用贝尔曼方程进行迭代求解”的一类算法统称。所以别再纠结“为什么RL的DP和算法题长得不像”了。算法题里的DP是递归公式的优化计算RL里的DP是在MDP框架下同步计算价值函数并推导策略。两者共享的只有“状态”和“递推”这两个灵魂真要上手方法论完全不同。1.2 MDP给了DP发挥的前提动态规划在强化学习里能成立完全依赖于MDP这个假设。MDP用五元组来描述决策问题状态集合S、动作集合A、状态转移概率P、奖励函数R和折扣因子γ。其中最核心的是转移概率P(s|s,a)它告诉你“在状态s下执行动作a之后环境会以什么概率跳转到哪个后续状态”以及这个过程中你会拿到多少即时奖励。有了转移概率问题就成了一个完全已知的模型。DP算法利用这个模型从初始估计出发不断迭代逐步逼近真实的期望回报。注意“期望”这两个字因为环境有随机性价值函数估算的必须是对未来奖励的期望而不是某次采样得到的随机结果。这也是DP和其他无模型方法最大的一条分界线DP吃的是“模型”MC和TD吃的是“样本”。1.3 基于模型与无模型的岔路口强化学习算法可以粗略分成两大家族基于模型的方法依赖已知或学习到的环境模型状态转移和奖励都能提前算无模型方法则依赖智能体与环境交互产生的样本从经验中估计价值。动态规划就是最典型的基于模型方法。这个区分非常关键。如果你手里有一个精确的仿真器比如机器人控制里的物理仿真、电网调度里的潮流计算器那你完全可以用DP思路直接优化策略不用浪费海量时间去采样。反过来如果环境是黑盒比如一场真实的游戏、一个真实的生产线你拿不到转移概率只能靠试错那么DP就从“直接求解器”降级成“理论基石”真正上场的是Q-learning、DQN这些算法。理解这条岔路能帮你少走很多弯路。2. 从贝尔曼方程到价值迭代把原理一次讲透2.1 价值函数是DP的核心对象动态规划不直接搜索策略而是先估计价值函数。价值函数分两种状态价值函数V(s)表示从某个状态出发按照指定策略继续行动未来能拿到的期望回报总和动作价值函数Q(s,a)表示在某个状态下先执行某个动作之后按照指定策略继续行动未来能拿到的期望回报总和。两者之间通过策略π关联起来。回报总和通常要乘上折扣因子γ原因很现实未来收益不确定、有风险而且无限时间步下不折扣的话总和可能发散。γ取值在0到1之间越接近1表示越看重长远收益越接近0表示越短视。这个参数几乎贯穿所有RL算法后面调参部分还会再提。贝尔曼方程的精髓是“当前价值可以用下一步价值来表达”它把无穷时间步的累计回报压缩成一个递推式。策略π下的状态价值满足Vπ(s) Σ_a π(a|s) Σ_s P(s|s,a) [R(s,a,s) γ Vπ(s)]这个方程看起来只是把未来回报拆成了“即时奖励 后续状态价值折现”但它是DP所有迭代公式的起点。解出这个方程就等于完成了策略评估。2.2 策略评估求解贝尔曼期望方程策略评估要做的事情就是给定一个固定策略π计算出每个状态的Vπ(s)。问题在于这个方程两边都包含Vπ(s)直接解线性方程组理论上可行但状态一多就麻烦。实际常用的是迭代法初始化一个全零的价值表然后反复套用更新公式把旧价值表代入右侧算出一张新的价值表直到两次迭代之间的变化小于阈值。伪代码可以写得很短repeat: delta 0 for s in S: v V(s) V(s) sum_a π(a|s) * sum_s P(s|s,a) * (R(s,a,s) γ * V(s)) delta max(delta, abs(v - V(s))) until delta theta这里插入的每一个环节都依赖已知模型。没有转移概率右侧第二层求和根本写不出来。这也是为什么在无模型环境里这条求和的“上帝视野”会消失然后才转向采样平均。2.3 策略迭代评估改进的循环策略评估解决的是“给定策略价值是多少”。可我们要的是最优策略光会评估还不够。于是就有了策略改进这一步拿着当前策略算出的价值函数贪心地更新策略让每个状态下都选择能使动作价值最大的动作。一轮评估加一轮改进叫策略迭代。策略迭代每轮都要把评估跑到完全收敛计算负担比较大但胜在理论上有严格保证只要改进一次策略就一定变好最终收敛到最优策略。实践中网格世界这类小问题往往只需要几轮迭代就出结果。2.4 价值迭代合并两步的加速版策略迭代有一个明显的浪费完全做精确评估没必要因为还没到最优策略精确评估的价值函数很快会被新策略推翻。价值迭代就聪明得多它直接把“策略评估只推一步 策略改进”合并成一个操作在每次更新时都对状态价值做贝尔曼最优性替换V(s) max_a Σ_s P(s|s,a) [R(s,a,s) γ V(s)]这个max操作代替了“先按当前策略求期望、再贪心改进”的两步流程省掉显式更新策略的步骤价值收敛后直接把最优策略隐式读出来。价值迭代收敛速度快很多尤其适合状态可数且规模不太大的MDP也是很多人入门时写的第一个RL求解器。3. 网格世界实战用三份代码把DP跑通3.1 环境建模与参数设置纸上谈兵这么久下面来实际操作。经典网格世界问题是验证DP算法最直观的场景一个5x5的网格智能体从左上角出发要走到右下角的终点每一步可以上下左右移动碰到边界就停在原地每走一步奖励为-1到达终点奖励为0。为了让问题稍微复杂一点我在中间加了几格障碍不允许穿越。用代码表达MDP时我习惯把状态编号为0到24动作编号0到3分别代表上、下、左、右。转移概率P(s|s,a)在这个确定性环境里是1或0奖励函数R按规则直接查表。虽然确定性环境没有体现“期望”的重要性但理解流程足够用了。完整的概率分布版本可以把动作执行失败的情况加进来比如20%概率滑到垂直方向后面可以自行扩展。3.2 策略评估代码解析下面这段代码实现策略评估。关键点有两个一是使用两层循环分别遍历状态和动作二是用一个临时变量old_v记录更新前的值用来计算变化量delta。千万不要在同一个循环体中一边更新一边又用新值去覆盖旧值那样会破坏迭代式右侧读取的“上一次迭代”结果。import numpy as np def policy_evaluation(policy, V, P, R, gamma0.99, theta1e-6): while True: delta 0 for s in range(len(V)): old_v V[s] v 0 for a in range(len(policy[s])): action_prob policy[s][a] if action_prob 0: # 确定性环境下只有一个s概率为1 s_next P[s][a] v action_prob * (R[s][a] gamma * V[s_next]) V[s] v delta max(delta, abs(old_v - V[s])) if delta theta: break return V这段代码假设策略以概率分布形式给出比如均匀随机策略下每个状态的每个动作概率都是0.25。如果想要更精确应该把P[s][a]扩展成字典或二维数组容纳多状态转移的情况。确定性环境简化了这一点但概念上不要丢掉。3.3 策略迭代与价值迭代的实现对比策略迭代在评估完价值函数之后紧接着做策略改进。改进时需要对每个状态计算所有动作的Q值然后把概率最大的动作选为唯一动作。这里有个细节如果多个动作的Q值并列最大可以随机挑一个也可以保留概率均分但常见实现都是直接取第一个或随机取一个别在并列情况上纠结太久。def policy_improvement(V, P, R, gamma0.99, n_actions4, n_states25): policy np.zeros((n_states, n_actions)) for s in range(n_states): q_values [] for a in range(n_actions): s_next P[s][a] q_values.append(R[s][a] gamma * V_s_copy[s_next]) best_a np.argmax(q_values) policy[s][best_a] 1.0 return policy def policy_iteration(P, R, gamma0.99, theta1e-6): n_states len(R) V np.zeros(n_states) # 初始化为均匀随机策略 policy np.ones((n_states, 4)) / 4 while True: V policy_evaluation(policy, V, P, R, gamma, theta) new_policy policy_improvement(V, P, R, gamma) if np.array_equal(new_policy, policy): break policy new_policy return V, policy价值迭代的代码则简洁得多不需要维护策略表只更新价值函数。终止条件同样是看价值表变化量但这里的更新公式用的是max并且隐含了“即时奖励 后续最优价值”这一层一步拓展。def value_iteration(P, R, gamma0.99, theta1e-6): n_states len(R) V np.zeros(n_states) while True: delta 0 for s in range(n_states): old_v V[s] q_values [] for a in range(4): s_next P[s][a] q_values.append(R[s][a] gamma * old_v # 注意这里要小心 V[s] max(q_values) delta max(delta, abs(old_v - V[s])) if delta theta: break return V上面代码里我故意写了一个常见的坑q_values更新时误用了old_v而不是当前的V[s_next]。很多新手会犯这个错误因为脑子里知道“应该使用上一轮的价值函数”于是误以为整张价值表都不能变。实际上价值迭代可以在一次内部循环中直接使用正在更新中的V[s_next]因为它只遍历一次状态且修改顺序有讲究。正确做法是每次更新前取当前V[s_next]没有必要刻意保留旧表。我的建议是如果你刚接触先把value iteration写成“每轮迭代前复制一份V_old然后所有更新都读V_old”的版本保证逻辑清楚再考虑优化成原地更新的版本。3.4 观察收敛从数值里读懂行为跑完上面的代码后把最终价值表按网格形状打印出来会看到终点附近的状态价值最高越靠近起点价值越低因为走的路更长负奖励累积更多。配合策略表可以看到智能体基本会沿着最短路径走向终点。一个很有意思的观察是策略迭代明显比价值迭代多跑了不少轮但每一轮计算量略小价值迭代虽然轮数少但每轮都要对所有状态计算一遍max。在小网格上两者差距不大在几百个状态的中等规模问题上价值迭代通常胜出。如果你再细致一点把每轮迭代的max-delta画成曲线会发现早期下降非常快后期放缓这是指数收敛的典型特征。4. DP的边界为什么真实任务不能直接套4.1 维数灾难与计算复杂度DP最大的软肋是计算量和状态空间的规模强相关。5x5网格只有25个状态迭代几百次毫无压力但机器人关节角度连续变化、围棋盘面组合爆炸、城市路网节点上万这些场景状态量瞬间冲到百万级以上。每一次迭代都要对所有状态做一次完整扫描复杂度O(|S|²|A|)乃至更高轮数还随状态数增大而变多DP在这个尺度下直接失去实用价值。这就是为什么很多实际工程问题最终转向采样类算法。蒙特卡洛和时序差分方法不扫描全部状态只靠与环境交互的轨迹来更新价值计算量集中在真正访问到的状态上。即便它们会有方差问题但在DP根本跑不动的规模下“有偏但能跑”比“精确但卡死”实际得多。4.2 模型未知从DP到无模型方法除了规模问题模型未知是另一个硬伤。DP要求你知道P(s|s,a)和R(s,a,s)也就是必须拥有环境的“上帝视角”。但大部分场景下这根本不现实。一个自动驾驶系统面对的真实道路不存在确定性转移概率表一个推荐系统面对的用户点击行为也不是固定概率能描述的。无模型方法干脆绕开这个前提用“采样去估计期望”。Q-learning的更新公式看起来和贝尔曼最优方程很像但P和R都消失了取而代之的是观测到的下一状态和即时奖励。换句话说DP是无模型方法的“哥哥”它教了弟弟们“价值函数应该怎么递推”但弟弟们不再依赖那个全局模型只靠经验去逼近同一个目标。4.3 DP思想仍然活跃的地方虽然直接套用DP的范围有限但它的思想在现代算法中四处可见。Dyna架构把真实采样和模型模拟结合起来本质上就是把DP的价值更新当成一个“想象中经验的再利用”环节。AlphaGo系列里也大量运用了仿真搜索和自对弈动态规划式的评估-改进循环以更复杂的形态获得了重生。另外在组合优化领域DP思路依然非常能打。比如车辆路径问题、机械臂轨迹规划、以及混合整数规划MILP与强化学习的结合场景里小规模子问题常常用动态规划直接求解再用启发式或RL去处理大规模决策。我的经验是遇到一个决策问题别急着上深度强化学习如果状态空间小且模型可知先用DP解一遍得到的策略和价值函数往往是后续做深度RL时最好的初始化和调参参考。5. 高频问题与避坑指南5.1 收敛阈值怎么设置代码里的theta控制迭代终止精度。太小会导致迭代次数过多、白算很多轮太大会在价值函数还远没收敛时提前停止策略表现会很差。我一般用1e-6到1e-4这个范围状态规模越小、奖励绝对值越大越需要更小的阈值。判断终止条件时delta只衡量当前这轮所有状态更新的最大绝对值变化。如果奖励值本身很小比如全部在0.01附近delta小于1e-6可能非常慢反之奖励值动辄上百1e-6可能过于严苛。一个务实的经验是先看“策略是否还发生变化”如果连续几轮策略都不变价值迭代的后续收益就已经很有限了可以直接停。5.2 折扣因子的影响比想象中大γ在DP里不只是“偏好长远”它还直接影响贝尔曼方程的存在性和收敛速度。γ越接近1长期价值占比越高价值函数需要更多迭代才能从远端点传回信息。在网格世界里γ0.99和γ0.9的价值分布差异非常明显后者几乎看不到终点远期奖励对起点的拉动。如果拿DP做实际项目γ取值还要结合任务时间尺度来定。机器人走完一段路可能就几十秒设置γ0.999反而会让价值函数被遥远的奖励主导策略显得“迟钝”。反过来长期投资决策类任务需要γ极高。我的建议是先大概估算任务的有效决策步数N令γ≈1-1/N作为起点再上下微调。5.3 初始策略怎么选策略迭代对初始策略的要求不苛刻均匀随机策略是默认选择。不过在某些稀疏奖励环境里随机策略可能导致价值函数长时间都是负的改进过程进展很慢。这时可以用启发式信息做初始化比如让智能体偏向某个方向或者手动设计一条保守轨迹。一个常见的坑是策略改进阶段过于贪心遇到并列Qi相等时总是固定选同一个动作。这可能造成策略“偏科”在确定性环境中表现不明显但在随机环境里会被放大。我的处理方式是在相等时才用随机打破平衡。5.4 调试技巧与可视化跑DP时我最推荐的做法不是只打印最终数字而是把“价值函数变化曲线”“策略在网格上的箭头图”“每轮策略不同状态变化次数”同时可视化。价值函数曲线能反映收敛速度策略箭头图能直观看到智能体的“决策意图”策略变化次数则能暴露“算法在策略空间震荡”的问题。如果发现价值函数里有某些状态数值特别异常先别急着怀疑算法检查这些状态是否被障碍或边缘卡住。边界状态的动作往往会把智能体撞向原地导致价值偏低这本身是合理的。真正需要调试的是奖励函数设置是否与目标一致、终点是否有明确的终止判定、障碍状态的转移概率是否被错误地归零。网格世界的Debug基本都能归到这三类。最后再分享一个自己的习惯在做任何复杂RL项目前我都会构造一个小规模、可穷举的MDP把DP算法跑一遍作为“标定”。如果DP结果和理论最优解对不上说明是环境建模出了问题如果对得上再把这个环境作为后续无模型算法的测试床用来校验采样类算法的可靠性。DP可能不会出现在生产环境的最终部署里但它是我检验所有RL代码的第一道安全网这个习惯一直延续到现在。