一、DP 算法核心基础

（一）算法定位与本质

动态规划（Dynamic Programming, DP）是强化学习中最早用于求解最优策略的有模型算法框架，其本质是利用环境的完整模型（状态转移概率$P$和奖励函数$R$），通过递归分解问题、迭代优化价值函数，最终导出最优策略。它为后续无模型算法（如蒙特卡洛、时序差分）提供了核心思想范式，是理解强化学习 “预测 - 控制” 逻辑的基础。

（二）核心前提假设

DP 算法的有效运行依赖两个关键前提，这也是其与无模型算法的核心区别：

1. 环境完全可知：智能体已掌握状态转移概率$P(s^{\prime }|s,a)$（从状态$s$执行动作$a$转移到$s^{\prime }$的概率）和奖励函数$R(s,a)$（从状态$s$执行动作$a$的即时奖励期望），无需通过交互采样获取环境信息。

2. 状态空间有限：问题的状态空间$\mathcal{S}$和动作空间$\mathcal{A}$均为有限集，可通过表格形式存储价值函数和策略（即 “表格型 DP”）。

（三）与强化学习核心概念的关联

DP 算法深度依赖强化学习的基础要素，其优化逻辑可通过以下概念串联：

• 价值函数：DP 通过迭代更新状态价值函数$v_{\pi }(s)$或状态 - 动作价值函数$q_{\pi }(s,a)$实现策略评估；

• 贝尔曼方程：作为 DP 算法的数学核心，用于刻画价值函数的递归关系；

• 广义策略迭代（GPI）：DP 算法的核心框架，通过 “策略评估→策略提升” 的循环实现最优策略收敛。

二、DP 算法的数学核心：贝尔曼方程

（一）贝尔曼期望方程（策略评估基础）

对于给定策略$\pi$，状态价值函数$v_{\pi }(s)$满足贝尔曼期望方程，它将当前状态价值分解为即时奖励与未来状态价值的加权和：

$v_{\pi }(s)={\mathbb{E}}_{\pi }\left[R_{t+1}+\gamma v_{\pi }(S_{t+1})\mid S_t=s\right]$

结合环境模型可展开为：

$v_{\pi }(s)={\sum }_a\pi (a|s){\sum }_{s^{\prime }}P(s^{\prime }|s,a)\left[R(s,a)+\gamma v_{\pi }(s^{\prime })\right]$

• 含义：在策略$\pi$下，状态$s$的价值等于选择每个动作$a$的概率$\pi (a|s)$，乘以该动作带来的即时奖励$R(s,a)$与未来所有状态价值期望（加权折扣因子$\gamma$）之和。

（二）贝尔曼最优方程（策略优化目标）

当策略为最优策略${\pi }_{\ast }$时，价值函数满足贝尔曼最优方程，此时每个状态的价值等于选择最优动作后的最大期望回报：

$v_{\ast }(s)={\max }_a{\sum }_{s^{\prime }}P(s^{\prime }|s,a)\left[R(s,a)+\gamma v_{\ast }(s^{\prime })\right]$

• 核心逻辑：最优策略下，智能体在每个状态都会选择能最大化后续累积回报的动作，因此无需考虑动作选择概率（直接取最大值）。这是 DP 算法实现策略提升的数学依据。

（三）自举（Bootstrapping）特性

DP 算法的关键特征是自举—— 利用当前对未来状态价值的估计值来更新当前状态价值，而非等待完整交互序列的回报。例如，在计算$v_t(s)$时，会使用已有的估计值$v_t(s^{\prime })$进行更新，再得到$v_{t+1}(s)$，这一特性大幅提升了价值更新的效率。

三、核心 DP 算法：策略迭代与价值迭代

（一）策略迭代（Policy Iteration）

策略迭代是 DP 算法的经典实现，通过 “策略评估→策略提升” 的严格循环求解最优策略，收敛性可严格证明。

1. 算法流程

1. 初始化：

• 随机初始化策略${\pi }_0$（如每个状态下均匀选择动作）；

• 初始化状态价值函数$v_0(s)=0$（对所有$s\in \mathcal{S}$）；

• 设置折扣因子$\gamma$（通常取 0.9~0.99）和收敛阈值$\theta$（如$10^{-4}$）。

2. 策略评估（Policy Evaluation）：

• 基于当前策略${\pi }_t$，利用贝尔曼期望方程迭代更新价值函数，直至收敛：

$v_{t+1}(s)={\sum }_a{\pi }_t(a|s){\sum }_{s^{\prime }}P(s^{\prime }|s,a)\left[R(s,a)+\gamma v_t(s^{\prime })\right]$

• 收敛判断：当所有状态的价值更新量均小于$\theta$（即${\max }_s|v_{t+1}(s)-v_t(s)|<\theta$），停止评估，得到$v_{{\pi }_t}(s)$。

3. 策略提升（Policy Improvement）：

• 基于评估得到的$v_{{\pi }_t}(s)$，采用贪婪策略更新策略：

${\pi }_{t+1}(a|s)=\{\begin{array}{ll}1& \text{if }a=\arg {\max }_a{\sum }_{s^{\prime }}P(s^{\prime }|s,a)\left[R(s,a)+\gamma v_{{\pi }_t}(s^{\prime })\right]\\ 0& \text{otherwise}\end{array}$

• 含义：在每个状态$s$下，选择能最大化即时奖励与未来价值之和的动作，形成确定性的改进策略。

1. 收敛判断：

• 若${\pi }_{t+1}={\pi }_t$（策略不再变化），输出最优策略${\pi }_{\ast }={\pi }_t$和最优价值函数$v_{\ast }=v_{{\pi }_t}$；否则返回步骤 2。

2. 关键特性

• 策略迭代的策略提升过程保证了${\pi }_{t+1}$的性能不劣于${\pi }_t$（即$v_{{\pi }_{t+1}}(s)\ge v_{{\pi }_t}(s)$对所有$s$成立）；

• 由于状态空间有限，策略数量有限，迭代必然收敛到最优策略。

（二）价值迭代（Value Iteration）

价值迭代是对策略迭代的优化，通过 “直接优化价值函数→导出最优策略” 的方式，省略策略评估的完整收敛过程，效率更高。

1. 算法原理

价值迭代跳过策略评估的多次迭代，直接利用贝尔曼最优方程更新价值函数，本质是 “每次价值更新都隐含一次策略提升”。其核心公式为：

$v_{t+1}(s)={\max }_a{\sum }_{s^{\prime }}P(s^{\prime }|s,a)\left[R(s,a)+\gamma v_t(s^{\prime })\right]$

• 与策略迭代的区别：策略迭代需等待价值函数完全收敛后再提升策略，而价值迭代每次更新价值函数时均采用 “取最大值” 的贪婪操作，同步实现价值优化与策略改进。

2. 算法流程

1. 初始化：设置$v_0(s)=0$（所有$s\in \mathcal{S}$），给定$\gamma$和$\theta$。

2. 价值更新：对每个状态$s$，按贝尔曼最优方程计算$v_{t+1}(s)$。

3. 收敛判断：若${\max }_s|v_{t+1}(s)-v_t(s)|<\theta$，停止价值更新，得到最优价值函数$v_{\ast }$。

4. 导出最优策略：基于$v_{\ast }$采用贪婪策略生成${\pi }_{\ast }$：

${\pi }_{\ast }(a|s)=\arg {\max }_a{\sum }_{s^{\prime }}P(s^{\prime }|s,a)\left[R(s,a)+\gamma v_{\ast }(s^{\prime })\right]$

3. 适用场景

• 价值迭代无需存储中间策略，计算开销低于策略迭代；

• 更适用于状态空间较大但收敛速度快的场景，是实际应用中更常用的 DP 变种。

（三）两种迭代算法的对比

维度	策略迭代	价值迭代
核心逻辑	策略评估→策略提升（循环）	价值优化→策略导出（单阶段）
中间输出	一系列改进的策略	一系列优化的价值函数
计算效率	策略评估需多次迭代，开销较高	直接优化价值，开销较低
收敛速度	策略收敛快，价值收敛慢	价值收敛快，策略导出一步完成
适用场景	状态空间小，需观察策略改进过程	状态空间较大，追求计算效率

四、实例解析：网格世界（Grid World）

以 4×4 网格世界为例，直观展示价值迭代的运行过程：

• 环境设定：网格共 16 个状态（$s_{11}$~$s_{44}$），其中$s_{11}$为起点，$s_{44}$为终点（终止状态，奖励$R=0$）；

• 动作空间：上、下、左、右（若撞墙则停留在原状态）；

• 奖励函数：非终止状态执行动作后奖励$R=-1$（鼓励快速到达终点）；

• 状态转移：确定性转移（$P(s^{\prime }|s,a)=1$， if 动作有效，否则$P(s^{\prime }|s,a)=0$）；

• 参数设置：$\gamma =0.9$，$\theta =0.01$。

（一）迭代过程

1. 初始状态：所有非终止状态$v_0(s)=0$。

2. 第 1 次迭代：

• 对$s_{43}$（终点左侧）：执行 “右” 动作到达终点，价值$v_1(s_{43})={\max }_a[-1+0.9\times v_0(s^{\prime })]=-1+0.9\times 0=-1$；

• 对$s_{34}$（终点上方）：执行 “下” 动作到达终点，价值$v_1(s_{34})=-1$；

• 其他状态价值均为$-1+0.9\times 0=-1$。

2. 第 2 次迭代：

• 对$s_{42}$：执行 “右” 到$s_{43}$，价值$v_2(s_{42})=-1+0.9\times (-1)=-1.9$；

• 对$s_{33}$：执行 “右” 到$s_{34}$或 “下” 到$s_{43}$，价值$v_2(s_{33})=-1+0.9\times (-1)=-1.9$；

• 以此类推，离终点越近的状态价值越高（负向程度越小）。

3. 收敛后：

• 终点$s_{44}$价值$v_{\ast }(s_{44})=0$；

• 相邻状态$s_{43}$、$s_{34}$价值$v_{\ast }\approx -1$；

• 起点$s_{11}$价值$v_{\ast }\approx -14$（需 14 步到达终点，累积奖励约 - 14）。

（二）最优策略导出

基于收敛的$v_{\ast }$，每个状态选择能最大化价值的动作：

• $s_{11}$：“右” 或 “下”（均指向离终点更近的方向）；

• $s_{43}$：“右”（直接到达终点）；

• 所有状态的最优动作均指向终点，形成最短路径策略。

五、DP 算法的扩展与局限

（一）常见扩展变种

1. 异步动态规划（Asynchronous DP）：

• 传统 DP 需同步更新所有状态价值，异步 DP 则随机或按顺序更新单个 / 部分状态（如优先级扫描），减少计算冗余，适用于大规模状态空间。

1. 近似动态规划（Approximate DP）：

• 对无限或高维状态空间，用函数近似（如线性函数、神经网络）替代表格存储价值函数，是连接传统 DP 与深度强化学习的桥梁。

（二）核心局限性

1. 模型依赖：必须已知完整的$P$和$R$，而现实场景中环境模型往往难以获取（如机器人控制、游戏 AI）；

2. 维度灾难：状态空间随变量维度指数增长（如围棋状态空间达$10^{170}$），表格型 DP 完全失效；

3. 计算开销：即使状态空间有限，每次迭代需遍历所有状态，计算资源需求高；

4. 缺乏探索：依赖模型预测而非实际交互，无法应对环境模型的不确定性或动态变化。

六、DP 算法的影响与延伸

（一）对强化学习的理论贡献

1. 确立了 “预测 - 控制” 的核心框架，为后续算法提供范式；

2. 贝尔曼方程成为价值函数优化的通用数学工具；

3. 自举特性被时序差分（TD）算法继承，形成无模型学习的核心机制。

（二）与现代强化学习的结合

1. 有模型强化学习：DP 的模型利用思想延伸至模型预测控制（MPC），通过学习环境模型实现高效规划；

2. 深度强化学习：近似 DP 与神经网络结合，产生 DQN（深度 Q 网络）等算法，突破维度灾难限制；

3. 策略优化：DP 的贪婪提升思想为策略梯度算法提供了价值评估的参照标准。