第4章：动态规划（Dynamic Programming）
一、导读
1.1 本章学习目标
第4章讲解如何使用动态规划（DP）方法求解有限 MDP。动态规划的核心思想是利用贝尔曼方程的递归结构，将复杂的全局优化问题分解为一系列简单的子问题。虽然 DP 要求已知环境的完整模型（转移概率和奖励函数），在实际中往往不满足，但 DP 是理解后续无模型方法（蒙特卡洛、时序差分）的重要基础。
本章的核心学习目标包括：
- 理解策略评估（Policy Evaluation）：给定策略，用贝尔曼方程迭代计算价值函数
- 掌握策略改进（Policy Improvement）：给定价值函数，贪心地改进策略
- 理解策略迭代（Policy Iteration）：交替执行策略评估和策略改进，直到收敛
- 掌握值迭代（Value Iteration）：将策略评估压缩为一步，直接迭代贝尔曼最优方程
- 理解 DP 方法的局限性：需要完整的环境模型、计算复杂度高
- 了解广义策略迭代（GPI）：策略评估和策略改进的交互框架
1.2 为什么本章如此重要
动态规划是强化学习算法的理论基石。即使在实际应用中我们很少直接使用 DP（因为通常需要环境模型），但 DP 的思想贯穿了几乎所有强化学习算法：
- 蒙特卡洛方法用采样回报替代 DP 中的期望
- 时序差分方法用估计值替代 DP 中的真实价值
- 策略梯度方法仍然在优化 DP 定义的目标函数
理解 DP，就理解了强化学习算法的"理想形态"——在拥有完整信息时，最优解是什么样的。
1.3 核心问题引导
策略评估为什么可以用迭代法求解？它保证收敛吗？
策略改进定理告诉我们什么？为什么贪心改进一定能让策略变好？
值迭代与策略迭代的区别是什么？各自适用于什么场景？
广义策略迭代（GPI）如何统一了各种强化学习算法？
当状态空间很大时，DP 面临什么挑战？如何缓解？
二、核心概念详解
4.1 策略评估（Policy Evaluation）
给定策略 $\pi$，策略评估的目标是计算状态价值函数 $v_\pi$。由于 $v_\pi$ 满足贝尔曼方程：
$$v_\pi(s) = \sum_a \pi(a|s) \sum_{s'} P(s'|s,a) [R(s,a,s') + \gamma v_\pi(s')]$$
我们可以用迭代法求解。初始化 $v_0(s) = 0$（或任意值），然后反复应用贝尔曼备份：
$$v_{k+1}(s) = \sum_a \pi(a|s) \sum_{s'} P(s'|s,a) [R(s,a,s') + \gamma v_k(s')]$$
当 $v_k$ 收敛时，$v_k \to v_\pi$。
import numpy as np
class GridWorld:
def __init__(self, size=4):
self.size = size
self.n_states = size * size
self.n_actions = 4
self.gamma = 1.0
self.actions = [(-1,0),(1,0),(0,-1),(0,1)]
self.terminal = [(0,0), (size-1, size-1)]
def is_terminal(self, state):
r, c = state // self.size, state % self.size
return (r, c) in self.terminal
def get_transitions(self, state, action):
if self.is_terminal(state):
return [(state, 0.0, True)]
r, c = state // self.size, state % self.size
dr, dc = self.actions[action]
nr, nc = max(0, min(self.size-1, r+dr)), max(0, min(self.size-1, c+dc))
next_state = nr * self.size + nc
reward = -1.0
return [(next_state, reward, self.is_terminal(next_state))]
def policy_evaluation(grid, policy, theta=1e-4):
V = np.zeros(grid.n_states)
while True:
delta = 0
for s in range(grid.n_states):
if grid.is_terminal(s):
continue
v = V[s]
new_v = 0
for a in range(grid.n_actions):
prob = policy[s][a]
if prob == 0:
continue
for next_s, reward, _ in grid.get_transitions(s, a):
new_v += prob * (reward + grid.gamma * V[next_s])
V[s] = new_v
delta = max(delta, abs(v - V[s]))
if delta < theta:
break
return V
grid = GridWorld(size=4)
random_policy = np.ones((grid.n_states, grid.n_actions)) / grid.n_actions
V = policy_evaluation(grid, random_policy)
print("Value function under random policy:")
for r in range(4):
row = []
for c in range(4):
s = r * 4 + c
if grid.is_terminal(s):
row.append(" 0")
else:
row.append(f"{V[s]:5.1f}")
print(" ".join(row))4.2 策略改进（Policy Improvement）
给定价值函数 $v_\pi$，策略改进通过贪心地选择每个状态下价值最高的动作来改进策略：
$$\pi'(s) = \arg\max_a \sum_{s'} P(s'|s,a) [R(s,a,s') + \gamma v_\pi(s')]$$
策略改进定理：如果 $\pi'$ 是通过上述方式从 $\pi$ 得到的，则 $v_{\pi'}(s) \geq v_\pi(s)$ 对所有 $s$ 成立。如果 $\pi' = \pi$，则 $\pi$ 已经是最优策略。
def policy_improvement(grid, V):
policy = np.zeros((grid.n_states, grid.n_actions))
for s in range(grid.n_states):
if grid.is_terminal(s):
continue
action_values = np.zeros(grid.n_actions)
for a in range(grid.n_actions):
for next_s, reward, _ in grid.get_transitions(s, a):
action_values[a] += reward + grid.gamma * V[next_s]
best_action = np.argmax(action_values)
policy[s][best_action] = 1.0
return policy
V = policy_evaluation(grid, random_policy)
new_policy = policy_improvement(grid, V)
action_names = ['up', 'down', 'left', 'right']
print("\nImproved policy:")
for r in range(4):
row = []
for c in range(4):
s = r * 4 + c
if grid.is_terminal(s):
row.append("T")
else:
a = np.argmax(new_policy[s])
row.append(action_names[a][0].upper())
print(" ".join(row))4.3 策略迭代（Policy Iteration）
策略迭代交替执行策略评估和策略改进，直到策略不再改变：
初始化：随机策略 $\pi$
策略评估：计算 $v_\pi$
策略改进：$\pi' \leftarrow$ greedy($v_\pi$)
检查收敛：如果 $\pi' = \pi$，停止；否则 $\pi \leftarrow \pi'$，回到步骤2
def policy_iteration(grid, theta=1e-4):
policy = np.ones((grid.n_states, grid.n_actions)) / grid.n_actions
iteration = 0
while True:
V = policy_evaluation(grid, policy, theta)
new_policy = policy_improvement(grid, V)
iteration += 1
policy_stable = np.allclose(policy, new_policy)
print(f"Iteration {iteration}: stable={policy_stable}")
if policy_stable:
break
policy = new_policy
return V, policy
grid = GridWorld(size=4)
V, optimal_policy = policy_iteration(grid)
print("\nOptimal value function:")
for r in range(4):
row = []
for c in range(4):
s = r * 4 + c
if grid.is_terminal(s):
row.append(" 0")
else:
row.append(f"{V[s]:5.1f}")
print(" ".join(row))
action_names = ['up', 'down', 'left', 'right']
print("\nOptimal policy:")
for r in range(4):
row = []
for c in range(4):
s = r * 4 + c
if grid.is_terminal(s):
row.append("T")
else:
a = np.argmax(optimal_policy[s])
row.append(action_names[a][0].upper())
print(" ".join(row))4.4 值迭代（Value Iteration）
策略迭代的一个问题是每次策略评估都需要迭代到收敛，这很耗时。值迭代将策略评估压缩为一步贝尔曼备份，直接迭代贝尔曼最优方程：
$$v_{k+1}(s) = \max_a \sum_{s'} P(s'|s,a) [R(s,a,s') + \gamma v_k(s')]$$
def value_iteration(grid, theta=1e-4):
V = np.zeros(grid.n_states)
iteration = 0
while True:
delta = 0
for s in range(grid.n_states):
if grid.is_terminal(s):
continue
v = V[s]
max_val = -float('inf')
for a in range(grid.n_actions):
expected = 0
for next_s, reward, _ in grid.get_transitions(s, a):
expected += reward + grid.gamma * V[next_s]
max_val = max(max_val, expected)
V[s] = max_val
delta = max(delta, abs(v - V[s]))
iteration += 1
if delta < theta:
break
policy = np.zeros((grid.n_states, grid.n_actions))
for s in range(grid.n_states):
if grid.is_terminal(s):
continue
action_values = np.zeros(grid.n_actions)
for a in range(grid.n_actions):
for next_s, reward, _ in grid.get_transitions(s, a):
action_values[a] += reward + grid.gamma * V[next_s]
best_action = np.argmax(action_values)
policy[s][best_action] = 1.0
return V, policy, iteration
grid = GridWorld(size=4)
V, policy, iters = value_iteration(grid)
print(f"Value iteration converged in {iters} iterations")4.5 广义策略迭代（GPI）
广义策略迭代（Generalized Policy Iteration, GPI）是一个统一的框架，描述了策略评估和策略改进之间的交互关系：
- 策略评估：使价值函数与当前策略一致
- 策略改进：使策略相对于当前价值函数贪心最优
这两个过程相互竞争又相互促进：策略改进使价值函数"过时"，策略评估又使价值函数与改进后的策略一致。当两者都达到稳定时，就得到了最优策略。
几乎所有强化学习算法都可以被理解为 GPI 的实例：
- 动态规划：两个过程都完全收敛
- 蒙特卡洛方法：策略评估通过采样完成
- 时序差分：策略评估通过自举完成
4.6 DP 的局限性
动态规划方法有两个主要局限：
需要完整的环境模型：DP 需要知道状态转移概率 $P(s'|s,a)$ 和奖励函数 $R(s,a,s')$。在大多数实际问题中，这些是未知的。
计算复杂度高：每次迭代需要遍历所有状态和动作。当状态空间为 $10^{10}$（如围棋）时，DP 完全不可行。
这些局限催生了无模型方法（蒙特卡洛、时序差分）和函数近似方法（深度强化学习）。
三、实战案例
3.1 案例一：Jack 的租车问题
经典的 Jack 租车问题是 DP 的经典应用。Jack 在两个地点经营租车业务，每天可以在两个地点之间转移车辆，目标是最大化长期收益。
class JacksCarRental:
def __init__(self, max_cars=20, max_move=5):
self.max_cars = max_cars
self.max_move = max_move
self.gamma = 0.9
self.rental_reward = 10
self.moving_cost = 2
self.poisson_rental = {1: 3, 2: 4}
self.poisson_return = {1: 3, 2: 2}
def solve(self, theta=0.01):
n = self.max_cars + 1
V = np.zeros((n, n))
policy = np.zeros((n, n), dtype=int)
for iteration in range(10):
V = self._policy_evaluation(V, policy)
policy, stable = self._policy_improvement(V, policy)
print(f"Iteration {iteration}: policy stable = {stable}")
if stable:
break
return V, policy
def _policy_evaluation(self, V, policy, theta=0.01):
n = self.max_cars + 1
while True:
delta = 0
for i in range(n):
for j in range(n):
v = V[i, j]
move = policy[i, j]
new_i = min(n-1, max(0, i - move))
new_j = min(n-1, max(0, j + move))
cost = abs(move) * self.moving_cost
expected = -cost
for r1 in range(min(10, new_i+1)):
for r2 in range(min(10, new_j+1)):
prob = 0.01
reward = (r1 + r2) * self.rental_reward
next_i = min(n-1, max(0, new_i - r1 + int(r1*0.5)))
next_j = min(n-1, max(0, new_j - r2 + int(r2*0.5)))
expected += prob * (reward + self.gamma * V[next_i, next_j])
V[i, j] = expected
delta = max(delta, abs(v - V[i, j]))
if delta < theta:
break
return V
def _policy_improvement(self, V, policy):
n = self.max_cars + 1
new_policy = np.zeros_like(policy)
stable = True
for i in range(n):
for j in range(n):
old_action = policy[i, j]
best_value = -float('inf')
best_action = 0
for move in range(-self.max_move, self.max_move + 1):
new_i = min(n-1, max(0, i - move))
new_j = min(n-1, max(0, j + move))
if new_i < 0 or new_i >= n or new_j < 0 or new_j >= n:
continue
cost = abs(move) * self.moving_cost
expected = -cost
for r1 in range(min(10, new_i+1)):
for r2 in range(min(10, new_j+1)):
prob = 0.01
reward = (r1 + r2) * self.rental_reward
next_i = min(n-1, max(0, new_i - r1 + int(r1*0.5)))
next_j = min(n-1, max(0, new_j - r2 + int(r2*0.5)))
expected += prob * (reward + self.gamma * V[next_i, next_j])
if expected > best_value:
best_value = expected
best_action = move
new_policy[i, j] = best_action
if old_action != best_action:
stable = False
return new_policy, stable
print("Jack's Car Rental (simplified)")
jcr = JacksCarRental(max_cars=5, max_move=3)
V, policy = jcr.solve()
print(f"Optimal policy shape: {policy.shape}")
print(f"Sample policy values:\n{policy[:6, :6]}")3.2 案例二：值迭代 vs 策略迭代的效率对比
def compare_dp_methods():
import time
sizes = [4, 8, 12]
for size in sizes:
grid = GridWorld(size=size)
start = time.time()
V1, pi1 = policy_iteration(grid)
pi_time = time.time() - start
start = time.time()
V2, pi2, vi_iters = value_iteration(grid)
vi_time = time.time() - start
print(f"Size {size}x{size}:")
print(f" Policy iteration: {pi_time:.4f}s")
print(f" Value iteration: {vi_time:.4f}s ({vi_iters} iters)")
print(f" Values match: {np.allclose(V1, V2)}")
compare_dp_methods()四、本章小结
第4章讲解了动态规划方法求解 MDP 的完整框架：
策略评估：通过迭代贝尔曼方程计算给定策略的价值函数
策略改进：贪心地选择最优动作来改进策略
策略迭代：交替执行评估和改进，保证单调改进直到最优
值迭代：直接迭代贝尔曼最优方程，更高效但每步不完全评估
GPI 框架：统一了各种强化学习算法的核心思想
局限性：需要完整模型、计算复杂度高，催生了无模型方法
五、思考与练习
思考题
策略迭代为什么保证收敛？它最多需要多少次迭代？
值迭代的收敛速度受哪些因素影响？折扣因子 $\gamma$ 如何影响收敛速度？
在什么情况下策略迭代比值迭代更快？反之呢？
如果状态空间有 $10^6$ 个状态，DP 方法可行吗？有什么替代方案？
编程练习
在一个 8x8 的网格世界中比较策略迭代和值迭代的收敛速度
实现异步值迭代：不要求按固定顺序遍历所有状态
在有随机动作（10%概率执行错误方向）的环境中求解最优策略