RL-03-01-算法-动态规划

发表于 | 分类于 ，
动态规划 DP：策略评估、策略迭代、价值迭代；已知模型 P/R 下的表格求解与收敛性。

← 上级：RL-03.算法分类与选型 · 原理：RL-02-02-价值函数与策略 · 后续：RL-03-04-算法-蒙特卡洛

动态规划（Dynamic Programming，DP）在已知完整环境模型 $P(s’|s,a)$ 与 $R(s,a)$ 时，通过 Bellman 方程迭代求解 $V^$、$Q^$ 与 $\pi^$。它不采样、不试错，是理解 MC / TD / Q-Learning 的*理论起点。

段末注释：动态规划（Dynamic Programming，DP）指利用 Bellman 递推在状态空间上批量更新价值或策略的方法；后文沿用 DP。

一、前提与定位

条件 DP 采样方法（MC / TD）
已知 $P, R$ ✓ 必需 ✗ 不需要
状态空间 有限、可枚举 可很大或连续
数据 无交互 需与环境交互
典型用途 小 MDP 精确解、教学 实际 RL 主流

DP 解决的是规划（Planning）；真实 RL 多为模型未知，但 DP 思想体现在：Bellman 备份、策略改进、价值迭代——以及 Dyna-Q 等「学模型 + 规划」方法。

二、策略评估（Policy Evaluation）

给定策略 $\pi$，求 $V^\pi$。

迭代策略评估（同步更新）：

$$
V_{k+1}(s) = \sum_a \pi(a|s) \sum_{s’} P(s’|s,a) \left[ R(s,a,s’) + \gamma V_k(s’) \right]
$$

直到 $\max_s |V_{k+1}(s) - V_k(s)| < \theta$。

对 $Q^\pi$ 同理，用 Bellman 期望方程 备份 $Q$。

三、策略迭代（Policy Iteration）

交替两步直至策略不变：

  1. 评估：对当前 $\pi$，解 $V^\pi$（可迭代至收敛或若干步）
  2. 改进：$\pi’(s) = \arg\max_a \sum_{s’} P(s’|s,a)[R + \gamma V^\pi(s’)]$

由 策略改进定理，$V^{\pi’} \geq V^\pi$，有限 MDP 下有限步收敛到 $\pi^*$。

1
π₀ 任意 → 评估 V^π → 贪心改进 π' → 评估 → … → π*

四、价值迭代（Value Iteration）

直接用 Bellman 最优算子 $\mathcal{T}^*$ 更新：

$$
V_{k+1}(s) = \max_a \sum_{s’} P(s’|s,a) \left[ R(s,a,s’) + \gamma V_k(s’) \right]
$$

收敛后导出策略：

$$
\pi^(s) = \arg\max_a \sum_{s’} P(s’|s,a) \left[ R + \gamma V^(s’) \right]
$$

策略迭代 价值迭代
每轮 完整/部分策略评估 + 改进 仅最优 Bellman 备份
策略 每轮显式 $\pi$ 收敛后一次导出
收敛速度 评估可能慢 常更少外层轮数

五、网格世界算例（梗概）

$4\times4$ 网格，每步 $-1$，目标格 $0$，撞墙不动。已知 $P$（确定性转移），运行价值迭代：

  1. 初始化 $V(s)=0$
  2. 对每个 $s$ 用 $\mathcal{T}^*$ 更新
  3. 重复至变化 $< \theta$
  4. $\pi^(s) = \arg\max_a Q^(s,a)$

可手算验证：最优策略为最短路径指向目标。

六、伪代码（价值迭代）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def value_iteration(P, R, gamma, theta=1e-6):
    V = {s: 0.0 for s in states}
    while True:
        delta = 0
        for s in states:
            v = V[s]
            V[s] = max(
                sum(P[s][a][sp] * (R[s][a][sp] + gamma * V[sp]) for sp in states)
                for a in actions(s)
            )
            delta = max(delta, abs(v - V[s]))
        if delta < theta:
            break
    pi = {s: argmax_a Q_from_V(s, a, V, P, R, gamma) for s in states}
    return V, pi

七、局限与延伸

局限 延伸
需完整 $P$ 模型未知 → 蒙特卡洛、时序差分
状态空间大 函数逼近、采样近似
无探索问题 模型已知时直接算最优

异步 DP、实时 DP（RTDP）在部分状态上更新，适合大空间稀疏访问；深度时代 MCTS / MuZero 可看作在 learned model 上的规划。

八、在算法谱系中的位置

1
2
3
4
5
6
7
已知 P, R
    ↓
动态规划（策略迭代 / 价值迭代）→ V*, π*
    ↓ 模型未知，采样
蒙特卡洛 MC → 时序差分 TD → Q-Learning / SARSA
    ↓ 学近似模型 + 规划
Dyna-Q → Model-Based（MCTS / Dreamer）

九、小结

  • DP = 已知模型 + Bellman 备份 + 策略/价值迭代。
  • 策略迭代与价值迭代均收敛到 $V^, \pi^$（有限 MDP、$\gamma < 1$）。
  • 下一篇：Q-Learning（无模型 Off-Policy TD 控制）· 采样理论：蒙特卡洛
-------------本文结束感谢您的阅读-------------