动态规划（Dynamic Programming, DP）是强化学习中最基础、最重要的理论工具之一。它通过利用马尔可夫决策过程（MDP）的结构化性质——最优子结构和重叠子问题——来高效求解最优策略。虽然经典的动态规划方法要求已知环境的完整模型（即转移概率 P ( s ′ ∣ s , a ) P ( s ′ ∣ s , a ) R ( s , a ) R ( s , a ) 通过自举（bootstrapping）迭代地改进值函数估计 ——深刻影响了后续所有的无模型强化学习算法。
本文将系统阐述基于动态规划的强化学习方法，包括策略评估、策略改进、策略迭代、值迭代和广义策略迭代，并通过数值例子和对比分析帮助理解其原理与适用场景。
考虑一个折扣马尔可夫决策过程 M = ⟨ S , A , P , R , γ ⟩ M = ⟨ S , A , P , R , γ ⟩
S S ∣ S ∣ = n ∣ S ∣ = n A A ∣ A ∣ = m ∣ A ∣ = m P ( s ′ ∣ s , a ) P ( s ′ ∣ s , a ) s s a a s ′ s ′ R ( s , a ) R ( s , a ) γ ∈ [ 0 , 1 ) γ ∈ [ 0 , 1 )
我们的目标是找到一个策略 π : S → Δ ( A ) π : S → Δ ( A )
V π ( s ) = E π [ ∑ t = 0 ∞ γ t R ( s t , a t ) | s 0 = s ] V π ( s ) = E π [ t = 0 ∑ ∞ γ t R ( s t , a t ) s 0 = s ]
动态规划之所以能够高效求解这个问题，依赖于 MDP 的如下两个关键性质：
性质
描述
数学表达
最优子结构 最优策略的子策略也是最优的
贝尔曼最优方程
重叠子问题 不同状态的值函数共享相同的底层递归结构
V ( s ) V ( s ) V ( s ′ ) V ( s ′ )
正是这两个性质使得我们可以将复杂的全局最优问题分解为一组相互关联的、更简单的子问题，并通过迭代求解。
策略评估（Policy Evaluation）也称为预测问题 ：给定一个确定性或随机性策略 π π V π V π
对于策略 π π
V π ( s ) = E π [ R ( s , a ) + γ ∑ s ′ P ( s ′ ∣ s , a ) V π ( s ′ ) ] , ∀ s ∈ S V π ( s ) = E π [ R ( s , a ) + γ s ′ ∑ P ( s ′ ∣ s , a ) V π ( s ′ ) ] , ∀ s ∈ S
将期望展开，可以写成更具体的形式：
V π ( s ) = ∑ a ∈ A π ( a ∣ s ) [ R ( s , a ) + γ ∑ s ′ ∈ S P ( s ′ ∣ s , a ) V π ( s ′ ) ] V π ( s ) = a ∈ A ∑ π ( a ∣ s ) [ R ( s , a ) + γ s ′ ∈ S ∑ P ( s ′ ∣ s , a ) V π ( s ′ ) ]
这是一个关于 V π V π n n O ( n 3 ) O ( n 3 ) 迭代方法 ：从一个任意的初始估计 V 0 V 0 T π T π
V k + 1 ( s ) = ∑ a π ( a ∣ s ) [ R ( s , a ) + γ ∑ s ′ P ( s ′ ∣ s , a ) V k ( s ′ ) ] , ∀ s V k + 1 ( s ) = a ∑ π ( a ∣ s ) [ R ( s , a ) + γ s ′ ∑ P ( s ′ ∣ s , a ) V k ( s ′ ) ] , ∀ s
可以证明，贝尔曼算子 T π T π γ γ { V k } { V k } V π V π
环境设定 ：设在一个 3 × 3 3 × 3 γ = 0.9 γ = 0.9 随机策略 （每个动作等概率 0.25）。为简化，假设动作是确定性的（100% 执行成功）。
状态编号
位置
类型
转移
奖励
0
(0,0)
起点
上:0, 下:3, 左:0, 右:1
0
1
(0,1)
普通
上:1, 下:4, 左:0, 右:2
0
2
(0,2)
冰洞
任意 → 终止
-1
3
(1,0)
普通
上:0, 下:6, 左:3, 右:4
0
4
(1,1)
普通
上:1, 下:7, 左:3, 右:5
0
5
(1,2)
普通
上:2, 下:8, 左:4, 右:5
0
6
(2,0)
普通
上:3, 下:6, 左:6, 右:7
0
7
(2,1)
普通
上:4, 下:7, 左:6, 右:8
0
8
(2,2)
目标
任意 → 终止
+1
初始值函数 V 0 ( s ) = 0 V 0 ( s ) = 0
第 1 次迭代 V 1 V 1
对于每个状态（非终止态），V 1 ( s ) = ∑ a 1 4 [ 0 + 0.9 × V 0 ( s ′ ) ] = 0 V 1 ( s ) = ∑ a 4 1 [ 0 + 0.9 × V 0 ( s ′ )] = 0
State
V 1 V 1 State
V 1 V 1
0
0.00
4
0.00
1
0.00
5
0.00
2
-1.00
6
0.00
3
0.00
7
0.00
8
1.00
第 2 次迭代 V 2 V 2
以状态 5 为例：V 2 ( 5 ) = 0.25 [ 0 + 0.9 × V 1 ( 2 ) ] + 0.25 [ 0 + 0.9 × V 1 ( 8 ) ] + 0.25 [ 0 + 0.9 × V 1 ( 4 ) ] + 0.25 [ 0 + 0.9 × V 1 ( 5 ) ] V 2 ( 5 ) = 0.25 [ 0 + 0.9 × V 1 ( 2 )] + 0.25 [ 0 + 0.9 × V 1 ( 8 )] + 0.25 [ 0 + 0.9 × V 1 ( 4 )] + 0.25 [ 0 + 0.9 × V 1 ( 5 )]
= 0.25 × 0.9 × ( − 1 ) + 0.25 × 0.9 × 1 + 0.25 × 0.9 × 0 + 0.25 × 0.9 × 0 = 0.25 × 0.9 × ( − 1 ) + 0.25 × 0.9 × 1 + 0.25 × 0.9 × 0 + 0.25 × 0.9 × 0
= 0.25 × ( − 0.9 ) + 0.25 × 0.9 + 0 + 0 = 0.00 = 0.25 × ( − 0.9 ) + 0.25 × 0.9 + 0 + 0 = 0.00
以状态 8 为例（目标状态，吸收态）：V 2 ( 8 ) = 1 V 2 ( 8 ) = 1
以状态 2 为例（冰洞，终止态）：V 2 ( 2 ) = − 1 V 2 ( 2 ) = − 1
在 V 2 V 2
完整迭代过程展示 （仅几个代表性状态）：
迭代 k
V k ( 0 ) V k ( 0 ) V k ( 3 ) V k ( 3 ) V k ( 5 ) V k ( 5 ) V k ( 7 ) V k ( 7 ) V k ( 8 ) V k ( 8 )
0
0.000
0.000
0.000
0.000
1.000
1
0.000
0.000
0.000
0.000
1.000
2
0.000
0.000
0.000
0.225
1.000
5
0.030
0.068
0.152
0.405
1.000
10
0.076
0.156
0.302
0.546
1.000
20
0.100
0.200
0.372
0.623
1.000
50
0.110
0.219
0.403
0.662
1.000
∞ ∞ 0.111 0.222 0.407 0.667 1.000
收敛后的值函数显示：越靠近目标的状态（状态 7、5）值越高，而远离目标的状态（状态 0、3）值较低。这是合理的，因为随机策略下的路径越长，折扣累积奖励越低。
迭代策略评估的收敛速度取决于折扣因子 γ γ V π V π V k V k k k
∥ V k − V π ∥ ∞ ≤ γ k ∥ V 0 − V π ∥ ∞ ∥ V k − V π ∥ ∞ ≤ γ k ∥ V 0 − V π ∥ ∞
这意味着：
γ γ k = 10 k = 10 k = 50 k = 50 到 ϵ = 0.01 ϵ = 0.01
0.9
0.9 10 ≈ 0.349 0. 9 10 ≈ 0.349 0.9 50 ≈ 0.005 0. 9 50 ≈ 0.005 k ≥ log 0.01 log 0.9 ≈ 44 k ≥ l o g 0.9 l o g 0.01 ≈ 44
0.99
0.99 10 ≈ 0.904 0.9 9 10 ≈ 0.904 0.99 50 ≈ 0.605 0.9 9 50 ≈ 0.605 k ≥ log 0.01 log 0.99 ≈ 458 k ≥ l o g 0.99 l o g 0.01 ≈ 458
0.5
0.5 10 ≈ 0.001 0. 5 10 ≈ 0.001 0.5 50 ≈ 10 − 15 0. 5 50 ≈ 1 0 − 15 k ≥ log 0.01 log 0.5 ≈ 7 k ≥ l o g 0.5 l o g 0.01 ≈ 7
从上表可以看出，γ γ 长视野问题 （long-horizon problems）需要更多的迭代来让远处的奖励信息反向传播到起始状态。
实践中我们不会无限迭代，而是在值函数变化足够小时停止：
max s ∈ S ∣ V k + 1 ( s ) − V k ( s ) ∣ < ϵ s ∈ S max ∣ V k + 1 ( s ) − V k ( s ) ∣ < ϵ
其中 ϵ ϵ 10 − 3 1 0 − 3 10 − 6 1 0 − 6 ∥ V k − V π ∥ ∞ ≤ 2 ϵ γ 1 − γ ∥ V k − V π ∥ ∞ ≤ 1 − γ 2 ϵ γ
当我们获得当前策略 π π V π V π
策略改进定理 （Policy Improvement Theorem）：令 π π π ′ π ′ s ∈ S s ∈ S
Q π ( s , π ′ ( s ) ) ≥ V π ( s ) Q π ( s , π ′ ( s )) ≥ V π ( s )
则 π ′ π ′ π π s s V π ′ ( s ) ≥ V π ( s ) V π ′ ( s ) ≥ V π ( s ) V π ′ ( s ) > V π ( s ) V π ′ ( s ) > V π ( s )
这个定理为策略改进提供了理论基础：我们可以通过贪心地选择动作来构造更好的策略。
给定 V π V π π ′ π ′
π ′ ( s ) = Q π ( s , a ) = [ R ( s , a ) + γ ∑ s ′ P ( s ′ ∣ s , a ) V π ( s ′ ) ] π ′ ( s ) = a ∈ A arg max Q π ( s , a ) = a ∈ A arg max [ R ( s , a ) + γ s ′ ∑ P ( s ′ ∣ s , a ) V π ( s ′ ) ]
这个策略被称为 π π 贪心策略 （greedy policy）。策略改进定理保证了 π ′ ≥ π π ′ ≥ π
沿用上面的冰湖行走环境，假设随机策略 π random π random V π random V π random
状态 5 的四个动作选择：
动作
下一状态
R + γ V π ( s ′ ) R + γ V π ( s ′ ) 值
上 (up)
2 (冰洞)
− 1 + 0.9 × ( − 1.00 ) = − 1.90 − 1 + 0.9 × ( − 1.00 ) = − 1.90 -1.90
下 (down)
8 (目标)
1 + 0.9 × 1.00 = 1.90 1 + 0.9 × 1.00 = 1.90 1.90 ✅
左 (left)
4
0 + 0.9 × 0.37 = 0.33 0 + 0.9 × 0.37 = 0.33 0.33
右 (right)
5 (自身)
0 + 0.9 × 0.41 = 0.37 0 + 0.9 × 0.41 = 0.37 0.37
因此，π ′ ( 5 ) = down π ′ ( 5 ) = down
策略迭代（Policy Iteration）将策略评估和策略改进交替进行，形成一个单调改进的循环：
初始化 ：随机选择一个初始策略 π 0 π 0 策略评估 ：计算 V π k V π k 策略改进 ：构造 π k + 1 ( s ) = arg max a Q π k ( s , a ) π k + 1 ( s ) = arg max a Q π k ( s , a ) 终止检查 ：如果 π k + 1 = π k π k + 1 = π k s s π k π k
算法：策略迭代
─────────────────────────────────────────
输入：MDP M = ⟨S, A, P, R, γ⟩, 阈值 ε > 0
1. 初始化 π(s) ∈ A（随机），∀s
2. 重复直到收敛：
a. 策略评估（迭代法）：
V ← 0
重复直到 max_s|V_{new}(s) - V(s)| < ε:
对每个 s ∈ S:
V_{new}(s) ← Σ_a π(a|s)[R(s,a) + γ Σ_{s'} P(s'|s,a) V(s')]
V ← V_{new}
b. 策略改进：
policy_stable ← True
对每个 s ∈ S:
a_new ← argmax_a [R(s,a) + γ Σ_{s'} P(s'|s,a) V(s')]
如果 a_new ≠ π(s):
π(s) ← a_new
policy_stable ← False
如果 policy_stable = True:
返回 π（最优策略）
─────────────────────────────────────────
策略迭代具有如下重要性质：
单调性 ：每次迭代产生的策略 V π k + 1 ≥ V π k V π k + 1 ≥ V π k 有限收敛 ：对于有限 MDP（∣ S ∣ = n ∣ S ∣ = n ∣ A ∣ = m ∣ A ∣ = m m n m n 收敛速度 ：实际收敛通常非常快，通常只需要 3-10 次迭代即可达到最优策略，远少于 m n m n
特性
策略迭代
值迭代
每轮计算
策略评估（内层多次迭代）
单次贝尔曼最优更新
收敛步数
少（通常 3-10 轮）
多（通常数十到数百轮）
每轮成本
O ( ∣ S ∣ 2 ⋅ ∣ A ∣ ⋅ K 评估 ) O ( ∣ S ∣ 2 ⋅ ∣ A ∣ ⋅ K 评估 ) O ( ∣ S ∣ 2 ⋅ ∣ A ∣ ) O ( ∣ S ∣ 2 ⋅ ∣ A ∣ )
总成本
通常更低
通常更高
适用于
中等规模问题
大规模问题（可截断）
精确性
可达数值精度
截断误差可控
为了展示策略迭代的完整过程，考虑一个更简洁的 4 状态 MDP：
状态集合 S = { s 0 , s 1 , s 2 , s 3 } S = { s 0 , s 1 , s 2 , s 3 } s 3 s 3 { a 0 , a 1 } { a 0 , a 1 }
转移与奖励：
状态
动作
下一状态
概率
奖励
s 0 s 0 a 0 a 0 s 1 s 1 0.5
1
s 0 s 0 a 0 a 0 s 2 s 2 0.5
2
s 0 s 0 a 1 a 1 s 0 s 0 0.5
0
s 0 s 0 a 1 a 1 s 2 s 2 0.5
-1
s 1 s 1 a 0 a 0 s 3 s 3 1.0
10
s 1 s 1 a 1 a 1 s 1 s 1 0.5
0
s 1 s 1 a 1 a 1 s 2 s 2 0.5
3
s 2 s 2 a 0 a 0 s 0 s 0 1.0
5
s 2 s 2 a 0 a 0 s 3 s 3 0.0
-
s 2 s 2 a 1 a 1 s 3 s 3 1.0
1
γ = 0.9 γ = 0.9
第 1 轮策略评估 （初始策略 π 0 π 0 a 0 a 0
解线性方程组：
V ( s 0 ) = 0.5 [ 1 + 0.9 V ( s 1 ) ] + 0.5 [ 2 + 0.9 V ( s 2 ) ] V ( s 0 ) = 0.5 [ 1 + 0.9 V ( s 1 )] + 0.5 [ 2 + 0.9 V ( s 2 )] V ( s 1 ) = 1.0 [ 10 + 0.9 × 0 ] = 10 V ( s 1 ) = 1.0 [ 10 + 0.9 × 0 ] = 10 V ( s 2 ) = 1.0 [ 5 + 0.9 V ( s 0 ) ] V ( s 2 ) = 1.0 [ 5 + 0.9 V ( s 0 )] V ( s 3 ) = 0 V ( s 3 ) = 0
代入 V ( s 1 ) = 10 V ( s 1 ) = 10
V ( s 2 ) = 5 + 0.9 V ( s 0 ) V ( s 2 ) = 5 + 0.9 V ( s 0 ) V ( s 0 ) = 0.5 [ 1 + 9 ] + 0.5 [ 2 + 0.9 ( 5 + 0.9 V ( s 0 ) ) ] = 5 + 0.5 × [ 2 + 4.5 + 0.81 V ( s 0 ) ] = 5 + 3.25 + 0.405 V ( s 0 ) V ( s 0 ) = 0.5 [ 1 + 9 ] + 0.5 [ 2 + 0.9 ( 5 + 0.9 V ( s 0 ))] = 5 + 0.5 × [ 2 + 4.5 + 0.81 V ( s 0 )] = 5 + 3.25 + 0.405 V ( s 0 ) V ( s 0 ) = 8.25 + 0.405 V ( s 0 ) V ( s 0 ) = 8.25 + 0.405 V ( s 0 ) 0.595 V ( s 0 ) = 8.25 0.595 V ( s 0 ) = 8.25 V ( s 0 ) ≈ 13.87 V ( s 0 ) ≈ 13.87 V ( s 2 ) = 5 + 0.9 × 13.87 ≈ 17.48 V ( s 2 ) = 5 + 0.9 × 13.87 ≈ 17.48
所以 V π 0 = [ 13.87 , 10.00 , 17.48 , 0.00 ] V π 0 = [ 13.87 , 10.00 , 17.48 , 0.00 ]
第 1 轮策略改进 （对每个状态计算贪心动作）：
以 s 0 s 0
a 0 a 0 0.5 ( 1 + 0.9 × 10.00 ) + 0.5 ( 2 + 0.9 × 17.48 ) = 0.5 × 10 + 0.5 × 17.73 = 13.87 0.5 ( 1 + 0.9 × 10.00 ) + 0.5 ( 2 + 0.9 × 17.48 ) = 0.5 × 10 + 0.5 × 17.73 = 13.87 a 1 a 1 0.5 ( 0 + 0.9 × 13.87 ) + 0.5 ( − 1 + 0.9 × 17.48 ) = 0.5 × 12.48 + 0.5 × 14.73 = 13.61 0.5 ( 0 + 0.9 × 13.87 ) + 0.5 ( − 1 + 0.9 × 17.48 ) = 0.5 × 12.48 + 0.5 × 14.73 = 13.61 选择 a 0 a 0
以 s 1 s 1
a 0 a 0 10 + 0 = 10.00 10 + 0 = 10.00 a 1 a 1 0.5 ( 0 + 0.9 × 10 ) + 0.5 ( 3 + 0.9 × 17.48 ) = 0.5 × 9 + 0.5 × 18.73 = 13.87 0.5 ( 0 + 0.9 × 10 ) + 0.5 ( 3 + 0.9 × 17.48 ) = 0.5 × 9 + 0.5 × 18.73 = 13.87 选择 a 1 a 1
以 s 2 s 2
a 0 a 0 5 + 0.9 × 13.87 = 17.48 5 + 0.9 × 13.87 = 17.48 a 1 a 1 1 + 0 = 1.00 1 + 0 = 1.00 选择 a 0 a 0
新策略 π 1 π 1 π ( s 0 ) = a 0 π ( s 0 ) = a 0 π ( s 1 ) = a 1 π ( s 1 ) = a 1 π ( s 2 ) = a 0 π ( s 2 ) = a 0
第 2 轮策略评估 ：
V ( s 1 ) = 0.5 [ 0 + 0.9 V ( s 1 ) ] + 0.5 [ 3 + 0.9 V ( s 2 ) ] V ( s 1 ) = 0.5 [ 0 + 0.9 V ( s 1 )] + 0.5 [ 3 + 0.9 V ( s 2 )] V ( s 1 ) = 0.45 V ( s 1 ) + 1.5 + 0.45 V ( s 2 ) V ( s 1 ) = 0.45 V ( s 1 ) + 1.5 + 0.45 V ( s 2 ) 0.55 V ( s 1 ) = 1.5 + 0.45 V ( s 2 ) 0.55 V ( s 1 ) = 1.5 + 0.45 V ( s 2 ) V ( s 1 ) ≈ 2.73 + 0.82 V ( s 2 ) V ( s 1 ) ≈ 2.73 + 0.82 V ( s 2 )
解完整的方程组（此处省略详细的代数推导）得到：V π 1 ≈ [ 28.05 , 26.65 , 30.25 , 0.00 ] V π 1 ≈ [ 28.05 , 26.65 , 30.25 , 0.00 ]
第 2 轮策略改进 ：
检查 s 1 s 1 a 1 a 1
a 0 a 0 s 1 s 1 10 10 a 1 a 1 s 1 s 1 0.5 ( 0 + 0.9 × 26.65 ) + 0.5 ( 3 + 0.9 × 30.25 ) = 0.5 × 23.99 + 0.5 × 30.23 = 27.11 0.5 ( 0 + 0.9 × 26.65 ) + 0.5 ( 3 + 0.9 × 30.25 ) = 0.5 × 23.99 + 0.5 × 30.23 = 27.11
27.11 > 10 27.11 > 10 a 1 a 1
检查 s 0 s 0 a 1 a 1
a 1 a 1 0.5 ( 0 + 0.9 × 28.05 ) + 0.5 ( − 1 + 0.9 × 30.25 ) = 0.5 × 25.25 + 0.5 × 26.23 = 25.74 0.5 ( 0 + 0.9 × 28.05 ) + 0.5 ( − 1 + 0.9 × 30.25 ) = 0.5 × 25.25 + 0.5 × 26.23 = 25.74 a 0 a 0 13.87 13.87 所以 s 0 s 0 a 1 a 1
新策略 π 2 π 2 π ( s 0 ) = a 1 π ( s 0 ) = a 1 π ( s 1 ) = a 1 π ( s 1 ) = a 1 π ( s 2 ) = a 0 π ( s 2 ) = a 0
经过第 3 轮评估和改进后，策略不再变化，因此 π 2 π 2
值迭代（Value Iteration）将策略评估和策略改进合并为一个步骤 。它不再显式计算某个策略的值函数，而是直接迭代地求解贝尔曼最优方程：
V k + 1 ( s ) = max a ∈ A [ R ( s , a ) + γ ∑ s ′ P ( s ′ ∣ s , a ) V k ( s ′ ) ] , ∀ s V k + 1 ( s ) = a ∈ A max [ R ( s , a ) + γ s ′ ∑ P ( s ′ ∣ s , a ) V k ( s ′ ) ] , ∀ s
与策略评估不同，值迭代在每次更新中取 max max
算法：值迭代
─────────────────────────────────────────
输入：MDP M = ⟨S, A, P, R, γ⟩, 阈值 ε > 0
1. 初始化 V(s) ← 0, ∀s
2. 重复直到 max_s|V_{new}(s) - V(s)| < ε:
对每个 s ∈ S:
V_{new}(s) ← max_a [R(s,a) + γ Σ_{s'} P(s'|s,a) V(s')]
V ← V_{new}
3. 从最终的 V 中提取策略:
π(s) ← argmax_a [R(s,a) + γ Σ_{s'} P(s'|s,a) V(s')]
4. 返回 π
─────────────────────────────────────────
与策略评估类似，贝尔曼最优算子 T ∗ T ∗
( T ∗ V ) ( s ) = max a ∈ A [ R ( s , a ) + γ ∑ s ′ P ( s ′ ∣ s , a ) V ( s ′ ) ] ( T ∗ V ) ( s ) = a ∈ A max [ R ( s , a ) + γ s ′ ∑ P ( s ′ ∣ s , a ) V ( s ′ ) ]
T ∗ T ∗ γ γ V k + 1 = T ∗ V k V k + 1 = T ∗ V k V 0 V 0 V ∗ V ∗
值迭代的一个重要特性是，它可以在 O ( log ( 1 / ϵ ) ) O ( log ( 1/ ϵ )) ϵ ϵ
∥ V k − V ∗ ∥ ∞ ≤ γ k 1 − γ ∥ V 1 − V 0 ∥ ∞ ∥ V k − V ∗ ∥ ∞ ≤ 1 − γ γ k ∥ V 1 − V 0 ∥ ∞
依旧使用上文 4 状态 MDP。初始 V 0 ( s ) = 0 V 0 ( s ) = 0
第 1 次迭代 V 1 V 1
V 1 ( s ) = max a [ R ( s , a ) + 0.9 × 0 ] V 1 ( s ) = max a [ R ( s , a ) + 0.9 × 0 ]
状态
a 0 a 0 a 1 a 1 V 1 V 1
s 0 s 0 0.5 × 1 + 0.5 × 2 = 1.5 0.5 × 1 + 0.5 × 2 = 1.5 0.5 × 0 + 0.5 × ( − 1 ) = − 0.5 0.5 × 0 + 0.5 × ( − 1 ) = − 0.5 1.50
s 1 s 1 10 10 0.5 × 0 + 0.5 × 3 = 1.5 0.5 × 0 + 0.5 × 3 = 1.5 10.00
s 2 s 2 5 5 1 1 5.00
s 3 s 3 0 0 0 0 0.00
第 2 次迭代 V 2 V 2
以 s 0 s 0 a 0 a 0 0.5 [ 1 + 0.9 × V 1 ( s 1 ) ] + 0.5 [ 2 + 0.9 × V 1 ( s 2 ) ] = 0.5 ( 1 + 9 ) + 0.5 ( 2 + 4.5 ) = 5 + 3.25 = 8.25 0.5 [ 1 + 0.9 × V 1 ( s 1 )] + 0.5 [ 2 + 0.9 × V 1 ( s 2 )] = 0.5 ( 1 + 9 ) + 0.5 ( 2 + 4.5 ) = 5 + 3.25 = 8.25 a 1 a 1 0.5 [ 0 + 0.9 × V 1 ( s 0 ) ] + 0.5 [ − 1 + 0.9 × V 1 ( s 2 ) ] = 0.5 ( 0 + 1.35 ) + 0.5 ( − 1 + 4.5 ) = 0.675 + 1.75 = 2.425 0.5 [ 0 + 0.9 × V 1 ( s 0 )] + 0.5 [ − 1 + 0.9 × V 1 ( s 2 )] = 0.5 ( 0 + 1.35 ) + 0.5 ( − 1 + 4.5 ) = 0.675 + 1.75 = 2.425
V 2 ( s 0 ) = max ( 8.25 , 2.425 ) = 8.25 V 2 ( s 0 ) = max ( 8.25 , 2.425 ) = 8.25
状态
V 2 V 2
s 0 s 0 8.25
s 1 s 1 10.00
s 2 s 2 5 + 0.9 × 1.50 = 6.35 5 + 0.9 × 1.50 = 6.35
s 3 s 3 0.00
完整迭代过程：
迭代 k
V k ( s 0 ) V k ( s 0 ) V k ( s 1 ) V k ( s 1 ) V k ( s 2 ) V k ( s 2 ) V k ( s 3 ) V k ( s 3 )
0
0.00
0.00
0.00
0.00
1
1.50
10.00
5.00
0.00
2
8.25
10.00
6.35
0.00
3
12.57
17.72
12.43
0.00
5
20.04
24.52
18.04
0.00
10
27.81
26.49
27.39
0.00
15
28.04
26.65
28.07
0.00
∞ ∞ 28.05 26.65 30.25 0.00
注意 V 15 V 15
s 0 s 0 a 0 a 0 a 1 a 1 a 1 a 1 s 1 s 1 a 0 a 0 a 1 a 1 a 1 a 1 s 2 s 2 a 0 a 0 a 1 a 1 a 0 a 0
这与策略迭代得到的最优策略一致。值迭代大约需要 10-15 轮收敛，而策略迭代只需 2-3 轮，但每步策略评估都需要多次内循环。
在实际应用中，策略迭代和值迭代的选择取决于具体问题特征：
场景
推荐方法
原因
状态空间小，动作空间大
策略迭代
每轮需要多次策略评估，但整体迭代次数少
状态空间大，动作空间小
值迭代
每轮只需一次扫描，容易实现截断
需要最优值函数
值迭代
直接得到 V ∗ V ∗
需要最优策略
策略迭代
策略空间收敛更快
高折扣因子 γ → 1 γ → 1
值迭代 + 改进边界
策略评估收敛极慢，截断值迭代更有效
实际应用中，严格区分策略评估和策略改进的"完整"版本并不常见。相反，大多数强化学习算法遵循广义策略迭代 （Generalized Policy Iteration, GPI）的框架：
GPI 是指策略评估和策略改进这两个过程的任何交互方式 ——不完全是一个过程结束后再启动另一个，而是两个过程以任意粒度交替进行。
策略评估
┌──────────┐
│ │
▼ │
V ≈ V^π │
│ │
│ │ 交替进行
│ 策略改进 │
│ ┌──────────┘
│ ▼
│ π' = greedy(V)
└──┘
── 收敛时 ──► π* (V*)
GPI 的核心洞察是：不需要在每次改进前完全精确评估策略 。只要值函数和策略"大致"匹配，GPI 的双向过程就能逐渐推向最优。
变体 1：截断策略迭代（Truncated Policy Iteration）
只在策略评估阶段进行固定次数 k k
重复直到收敛:
对每个状态做 k 次贝尔曼期望更新:
V(s) ← Σ_a π(a|s)[R(s,a) + γ Σ_{s'} P V(s')]
策略改进:
π(s) ← argmax_a [R(s,a) + γ Σ_{s'} P V(s')]
当 k = 1 k = 1 k → ∞ k → ∞ k k
变体 2：异步动态规划（Asynchronous DP）
不对所有状态同时更新，而是以任意顺序就地更新 单个状态：
重复直到收敛:
选择任意状态 s ∈ S
策略评估更新:
V(s) ← Σ_a π(a|s)[R(s,a) + γ Σ_{s'} P V(s')]
或值迭代更新:
V(s) ← max_a [R(s,a) + γ Σ_{s'} P V(s')]
异步 DP 的优势在于可以聚焦更新"重要"的状态，并且在某些状态的值函数已经接近收敛时可以节省计算量。
变体 3：原位优先遍历（Prioritized Sweeping）
为每个状态维护一个贝尔曼误差 （Bellman error）度量：
δ ( s ) = ∣ V new ( s ) − V old ( s ) ∣ δ ( s ) = ∣ V new ( s ) − V old ( s ) ∣
优先更新误差最大的状态。更新后，该状态的前驱状态的误差也需要重新计算。这种方法可以显著加速收敛，尤其是在奖励稀疏的环境中。
在 10 × 10 10 × 10
方法
达到收敛需要的更新次数
每步计算成本
适用场景
同步值迭代
1,500
O ( n m ) O ( nm ) 基准方法
截断策略迭代 (k = 5 k = 5
800
O ( k n m ) O ( k nm ) 通用
截断策略迭代 (k = 20 k = 20
400
O ( k n m ) O ( k nm ) 需精确策略
异步值迭代
1,200
O ( 1 ) O ( 1 ) 大规模问题
优先级扫描
300
O ( log n ) O ( log n ) 奖励稀疏问题
对于 n n m m
操作
时间复杂度
空间复杂度
一次同步值迭代
O ( ∣ S ∣ 2 ⋅ ∣ A ∣ ) O ( ∣ S ∣ 2 ⋅ ∣ A ∣ ) O ( ∣ S ∣ ) O ( ∣ S ∣ )
一次策略评估迭代
O ( ∣ S ∣ 2 ⋅ ∣ A ∣ ) O ( ∣ S ∣ 2 ⋅ ∣ A ∣ ) O ( ∣ S ∣ ) O ( ∣ S ∣ )
值迭代到 ϵ ϵ
O ( ∣ S ∣ 2 ⋅ ∣ A ∣ ⋅ log ( 1 / ϵ ) / ( 1 − γ ) ) O ( ∣ S ∣ 2 ⋅ ∣ A ∣ ⋅ log ( 1/ ϵ ) / ( 1 − γ )) O ( ∣ S ∣ ) O ( ∣ S ∣ )
策略迭代（完整）
O ( ∣ S ∣ 3 ) O ( ∣ S ∣ 3 ) O ( ∣ S ∣ 5 ) O ( ∣ S ∣ 5 ) O ( ∣ S ∣ ) O ( ∣ S ∣ )
主要瓶颈 ：每次更新都需要遍历所有 ∣ S ∣ 2 ∣ S ∣ 2 ∣ S ∣ = 10 6 ∣ S ∣ = 1 0 6 10 12 1 0 12
动态规划面临的核心挑战是维度灾难 （Curse of Dimensionality）：
维度数
每个维度离散化数
总状态数
DP 一次扫描耗时
1
10
10
微秒级
2
10
100
毫秒级
4
10
10,000
秒级
8
10
10^8
~1 天
20
10
10^20
不可行
这就是为什么经典 DP 只能解决小规模问题，而现实世界的强化学习问题（如机器人控制、围棋、游戏 AI）需要无模型方法和函数近似。
策略
描述
效果
异步更新 只更新相关状态子集
可减少 10-100 倍计算量
函数近似 用神经网络表示值函数
突破维度灾难（现代深度 RL）
维度约简 识别并利用问题中的对称性
适用于结构化问题
分层抽象 将大问题分解为小问题的层次结构
选项框架（Options Framework）
蒙特卡洛采样 用采样替代全空间枚举
无模型方法的基础
算法
更新公式
每步更新
策略显式
收敛保证
适用规模
策略评估
V ← T π V V ← T π V 求期望（均值）
是
线性收敛
中
策略迭代
评估 + 改进
两者交替
是
有限步收敛
小到中
值迭代
V ← T ∗ V V ← T ∗ V 求最大
否（隐式）
线性收敛
中到大
截断策略迭代
V ← T π k V V ← T π k V k k 折中
是
线性收敛
中到大
异步 DP
任意顺序单状态更新
单状态
均可
线性收敛
大
理论基础坚实 ：有完整的收敛性证明和误差界分析计算可预测 ：收敛步数有理论保证，不像蒙特卡洛方法那样依赖方差充分利用模型信息 ：当转移概率已知时，DP 比采样方法更高效自举机制 ：利用当前估计来更新自身，加速学习（这一点被后续 TD 方法继承）
需要完整的环境模型 ：现实中转移概率通常未知维度灾难 ：状态空间指数增长不适用于连续状态或动作空间 ：需要离散化或函数近似同步更新成本高 ：每次更新需要扫描所有状态-动作对
动态规划中的核心概念在后续的各种强化学习算法中都有体现：
DP 概念
继承该概念的方法
转换方式
自举 TD 学习、Q 学习、DQN
用采样替代期望，用当前估计替代真实 V π V π
广义策略迭代 Actor-Critic、PPO、SAC
策略网络（Actor）和价值网络（Critic）交替更新
值迭代 DQN、Double DQN
用神经网络逼近 V ∗ V ∗ Q ∗ Q ∗
策略迭代 自然策略梯度、TRPO、PPO
用采样近似策略评估，用 KL 约束策略改进
异步更新 经验回放（Experience Replay）
从回放缓冲区采样小批量更新
优先级扫描 优先经验回放（Prioritized Replay）
按 TD 误差大小排序采样
如下图所示，动态规划是连接"基于模型"和"无模型"方法的桥梁，其自举思想贯穿了整个强化学习的发展历史：
┌─────────────────────────────────────────────────────────────┐
│ 动态规划 (DP) │
│ 已知模型 + 自举 + 全状态空间更新 │
└─────────┬──────────────────────┬────────────────────────────┘
│ │
▼ ▼
┌──────────────────┐ ┌──────────────────────┐
│ 基于模型RL │ │ 无模型RL │
│ │ │ │
│ Dyna-Q │ │ TD学习、Q学习 │
│ 基于模型策略优化 │ │ DQN系列 │
│ 世界模型(MBRL) │ │ Policy Gradient │
│ │ │ Actor-Critic │
└──────────────────┘ └──────────────────────┘
│ │
▼ ▼
┌──────────────────────────────┐
│ 现代深度RL (Deep RL) │
│ ┌────────────────────┐ │
│ │ 价值迭代 + 神经网络 │ │
│ │ 策略迭代 + 神经网络 │ │
│ │ GPI + 经验回放 │ │
│ └────────────────────┘ │
└──────────────────────────────┘
在实际工程中（而非教学环境），很少直接使用 DP 解决原始问题。但在以下场景中 DP 的思想非常有用：
小规模基准测试 ：当状态空间小于 10 4 1 0 4 子问题求解器 ：在分层 RL 或选项框架中，可以用 DP 求解低层子策略模型预测控制 ：如果学到一个环境模型，可以用 DP 进行规划理论分析工具 ：评估近似方法的最优性差距
稀疏矩阵 ：转移矩阵 P P 向量化操作 ：利用 NumPy 等库的向量化操作替代 Python 循环，可获得 10-100 倍的加速收敛检测 ：不要等到完全收敛，使用合理的 ϵ ϵ 10 − 3 1 0 − 3 10 − 4 1 0 − 4 初始值 ：对于最优值函数使用乐观初始值（如 V 0 ( s ) = R max / ( 1 − γ ) V 0 ( s ) = R m a x / ( 1 − γ )
Sutton, R. S., & Barto, A. G. (2018). Reinforcement Learning: An Introduction (2nd ed.). MIT Press. 第 4 章：Dynamic Programming
Bellman, R. (1957). Dynamic Programming . Princeton University Press.
Puterman, M. L. (1994). Markov Decision Processes: Discrete Stochastic Dynamic Programming . Wiley.
Bertsekas, D. P. (2012). Dynamic Programming and Optimal Control (Vol. 1-2, 4th ed.). Athena Scientific.
Howard, R. A. (1960). Dynamic Programming and Markov Processes . MIT Press.
Van Seijen, H., Van Hasselt, H., Whiteson, S., & Wiering, M. (2009). "A theoretical and empirical analysis of Expected Sarsa." IEEE Symposium on Adaptive Dynamic Programming and Reinforcement Learning .
关联页面 ：