3 基于动态规划的强化学习方法

我们的目标是：不仅知道动态规划在强化学习里怎么用，更要理解 为什么能用，以及 怎样从基本思想一步步生长出策略迭代、值迭代和截断策略迭代这些算法 。

1. 引言：强化学习的骨架——马尔可夫决策过程#

在聊动态规划之前，我们必须先快速建好一个舞台——马尔可夫决策过程 (MDP)。强化学习要解决的问题，几乎都可以形式化为 MDP。

想象一个网格世界，一个智能体要从左上角走到右下角，避开陷阱，捡到宝石。这个场景天然包含几个要素：

状态 (State)：智能体在哪个格子，比如坐标 (1,1) 到 (4,4)。
动作 (Action)：向上、向下、向左、向右。
奖励 (Reward)：踩到宝石 +1，掉进陷阱 -1，其他每走一步 -0.01（鼓励尽快到达）。
状态转移概率 $P(s'|s,a)$ ：给定当前状态 $s$ 和动作 $a$ ，到达下一个状态 $s'$ 的概率。比如机器人可能因地面湿滑，有 20%概率滑向别的方向。
折扣因子 $\gamma \in [0,1]$ ：未来奖励的折扣程度。

MDP 的核心假设——马尔可夫性：下一状态只依赖于当前状态和动作，与历史无关。这个假设让我们能递归地定义“长期收益”。

给定一个策略 $\pi(a|s)$ （在状态 $s$ 选各动作的概率），从状态 $s$ 出发的期望回报就是状态价值函数：

v_\pi(s) = \mathbb{E}_\pi\left[ \sum_{t=0}^\infty \gamma^t R_{t+1} \mid S_0 = s \right]

通过全概率展开，我们得到著名的贝尔曼期望方程：

v_\pi(s) = \sum_a \pi(a|s) \sum_{s'} P(s'|s,a) \left[ R(s,a,s') + \gamma v_\pi(s') \right]

也就是说，一个状态的价值，等于即时奖励加上下一状态价值的期望折现值。这个方程看上去简单，但它揭示了价值函数的自洽性——我们后面所有动态规划算法，本质上都是在不断强制这种自洽性成立。

例子 1（4×4 网格世界）：假设智能体策略是“均匀随机行走”， $\gamma=0.9$ 。计算状态(4,4)是终点， $v(4,4)=0$ 。那么状态(4,3)的值，就等于向右走的期望回报： $-0.01 + 0.9 \times 1 \times 0 = -0.01$ （若确定转移）。但实际上随机策略有概率走到别处，所以值会略有不同。通过贝尔曼方程，我们可以从终点倒推每个格子的值。

现在的问题是：如果环境模型（ $P$ 和 $R$ ）完全已知，我们要么找出最优策略，要么评估某个策略的值，该怎么做？这便引入了动态规划。

2. 动态规划引入：贝尔曼方程的另一种视角#

2.1 什么是动态规划#

“动态规划 (Dynamic Programming, DP)”这个名词里的“规划”，不是编程，而是规划 (Planning)，即在已知环境模型的前提下，进行推理和优化。Bellman 在 1950 年代提出 DP 时，核心思想就两条：

最优子结构：一个问题的最优解包含其子问题的最优解。
重叠子问题：递归求解时，同样的子问题被反复计算。

在 MDP 中，这两个性质体现得淋漓尽致：价值函数定义本身就是递归的；同一个状态的价值在评估多个策略时会反复用到。

2.2 强化学习为什么能使用动态规划？#

回答这个问题，只需看 DP 的两个前提条件在我们这里是否满足：

最优子结构存在吗？ 是的。贝尔曼最优方程给出了最优价值函数的递归定义：
$v_*(s) = \max_a \sum_{s'} P(s'|s,a) \left[ R(s,a,s') + \gamma v_*(s') \right]$
最优策略的长期收益最大值，等于当前最佳动作带来的即时收益加上后续最优收益。
重叠子问题存在吗？ 是的。整个 MDP 的状态空间是有限的，价值函数对每个状态都需要求解，而相邻状态的值相互依赖，天然是一个包含大量重叠的方程组。

但还有一个更实际的约束：MDP 模型完全已知。在“规划”问题里， $P$ 和 $R$ 都是已知的，这允许我们直接使用 DP 进行迭代求解。强化学习中的很多问题（如围棋棋盘、机器人控制）模型未知或难以精确建模，那时就需要模型自由的方法。但理解 DP 是理解一切强化学习的起点。

小结：如果 MDP 已知且状态-动作空间不太大，DP 就能大展拳脚。

3. 策略迭代：先评后改，循环往复#

策略迭代是 DP 最直接的体现，包含两步：策略评估 和 策略改进。

3.1 策略评估（Policy Evaluation）#

给定一个策略 $\pi$ ，我们想计算它的价值函数 $v_\pi$ 。贝尔曼期望方程给出了一个方程组，对每个状态 $s$ ：

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) \leftarrow \sum_a \pi(a|s) \sum_{s'} P(s'|s,a) [R + \gamma v_k(s')]

这被称为迭代策略评估。理论上，当 $k \to \infty$ ， $v_k$ 会收敛到 $v_\pi$ 。

3.2 策略改进（Policy Improvement）#

有了 $v_\pi$ ，我们可以问：在当前状态 $s$ ，是否有一个动作 $a$ 比遵循 $\pi$ 带来更高收益？只需计算动作价值函数：

q_\pi(s,a) = \sum_{s'} P(s'|s,a)[R + \gamma v_\pi(s')]

如果存在 $a$ 使得 $q_\pi(s,a) > v_\pi(s)$ ，那么把 $s$ 的策略改为始终选 $a$ ，就得到了一个更好的策略。正式地，产生新策略 $\pi'$ ：

\pi'(s) = \arg\max_a q_\pi(s,a)

这就是策略改进定理，保证 $\pi'$ 严格优于 $\pi$ （除非 $\pi$ 已是最优）。

3.3 策略迭代算法#

将评估和改进结合：

初始化 $v(s)$ 和 $\pi(s)$ 任意。
策略评估：循环更新 $v(s)$ 直到收敛（或变化足够小）。
策略改进：对每个状态，更新策略 $\pi(s) \leftarrow \arg\max_a q_\pi(s,a)$ 。
若策略不再变化，停止；否则回到步骤 2。

例子 2（网格世界策略迭代）
还是 4×4 网格，终点(4,4)，陷阱(2,2)， $\gamma=0.9$ 。初始策略：全向上。

第一轮策略评估：计算出向上策略的价值。发现(1,1)的价值很低，因为向上撞墙。(3,4)价值较高，因为向右可快速到终点。
策略改进：在(3,4)处，计算各动作的 $q$ 值，发现向右的 $q$ 值最大，策略改为向右；在(1,1)处，向下 $q$ 值更大，策略改为向下。
重复评估-改进，最终得到最优策略：从任何格子出发都沿着最优路径走向(4,4)，避开(2,2)。

这个过程就像“自我反省”：先完整地把当前策略的后果想清楚（评估），再据此调整行动（改进）。

4. 值迭代：一步到位，省去漫长的评估#

策略迭代每轮都要把 $v_\pi$ 算到收敛，这在大型问题中开销巨大。我们能否在一次迭代中同时做评估和改进？这就是值迭代。

回忆贝尔曼最优方程：

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

它本身就是一个不动点方程。我们可以直接从任意 $v_0$ 开始，反复应用最优备份：

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

这个更新规则不需要策略，直接在值函数上贪婪地取 max。它就是值迭代。

值迭代可以看作策略迭代的极限情况：在策略评估阶段，我们只做一次全扫描，然后就进行策略改进（即贪婪选择 max），但其实 max 操作已经内嵌了改进。更准确地说，值迭代是在 $v$ 上直接运行贝尔曼最优备份，直到收敛。收敛后，最优策略就是：

\pi_*(s) = \arg\max_a \sum_{s'} P(s'|s,a)[R + \gamma v_*(s')]

例子 3（最短路径问题）
考虑一个最短路径 MDP：状态为节点，每走一步奖励 $-1$ ，直到到达终点， $\gamma=1$ （无折扣）。这是一个确定性环境。

初始 $v_0(s)=0$ 对所有非终点，终点值恒为 0。
第一轮值迭代：对每个节点， $v_1(s) = \max_a [-1 + v_0(s')] = -1$ （因为 $v_0(s')=0$ ）。这样相邻终点的节点获得价值-1。
第二轮：这些节点的邻居再往外传，价值变成-2。不断向外扩散，最终每个节点的 $v$ 值就是负的最短距离。这正是经典的 Bellman-Ford 算法思想。每一步，信息从终点向外传播一个距离单位。

例子 4（赌徒问题）
赌徒有资金 $s \in \{1,2,\dots,99\}$ ，目标是达到 100。每轮可下注 $a \in \{1,\dots,\min(s,100-s)\}$ ，以概率 $p=0.4$ 赢（资金+ $a$ ），否则输（资金- $a$ ）。奖励在达到 100 时为+1，其他为 0。 $\gamma=1$ 。

状态空间 101 个（含 0 和 100 吸收态）。
值迭代：初始化 $v_0(s)=0$ ，终点 $v(100)=1, v(0)=0$ 。
迭代过程： $v_{k+1}(s) = \max_a [0.4 v_k(s+a) + 0.6 v_k(s-a)]$ 。随着 $k$ 增大，赢的概率信息从 100 传播回小资金状态。观察值函数的形状会是一个有趣的阶梯状，反映最优下注策略（通常倾向于大胆下注）。这个例子很好地展示了值迭代如何处理概率性 MDP。

值迭代的优势是简单，每轮只需 $O(|S|^2 |A|)$ 或类似复杂度的一次扫描。但它每次更新都取 max，容易在早期高估，不过收敛是有保证的。

5. 截断策略迭代：在两种极端之间自由游走#

5.1 广义策略迭代（GPI）#

策略迭代和值迭代其实是两个极端：一个是评估到收敛再改进，一个是评估一步就改进。实际上，任何评估与改进交替进行的过程，都称为广义策略迭代 (GPI)。评估让价值与当前策略一致，改进让策略相对当前价值变得贪婪；两者相互驱动，直到同时达到稳定，即最优。

5.2 截断策略迭代#

截断策略迭代（Truncated Policy Iteration）就是在策略评估时，不等到收敛，只做固定次数的迭代（如 $m$ 次），然后停止评估并改进策略。当 $m=1$ 时，它退化为值迭代；当 $m=\infty$ 时，就是策略迭代。所以它是一个灵活的算法族。

为什么需要它？ 在大型状态空间中，策略迭代的完全评估太慢，值迭代的 max 更新又可能振荡、收敛也不总是最快。适当多评估几次（ $m>1$ ）常能显著加速总收敛时间——用更少的全局扫描次数得到最优解。

例子 5（网格世界加速对比）
同一网格世界任务，比较三种方法达到收敛所需的扫描次数：

策略迭代：每次评估需约 200 次扫描（收敛门槛很小），但改进后策略跳变得大，总扫描次数可能中等。

值迭代：每次只做 1 次评估扫描，但需要上千次迭代才收敛。

截断策略迭代（ $m=10$ ）：每次评估 10 次扫描，策略改进更快，总扫描次数可能远小于前两者。这直观体现了：少量额外的评估可以带来更“稳定”的价值估计，使策略改进更准确，避免值迭代中因贪婪造成的“短视震荡”。

算法伪代码：

初始化 v(s) 任意，π(s) 任意
循环：
    # 截断策略评估：对当前 π，进行 m 次更新
    重复 m 次：
        对每个状态 s：
            v(s) ← Σ_a π(a|s) Σ_{s'} P(s'|s,a)[R + γ v(s')]
    # 策略改进
    对每个状态 s：
        π_old(s) ← π(s)
        π(s) ← argmax_a Σ_{s'} P(s'|s,a)[R + γ v(s')]
    若 π 未改变，跳出循环
返回 π 和 v

plaintext

这个框架揭示了强化学习方法的核心哲学：评估与改进的交替。这不仅是 DP，之后的蒙特卡洛、TD 学习等无非是把未知模型下的采样引入进来，但 GPi 结构永恒不变。

6. 总结与展望#

我们今天从 MDP 出发，认识了状态价值函数和贝尔曼方程，这为动态规划提供了理论上的“最优子结构”和“重叠子问题”性质。当模型已知时，DP 便成为求解最优策略的利器。

我们依次探讨了：

策略迭代：完整评估当前策略，然后贪婪改进，循环往复。
值迭代：将评估与改进融合在一步贝尔曼最优备份中，省去完整评估。
截断策略迭代：在评估过程中只做有限次迭代，是前两者的折中，常常在实践中收敛最快。

每一个算法都在回答同一个核心问题：如何利用递归结构，高效地计算出每个状态的长期价值，并从中提炼出最优行为。

下一步的伏笔：

当模型 $P, R$ 未知时，DP 无法直接应用，我们需要从与环境交互的数据中学习——这导向蒙特卡洛方法和时序差分学习 (TD)。
当状态空间巨大或连续时，表格型 DP 不适用，我们需要引入函数逼近（如神经网络）——这导向深度强化学习。

但无论走多远，DP 中的贝尔曼方程、价值函数自洽性、以及广义策略迭代的结构，始终是支撑整个强化学习大厦的根基。

讨论与问答环节（开放）#

欢迎大家提出问题。如果时间有余，我们可以围绕以下问题进行讨论：

策略迭代中，策略评估到底需要多精确？不精确的评估会不会导致改进失效？
值迭代和策略迭代在收敛速度上的理论保证是什么？
截断策略迭代中 $m$ 如何选择？有没有自适应的方法？