Skip to content

动态规划

动态规划（Dynamic Programming, DP）是指在给定一个完美的环境模型（即MDP的完整知识）时，用于计算最优策略的一组算法。经典的DP算法在强化学习中的实际应用有限（因为它们要求完美模型且计算开销大），但在理论上非常重要——后续几乎所有的强化学习方法都可以看作是试图以更少的计算量、不需要完美环境模型来实现与DP相同效果的尝试。

前置知识： 在开始本章之前，需要先了解有限MDP的基本概念，包括状态价值函数 \(v_\pi(s)\)、动作价值函数 \(q_\pi(s,a)\)、贝尔曼方程等（参见有限MDP）。

DP的核心思想

DP的核心思想是利用贝尔曼方程作为更新规则，将价值函数的计算转化为迭代更新过程。

回顾贝尔曼期望方程（状态价值函数版本）：

\[ v_\pi(s) = \sum_a \pi(a|s) \sum_{s', r} p(s', r | s, a) [r + \gamma v_\pi(s')] \]

以及贝尔曼最优方程：

\[ v_*(s) = \max_a \sum_{s', r} p(s', r | s, a) [r + \gamma v_*(s')] \]

DP方法的关键假设是我们知道转移概率 \(p(s', r | s, a)\)，即完整的环境模型。

策略评估 (Policy Evaluation)

策略评估解决的问题是：给定一个策略 \(\pi\)，计算其状态价值函数 \(v_\pi\)。

迭代策略评估

将贝尔曼期望方程转化为迭代更新规则：

\[ v_{k+1}(s) = \sum_a \pi(a|s) \sum_{s', r} p(s', r | s, a) [r + \gamma v_k(s')], \quad \forall s \in \mathcal{S} \]

从任意初始值 \(v_0\) 开始（通常全部初始化为 0），不断迭代直到收敛。可以证明当 \(k \to \infty\) 时，\(v_k\) 收敛到 \(v_\pi\)。

算法流程：

  1. 初始化 \(V(s) = 0\)，对所有 \(s \in \mathcal{S}\)
  2. 重复以下步骤直到收敛（\(\Delta < \theta\)，其中 \(\theta\) 是一个很小的正数）：
    • \(\Delta \leftarrow 0\)
    • 对每个状态 \(s\)：
      • \(v \leftarrow V(s)\)
      • \(V(s) \leftarrow \sum_a \pi(a|s) \sum_{s', r} p(s', r | s, a) [r + \gamma V(s')]\)
      • \(\Delta \leftarrow \max(\Delta, |v - V(s)|)\)

更新方式： 上述算法使用"就地更新"（in-place update），即每次更新 \(V(s)\) 时使用的是其他状态已经更新后的新值。这通常比使用旧值更新（需要两个数组）收敛更快。

网格世界示例

考虑一个 4x4 的网格世界，左上角和右下角是终止状态。智能体在每个非终止状态有四个等概率动作（上下左右），每步奖励为 -1。

在均匀随机策略下（每个方向概率 0.25），迭代策略评估会逐步计算出每个状态的价值。距离终止状态越远的状态，价值越低（因为需要更多步才能到达终止状态，累积更多的 -1 奖励）。

策略改进 (Policy Improvement)

策略评估告诉我们一个策略有多好，而策略改进则是利用价值函数来找到更好的策略。

策略改进定理

对于策略 \(\pi\)，如果我们在状态 \(s\) 选择动作 \(a\) 使得 \(q_\pi(s, a) \geq v_\pi(s)\)，那么新策略至少和 \(\pi\) 一样好。

具体地，给定 \(v_\pi\)，我们可以构造一个贪心策略 \(\pi'\)：

\[ \pi'(s) = \arg\max_a q_\pi(s, a) = \arg\max_a \sum_{s', r} p(s', r | s, a) [r + \gamma v_\pi(s')] \]

这个贪心策略 \(\pi'\) 满足 \(v_{\pi'}(s) \geq v_\pi(s)\)，对所有 \(s\) 成立。当且仅当 \(\pi\) 已经是最优策略时，\(v_{\pi'} = v_\pi\)。

策略迭代 (Policy Iteration)

策略迭代将策略评估和策略改进交替进行，逐步逼近最优策略：

\[ \pi_0 \xrightarrow{\text{评估}} v_{\pi_0} \xrightarrow{\text{改进}} \pi_1 \xrightarrow{\text{评估}} v_{\pi_1} \xrightarrow{\text{改进}} \pi_2 \xrightarrow{\text{评估}} \cdots \xrightarrow{\text{改进}} \pi_* \xrightarrow{\text{评估}} v_* \]

算法流程：

  1. 初始化： 对所有 \(s\)，任意初始化 \(V(s)\) 和 \(\pi(s)\)
  2. 策略评估： 用迭代策略评估计算 \(V \approx v_\pi\)（直到收敛）
  3. 策略改进： 对每个 \(s\)，令 \(\pi(s) \leftarrow \arg\max_a \sum_{s',r} p(s',r|s,a)[r + \gamma V(s')]\)
  4. 如果策略没有变化，则停止；否则回到步骤 2

收敛性： 由于有限MDP只有有限多个策略，而每次策略改进都会严格改善策略（除非已经最优），因此策略迭代必然在有限步内收敛到最优策略 \(\pi_*\)。

值迭代 (Value Iteration)

策略迭代的一个缺点是每次迭代都需要完整的策略评估（多轮扫描），计算开销大。值迭代将策略评估截断为只做一轮扫描，同时融入策略改进：

\[ v_{k+1}(s) = \max_a \sum_{s', r} p(s', r | s, a) [r + \gamma v_k(s')] \]

这实际上就是贝尔曼最优方程的迭代版本。

算法流程：

  1. 初始化 \(V(s)\) 为任意值（终止状态为 0）
  2. 重复直到收敛：
    • 对每个状态 \(s\)：
      • \(V(s) \leftarrow \max_a \sum_{s',r} p(s',r|s,a)[r + \gamma V(s')]\)
  3. 收敛后，输出确定性最优策略：
    • \(\pi(s) = \arg\max_a \sum_{s',r} p(s',r|s,a)[r + \gamma V(s')]\)

与策略迭代的关系： 值迭代可以看作是策略迭代的特殊情况——每次策略评估只做一步就进行策略改进。实践中，值迭代通常比策略迭代更快收敛。

策略迭代 vs 值迭代

维度 策略迭代 值迭代
每轮操作 完整策略评估 + 策略改进 一步贝尔曼最优更新
收敛速度（轮数） 通常更少的外层迭代 通常需要更多的外层迭代
每轮计算量 大（完整策略评估） 小（一轮扫描）
总计算量 状态空间小时通常更快 状态空间大时通常更快

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

GPI 是一个贯穿整个强化学习的核心概念。它指的是策略评估和策略改进交互进行的一般性思想，不限于特定的实现方式：

  • 策略评估使价值函数向当前策略的真实价值靠拢
  • 策略改进使策略相对于当前价值函数变得贪心

这两个过程相互竞争又相互合作——评估和改进可以是完整的（如策略迭代），也可以是部分的（如值迭代），甚至可以交替进行（如后面章节的 TD 方法）。

本书后面介绍的几乎所有强化学习方法都可以用 GPI 的框架来理解：蒙特卡洛方法、TD 学习、Sarsa、Q-learning 等，它们的区别主要在于策略评估使用了什么方法（采样 vs 完整期望），以及评估和改进的频率。

DP的局限性

  • 需要完整的环境模型： 必须知道转移概率 \(p(s',r|s,a)\)，这在大多数实际问题中是不可获得的
  • 计算开销大： 每次更新需要遍历所有状态，状态空间大时不可行（"维数灾难"）
  • 存储需求高： 需要存储整个价值函数表

这些局限性催生了后续章节的方法：蒙特卡洛方法（不需要模型）、TD学习（不需要完整回合）、函数逼近（处理大状态空间）。

参考

  • Sutton & Barto, "Reinforcement Learning: An Introduction", 2nd Edition, Chapter 4

评论 #