动态规划：深度强化学习绕不开的数学基石

深度强化学习Deep Reinforcement Learning这些年看起来风光无限从棋类博弈到机器人控制似乎所有难题都能用一套“神经网络加奖励”的组合拳搞定。但如果你真去翻开源码和论文会发现一个很有意思的现象几乎所有稳定的算法骨子里都埋着同一条数学主线——动态规划Dynamic Programming简称 DP。这篇东西我想把动态规划在深度强化学习里的角色彻底讲透。它不是一篇干巴巴的课本复述而是把我自己从“看懂公式”到“跑通实验”再到“理解 DQN 系列算法为什么那样设计”的过程拆开揉碎聊聊 DP 到底解决了什么问题、哪些地方值得反复琢磨、哪些坑我替你们踩过了。适合正在学强化学习基础、想做算法对比实验、或者看完 DQN 源码后觉得似懂非懂的读者。1. 为什么深度强化学习绕不开动态规划1.1 从智能体学习路径看 DP 的位置先回到底层逻辑。强化学习要解决的核心问题是一个智能体Agent如何在环境Environment里通过不断试错学到一套能让长期回报最大化的策略Policy。这里的“长期回报”不是眼前这一步的即时奖励而是未来所有奖励的加权总和这个总和通常用一个叫折扣因子Discount Factor的系数 γ 来控制。动态规划在这条学习路径上正好卡在最关键的位置它提供了一套在“模型已知”前提下精确求解最优策略的方法论。也就是说如果环境的状态转移概率 P(s|s,a) 和奖励函数 R(s,a) 都完全公开DP 就能直接算出每个状态的价值进而推出最优策略。这一点在深度强化学习里特别容易被忽略。深度学习那一套本质上是拿神经网络去拟合未知的映射关系。但“拟合”需要一个目标函数作为锚点而 DP 恰恰给出了强化学习里的最优目标函数——贝尔曼最优方程。没有这个锚点神经网络根本不知道自己要逼近什么。1.2 DP 思想在深度 RL 中的体现你可能会问“现在的算法不都是 DQN、PPO、SAC 这些吗哪里还有动态规划的影子”实际上每一次神经网络参数的更新背后都站着 DP 的身影。以最经典的 DQNDeep Q-Network为例。它的训练目标是让 Q 网络逼近真实的动作价值函数 Q(s,a)而训练时使用的目标值是[ r \gamma \max_{a} Q_{\text{target}}(s, a) ]这个式子不是凭空来的。它正是从贝尔曼最优方程拆出来的也就是动态规划里“价值迭代”的单步更新形式。DQN 做的不过是用一个神经网络替换掉 DP 里的价值函数表用大量采样的经验回放Experience Replay替换掉对完整状态空间的遍历。所以理解 DP你就能理解为什么 DQN 要把目标网络和评估网络分开为什么 TD时序差分误差那么重要为什么 γ 的取值会影响整个训练过程。这些东西在幼稚的阶段会被当成纯工程技巧但回过头看每一个设计都是在有限计算资源下对 DP 精确求解的一种妥协。1.3 经典方法并没有过时这些年经常有人讨论“动态规划是不是过时了”。我的看法是DP 作为独立算法确实很少直接被用在大规模深度强化学习任务里因为真实环境的模型状态转移概率基本是不可得的而且状态空间往往巨大到不可能逐个遍历。但 DP 的思想不是“过时”而是“内化”了。今天的强化学习研究者默认每个人都懂 DP论文里写“based on the Bellman equation”的时候不会费劲解释为什么目标值要那样构造。一个不懂 DP 的人去读强化学习论文就像不懂微积分的人去读物理每个公式都认识但连不成线。所以这篇文章的核心任务是把这条线画清楚。2. 先说清楚 MDP动态规划要解决的数学问题2.1 五元组与几个关键符号要聊 DP必须先明确它作用的载体——马尔可夫决策过程Markov Decision ProcessMDP。MDP 用一个五元组表示S状态集合所有可能的环境状态A动作集合每个状态下可执行的动作P状态转移概率P(s|s,a) 表示在状态 s 执行动作 a 后跳到状态 s 的概率R奖励函数R(s,a) 表示在状态 s 执行动作 a 后获得的即时奖励γ折扣因子取值通常在 [0,1] 之间注意这里的“马尔可夫”性质下一时刻的状态只取决于当前状态和当前动作与更早的历史无关。这个性质是 DP 能递归求解的数学前提。如果环境不是马尔可夫的dp 式的递推式根本站不住脚。强化学习领域经常用一个小型网格世界Grid World作为入门例子因为它直观智能体在一个格子地图上移动每个格子就是一个离散状态动作有上下左右四种地图上有障碍物和目标点。这个例子既有完整的 P 和 R 信息又足够简单适合把 DP 的每个步骤在代码里跑一遍。2.2 状态价值函数与动作价值函数MDP 定义了问题框架但真正要算的是“价值”。状态价值函数 V(s) 的定义是从状态 s 出发按照某个策略 π 行动所能获得的期望折扣回报总和[ V_\pi(s) \mathbb{E}_\pi [G_t | S_t s] ]其中 (G_t \sum_{k0}^{\infty} \gamma^k R_{tk1}) 是折扣回报。动作价值函数 Q(s,a) 的定义是在状态 s 先执行动作 a之后按照策略 π 行动所能获得的期望折扣回报总和[ Q_\pi(s,a) \mathbb{E}_\pi [G_t | S_t s, A_t a] ]V 和 Q 之间的关系是V 是对 Q 在动作维度上按策略概率求期望Q 则可以通过环境反馈转移到下一个状态的价值。这是后面所有 DP 算法推导的基础。2.3 贝尔曼方程递归的价值分解贝尔曼方程Bellman Equation是整个 DP 的心脏。它说的其实是一句大白话当前状态的价值等于当前即时奖励加上未来所有状态价值的折扣和。对于确定性策略 π状态价值函数的贝尔曼期望方程为[ V_\pi(s) \sum_{a} \pi(a|s) \sum_{s} P(s|s,a) [R(s,a) \gamma V_\pi(s)] ]再看贝尔曼最优方程它把“策略”这一步缩成了最大化[ V_(s) \max_{a} \sum_{s} P(s|s,a) [R(s,a) \gamma V_(s)] ]这两个式子的区别很关键期望方程是在给定策略下的“自洽”递归最优方程直接把“选择最优动作”这个操作融合进去了。DP 的三大经典方法本质上就是围绕这两个方程做迭代求解。提示贝尔曼方程是“递归”的这意味着一组状态的价值函数彼此依赖。理论上你可以列一个巨大的线性方程组直接解出来但状态一多就崩了。所以实际使用 DP 时几乎总是用迭代的方式逼近真实解。3. 三种核心 DP 方法的原理拆解3.1 策略评估固定策略下算价值第一种方法是策略评估Policy Evaluation目标是给定一个策略 π算出每个状态的 V(s)。方法很朴素——从一个全零的 V 向量出发反复套用贝尔曼期望方程去更新每个状态的价值直到变化量小于一个阈值[ V_{k1}(s) \sum_{a} \pi(a|s) \sum_{s} P(s|s,a) [R(s,a) \gamma V_k(s)] ]这个迭代为什么能收敛从数学角度看贝尔曼期望方程是一个压缩映射每次迭代都会让 V 向量朝真实解 V_π 逼近一定距离。直观理解是每一轮更新都让每个状态的价值往后多“看”了一步。第一轮更新后V 只包含了下一步远的奖励第二轮更新后V 包含了两步远的奖励迭代足够多轮V 就包含了几乎无限远处的奖励收敛自然发生。实际实现中收敛条件通常是两次迭代之间所有状态的最大差值小于一个小常数比如 1e-4。这个常数直接决定计算时间和精度之间的平衡太小会浪费算力太大则价值函数不够精确。3.2 策略迭代评估加改进交替滚动有了策略评估策略迭代Policy Iteration就顺理成章了。它把过程分成两步循环策略评估用当前策略 π迭代计算价值函数 V_π策略改进根据 V_π对每个状态贪心地选择使 Q 值最大的动作更新策略 π策略改进的理论依据是一个重要定理如果某个新策略 π 在每个状态选择的动作都是当前 Q 值最大的动作那么新策略的价值至少不差于旧策略即 V_π(s) ≥ V_π(s) 对所有状态成立。这个结果保证了迭代过程的单调性——策略只会越改越好不会退回更差的方案。策略迭代的收敛速度通常很快尤其在状态动作空间有限、模型精确的场景下。它的一个重要特点是策略评估部分本身也要做循环迭代所以整体时间由“评估的轮数”乘“评估内层的迭代次数”决定。如果策略评估收敛得很慢策略迭代就变得很慢。这也是后续所有加速技巧的出发点。3.3 价值迭代把评估和改进合并成一步价值迭代Value Iteration是策略迭代的优雅优化。它不再显式维护策略而是把策略改进的过程直接塞进价值更新的公式里[ V_{k1}(s) \max_{a} \sum_{s} P(s|s,a) [R(s,a) \gamma V_k(s)] ]你会发现这就是贝尔曼最优方程的迭代版。每一轮更新时它直接选当前状态下能让价值最大的动作然后更新价值。这个操作等于同时做了一步“评估”和一步“改进”。价值迭代的收敛速度在理论上比策略迭代慢一点但因为每一轮计算量更小在很多实际场景里总运行时间反而更快。而且价值迭代最终得到的 V 就是最优状态价值函数 V_策略可以从 V_中直接读出来。3.4 三种方法的对比与适用场景方法输入要求每轮计算复杂度收敛速度最终输出策略评估完整策略 πO(|S|²|A|)慢需要很多轮V_π策略迭代随机初始策略评估内层迭代 改进快通常 2-10 轮收敛最优策略 π_*价值迭代任意初始 VO(|S|²|A|)中等最优状态价值 V_* 与最优策略适用场景上如果你只关心某个特定策略的价值比如分析安全策略用策略评估就够了如果你要快速求出最优策略策略迭代通常更高效如果状态空间很大但动作空间相对简单价值迭代的简洁形式往往更容易实现和调试。注意上面表格里的复杂度是朴素实现的复杂度。实际工程里会利用稀疏转移矩阵、优先级队列、异步更新等手段大幅降低开销。初学者不要把表格里的复杂度当成“铁律”它只是理解算法相对成本的一个标尺。4. 用代码走一遍完整流程网格世界实操4.1 建模一个 4x4 的网格世界动手写代码之前模拟环境必须先搭好。我用一个非常经典的 4x4 网格世界左上角是起点右下角是目标点到达目标后获得奖励并终止每一步移动产生 -1 的惩罚奖励。状态空间大小为 16动作空间大小为 4上下左右。这个环境的好处是状态转移概率可以手动指定。我故意设置成“有风”的环境——执行某个动作时有 20% 的概率随机滑向相邻的非目标方向这样 P(s|s,a) 就不是一个确定性稀疏矩阵带上了一点随机性让 DP 的价值计算更有意义。import numpy as np GRID_SIZE 4 TERMINAL_STATE (3, 3) GAMMA 0.9 THETA 1e-4 # 动作映射0上1下2左3右 ACTIONS [(-1, 0), (1, 0), (0, -1), (0, 1)] NOISE_PROB 0.2 # 随机偏移概率 def step(state, action): 返回 (下一状态列表, 概率列表, 奖励) if state TERMINAL_STATE: return [state], [1.0], 0 r, c state dr, dc ACTIONS[action] nexts [] probs [] # 主方向 nr, nc r dr, c dc if 0 nr GRID_SIZE and 0 nc GRID_SIZE: nexts.append((nr, nc)) probs.append(1 - NOISE_PROB) else: nexts.append(state) probs.append(1 - NOISE_PROB) # 随机偏移方向简化为向左右偏移 for (dr2, dc2) in [(0, 1), (0, -1)]: nr, nc r dr2, c dc2 if 0 nr GRID_SIZE and 0 nc GRID_SIZE: nexts.append((nr, nc)) probs.append(NOISE_PROB / 2) else: nexts.append(state) probs.append(NOISE_PROB / 2) return nexts, probs, -1注意这里的奖励设置每个非终止状态移动一步都是 -1。这个设计不是为了难为智能体而是为了让策略倾向于用最少步数到达目标因为步数越少累计负奖励越小。4.2 策略评估的实现策略评估的代码很直观就是双层循环外层迭代价值函数内层枚举所有状态执行贝尔曼期望方程。def policy_evaluation(policy, V): 给定策略 policy16x4 的概率矩阵迭代评估状态价值 while True: delta 0.0 for r in range(GRID_SIZE): for c in range(GRID_SIZE): s (r, c) if s TERMINAL_STATE: continue v_new 0.0 for a_idx, prob_a in enumerate(policy[r * GRID_SIZE c]): if prob_a 0: continue nexts, probs, reward step(s, a_idx) v_new prob_a * sum( p * (reward GAMMA * V[nr * GRID_SIZE nc]) for (nr, nc), p in zip(nexts, probs) ) delta max(delta, abs(v_new - V[r * GRID_SIZE c])) V[r * GRID_SIZE c] v_new if delta THETA: break return V这段代码最核心的点在于它利用上一轮迭代得到的 V 值来计算当前状态的新价值然后同步更新。很多初学者会问“为什么不用更新后的值再往后算一步”其实同步更新可以保证收敛过程中的单调性和稳定性异步更新也可以收敛但顺序会影响结果的走向。4.3 策略迭代的完整过程策略迭代把评估和改进串起来。改进步骤里我们需要从状态价值 V 算出每个动作的 Q 值然后对每个状态选 Q 值最大的动作def policy_improvement(policy, V): 基于当前价值函数贪心改进策略 new_policy np.zeros_like(policy) for r in range(GRID_SIZE): for c in range(GRID_SIZE): s (r, c) if s TERMINAL_STATE: new_policy[r * GRID_SIZE c, 0] 1.0 continue q_values [] for a_idx in range(4): nexts, probs, reward step(s, a_idx) q_value sum( p * (reward GAMMA * V[nr * GRID_SIZE nc]) for (nr, nc), p in zip(nexts, probs) ) q_values.append(q_value) best_action int(np.argmax(q_values)) new_policy[r * GRID_SIZE c, best_action] 1.0 return new_policy def policy_iteration(): V np.zeros(GRID_SIZE * GRID_SIZE) policy np.ones((GRID_SIZE * GRID_SIZE, 4)) / 4.0 # 初始随机策略 while True: V policy_evaluation(policy, V) new_policy policy_improvement(policy, V) if np.array_equal(new_policy, policy): break policy new_policy return policy, V这里判断策略是否稳定的条件是“两次策略完全相同”。因为策略改进步骤是确定性的贪心操作只要策略不再变化说明任何状态下的贪心动作就是旧策略的动作策略已收敛到最优。实际跑一遍你会发现策略迭代在 4x4 网格上收敛得非常快大概 4 轮左右就结束了。原因是策略空间相对于价值空间小得多——16 个状态每个状态最多 4 个动作选择策略从随机到最优只需要有限几步“修正”。这种快速收敛也是策略迭代备受喜爱的原因。4.4 价值迭代的完整过程价值迭代代码更短因为少了一个显式的策略维护def value_iteration(): V np.zeros(GRID_SIZE * GRID_SIZE) while True: delta 0.0 for r in range(GRID_SIZE): for c in range(GRID_SIZE): s (r, c) if s TERMINAL_STATE: continue q_values [] for a_idx in range(4): nexts, probs, reward step(s, a_idx) q_value sum( p * (reward GAMMA * V[nr * GRID_SIZE nc]) for (nr, nc), p in zip(nexts, probs) ) q_values.append(q_value) v_new max(q_values) delta max(delta, abs(v_new - V[r * GRID_SIZE c])) V[r * GRID_SIZE c] v_new if delta THETA: break # 从最优价值函数读策略 policy np.zeros((GRID_SIZE * GRID_SIZE, 4)) for r in range(GRID_SIZE): for c in range(GRID_SIZE): s (r, c) if s TERMINAL_STATE: policy[r * GRID_SIZE c, 0] 1.0 continue q_values [] for a_idx in range(4): nexts, probs, reward step(s, a_idx) q_value sum( p * (reward GAMMA * V[nr * GRID_SIZE nc]) for (nr, nc), p in zip(nexts, probs) ) q_values.append(q_value) best_action int(np.argmax(q_values)) policy[r * GRID_SIZE c, best_action] 1.0 return policy, V这段代码的收敛条件还是 delta 小于一个阈值。但你会发现价值迭代需要的迭代轮数比策略评估多因为从随机初始化价值出发需要更多轮才能“传播”足够远的奖励信息。尤其是在网格世界里目标点在最右下角信息从目标点向所有方向扩散是需要步数支撑的这就是所谓的“奖励传播速度”问题。这个现象在深度强化学习里也很常见稀疏奖励环境下TD 误差传播慢训练就会很慢。DP 把这个机制用最朴素的方式展示出来了。5. 动态规划与深度强化学习的衔接点5.1 DQN 里的贝尔曼更新就是一步价值迭代现在再回头看 DQN。它的损失函数是[ L(\theta) \mathbb{E}{(s,a,r,s) \sim D} \left[ (r \gamma \max{a} Q_{\theta^-}(s,a) - Q_\theta(s,a))^2 \right] ]其中 θ 是主网络参数θ⁻ 是目标网络参数D 是经验回放池。这里的目标值 (y r \gamma \max_{a} Q_{\theta^-}(s,a)) 和 DP 价值迭代的更新式如出一辙。区别只在于价值迭代在更新时用的是“查表”的精确 V 值DQN 用的是一对样本的“估计值”。所以 DQN 本质上是价值迭代的“采样版”——用有限样本的均值近似真实期望。理解了这一点你就能解释为什么 DQN 需要目标网络目标网络其实是在“冻结”一个旧价值函数作为引导用来计算目标值。如果不用目标网络每次更新梯度时目标值也在变化训练过程会像“追自己的尾巴”很容易发散。这个设计本质上是为采样化的价值迭代加了一层稳定性保证。5.2 为什么深度 RL 不能直接全用 DP既然 DQN 跟价值迭代这么像为什么我们不直接用价值迭代的思路一步到位算清所有状态的价值原因有两个一是模型不可知。真实环境里P(s|s,a) 基本拿不到。机器人控制、棋类博弈、自动驾驶哪个环境能给你精确的转移概率DP 要求完整的数学模型这在大多数现实任务里不成立。所以深度强化学习把 DP 的“全状态遍历”换成了“经验采样”用数据驱动的方式去近似贝尔曼方程的解。二是状态空间巨大。图像输入、连续状态、高维动作都让“遍历所有状态”变得荒谬。围棋的状态数量远超宇宙原子总数遍历无从谈起。深度学习在这里的价值是“泛化”——用有限的参数表示覆盖庞大的状态空间近似地拟合价值函数。神经网络就是一台可微分的函数逼近器替代了 DP 里的查表操作。5.3 从 DP 到深度 RL 的学习路线建议我的亲身经历是先彻底搞懂 DP 再碰 DQN学习曲线会平滑很多。建议按这个顺序走手写一遍策略评估和价值迭代跑通网格世界把价值迭代改写成一版表格版 Q-learning验证两者结果是否一致再上手 DQN 源码重点关注目标网络和损失计算部分尝试把网格世界的价值迭代扩展成连续状态版本体会函数逼近带来的变量很多人在第二步就会恍然大悟——Q-learning 的更新式 (Q(s,a) \leftarrow Q(s,a) \alpha [r \gamma \max_{a} Q(s,a) - Q(s,a)]) 其实就是价值迭代在“不知道转移概率、只能用实际采样替代期望”时的自然延伸。α 是学习率取代了 DP 里的“全量更新”。6. 常见问题与避坑记录6.1 收敛慢是阈值设得太小了我最初跑策略评估时把收敛阈值 THETA 设成了 1e-8结果迭代了上千轮还没停。后来才发现阈值过小会导致算法在浮点精度附近反复震荡白白浪费算力。实践经验一般设 1e-4 就够用了。如果你的最终目标是策略而不是价值函数本身甚至可以设到 1e-3因为价值的小误差不会影响贪心动作的选择。6.2 状态遍历顺序影响结果同步更新和异步更新在代码里差异很大。同步更新用上一轮的 V 值计算新值收敛更稳定但每轮需要保存一份旧 V 副本内存开销大。异步更新就地更新收敛更快但顺序会引入轻微累积偏差可能让最终价值有一点偏移。网格世界里两种方式都能跑但到了大规模环境异步更新几乎是唯一选择。工程上常用优先级队列控制更新顺序让误差大的状态优先更新这就是优先级经验回放Prioritized Experience Replay的思想雏形。6.3 奖励设计对 DP 结果的影响网格世界的每一步 -1 惩罚会让智能体倾向于最短路径。如果我改成每一步 0 奖励、终点设 1结果会相似但如果终点奖励是 1沿途没有惩罚智能体就可能走出“绕路”策略。这个现象在 DP 里尤其明显因为价值函数高度依赖奖励设置。到了深度强化学习里奖励工程Reward Shaping就成了一门重要的手艺。我总结过一条经验先在一个简单环境里用 DP 验证奖励设计的合理性再去跑深度算法能省下大量调参时间。6.4 常见问题速查表问题表现可能原因解决建议迭代迟迟不收敛收敛阈值太小增大 THETA 至 1e-4价值函数震荡不降折扣因子 γ 太大试着降低 γ 到 0.8 观察变化策略改进时 Q 值重复计算状态动作空间大把 step 的结果缓存下来避免重复调用最终策略绕路奖励设计问题调整非终止状态的惩罚或终点奖励与 Q-learning 结果不一致没有正确实现同步更新检查每轮更新是否使用了旧 V 副本7. 实操总结与个人体会网格世界这套 DP 代码我前前后后跑过很多次。每次重写都有新的体会因为 DP 的每一行代码背后都拴着强化学习的核心概念。写策略评估时你对“价值传播”会有直观感觉——目标点附近的格子先变“亮”然后一点点往外“照亮”。写价值迭代时你会惊讶于“贪心更新居然能自己收敛到全局最优”。这种从“看懂”到“跑通”再到“体会到”的递进是任何论文公式都给不了的。最后分享一个小技巧当你需要调试一套新的深度强化学习算法时先造一个小的、模型已知的环境比如这个 4x4 网格用 DP 算出真实最优 V 和 Q 值。然后拿你的深度算法去学对比它的估计值和真实值的差距。这个方法能帮你快速定位 bug 出在采样、网络结构还是目标函数上比直接甩一个大环境去盲跑高效得多。这就是 DP 的魅力——它既是强化学习的数学基石也是一面照妖镜能照出你对公式理解的一切含混之处。希望这篇文章能帮你少走几步弯路。