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

1. 从“查表”说起：动态规划法到底在强化学习里扮演什么角色

很多人第一次接触强化学习，脑子里浮现的都是神经网络、梯度下降、各种花哨的策略网络。但如果你把时间倒回几十年前，强化学习最核心的那套数学骨架，其实是用动态规划搭起来的。我刚开始学的时候也犯过这个毛病，觉得动态规划太“古典”，不如直接上深度Q网络来得痛快。后来踩了几次坑才明白，不理解动态规划，你连Q-learning里那个贝尔曼更新公式是怎么来的都说不清楚。

动态规划法在强化学习里的定位，说白了就是在已知环境完整模型的前提下，通过迭代的方式精确求解最优策略。这里的“已知环境完整模型”是关键——你得知道状态转移概率和奖励函数长什么样。这在实际问题里往往不成立，但它是理解后续所有无模型方法的基石。

打个比方，动态规划就像你手里有一张完整的地图，上面标好了每条路的长度和通往哪里，你要做的就是反复计算从每个路口到终点的最短路径。而像Q-learning这类无模型方法，相当于你被扔进迷宫，只能靠走一步看一步来摸索。前者是“上帝视角”，后者是“盲人摸象”。但恰恰是有了上帝视角的精确解，你才能验证后面那些摸索方法到底靠不靠谱。

这篇文章我会把动态规划法在强化学习里的两个核心算法——策略迭代和价值迭代——从原理到代码实现完整拆一遍。适合已经了解马尔可夫决策过程基本概念、但还没真正动手写过动态规划求解的读者。如果你连状态、动作、奖励、折扣因子这些词都还陌生，建议先补一下MDP的基础，不然往下看会有点吃力。

2. 核心思路拆解：为什么偏偏是“动态规划”

2.1 动态规划的两个前提条件

动态规划不是随便什么优化问题都能用的，它有两个硬性前提。第一个是最优子结构，也就是说一个问题的最优解可以由其子问题的最优解构造出来。在强化学习里，这体现为贝尔曼最优方程：一个状态的最优价值等于从该状态出发，选一个动作后得到的即时奖励加上折扣后的下一状态最优价值的期望，再对所有动作取最大。这个递归结构就是最优子结构的直接体现。

第二个是重叠子问题。如果子问题之间互相独立、不重复，那分治就够了，用不着动态规划。强化学习里，同一个状态可能从很多不同的路径到达，如果每次都重新计算它的价值，计算量会爆炸。动态规划的做法是把每个状态的价值存下来，算过一次就不再重复算，这就是“查表”的思路。

我见过不少初学者写代码时犯一个错误：在策略评估的循环里，每更新一个状态的价值就立刻用新值去更新下一个状态。这其实变成了异步更新，虽然在某些情况下也能收敛，但和标准动态规划的同步更新语义不同，分析起来会复杂很多。标准做法是维护两份价值表，一份是旧的，一份是新的，每轮迭代用旧表算新表，算完再整体替换。

2.2 策略迭代和价值迭代的分野

动态规划法在强化学习里有两个经典变体，它们的核心区别在于策略评估和价值更新是否交替进行。

策略迭代的思路很直白：先固定一个策略，把它到底有多好算清楚（策略评估），然后基于算出来的价值，在每个状态选那个能让你拿到最高价值的动作（策略改进）。改进完再评估，评估完再改进，如此反复，直到策略不再变化。这就像你先按一套菜谱做菜，尝一口觉得咸了，调整盐量，再尝一口，再调整，直到味道满意为止。

价值迭代则更“激进”一些。它不等到策略评估完全收敛，而是每轮只做一次贝尔曼最优更新，直接把当前状态的价值替换为“选最优动作后能得到的价值”。你可以理解为它把策略评估和策略改进揉在了一起，每步都在同时做这两件事。价值迭代通常收敛更快，但每轮的计算量稍大，因为要对每个状态的所有动作取最大值。

那到底该用哪个？我的经验是：状态空间小、动作空间小的时候，两者差别不大，策略迭代的策略评估可以设一个较小的收敛阈值来加速；状态空间大的时候，价值迭代往往更省事，因为它不需要内层循环。但要注意，这里的“大”是相对的，动态规划本身只适用于状态空间有限且不太大的问题，状态一多，表格存不下，就得转向函数逼近的方法了。

2.3 折扣因子的作用与选择

折扣因子γ这个参数，很多人随手设个0.9或0.99就完事了，但它对动态规划的结果影响非常大。γ接近0时，智能体变得“短视”，只关心眼前的奖励；γ接近1时，智能体变得“远视”，愿意为了长远利益牺牲当下。

从数学上看，γ还决定了价值函数的取值范围。如果奖励的绝对值上界是R_max，那么价值的上界是R_max/(1-γ)。当γ=0.99时，这个上界是100倍的R_max；当γ=0.9时，上界是10倍。这意味着γ越大，价值数值越大，迭代收敛需要的轮数也越多。

我在实际项目中一般这样选：如果任务有明显的阶段性，比如走迷宫走到终点就结束，γ设0.9到0.95比较合适；如果是持续性的任务，没有明确终止状态，γ设0.99甚至更高。但γ太高会导致收敛慢，这时候可以配合价值迭代使用，因为价值迭代每轮都在做最优更新，收敛速度比策略迭代的内层循环快。

3. 核心细节解析与实操要点

3.1 策略评估的迭代公式与收敛判断

策略评估要做的事情是：给定策略π，计算每个状态的价值函数V_π(s)。迭代公式是：

V_{k+1}(s) = Σ_a π(a|s) Σ_{s'} P(s'|s,a) [R(s,a,s') + γ V_k(s')]

这个公式的意思是：状态s的价值等于，按照策略π选动作，每个动作带来的即时奖励加上折扣后的下一状态价值的期望，再对所有动作按策略概率加权求和。

收敛判断通常用最大价值变化量：max_s |V_{k+1}(s) - V_k(s)| < θ。θ一般设1e-6到1e-4之间。θ设太小，迭代轮数多，浪费时间；θ设太大，价值估计不准，影响后续策略改进。我一般先用1e-4跑一遍看看收敛轮数，如果轮数在几百以内，就调到1e-6再跑一次拿精确解。

这里有个实操细节：价值表的初始化。全零初始化是最简单的，但如果奖励都是正数，全零初始化会让第一轮迭代时所有状态的价值都偏低，收敛会慢一些。另一种做法是用一个乐观的初始值，比如用R_max/(1-γ)初始化，这样第一轮就能得到比较合理的估计。不过对于动态规划这种精确求解方法，初始化影响不大，因为最终都会收敛到同一个解，只是轮数差异。

3.2 策略改进的贪心选择与策略稳定性

策略改进的公式很简单：

π'(s) = argmax_a Σ_{s'} P(s'|s,a) [R(s,a,s') + γ V_π(s')]

也就是在每个状态，选那个能让你得到最高动作价值的动作。如果多个动作的价值相同，可以任选一个，或者保持原来的选择以维持策略稳定。

策略稳定性的判断是：如果改进后的策略π'和原策略π在每个状态上的动作选择都相同，说明策略已经收敛到最优。这里要注意，策略稳定和价值收敛不是一回事。有时候价值还没完全收敛，但策略已经不再变化了，这时候其实已经找到了最优策略，可以提前停止。我在代码里会同时检查这两个条件，只要策略稳定就跳出外层循环。

还有一个容易忽略的点：策略评估不需要完全收敛。理论上策略迭代要求策略评估收敛到V_π，但实际上做几次迭代得到的近似价值就足以支撑策略改进了。这种“截断策略迭代”在实践中往往更快，因为外层策略改进会纠正内层评估的误差。我一般把策略评估的收敛阈值设得比价值迭代松一些，比如1e-3，效果通常没问题。

3.3 价值迭代的贝尔曼最优更新

价值迭代的更新公式是：

V_{k+1}(s) = max_a Σ_{s'} P(s'|s,a) [R(s,a,s') + γ V_k(s')]

和策略评估的区别在于，这里没有对动作按策略概率加权，而是直接取最大值。这意味着价值迭代在每轮更新时，隐含地假设当前策略就是贪心策略，所以它同时完成了评估和改进。

价值迭代的收敛判断和策略评估一样，用最大价值变化量。收敛后，最优策略就是在每个状态选那个使动作价值最大的动作。

这里有个常见的坑：价值迭代的收敛速度受γ影响很大。γ=0.99时，可能需要几千轮迭代；γ=0.9时，几百轮就够了。如果发现迭代轮数太多，先检查γ是不是设得太高，再检查状态空间是不是太大。如果状态空间确实大，动态规划就不太适合了，得考虑其他方法。

3.4 同步更新与异步更新的取舍

标准动态规划用的是同步更新：每轮迭代用上一轮的价值表计算新的价值表，算完统一替换。这样做的好处是收敛性有理论保证，分析起来清晰。缺点是每轮需要存两份价值表，内存占用翻倍。

异步更新则是每算出一个状态的新价值就立刻写回价值表，后续状态的计算直接用新值。这样做收敛通常更快，因为新信息传播得更快，而且只需要一份价值表。但异步更新的收敛性分析更复杂，某些更新顺序可能导致震荡。

我在实际写代码时，如果状态空间不大（比如几千个状态），直接用同步更新，代码简单不易出错。如果状态空间上万，内存吃紧，就改用异步更新，但要注意更新顺序——一般按状态编号顺序更新就行，不要随机打乱，否则收敛判断会变得不稳定。

4. 实操过程与核心环节实现

4.1 环境设定：一个可以手算验证的小例子

为了把动态规划法讲透，我用一个经典的网格世界作为例子。这个例子足够简单，可以手算验证，又足够典型，能体现强化学习的核心概念。

网格世界是一个4x4的方格，左上角是起点，右下角是终点。智能体每步可以向上、下、左、右移动一格，不能移出边界。走到终点获得奖励+1，其他移动获得奖励-0.04（每走一步消耗一点能量）。折扣因子γ设为0.9。

这个环境的状态空间是16个格子（终点也算一个状态，到达后终止），动作空间是4个方向。状态转移概率是确定的：选一个方向，如果没撞墙就移动到相邻格子，撞墙就留在原地。

为什么选这个例子？因为它的状态转移和奖励都可以直接写成表格，不需要任何采样，完美符合动态规划“已知模型”的前提。而且16个状态手算也能算出来，方便验证代码的正确性。

4.2 用Python实现策略迭代

先定义环境的基本参数：

import numpy as np # 网格大小 ROWS, COLS = 4, 4 N_STATES = ROWS * COLS N_ACTIONS = 4 # 上、下、左、右 # 动作定义：上、下、左、右 ACTIONS = [(-1, 0), (1, 0), (0, -1), (0, 1)] # 奖励设置 STEP_REWARD = -0.04 GOAL_REWARD = 1.0 GAMMA = 0.9 # 终点状态 GOAL_STATE = N_STATES - 1 def state_to_pos(s): return s // COLS, s % COLS def pos_to_state(r, c): return r * COLS + c def is_valid(r, c): return 0 <= r < ROWS and 0 <= c < COLS

接下来构建状态转移和奖励表。因为环境是确定性的，每个状态-动作对只有一个下一状态和一个奖励：

def build_transition_and_reward(): P = np.zeros((N_STATES, N_ACTIONS, N_STATES)) R = np.zeros((N_STATES, N_ACTIONS)) for s in range(N_STATES): if s == GOAL_STATE: # 终点状态自循环，奖励为0 for a in range(N_ACTIONS): P[s, a, s] = 1.0 R[s, a] = 0.0 continue r, c = state_to_pos(s) for a, (dr, dc) in enumerate(ACTIONS): nr, nc = r + dr, c + dc if is_valid(nr, nc): ns = pos_to_state(nr, nc) else: ns = s # 撞墙留在原地 P[s, a, ns] = 1.0 if ns == GOAL_STATE: R[s, a] = GOAL_REWARD else: R[s, a] = STEP_REWARD return P, R

这段代码里有个细节：终点状态的处理。终点状态到达后任务结束，但在动态规划里我们仍然把它当作一个状态，给它一个自循环，奖励为0。这样价值迭代和策略评估的公式可以统一处理，不需要在循环里加特判。这是我在实际写代码时总结的一个小技巧，能让代码干净不少。

策略评估的实现：

def policy_evaluation(policy, P, R, theta=1e-6, max_iter=10000): V = np.zeros(N_STATES) for it in range(max_iter): delta = 0 V_new = np.zeros(N_STATES) for s in range(N_STATES): v = 0 for a in range(N_ACTIONS): if policy[s, a] == 0: continue # 确定性环境下，下一状态只有一个 ns = np.argmax(P[s, a]) v += policy[s, a] * (R[s, a] + GAMMA * V[ns]) V_new[s] = v delta = max(delta, abs(V_new[s] - V[s])) V = V_new if delta < theta: break return V

注意这里用了np.argmax(P[s, a])来取下一状态，因为确定性环境下转移概率只有一个1，其余都是0。如果是随机环境，这里应该改成对所有下一状态求和。

策略改进的实现：

def policy_improvement(V, P, R): policy = np.zeros((N_STATES, N_ACTIONS)) for s in range(N_STATES): action_values = np.zeros(N_ACTIONS) for a in range(N_ACTIONS): ns = np.argmax(P[s, a]) action_values[a] = R[s, a] + GAMMA * V[ns] best_action = np.argmax(action_values) policy[s, best_action] = 1.0 return policy

策略迭代的主循环：

def policy_iteration(P, R): # 初始策略：每个状态随机选一个动作 policy = np.zeros((N_STATES, N_ACTIONS)) for s in range(N_STATES): policy[s, np.random.randint(N_ACTIONS)] = 1.0 for it in range(100): V = policy_evaluation(policy, P, R) new_policy = policy_improvement(V, P, R) if np.array_equal(policy, new_policy): print(f"策略迭代在第 {it+1} 轮收敛") break policy = new_policy return policy, V

跑一遍这个代码，你会看到策略迭代大概在5到10轮就收敛了。收敛后打印每个状态的最优动作，应该能看到智能体从左上角一路指向右下角。

4.3 用Python实现价值迭代

价值迭代的代码更简洁，不需要内层的策略评估循环：

def value_iteration(P, R, theta=1e-6, max_iter=10000): V = np.zeros(N_STATES) for it in range(max_iter): delta = 0 V_new = np.zeros(N_STATES) for s in range(N_STATES): action_values = np.zeros(N_ACTIONS) for a in range(N_ACTIONS): ns = np.argmax(P[s, a]) action_values[a] = R[s, a] + GAMMA * V[ns] V_new[s] = np.max(action_values) delta = max(delta, abs(V_new[s] - V[s])) V = V_new if delta < theta: print(f"价值迭代在第 {it+1} 轮收敛") break # 从收敛的价值函数提取最优策略 policy = np.zeros((N_STATES, N_ACTIONS)) for s in range(N_STATES): action_values = np.zeros(N_ACTIONS) for a in range(N_ACTIONS): ns = np.argmax(P[s, a]) action_values[a] = R[s, a] + GAMMA * V[ns] policy[s, np.argmax(action_values)] = 1.0 return policy, V

价值迭代在这个例子上大概需要50到100轮收敛，比策略迭代的外层轮数多，但每轮计算量小，总时间其实差不多。你可以自己跑一下对比。

4.4 结果验证与可视化

跑完代码后，把最优价值函数打印成4x4的网格，你会看到从终点往起点方向价值逐渐降低，形成一个梯度。最优策略在每个格子上的箭头应该指向价值更高的相邻格子，最终汇聚到终点。

我建议你手动算一下起点状态的价值，和代码输出对比。起点在左上角，最优路径是向右走3步再向下走3步，共6步到达终点。每步奖励-0.04，最后一步奖励+1。折扣因子0.9，所以价值是：

-0.04 + 0.9*(-0.04) + 0.9^2*(-0.04) + ... + 0.9^5*(-0.04) + 0.9^6*1

算出来大概是0.59左右。如果你的代码输出接近这个值，说明实现是对的。

5. 常见问题与排查技巧实录

5.1 迭代不收敛或收敛到错误结果

这是最常见的问题，通常有以下几个原因。

第一，折扣因子设成了1或大于1。γ必须严格小于1，否则价值函数的无穷级数不收敛。我见过有人把γ设成1.0，然后发现价值迭代跑了几万轮还在震荡。检查一下你的γ参数。

第二，奖励函数设计有问题。如果所有状态的奖励都是正数，且没有终止状态，价值会无限增大。确保终点状态的奖励设置正确，且非终点状态的奖励不要太大。在我的例子里，每步-0.04是为了鼓励智能体尽快到达终点，如果设成+0.04，智能体就会故意绕路。

第三，收敛阈值设得太小。如果θ设成1e-10，浮点数精度可能不够，迭代永远达不到这个精度。一般1e-6就够了，再小没有意义。

第四，状态转移概率没有归一化。每行P(s,a,:)的和应该等于1。如果构建转移表时漏了某些情况，概率和不为1，价值更新就会出错。写个检查：assert np.allclose(P.sum(axis=2), 1.0)。

5.2 策略评估轮数过多

策略评估如果跑了几千轮还没收敛，先检查γ是不是太大。γ=0.99时，收敛轮数和1/(1-γ)成正比，大概需要几百到上千轮。如果γ=0.999，那就要上万轮了。

另一个原因是状态空间太大。动态规划的时间复杂度是O(N_states^2 * N_actions)每轮，状态数上万时，每轮就要几亿次运算，跑不动是正常的。这时候要么缩小状态空间，要么换用函数逼近的方法。

还有一个容易被忽略的点：策略评估不需要完全收敛。我通常把策略评估的θ设成1e-3，而不是1e-6。因为外层策略改进会纠正内层评估的误差，内层评估太精确反而浪费时间。实测下来，θ=1e-3和θ=1e-6得到的最终策略几乎一样，但前者快好几倍。

5.3 策略在多个动作之间震荡

如果发现策略迭代不收敛，每轮策略都在两个动作之间跳来跳去，通常是因为多个动作的价值非常接近，浮点数误差导致argmax的选择不稳定。

解决办法有两个。一是增加策略评估的精度，让价值估计更准确，减少误差。二是在策略改进时加入随机性，如果多个动作的价值在某个容差范围内，随机选一个，而不是严格取argmax。我一般用后者，容差设1e-8，效果不错。

还有一种情况是环境本身有对称性，比如网格世界里起点到终点有多条等长路径，这时候最优策略不唯一，策略在等价动作之间切换是正常的。只要价值函数收敛了，策略震荡不影响最终结果。

5.4 常见问题速查表

5.5 几个我踩过的坑

坑一：用异步更新时收敛判断失效。异步更新下，delta的计算不能用新旧价值表的差，因为旧值可能已经被覆盖了。正确做法是每更新一个状态，记录更新前后的差值，取所有差值的最大值。我一开始没注意这个，导致程序提前退出，策略根本没收敛。

坑二：终点状态的价值没有固定。在某些实现里，终点状态的价值应该固定为0（因为到达后不再有奖励），但如果你让它参与迭代，它会被更新成非零值，影响其他状态的价值计算。我的做法是在每次迭代后强制把终点状态的价值设回0。

坑三：动作编号和方向对应错误。这个听起来很蠢，但我确实犯过。动作0对应上，动作1对应下，结果在策略改进时把上下搞反了，策略看起来收敛了，但智能体在网格里原地打转。建议在代码里用常量定义动作，不要用魔法数字。

坑四：浮点数比较用==。判断策略是否稳定时，用np.array_equal比较两个策略数组。如果策略是概率分布，浮点数可能有微小误差，导致永远不相等。正确做法是用np.allclose或者比较argmax后的动作编号。

6. 从动态规划到更实用的方法：什么时候该换工具

动态规划法在强化学习里的地位，有点像汇编语言在编程里的地位——它是理解上层方法的基础，但实际项目中很少直接用。原因很简单：它要求已知环境模型，而这个条件在绝大多数真实问题里不成立。你不可能提前知道一个机器人每个动作会转移到什么状态，也不可能知道每次动作的精确奖励。

但动态规划的思想渗透到了几乎所有强化学习算法里。Q-learning的更新公式就是贝尔曼最优方程的无模型版本，只不过用采样代替了对所有下一状态的求和。策略梯度方法里的优势函数，本质上也是在估计动作价值。理解了动态规划，你看这些方法时会有一种“原来如此”的感觉。

那什么时候真的该用动态规划？我的经验是三种场景。第一种是问题本身就有精确模型，比如棋盘游戏、规划问题、资源分配问题，状态转移和奖励都可以精确计算。第二种是作为基准，当你实现了一个新的强化学习算法，想验证它是否正确时，可以先在一个小规模问题上用动态规划算出最优解，然后对比新算法的结果。第三种是状态空间很小的问题，比如几十个状态、几个动作，动态规划几秒钟就能算出精确解，没必要上神经网络。

如果状态空间超过几万个，或者环境模型未知，那就该考虑蒙特卡洛方法、时序差分学习或者函数逼近了。这些方法我在后续的文章里会逐一拆解，但前提是你先把动态规划这套骨架吃透。不然你调参的时候都不知道自己在调什么。

最后分享一个我常用的调试技巧：在动态规划代码里加一个手算验证的单元测试。选一个状态，手动算它的最优价值，和代码输出对比。如果对不上，说明转移表或者奖励函数有问题。这个习惯帮我省了很多排查时间，尤其是在环境比较复杂的时候。