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

本内容暂时为 PPT 转述，后续会进行修编

动态规划 (Dynamic Programming - DP)#

DP 概述#

定义与背景：DP 是一系列算法的总称，用于在给定完美环境模型 (MDP) 的情况下计算最优策略 $\pi_*$ 。这个术语由 Richard Bellman 创造。
核心思想：DP 利用价值函数 (Value Function) 的结构，特别是贝尔曼方程 (Bellman Equation)，来组织和简化最优策略的搜索过程。DP 适用于具有最优子结构 (Optimal Substructure) 和重叠子问题 (Overlapping Subproblems) 特征的问题，而 MDP 正好满足这些特征（贝尔曼方程体现了递归分解，价值函数计算会被复用）。
DP 用于 MDP 规划：
- 预测 (Prediction)：输入 MDP 和一个策略 $\pi$ ，输出该策略的价值函数 $v_\pi$ 。（评估一个给定的策略有多好）
- 控制 (Control)：输入 MDP，输出最优价值函数 $v_*$ 和最优策略 $\pi_*$ 。（找到最好的行为方式）
关键方程回顾：DP 算法的基础是最优价值函数 $v_*$ 和 $q_*$ 必须满足的贝尔曼最优方程： $v_*(s) = \max_{a} \sum_{s',r} p(s',r|s,a) [r + \gamma v_*(s')]$ $q_*(s,a) = \sum_{s',r} p(s',r|s,a) [r + \gamma \max_{a'} q_*(s', a')]$

策略评估 (Policy Evaluation / Prediction)#

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

方法：迭代应用贝尔曼期望方程 (Iterative Application of Bellman Expectation Backup)：
- 回顾贝尔曼期望方程： $v_\pi(s) = \sum_a \pi(a|s) \sum_{s',r} p(s',r|s,a) [r + \gamma v_\pi(s')]$
- 这为 $v_\pi$ 定义了一个线性方程组。DP 通过迭代的方式求解。
- 从一个任意的初始价值函数估计 $v_0$ 开始。
- 在第 $k+1$ 次迭代中，对所有状态 $s \in \mathcal{S}$ ，使用 $v_k$ 的值来计算新的价值估计 $v_{k+1}(s)$ ： $v_{k+1}(s) \leftarrow \sum_a \pi(a|s) \sum_{s',r} p(s',r|s,a) [r + \gamma v_k(s')]$ 或者使用模型定义的 $\mathcal{R}_s^a$ 和 $\mathcal{P}_{ss'}^a$ ： $v_{k+1}(s) \leftarrow \sum_{a \in \mathcal{A}} \pi(a|s) \left( \mathcal{R}_s^a + \gamma \sum_{s' \in \mathcal{S}} \mathcal{P}_{ss'}^a v_k(s') \right)$
- 这个过程称为同步备份 (Synchronous Backup)，因为所有状态的价值在一次迭代中同时更新（基于上一轮的旧值）。
收敛性：当 $k \to \infty$ 时，价值函数序列 $v_0, v_1, v_2, \dots$ 会收敛到真实的 $v_\pi$ 。这基于贝尔曼期望算子是一个压缩映射 (Contraction Mapping) 的性质。

算法：迭代策略评估 (Iterative Policy Evaluation)：

初始化 V(s) = 0 对所有 s
循环 直到收敛:
    Δ = 0  // 初始化最大变化量
    对于 每个状态 s:
        v = V(s)  // 存储旧值
        // 应用贝尔曼期望备份
        V(s) = Σ[a] π(a|s) * Σ[s',r] p(s',r|s,a) * (r + γ * V(s'))
        Δ = max(Δ, |v - V(s)|) // 更新最大变化量
    如果 Δ < θ (一个小的阈值):
        终止循环
输出 V ≈ v_π

plaintext

例子：小网格世界 (Small Gridworld)：展示了在一个 4x4 网格中，对于一个均匀随机策略，价值函数 $v_k$ 如何随着迭代次数 $k$ 逐渐收敛到 $v_\pi$ 。

策略迭代 (Policy Iteration / Control)#

策略迭代是一种寻找最优策略 $\pi_*$ 的经典 DP 算法。它通过交替进行策略评估和策略改进来逐步逼近最优解。

核心思想：
1. 从一个任意初始策略 $\pi_0$ 开始。
2. 重复以下两个步骤：
  - (E) 策略评估 (Policy Evaluation)：计算当前策略 $\pi_k$ 的价值函数 $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) \leftarrow \arg\max_{a \in \mathcal{A}} q_{\pi_k}(s, a) = \arg\max_{a \in \mathcal{A}} \left\{ \mathcal{R}_s^a + \gamma \sum_{s' \in \mathcal{S}} \mathcal{P}_{ss'}^a v_{\pi_k}(s') \right\}$
策略改进定理 (Policy Improvement Theorem)：
- 定理保证：通过对 $v_\pi$ 贪心得到的策略 $\pi'$ ，其价值函数 $v_{\pi'}(s)$ 对于所有状态 $s$ 来说，都大于或等于 $v_\pi(s)$ ( $v_{\pi'} \ge v_\pi$ )。
- 收敛性：如果策略改进步骤没有改变策略（即 $\pi_{k+1} = \pi_k$ ），那么当前的价值函数 $v_{\pi_k}$ 必定满足贝尔曼最优方程，即 $v_{\pi_k} = v_*$ ，且 $\pi_k$ 是最优策略 $\pi_*$ 。由于状态和动作空间有限时，策略的数量也是有限的，因此策略迭代保证在有限次迭代内收敛到最优策略。

算法：策略迭代 (Policy Iteration)：

1. 初始化 V(s) 和 π(s) 任意
2. 循环:
    // 策略评估 (计算 v_π)
    循环 直到 V 收敛:
        Δ = 0
        对于 每个状态 s:
            v = V(s)
            V(s) = Σ[s',r] p(s',r|s, π(s)) * (r + γ * V(s')) // 注意这里用了 π(s)
            Δ = max(Δ, |v - V(s)|)
        如果 Δ < θ: 终止内循环

    // 策略改进
    policy_stable = true
    对于 每个状态 s:
        old_action = π(s)
        // 找到最大化 q_π(s,a) 的动作
        π(s) = argmax[a] Σ[s',r] p(s',r|s, a) * (r + γ * V(s'))
        如果 old_action != π(s):
            policy_stable = false

    如果 policy_stable:
        终止外循环，返回 V 和 π

plaintext

价值迭代 (Value Iteration / Control)#

价值迭代是另一种寻找最优策略 $\pi_*$ 的 DP 算法。它直接迭代贝尔曼最优方程。

核心思想：策略迭代中的策略评估步骤可能需要多次迭代才能收敛。价值迭代通过将一步策略评估（即一次贝尔曼备份）和策略改进（即 max 操作）结合到单次更新中，来直接逼近最优价值函数 $v_*$ 。
更新规则：从任意初始价值函数 $v_0$ 开始，迭代更新： $v_{k+1}(s) \leftarrow \max_{a \in \mathcal{A}} \left\{ \mathcal{R}_s^a + \gamma \sum_{s' \in \mathcal{S}} \mathcal{P}_{ss'}^a v_k(s') \right\}$ 这直接应用了贝尔曼最优方程作为迭代更新规则。
收敛性：当 $k \to \infty$ 时， $v_k$ 会收敛到最优价值函数 $v_*$ 。这同样基于贝尔曼最优算子是压缩映射的性质。
与策略迭代的区别：价值迭代的中间价值函数 $v_k$ 不一定对应任何特定策略的价值函数。它直接逼近 $v_*$ 。

算法：价值迭代 (Value Iteration) (Page 26)：

初始化 V(s) = 0 对所有 s
循环 直到收敛:
    Δ = 0
    对于 每个状态 s:
        v = V(s)
        // 应用贝尔曼最优备份
        V(s) = max[a] Σ[s',r] p(s',r|s,a) * (r + γ * V(s'))
        Δ = max(Δ, |v - V(s)|)
    如果 Δ < θ:
        终止循环
// 输出确定性最优策略
对于 每个状态 s:
    π(s) = argmax[a] Σ[s',r] p(s',r|s,a) * (r + γ * V(s'))
输出 π

plaintext

DP 算法总结与比较#

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

所有这些算法都基于状态价值函数 $v(s)$ （或动作价值函数 $q(s,a)$ ）。
每次迭代的计算复杂度大致为 $O(|\mathcal{S}|^2 |\mathcal{A}|)$ (对于 $v$ ) 或 $O(|\mathcal{S}|^2 |\mathcal{A}|^2)$ (对于 $q$ )，取决于具体实现和稀疏性。

异步动态规划 (Asynchronous DP)#

同步 DP（如上所述）在每次迭代中需要对所有状态进行备份。异步 DP 放宽了这个要求。

核心思想：以任意顺序、选择性地更新状态的价值，而不是每次都进行全局扫描。更新时使用其他状态的最新可用值。
优点：
- 减少计算量：可以跳过某些状态的更新。
- 聚焦计算：可以优先更新更重要或值变化更快的状态。
- 更快收敛：有时每次迭代能取得更大进展。
收敛性：只要保证所有状态最终都会被持续地选中进行更新，异步 DP 仍然能收敛。
常见变种：
- 原位 DP (In-place DP)：只维护一份价值函数数组 $V(s)$ ，更新时直接修改它。更新顺序会影响结果和收敛速度。
- 优先级扫描 (Prioritized Sweeping)：根据贝尔曼误差的大小来决定更新哪个状态的优先级。维护一个优先级队列，优先更新误差最大的状态，并将更新效果传播给其前驱状态。
- 实时 DP (Real-time DP)：只更新智能体在与环境（或模拟环境）交互过程中实际访问到的状态 $S_t$ 。非常适用于状态空间巨大但只有部分可达或相关的场景。

DP 的局限性#

维度诅咒 (Curse of Dimensionality)：DP 算法的计算复杂度随状态数量 $|\mathcal{S}|$ （有时还有动作数量 $|\mathcal{A}|$ ）的增长而急剧增加。对于状态空间非常大的问题，DP 变得不可行。
需要完整模型 (Requires a Perfect Model)：DP 假设 $\mathcal{P}$ 和 $\mathcal{R}$ 完全已知，这在许多现实问题中是不满足的。

广义策略迭代 (Generalized Policy Iteration - GPI)#

GPI 是一个通用框架，描述了策略评估和策略改进这两个过程如何相互作用以趋向最优解。
几乎所有的强化学习算法都可以看作是 GPI 的某种实现，只是它们在如何进行评估和改进（精确/近似、同步/异步、采样/全备份等）方面有所不同。

近似动态规划 (Approximate Dynamic Programming)#

当状态空间过大时，用函数逼近 (Function Approximation) $\hat{v}(s, w)$ 或 $\hat{q}(s, a, w)$ 来代替表格存储价值函数。 $w$ 是逼近函数的参数（例如神经网络的权重）。
DP 算法（如价值迭代）与函数逼近结合：
1. 从样本状态 $\tilde{\mathcal{S}}$ 中选择状态 $s$ 。
2. 使用当前的近似价值 $\hat{v}(s', w_k)$ 和贝尔曼（最优）备份计算目标价值 $\tilde{v}_k(s)$ 。
3. 将 $(s, \tilde{v}_k(s))$ 作为训练数据，通过监督学习更新参数 $w$ ，得到新的近似价值函数 $\hat{v}(s, w_{k+1})$ 。

小结 (Summary)#

DP 提供了一套基于模型的求解 MDP 最优策略的方法。
策略评估：计算给定策略的价值函数 (使用贝尔曼期望方程)。
策略迭代：交替进行策略评估和策略改进。
价值迭代：直接迭代贝尔曼最优方程。
GPI 是这些方法背后的通用思想。
异步 DP 通过非全局扫描更新来提高效率。
DP 的主要缺点是需要完整模型和对维度诅咒敏感。