动态规划在强化学习中的应用：策略迭代与价值迭代

如果你刚学完状态价值函数和贝尔曼方程，进入第4讲动态规划（Dynamic Programming，DP）的时候，通常会有一种明显的感觉：前面几讲都在搭概念框架，这一讲终于开始“算数”了。强化学习入门最容易卡住的位置，往往不是Q表，也不是策略梯度，恰恰就是这个动态规划。很多同学听完价值函数、折扣因子、贝尔曼期望方程之后，愣是不知道这些符号该怎么落到代码里；等到把动态规划这一套走通，回头再看那些公式，才会发现原来它们就是几行迭代循环。我带的强化学习课程里，第4讲的主题正好是这块。这一讲的定位很明确：把策略迭代和价值迭代两种经典算法讲透，同时让大家意识到，后面所有无模型强化学习算法，本质上都是从这个思路长出来的。

1. 动态规划在强化学习里到底在解什么问题

1.1 前几讲留下的“空中楼阁”

前面我们已经把强化学习建模成马尔可夫决策过程（MDP），一个MDP由状态集合、动作集合、奖励函数、状态转移概率和折扣因子组成。智能体做的事情就是维护一个策略，根据当前状态选择动作。而评价策略好坏的标准，是状态价值函数或者动作价值函数。

问题是，价值函数怎么算出来？理论上，如果我们完全知道状态转移概率和奖励函数，就可以列出关于每个状态价值的方程组：

v(s) = Σ π(a|s) Σ p(s', r | s, a) [r + γ v(s')]

这是一个包含N个未知数的方程组，N是状态数。状态少的时候，直接用线性代数工具求解就行。但状态一多，矩阵求逆的复杂度是O(N³)，根本扛不住。更重要的是，强化学习面对的状态空间往往大得惊人，一个简单的网格世界可能有几千个状态，更不用说连续控制问题。

动态规划提供的思路不是一次解出全部方程，而是“迭代地逼近”。先用一个猜测的价值函数起步，反复更新它，直到变化足够小。这个过程其实就是在解贝尔曼方程，只不过用的是数值迭代的方式。我课上经常用一个类比：这就像做菜时先放盐，尝一口，不够再加一点，来回调整，而不是一开始就精确称出所需的盐量。

1.2 一个反复使用的网格世界例子

要理解动态规划，最好有一个具体问题。我在课堂上每次都会用同一个例子：4×4的网格世界，一共16个格子，左上角是起点，右下角是终点。智能体每走一步，奖励是-1，到达终点则回合结束。对于非终点格子，智能体可以执行上、下、左、右四个动作，如果撞到边界，位置不变，但仍然得到-1的奖励。

在这个设定下，最优策略其实就是“以最短路径走到右下角”。因为每走一步都付出-1的代价，越短的路径累计奖励越大。这个例子虽然简单，却非常适合演示动态规划的每个环节：

• 状态价值函数是什么：每个格子的“未来累计奖励期望”。
• 策略评估是什么：给定一个策略，算出每个格子的价值。
• 策略改进是什么：比较不同动作的价值，选择更好的那个。
• 迭代收敛是什么：价值不再变化时，策略也稳定下来。

后面所有的推导和代码，都是围绕这个网格世界展开。别小看这种玩具问题，它就是强化学习算法调试的“hello world”。如果你的算法连这个确定性环境都跑不对，拿到真实环境里几乎必错。

2. 策略评估：给现有策略打一个准确的分

2.1 迭代式评估的思路

策略评估要解决的子问题是：给定一个策略π，计算每个状态的价值函数vπ(s)。计算公式就是贝尔曼期望方程，给定策略下，价值函数满足：

vπ(s) = Σ π(a|s) Σ p(s', r | s, a) [r + γ vπ(s')]

直接解这个方程组不方便，所以我们用迭代法。做法是这样的：

1. 初始化所有状态价值为0（或者任意值）。
2. 对每个状态，按照当前价值函数计算右侧的期望值，得到一轮新的价值。
3. 把新价值覆盖旧价值，重复步骤2。
4. 当新价值和旧价值的差距小于某个阈值时，停止。

公式写出来就是：

v_{k+1}(s) = Σ π(a|s) Σ p(s', r | s, a) [r + γ v_k(s')]

看起来简单，但其中有一个比较隐蔽的点：这是“期望”运算，是遍历所有动作和所有可能的下一状态，按概率加权求和。初学者最容易漏掉的就是动作概率π(a|s)。如果策略是确定性的，某个动作概率为1，其他为0，那求和自然就只剩一个动作。但策略并不一定是确定性的，比如随机策略中每个动作都有概率，这时候必须把所有动作价值的期望都算进去。

2.2 用网格世界看评估过程

假设初始策略是均匀随机策略：每个方向概率都是0.25。折扣因子γ取0.9。用上面这个迭代式跑几轮，价值函数的变化是这样的：

终点价值是0，因为它不会再有后续动作。离终点越近，价值衰减越慢，最终收敛值越接近0。起点距离终点远，需要付出的步数代价更大，价值更负。

这里有个很有意思的现象：价值从第一轮开始就是负的，随后慢慢往下沉，最终稳定。它不会出现波动，因为这是一个收缩映射，每次迭代都在缩短距离。实际调试的时候，如果你发现价值函数来回震荡不收敛，那大概率是更新式写错了，或者折扣因子设置有问题。

2.3 收敛判定怎么定才靠谱

实际操作中，不建议图省事设置一个固定的迭代次数就结束。更合理的做法是计算相邻两次迭代最大绝对差值，记作Δ，当Δ小于阈值θ时停止。θ设多少要看奖励尺度：如果奖励量级在个位数，θ设为1e-4通常很合适；如果奖励量级达到成百上千，θ需要相应缩放。

再补充一个细节：每次更新应该基于“上一轮的完整价值快照”，还是可以“就地覆写”？这在数学上对应同步迭代和异步迭代。同步迭代的安全性好，但需要额外保存一份上一轮的价值；异步迭代更省内存，收敛也常常更快，但价值更新的顺序会影响中间结果。入门阶段建议先用同步迭代，逻辑清晰不容易错。

3. 策略改进：算出分数后，怎么把策略升级

3.1 贪心动作真的更优吗

假设我们已经有了某个策略π的价值函数vπ，接下来要回答的问题是：在这个状态，是不是应该换一个动作？如果当前策略选择动作a，但另一个动作a'能带来更高的长期回报，那策略显然可以改进。

这里用到的核心工具是动作价值函数。对每个状态和动作，计算：

qπ(s, a) = Σ p(s', r | s, a) [r + γ vπ(s')]

直观地看，qπ(s, a)告诉你“如果我现在状态是s，先执行动作a，之后一直按策略π行动，最终能拿到多少回报”。如果某个动作的q值大于当前策略下状态价值的期望，那这个动作就比策略现在选择的动作更好。

这背后有严格的理论支撑，被称为策略改进定理：如果一个新策略在某些状态下选择了q值更高的动作，其他状态保持原策略不变，那么新策略的价值函数至少不低于旧策略。换句话说，“看到更好的选择就换过去”，这个操作永远不会让策略变差。

课上有同学问：那么贪心更新的策略会不会让价值反而降低？答案是单步不会，但它有可能在一个局部组合里打转。后面讲策略迭代的时候会看到，这种打转最终会被评估步骤修正。

3.2 改进操作的实操写法

对于确定性策略，改进的写法非常简单：遍历每个状态，计算所有动作的q值，取argmax作为新策略的动作。翻译成伪代码就是：

for s in all_states: best_action = None best_q = -inf for a in all_actions: q = sum_{s', r} p(s', r | s, a) * (r + gamma * V[s']) if q > best_q: best_q = q best_action = a pi_new[s] = best_action

实际操作中有一个容易犯的错误：状态如果是终止状态，不应该再做策略改进。终止状态本来就没有后续策略可言，对它做贪心更新会得到无意义的结果。代码里必须显式跳过终止状态，或者给终止状态一个固定的吸收策略。

还有一个细节值得留意：如果两个动作的q值完全相同，argmax选哪个都行，不会影响最终价值。但如果使用浮点数，可能出现微小误差导致随机选择，这种情况不影响收敛，只是每次运行结果略微不同。

4. 策略迭代：评估与改进交替推进，直到稳定

4.1 两个步骤拼成一个完整算法

策略迭代这个名字听起来很高级，其实就是一个循环：先对当前策略做完整的策略评估，然后基于评估得到的价值函数做一次策略改进。改进之后，策略已经变了，价值函数不再是新策略的价值函数，于是再评估、再改进，直到策略不再变化。

流程可以写成：

1. 初始化一个随机策略π。
2. 策略评估：迭代贝尔曼期望方程，求出vπ。
3. 策略改进：对每个状态执行贪心更新，得到π'。
4. 如果π'和π相同，结束；否则回到步骤2。

这里有一个数学保证：评估-改进的循环单调提升价值，由于策略数量有限，迭代一定会收敛到最优策略。我学生会问：“既然评估要迭代很多轮，改进又要重来，这得跑多久？”实际上，对这个小网格世界，整个策略迭代收敛通常只需要几次外层循环，因为价值函数“猜”得不离谱时，改进后的策略很快就稳定了。

4.2 一份可以直接跑的网格世界代码

用Python实现时，我先定义环境数据，再写评估和改进两个函数。完整代码如下：

import numpy as np rows, cols = 4, 4 actions = [(0, -1), (0, 1), (1, 0), (-1, 0)] gamma = 0.9 theta = 1e-4 # 状态编号: 0..15, 按行优先 terminal = [15] rewards = -1 # 每步都是-1 def next_state(s, a): r, c = divmod(s, cols) nr, nc = r + a[0], c + a[1] if nr < 0 or nr >= rows or nc < 0 or nc >= cols: return s return nr * cols + nc def policy_evaluation(pi, V): while True: delta = 0 V_new = V.copy() for s in range(rows * cols): if s in terminal: continue total = 0.0 for a_idx, a in enumerate(actions): s_next = next_state(s, a) total += pi[s, a_idx] * (rewards + gamma * V[s_next]) V_new[s] = total delta = max(delta, abs(V_new[s] - V[s])) V = V_new if delta < theta: break return V def policy_improvement(pi): policy_stable = True for s in range(rows * cols): if s in terminal: continue q_values = [] for a in actions: s_next = next_state(s, a) q_values.append(rewards + gamma * V[s_next]) best_action = int(np.argmax(q_values)) if pi[s, best_action] != 1.0: policy_stable = False pi[s, :] = 0.0 pi[s, best_action] = 1.0 return pi, policy_stable # 初始化随机均匀策略 pi = np.ones((rows * cols, len(actions))) / len(actions) V = np.zeros(rows * cols) for it in range(20): V = policy_evaluation(pi, V) pi, stable = policy_improvement(pi) if stable: print(f"策略第{it+1}轮后收敛") break print("价值函数:") print(np.round(V, 2).reshape((rows, cols)))

跑出来的价值函数大致是：终点那一格为0，终点正上方那格为-1，左上角那一格为-5附近。策略会形成一条明确指向右下角的最短路径。这段代码我在课上会让每个人都敲一遍，因为它涵盖了一个完整强化学习控制算法的全部要素。

4.3 策略迭代和价值迭代的取舍

策略迭代的代价在“完整评估”这一步，价值迭代的代价在放大了评估次数但仍在使用最终价值。看起来策略迭代更“次少但贵”，价值迭代更“次多但便宜”。实际选择要考虑环境规模：

实践中没有一个绝对优胜的选择，两者都是入门必须掌握的。

5. 价值迭代：绕开策略评估，直接用最优贝尔曼方程迭代

5.1 一步到位的思想

如果最终目标是找到最优价值函数，那中间步骤中的“显式策略”其实可以省略。价值迭代的公式是：

v_{k+1}(s) = max_a Σ p(s', r | s, a) [r + γ v_k(s')]

对比策略评估的公式，区别只有一个：期望符号里的动作平均变成了对所有动作取最大值。这意味着每一轮都在假设“当前状态下我总会选择最优动作”，并把这个最优动作对应的价值作为新的估计。

这个公式的直接来源是贝尔曼最优方程：

v*(s) = max_a Σ p(s', r | s, a) [r + γ v*(s')]

价值迭代的做法就是把等式右侧的v*换成本轮估计值v_k，然后反复套用。从理论上看，它依然是收缩映射，所以价值会单调逼近最优价值函数。

5.2 价值迭代的代码和结果

价值迭代的一个直观好处是代码极短，前面的网格世界只需要这样写：

V = np.zeros(rows * cols) iters = 0 while True: delta = 0 for s in range(rows * cols): if s in terminal: continue q_values = [rewards + gamma * V[next_state(s, a)] for a in actions] best_value = max(q_values) delta = max(delta, abs(best_value - V[s])) V[s] = best_value iters += 1 if delta < theta: break print(f"迭代{iters}轮后收敛") print(np.round(V, 2).reshape((rows, cols)))

跑起来之后，价值函数结果和策略迭代收敛到相同的结果。区别在于，这里从头到尾没有显式的策略变量，策略是在需要执行时才临时从价值函数推导出来：每次都选q值最大的动作。

5.3 价值迭代和策略迭代的深层联系

有同学会问：策略迭代不是也要先做评估，再做改进，价值迭代似乎完全绕过了评估，两者真的等价吗？

实际上，价值迭代可以理解为一种“截断策略迭代”：只做一轮策略评估就立刻做策略改进，然后再评估，再改进。如果用公式展开，价值迭代更新里的max操作，本身就是在“评估了一个策略”之后立刻“改进”的结果。因此它的每轮计算量比完整评估小得多，但震荡也可能更明显。

理解这个联系的价值在于，你不需要把两种算法当独立知识背下来，只要抓住“评估-改进”的GPI框架，所有变体都能归位。

6. 广义策略迭代：动态规划的真正核心

6.1 两条竞争线

广义策略迭代（GPI，Generalized Policy Iteration）描述的是策略评估和策略改进同时进行的过程：

• 策略评估一条线，不断把价值函数拉向当前策略的真实价值。
• 策略改进一条线，不断把策略推向当前价值函数下的贪心策略。

这两个过程互相依赖：策略变化后，价值函数不再匹配；价值函数更新后，策略又有可能变化。看起来像是两个人互相纠正，最终会稳定在最优策略和最优价值函数的交点。

我用一个生活类比：学开车的过程。评估线相当于你不断通过后视镜和反馈判断自己开得怎么样，改进线相当于根据判断调整方向盘。刚开始手忙脚乱，但每一次调整都让判断更准，判断更准又反过来帮助调整，最终形成稳定的驾驶策略。

6.2 无模型算法为什么也跳不出这个框架

动态规划要求已知转移概率和奖励函数。但大多数真实问题没有这个模型，只有与环境交互得到的样本。于是后来的蒙特卡洛方法、时序差分方法，做的事情其实都一样：

• 蒙特卡洛：用一整条回合的累计回报来估计价值，替代策略评估。
• 时序差分：用下一步的奖励加估计价值来更新当前价值，同样在做评估。
• Q-learning：直接用max操作更新Q值，本质上就是价值迭代的无模型采样版。
• SARSA：用策略自身的下一个动作更新Q值，本质上是策略评估的无模型采样版。

所以当你理解了动态规划的GPI框架，再去看这些算法，会发现它们只是把“期望计算”替换成了“采样计算”，骨架完全没变。很多初学者觉得后面内容难，是因为没把第4讲吃透；这一讲才是整个课程的地基。

7. 实现动态规划时的几个务实细节

7.1 同步更新和异步更新的实践选择

同步迭代容易理解，也容易写出正确代码。但状态空间一大，保存一份完整快照的额外开销可能不小。异步迭代（也叫就地迭代）不保留快照，直接更新当前状态的价值，后面的状态计算会用到刚刚更新的值。

异步迭代通常收敛更快，但结果对遍历顺序敏感。一个常见的可靠方案是“按状态编号顺序遍历”，简单且稳定。更高级的做法是优先扫描（prioritized sweeping），优先更新价值变化幅度大的状态。优先扫描在动态规划课程里提得少，但实际工程中很常见，它可以把计算集中到真正的“热点区域”。

7.2 折扣因子的影响

γ越接近1，智能体越“有远见”，价值函数的绝对数值也越大，收敛需要的轮数越多。当γ=1并且存在无限长轨迹时，价值可能发散。所以在练习环境里，γ取0.9到0.99非常常见。

有一个数学结论值得记住：如果奖励R_max有界，且γ<1，那么贝尔曼迭代的误差上界是γ乘以上一轮误差。这意味着γ越接近1，收敛越慢；γ越小，迭代跑得越快，但视野越短。做实验时如果发现调试参数老不收敛，先检查γ。

7.3 从表格走向函数近似

动态规划的价值函数可以做成一张表，但真实问题的状态空间往往是连续的或者维度极高。于是我们开始用神经网络表示价值函数，更新方式变成监督学习式的拟合。这正是深度强化学习的起点。但无论网络多复杂，它仍然需要一个评估信号，这个信号要么来自模型推导，要么来自采样。动态规划里的贝尔曼迭代，就是那个“评估信号”的数学基础。

8. 初学调试记录与避坑速查

8.1 常见问题速查表

8.2 两个值得养成的调试习惯

第一个习惯是“人工单步验证”：跑完一轮迭代之后，随机挑一个状态，用公式手算一遍贝尔曼期望值，和程序输出对比。只要有一个状态对不上，就能迅速发现是奖励项写错了、转移函数错了，还是折扣计算错了。大多数时候都是这些低级错误。

第二个习惯是“画一条收敛曲线”：记录每一轮的最大差值Δ，画出来。正常情况曲线单调下降且趋于平稳；如果曲线波动，说明更新逻辑有问题；如果曲线突然跳高再降下来，可能是某个状态的终止条件没处理好。这个习惯在之后规模更大的实验里也很有用。

8.3 建议动手练的三个层次

• 第一层：把本文的网格世界代码自己敲一遍，改变起点终点位置，观察价值函数的变化。
• 第二层：把环境改成带随机风的环境，让转移概率变成0.7/0.3，重新跑策略迭代，比较收敛轮数。
• 第三层：把网格扩大到10×10，对比同步迭代和异步迭代的时间差异，找一找哪种遍历顺序收敛最快。

我在实际带课中的体会是，动态规划这一讲的代码量虽然不多，却是整门课程里唯一能看到完整数学公式变成可运行程序的阶段。后面无模型算法引入采样噪声之后，很多问题反而不容易看清。所以每次有同学说强化学习难，我都会建议他们先把这里的每一个状态价值手算一遍，再把代码跑通一遍。这个过程做完，后面学Q-learning和策略梯度的时候，你会发现自己已经站在一个很稳的地基上。