RL笔记（4）：动态规划

引言（Introduction）#

动态规划（DP）在强化学习中指的是在环境模型已知（即状态转移概率 $\mathcal{P}$ 和奖励函数 $\mathcal{R}$ 已知）的情况下，计算最优策略的一类算法。 DP 的核心思想是将复杂问题分解为子问题，通过求解子问题来求解原问题。在 MDP 中，这体现为利用贝尔曼方程进行迭代更新。

策略迭代 (Policy Iteration)#

核心思想： “先以此为据，算个清楚；再择优而行。” 策略迭代将求解过程严格拆分为两个交替的步骤，直到策略不再改变。

• 步骤一：策略评估 (Policy Evaluation)：在当前策略 $\pi$ 固定不变的情况下，计算出该策略下精确的状态价值函数 $V^\pi$。这意味着在这个步骤里，我们通常需要多次迭代（或者解线性方程组）直到 $V^\pi$ 完全收敛。
• 步骤二：策略提升 (Policy Improvement)：基于刚刚算出来的精确 $V^\pi$，贪心地更新策略。即对于每个状态，选择那个能带来最大期望回报的动作 $\pi^\prime(s)=\arg\max_{a} Q^\pi(s,a)$。

特点： 收敛所需的迭代步数少，但每一步内部的计算量大（因为策略评估需要很久）。

策略评估（Policy Evaluation）#

策略评估的目标是求解给定策略 $\pi$ 的状态价值函数 $V^\pi$。 对于策略 $\pi$，状态价值函数满足贝尔曼期望方程：

$$V^\pi(s)=\sum_{a\in \mathcal{A}}\pi(a|s)(\mathcal{R}(s,a)+\gamma\sum_{s^\prime\in \mathcal{S}}\mathcal{P}(s^\prime|s,a)V^\pi(s^\prime))$$

这构成了一个线性方程组，但在状态空间较大时直接求解困难，因此采用迭代法。

贝尔曼迭代（Bellman Iteration）#

将当前时刻估计的价值函数 $V_k$ 代入贝尔曼方程右侧，计算下一轮的估计 $V_{k+1}$ ：

$$V_{k+1}(s)\leftarrow\sum_{a\in\mathcal{A}}\pi(a|s)(\mathcal{R}(s,a)+\gamma\sum_{s^\prime\in\mathcal{S}}\mathcal{P}(s^\prime|s,a)V_{k}(s^\prime))$$

随机选定初始值 $V_0$ ，当 $k\rightarrow\infin$ 时，序列 $\{ V_k \}$ 会收敛到 $V^\pi$ 。 为了方便证明收敛性，定义贝尔曼算子为 $\mathcal{T}^\pi$：

$$\mathcal{T}^\pi V_k = \sum_{a\in\mathcal{A}}\pi(a|s)(\mathcal{R}(s,a)+\gamma\sum_{s^\prime\in\mathcal{S}}\mathcal{P}(s^\prime|s,a)V_{k}(s^\prime))$$

收敛性证明（Banach不动点定理）#

为了证明序列 $\{ V_k \}$ 收敛于 $V^\pi$，我们将迭代过程看作算子 $\mathcal{T}^\pi$ 的应用：

$$V_{k+1}=\mathcal{T}^\pi V_k$$

证明步骤如下：

1. 定义范数：采用无穷范数 $\parallel V \parallel_\infty=\max_{s\in \mathcal{S}} | V(s)|$；
2. 压缩映射性质：对于任意两个价值函数 $U, V$，有： $$\begin{align} \parallel \mathcal{T}^\pi U - \mathcal{T}^\pi V \parallel_\infty &= \max_{s} | \gamma \sum_{a}\pi(a|s)\sum_{s^\prime}\mathcal{P}(s^\prime|s,a)(U(s^\prime)-V(s^\prime)) | \notag \\ &\leqslant \gamma \max_{s} \sum_{a}\pi(a|s)\sum_{s^\prime}\mathcal{P}(s^\prime|s,a) |U(s^\prime)-V(s^\prime)| \notag \\ &\leqslant \gamma \max_{s} \sum_{a}\pi(a|s)\sum_{s^\prime}\mathcal{P}(s^\prime|s,a) \parallel U - V \parallel_\infty \notag \\ &= \gamma \parallel U - V \parallel_\infty \notag \end{align}$$
3. 结论：只要折扣因子 satisfying $0 \le \gamma < 1$，算子 $\mathcal{T}^\pi$ 就是一个$\gamma$-压缩映射（Contraction Mapping）。根据 Banach 不动点定理，序列 $\{V_k\}$ 必收敛于唯一的固定点 $V^\pi$。

策略提升（Policy Improvement）#

在计算出 $V^\pi$ 后，我们需要判断当前策略是否最优。如果不是，如何改进？

策略提升理论（Policy Improvement Theorem）#

给定策略 $\pi$ 和其价值函数 $V^\pi$，构造新策略 $\pi^\prime$ 使得其在每个状态下都贪心地选择动作价值最大的动作：

$$\pi^\prime(s) = \argmax_{a\in\mathcal{A}} Q^\pi(s,a) = \argmax_{a\in\mathcal{A}} \left( r(s,a)+\gamma\sum_{s^\prime \in\mathcal{S}}\mathcal{P}(s^\prime|s,a)V^\pi(s^\prime) \right)$$

定理保证：

1. $V^{\pi^\prime}(s) \geqslant V^\pi(s), \forall s \in \mathcal{S}$（策略单调递增）。
2. 如果 $V^{\pi^\prime}(s) = V^\pi(s)$，则 $\pi$ 已经是与最优策略 $V^*$ 等价的策略。

理论证明（Theorem Proof）#

证明：对于任何状态 $s$，满足$V^{\pi^\prime}(s)\geqslant V^\pi(s)$。 证明思路：利用 $V^\pi(s) \leqslant \max_a Q^\pi(s,a) = Q^\pi(s, \pi^\prime(s))$，反复展开 $Q^\pi$ 即可证。

状态价值函数和动作价值函数之间的关系：

$$V^\pi(s)=\sum_{a\in\mathcal{A}}\pi(a|s)Q^\pi(s,a)$$

经过推导，可以得出：

$$\begin{align} V^\pi(s)&=\sum_{a\in\mathcal{A}}\pi(a|s)Q^\pi(s,a) \notag \\ &\leqslant \max_{a\in\mathcal{A}} Q^\pi(s,a) \notag \\ &=\max_{a\in\mathcal{A}} \left( r(s,a) + \gamma \sum_{s^\prime\in\mathcal{S}} \mathcal{P}(s^\prime|s,a) V^\pi(s^\prime)\right) \notag \\ &= Q^\pi(s,\pi^\prime(s)) \notag \\ \end{align}$$

有了 $V^\pi(s)\leqslant Q^\pi(s,\pi^\prime(s))$，可以进一步推导出：

$$\begin{align} V^\pi(s) &\leqslant Q^\pi(s,\pi^\prime(s)) \notag \\ &= \mathbb{E}_{\pi^\prime}[R_{t}+\gamma V^\pi(S_{t+1})|S_t=s] \notag \\ &\leqslant \mathbb{E}_{\pi^\prime}[R_t+\gamma Q^\pi(S_{t+1},\pi^\prime(S_{t+1}))|S_t=s]\notag \\ &= \mathbb{E}_{\pi^\prime}[R_t+\gamma R_{t+1}+\gamma^2V^\pi(S_{t+2})|S_t=s] \notag \\ &\leqslant \mathbb{E}_{\pi^\prime}[R_t+\gamma R_{t+1}+\gamma^2 R_{t+2} + \gamma^3 V^\pi(S_{t+3})|S_t=s] \notag \\ &\cdots \notag \\ &\leqslant \mathbb{E}_{\pi^\prime}[R_t+\gamma R_{t+1}+\gamma^2 R_{t+2} + \gamma^3 R_{t+3} + \cdots|S_t=s] \notag \\ &= V^{\pi^\prime}(s) \notag \end{align}$$

迭代算法（Iteration Algorithm）#

策略迭代交替进行“策略评估”和“策略提升”，直到策略不再变化。

流程：

$$\pi_0 \xrightarrow{E} V^{\pi_0} \xrightarrow{I} \pi_1 \xrightarrow{E} V^{\pi_1} \xrightarrow{I} \dots \xrightarrow{I} \pi_* \xrightarrow{E} V^*$$

算法伪代码：

1. 初始化：$V(s) \in \mathbb{R}$，$\pi(s) \in \mathcal{A}$ 任意。
2. 策略评估（循环直到收敛）：
   • $\Delta \leftarrow 0$
   • For each $s \in \mathcal{S}$:
     • $v \leftarrow V(s)$
     • $V(s) \leftarrow \sum_{s^\prime} \mathcal{P}(s^\prime|s,\pi(s))[\mathcal{R}(s,\pi(s)) + \gamma V(s^\prime)]$
     • $\Delta \leftarrow \max(\Delta, |v - V(s)|)$
   • 若 $\Delta < \theta$，停止评估。
3. 策略提升：
   • $policy\_stable \leftarrow true$
   • For each $s \in \mathcal{S}$:
     • $old\_action \leftarrow \pi(s)$
     • $\pi(s) \leftarrow \argmax_a \sum_{s^\prime} \mathcal{P}(s^\prime|s,a)[\mathcal{R}(s,a) + \gamma V(s^\prime)]$
     • If $old\_action \neq \pi(s)$, then $policy\_stable \leftarrow false$
   • If $policy\_stable$ is true，停止并返回 $V^*, \pi^*$；否则跳转至步骤 2。

注意：由于有限状态 MDP 的策略总数是有限的（$|\mathcal{A}|^{|\mathcal{S}|}$），且每次提升策略都严格（或非严格）变好，策略迭代保证在有限步内收敛。

价值迭代（Value Iteration）#

策略迭代的缺点是每次“策略评估”都需要迭代很多次直到完全收敛。 事实上，我们不需要等到 $V^\pi$ 完全收敛才进行策略提升。 如果将策略评估的迭代次数缩减为 1次，并结合策略提升，就得到了价值迭代。

贝尔曼最优迭代（Bellman Optimal Iteration）#

价值迭代直接迭代求解最优价值函数，基于贝尔曼最优方程进行迭代：

$$V_{k+1}(s) \leftarrow \max_{a\in\mathcal{A}} \left\{ \mathcal{R}(s,a) + \gamma \sum_{s^\prime \in \mathcal{S}} \mathcal{P}(s^\prime|s,a) V_k(s^\prime) \right\}$$

随机选定初始值 $V_0$ ，当 $k\rightarrow\infin$ 时，序列 $\{ V_k \}$ 会收敛到 $V^*$ 。为了方便证明收敛性，定义贝尔曼最优算子为 $\mathcal{T}^*$：

$$\mathcal{T}^* V_{k} = \max_{a\in\mathcal{A}} \left\{ \mathcal{R}(s,a) + \gamma \sum_{s^\prime \in \mathcal{S}} \mathcal{P}(s^\prime|s,a) V_k(s^\prime) \right\}$$

收敛性证明（Banach不动点定理）#

为了证明序列 $\{V_k\}$ 收敛于 $V^*$ ，将迭代过程看作算子 $\mathcal{T}^*$ 的应用：

$$V_{k+1} = \mathcal{T}^* V_k$$

证明步骤如下：

1. 定义范数：采用无穷范数 $||V||_{\infty}=\max_{s\in\mathcal{S}}|V(s)|$；
2. 压缩映射性质：对于 $\forall s\in\mathcal{S}$ 以及任意两个价值函数 $U,V$，有： $$\begin{align} |\mathcal{T}^* U(s) - \mathcal{T}^* V(s)| &=\left|\max_{a\in\mathcal{A}}\left\{\mathcal{R}(s,a)+\gamma\sum_{s^\prime\in\mathcal{S}}\mathcal{P}(s^\prime|s,a)U(s^\prime)\right\}-\max_{a\in\mathcal{A}}\left\{\mathcal{R}(s,a)+\gamma\sum_{s^\prime\in\mathcal{S}}\mathcal{P}(s^\prime|s,a)U(s^\prime)\right\}\right| \notag \\ &\leqslant \max_{a\in\mathcal{A}}\left|\gamma\sum_{s^\prime\in\mathcal{S}}\mathcal{P}(s^\prime|s,a)(U(s^\prime)-V(s^\prime))\right| \notag \\ &= \gamma\max_{a\in\mathcal{A}}\sum_{s^\prime\in\mathcal{S}}\mathcal{P}(s^\prime|s,a)\left|U(s)-V(s)\right| \notag \\ &\leqslant \gamma\max_{a\in\mathcal{A}}\sum_{s^\prime\in\mathcal{S}}\mathcal{P}(s^\prime|s,a)||U-V||_{\infty} \notag \\ &= \gamma ||U-V||_{\infty} \notag \end{align}$$
3. 对左式取最大值： $||\mathcal{T}^*U-\mathcal{T}^*V||_{\infty}\leqslant\gamma ||U-V||_{\infty}$
4. 结论：只要折扣因子 satisfying $0 \le \gamma < 1$，算子 $\mathcal{T}^*$ 就是一个$\gamma$-压缩映射（Contraction Mapping）。根据 Banach 不动点定理，序列 $\{V_k\}$ 必收敛于唯一的固定点 $V^*$。

迭代算法（Iteration Algorithm）#

1. 初始化：$V(s)$ 任意。
2. 迭代更新（Loop until $\Delta < \theta$）：
   • $\Delta \leftarrow 0$
   • For each $s \in \mathcal{S}$:
     • $v \leftarrow V(s)$
     • $V(s) \leftarrow \max_{a} \sum_{s^\prime\in\mathcal{S}} \mathcal{P}(s^\prime|s,a)[\mathcal{R}(s,a) + \gamma V(s^\prime)]$
     • $\Delta \leftarrow \max(\Delta, |v - V(s)|)$
3. 输出策略：
   • $\pi^*(s) = \argmax_{a} \sum_{s^\prime\in\mathcal{S}} \mathcal{P}(s^\prime|s,a)[\mathcal{R}(s,a) + \gamma V(s^\prime)]$

局限性（Limitation）#

动态规划方法（如策略迭代和价值迭代）是强化学习的理论基石，其核心优势在于理论完备性，利用自举（Bootstrapping）机制能够保证在有限步内稳定收敛至全局最优策略。 然而，其在实际应用中存在两大核心局限：一是强依赖完备的环境模型（Model-based），即必须预先知晓精确的状态转移概率和奖励函数，这在现实场景中往往难以满足； 二是受困于维数灾难（Curse of Dimensionality），随着状态变量增加，状态空间呈指数级膨胀，导致遍历所有状态进行全宽更新（Full-width Backup）在计算资源和存储空间上变得不可行，因此无法直接应用于大规模或连续状态空间的复杂问题。