RL学习笔记（4）: 动态规划 • AtPoint's Blog

引言#

由 Richard Bellman 提出的动态规划（Dynamic Programming）是一种用于解决决策问题的算法。在算法竞赛中，体现为将一个问题拆解为有递归关系的子问题，通过状态转移方程来解决。在强化学习中，DP 特指 在已知环境模型 (即马尔可夫决策过程 MDP) 完全信息的情况下，计算最优策略 $\pi_*$ 的一组算法。

核心思想: DP 充分利用了 价值函数 的结构，特别是通过 贝尔曼方程 (Bellman Equation) 来组织计算，有效地寻找最优策略。DP 适用的问题通常具有 最优子结构 和 重叠子问题 的性质，而 MDP 正好满足这些条件 (贝尔曼方程体现了递归分解，价值函数的计算会被重复利用)。

DP 主要解决的两类问题 (MDP 规划问题):

预测 (Prediction / Policy Evaluation): 评估一个给定的策略 $\pi$ 有多好。即输入 MDP 模型和策略 $\pi$ ，输出该策略下的价值函数 $v_\pi$ 。
控制 (Control): 寻找最优的行为方式。即输入 MDP 模型，输出最优价值函数 $v^*$ 和最优策略 $\pi^*$ 。

关键前提: DP 算法必须知道环境的完整动态特性，即状态转移概率 $p(s',r|s,a)$ 和奖励函数 $R^a_s$ 。这通常被称为“基于模型的规划” (Model-based Planning)。

核心工具: 贝尔曼方程回顾#

DP 算法的基础是价值函数必须满足的贝尔曼方程。

贝尔曼期望方程 (Bellman Expectation Equation for $v_\pi$ ): 描述了给定策略 $\pi$ 下的状态价值函数 $v_\pi$ 与其后继状态价值的关系。

v_\pi(s) = \sum_{a} \pi(a \mid s) \sum_{s',r}p(s',r \mid s,a) \left[ r + \gamma v_\pi(s') \right]

贝尔曼最优方程 (Bellman Optimal Equation for $v^*$ ): 描述了最优价值函数 $v^*(s)$ 与其后继状态价值的关系。 $v^*(s) = \max_{a} \sum_{s',r}p(s',r \mid s,a) \left[ r + \gamma v^*(s') \right]$ 类似地，对于最优动作价值函数 $q_*(s, a)$ : $q_*(s, a) = \sum_{s',r}p(s',r \mid s,a) \left[ r + \gamma \max_{a'} q^*(s',a') \right]$

策略评估 (预测问题)#

目标: 计算给定策略 $\pi$ 的状态价值函数 $v_\pi$ 。

方法: 迭代策略评估 (Iterative Policy Evaluation)

该方法通过迭代式地应用贝尔曼期望方程来逼近 $v_\pi$ 。

初始化: 从一个任意的初始价值函数估计 $v_0$ 开始 (通常是全零)。
迭代更新: 在第 $k+1$ 次迭代中，对所有状态 $s \in S$ ，使用第 $k$ 轮的价值 $v_k$ 来计算新的价值估计 $v_{k+1}(s)$ :
$v_{k+1}(s) ← \sum_{a} \pi(a \mid s) \sum_{s',r}p(s',r \mid s,a) \left[ r + \gamma v_k(s') \right]$
或使用模型定义的期望奖励 $\mathcal{R}^a_s=\sum_{s',r}p(s',r \mid s,a)r$ 和状态转移概率 $\mathcal{P}^a_{ss'}=\sum_{r}p(s',r \mid s,a)$ :
$v_{k+1}(s) ← \sum_{a \in \mathcal{A}} \pi(a \mid s) \left( \mathcal{R}^a_s + \gamma \sum_{s' \in S} \mathcal{P}^a_{ss'} v_k(s') \right)$
这种对所有状态同时基于旧值进行更新的方式称为同步备份 (Synchronous Backup)。

收敛性: 由于贝尔曼期望算子是一个 压缩映射 (Contractive Mapping) (在折扣因子 $\gamma < 1$ 时)，价值函数序列 $v_0, v_1, v_2, \ldots$ 会保证收敛到真实的 $v_\pi$ 。

算法: 迭代策略评估

输入: MDP (S, A, P, R, γ), 策略 π, 阈值 θ > 0
初始化 V(s) = 0 对于所有 s ∈ S

循环:
    Δ = 0   // 初始化本轮最大价值变化量
    对于每个状态 s ∈ S:
        v = V(s)  // 存储旧价值
        // 应用贝尔曼期望备份更新 V(s)
        V(s) = Σ[a] π(a|s) * Σ[s',r] p(s',r|s,a) * (r + γ * V(s'))
        Δ = max(Δ, |v - V(s)|)  // 更新最大变化量
    如果 Δ < θ:
        终止循环 (收敛)

输出 V ≈ v_π

plaintext

寻找最优策略 (控制问题)#

目标: 找到最优策略 $\pi^*$ 和相应的最优价值函数 $v^*$ (或 $q^*$ )。

控制问题通常基于一个重要的思想: 广义策略迭代 (Generalized Policy Iteration, GPI)。GPI 指的是策略评估 (Policy Evaluation) 和 策略改进 (Policy Improvement) 两个过程相互作用、共同驱动策略和价值函数趋向最优的通用模式。几乎所有 RL 算法都可以看作是 GPI 的某种实现。

DP 中实现 GPI 的两种主要算法是策略迭代和价值迭代。

策略迭代#

策略迭代通过显式地交替进行完整的策略评估和策略改进步骤来寻找最优策略。

核心流程:

初始化: 从一个任意 (通常是随机的) 策略 $\pi_0$ 和相应的 (可能不准确的) 价值函数 $v_0$ 开始。
重复以下两个步骤直至策略稳定:

(E) 策略评估 (Policy Evaluation) 使用当前策略 $\pi_k$ ，通过 迭代策略评估 (见第2部分—策略评估) 计算其精确的价值函数 $v_{\pi_k}$ 。
(I) 策略改进 (Policy Improvement) 基于计算得到的 $v_{\pi_k}$ ，生成一个新的、改进的策略 $\pi_{k+1}$ 。对每个状态 $s$ ，选择能够最大化基于 $v_{\pi_k}$ 的一步期望回报的动作 (即对动作价值函数 $q_{\pi_k}(s, a)$ 进行贪心选择):
$\pi_{k+1}(s) ← \argmax_{a \in \mathcal{A}} q_{\pi_k}(s, a) = \argmax_{a \in \mathcal{A}} \left\{ \sum_{s',r}p(s',r \mid s,a) [ r + \gamma v_{\pi_k}(s') ] \right\}$
即:
$\pi_{k+1}(s) = \argmax_{a \in \mathcal{A}} \left\{ \mathcal{R}^a_s + \gamma \sum_{s' \in S} \mathcal{P}^a_{ss'} v_{\pi_k}(s') \right\}$

策略改进定理 (Policy Improvement Theorem): 该定理保证，通过对 $v_\pi$ 贪心选择动作得到的新策略 $\pi'$ ，其价值函数 $v_\pi'$ 对于所有状态 $s$ 都满足 $v_\pi'(s) \geq v_\pi(s)$ 。如果 $v_\pi'= v_\pi$ ，则 $v_\pi'$ 必定等于 $v_*$ ，且 $\pi$ 是最优策略之一。

收敛性: 由于状态和动作空间有限时，策略的数量也是有限的，且每次改进要么严格提升价值，要么保持不变（此时已达到最优），因此策略迭代保证在有限次迭代内收敛到最优策略 $\pi^*$ 和最优价值函数 $v^*$ 。

算法: 策略迭代

1. 初始化：
   对于所有 s ∈ S，任意初始化 V(s) ∈ R
   对于所有 s ∈ S，任意初始化 π(s) ∈ A(s)      # 确定性策略
   终止状态的 V(s) = 0

2. 循环 (策略迭代主循环):

    // ===== (E) 策略评估（确定性策略版本）=====
    循环:
        Δ = 0
        对于每个状态 s ∈ S:
            v = V(s)
            # 确定性策略：直接取 π(s) 对应的转移
            V(s) = Σ_{s',r} p(s',r | s, π(s)) * [r + γ * V(s')]
            Δ = max(Δ, |v - V(s)|)
        如果 Δ < θ:
            终止内层循环

    // ===== (I) 策略改进 =====
    policy_stable = true
    对于每个状态 s ∈ S:
        old_action = π(s)
        
        # 贪心：最大化期望回报
        π(s) = argmax_a Σ_{s',r} p(s',r | s, a) * [r + γ * V(s')]
        
        如果 old_action ≠ π(s):
            policy_stable = false

    如果 policy_stable:
        终止外层循环，返回 V ≈ v_* 和 π ≈ π_*

plaintext

价值迭代#

价值迭代是另一种寻找最优策略的 DP 算法。它不显式地进行完整的策略评估，而是将一步策略评估和策略改进结合，直接迭代贝尔曼最优方程来逼近最优价值函数 $v^*$ 。

核心思想: 策略迭代中的策略评估步骤可能需要很多次迭代才能收敛。价值迭代通过在每次迭代中直接应用贝尔曼最优方程的备份操作，来更快速地逼近 $v^*$ 。

更新规则:

初始化: 从一个任意的初始价值函数估计 $v_0$ 开始 (通常为全零)。
迭代更新: 在第 $k+1$ 次迭代中，对所有状态 $s \in \mathcal{S}$ ，使用第 $k$ 轮的价值 $v_k$ 来计算新的价值估计 $v_{k+1}(s)$ ，直接结合了最大操作 (隐式的策略改进):
$v_{k+1}(s) ← \max_{a \in \mathcal{A}} \left\{ \sum_{s',r}p(s',r \mid s,a) [ r + \gamma v_k(s') ] \right\}$
或使用 $\mathcal{R}$ 和 $\mathcal{P}$ :
$v_{k+1}(s) ← \max_{a \in \mathcal{A}} \left\{ \mathcal{R}^a_s + \gamma \sum_{s' \in S} \mathcal{P}^a_{ss'} v_k(s') \right\}$

收敛性: 由于贝尔曼最优算子也是一个压缩映射，价值函数序列 $v_0, v_1, v_2, \ldots$ 会保证收敛到最优价值函数 $v^*$ 。

与策略迭代的区别: 价值迭代的中间价值函数 $v_k$ 不一定对应任何一个固定策略的价值函数 (除非到最后收敛)。它直接朝着 $v^*$ 逼近。策略迭代则是在完整的 $v_\pi$ 和 $\pi$ 之间切换。

算法: 价值迭代

输入: MDP (S, A, P, R, γ), 阈值 θ > 0
初始化 V(s) = 0 对于所有 s ∈ S

// ===== 价值迭代：直接优化贝尔曼最优方程 =====
循环:
    Δ = 0
    对于每个状态 s ∈ S:
        v = V(s)
        // 原位更新（异步风格，通常收敛更快）
        V(s) = max[a] Σ[s',r] p(s',r|s,a) * (r + γ * V(s'))
        Δ = max(Δ, |v - V(s)|)
    如果 Δ < θ:
        终止循环  // V ≈ v_*

// 从收敛的 V 中提取确定性最优策略 π_*
初始化 π(s) 任意地 // 或者直接在下一步中赋值
对于 每个状态 s ∈ S:
  // 根据最优价值函数 V 选择最优动作
  π(s) = argmax[a] Σ[s',r] p(s',r|s,a) * (r + γ * V(s'))

输出 π

plaintext

DP 算法总结与比较#

解决的问题类型	基于的贝尔曼方程	主要 DP 算法
预测 (评估策略)	贝尔曼期望方程	迭代策略评估
控制 (寻找最优)	贝尔曼期望 + 贪心改进	策略迭代 (PI)
控制 (寻找最优)	贝尔曼最优方程	价值迭代 (VI)

所有这些基本的 DP 算法都依赖于状态价值函数 $v(s)$ (或动作价值函数 $q(s, a)$ ) 的迭代更新。
每次同步迭代 (遍历所有状态) 的计算复杂度大致为 $O(|\mathcal{S}|^2|\mathcal{A}|)$ (对于基于 $v$ 的更新)。如果状态转移是稀疏的，可能会更低。

异步动态规划#

上述的 同步 DP 算法在每次迭代中都需要对整个状态集进行一次完整的扫描和更新。当状态空间很大时，这会非常耗时。异步 DP 放宽了这一要求，允许更灵活的更新方式。

核心思想: 不进行全局同步扫描，而是以任意顺序、选择性地备份状态的价值。更新一个状态的价值时，使用其他状态的最新可用值。
优点:
- 减少计算量: 可以避免对价值已经收敛或变化不大的状态进行计算。
- 聚焦计算: 可以优先更新那些与目标相关、或者贝尔曼误差较大的状态。
- 可能更快收敛: 有时通过优先更新关键状态，能够更快地传播价值信息。
收敛性: 只要保证所有状态最终都会被持续地 (无限次地) 选中进行更新，异步 DP 仍然能够收敛到正确的价值函数 ( $v_\pi$ 或 $v_*$ )。
常见变种:
- 原位 DP (In-place DP): 只维护一份价值函数数组 $V(s)$ ，更新时立即写入，后续状态的更新会直接使用这个新值。更新顺序变得重要。
- 优先级扫描 (Prioritized Sweeping): 维护一个优先级队列，根据状态的 贝尔曼误差 (当前价值与备份后价值的差) 的大小来决定更新哪个状态。优先更新误差较大的状态，并将更新的影响传播给其前驱状态 (那些可能转移到当前状态的状态)。
- 实时 DP (Real-time DP): 只更新智能体在与环境 (或模拟环境) 交互过程中实际访问到的状态 $S_t$ 。非常适用于状态空间巨大，但智能体实际能到达或关心的状态子集有限的情况。

DP 的局限性与展望#

尽管 DP 是理解 RL 价值函数和最优策略的基础，但它有两大主要局限性:

维度诅咒 (Curse of Dimensionality): DP 算法的计算和存储需求随着状态数量 $|\mathcal{S}|$ (有时还有动作数量 $|\mathcal{A}|$ ) 的增长而急剧增加 (通常是多项式级别，如 $O(|\mathcal{S}|^2|\mathcal{A}|)$ )。对于状态空间非常庞大的现实问题 (如围棋、机器人控制)，DP 变得不可行。
需要完美的环境模型 (Requires a Perfect Environment Model): DP 假设状态转移概率 $\mathcal{P}$ 和奖励函数 $\mathcal{R}$ 是完全已知的。然而，在许多实际应用中，我们无法事先获得精确的环境模型。

展望: 超越 DP

正是由于 DP 的这些局限性，特别是对模型的需求和计算复杂性问题，促使了 无模型 (Model-free) 强化方法的发展，例如 蒙特卡洛 (Monte Carlo) 和 时序差分 (Temporal Difference, TD) 学习。此外，为了解决维度诅咒问题，函数逼近 (Funcition Approximation) (如使用神经网络) 被引入来近似价值函数或策略，而不是使用表格存储，这引出了 深度强化学习 (Deep Reinforcement Learning)。

近似动态规划 (Approximate Dynamic Programming)

即使在有模型的情况下，如果状态空间过大，也可以使用函数逼近 (例如 $\hat{v}(s, w)$ 或 $\hat{q}(s, a, w)$ ，其中 $w$ 是参数) 来替代表格存储价值。DP 的备份操作可以用来生成训练样本:

选择一个状态 $s$ (或一批状态)。
使用当前的近似价值 $\hat{v}(s', w_k)$ 和贝尔曼 (最优或期望) 备份计算一个目标价值 $\tilde{v}_k(s)$ 。
将 $(s, \tilde{v}_k(s))$ 作为监督学习的样本，更新参数 $w$ 以最小化预测误差，得到 $w_{k+1}$ 和新的近似函数 $\hat{v}(s, w_{k+1})$ 。

这种方法结合了 DP 的思想和函数逼近的能力，有时也被称为 拟合价值迭代 (Fitted Value Iteration) 或相关方法。

小结 (Summary)#

动态规划提供了一套理论上保证找到最优策略 (在已知模型下) 的算法基础。
策略评估用于计算给定策略的价值 (预测问题)，基于贝尔曼期望方程。
策略迭代和价值迭代用于寻找最优策略 (控制问题)，分别基于贝尔曼期望方程+贪心改进和贝尔曼最优方程。
**广义策略迭代 (GPI)**是评估和改进相互作用以趋向最优的核心思想。
异步 DP提高了 DP 在实践中的效率，尤其适用于大规模问题。
DP 的主要缺点是对维度诅咒敏感和需要完美的环境模型，这激发了现代强化学习中无模型方法和函数逼近技术的发展。

本文参考如下:

[1] Axi’s Blog ↗

[2] Lou-uo’s Code（Cliff Walking Problem） ↗