动态规划中的值迭代算法
字数 3344 2025-12-15 19:31:46

好的，我们接下来讲解动态规划中的值迭代算法。

动态规划中的值迭代算法

值迭代算法是求解马尔可夫决策过程最优策略的一种经典且基础的动态规划方法。它通过迭代地更新“状态价值函数”，最终逼近最优值函数，从而导出最优策略。

为了让您彻底理解，我们将按以下逻辑展开：

  1. 理解马尔可夫决策过程的组成
  2. 明确“最优”的目标
  3. 从贝尔曼最优方程到值迭代的核心思想
  4. 值迭代算法的详细步骤
  5. 一个简单的数值算例
  6. 算法的收敛性与终止准则

步骤一：理解马尔可夫决策过程

值迭代算法解决的是马尔可夫决策过程问题。一个MDP通常由以下几个要素构成：

  • 状态 (S)：系统在某一时刻所有可能的情况的集合。例如，在棋盘游戏中，状态就是棋子在棋盘上的位置。
  • 动作 (A)：在每个状态下，决策者可以采取的行动的集合。例如，在某个棋格，你可以选择向上、下、左、右移动。
  • 转移概率 (P)：在状态s下采取动作a后，系统转移到下一个状态s'的概率，记为 \(P(s' | s, a)\)。
  • 奖励函数 (R)：在状态s采取动作a并转移到状态s'后，决策者立即获得的数值奖励，记为 \(r(s, a, s')\)。奖励反映了行动的即时好坏。
  • 折扣因子 (γ)：一个介于0和1之间的数，用于衡量未来奖励在当前的价值。γ=0表示只关心眼前利益；γ接近1表示非常看重长远回报。

简单来说，MDP描述了一个智能体如何在一个随机的、状态可观测的环境中，通过选择不同的动作来获取最大累积奖励的框架。

步骤二：明确“最优”的目标

我们的目标不是最大化单次动作的奖励，而是寻找一个策略 (π)——一个从状态到动作的映射规则（π(s)=a），使得遵循这个策略从任意初始状态出发，所获得的折扣累积奖励的期望值最大。

这个“折扣累积奖励的期望值”被称为状态价值函数 \(V^π(s)\)，它衡量了在状态s下，遵循策略π的长期价值。
最优策略 \(π^*\) 对应的价值函数，称为最优价值函数 \(V^*(s)\)，它满足对于任意状态s，其值都是所有可能策略中最大的。

步骤三：从贝尔曼最优方程到值迭代的核心思想

这是理解值迭代的关键。贝尔曼最优方程给出了最优价值函数 \(V^*\) 必须满足的一个自洽条件：

\[V^*(s) = \max_{a \in A} \left[ \sum_{s'} P(s' | s, a) \left( r(s, a, s') + \gamma V^*(s') \right) \right] \]

这个方程的意思是：状态s的最优价值，等于所有可选动作中，能带来的“即时奖励”加上“下一个状态的折扣最优价值”的期望值 的最大值。

值迭代的思想来源于此：如果我们不知道 \(V^*\)，我们可以先任意猜测一个价值函数 \(V\)，然后反复地用贝尔曼最优方程的右边去更新它（即执行最大化操作），这个迭代过程最终会使 \(V\) 收敛到 \(V^*\)。

步骤四：值迭代算法的详细步骤

  1. 初始化：为所有状态s，任意设定其价值函数 \(V_0(s)\)（例如，全部设为0）。设定一个很小的阈值 \(θ > 0\)（如0.001），用于判断收敛。令迭代计数器 \(k = 0\)。

  2. 价值更新（核心步骤）：对每一个状态 \(s \in S\)，计算：

\[ V_{k+1}(s) = \max_{a \in A} \left[ \sum_{s'} P(s' | s, a) \left( r(s, a, s') + \gamma V_k(s') \right) \right] \]

这个计算是同步的，意味着在计算 \(V_{k+1}\) 时，使用的都是上一轮迭代的 \(V_k\)，而不是本轮已经算出的新值。

  1. 检查收敛：计算当前迭代前后价值函数的最大变化量 \(Δ\)：

\[ Δ = \max_{s \in S} | V_{k+1}(s) - V_k(s) | \]

如果 \(Δ < θ\)，则算法终止，此时 \(V_{k+1}\) 已非常接近最优价值函数 \(V^*\)。否则，令 \(k = k + 1\)，返回步骤2。

  1. 提取最优策略：算法收敛后，最优策略 \(π^*\) 可以通过对每个状态s进行一次“贪婪”选择得到：

\[ π^*(s) = \arg\max_{a \in A} \left[ \sum_{s'} P(s' | s, a) \left( r(s, a, s') + \gamma V^*(s') \right) \right] \]

即，选择使得贝尔曼最优方程右边取最大值的那个动作。

核心特点：值迭代算法是先求最优价值函数，再导出最优策略。其更新过程直观体现了“反复评估并改进”的思想。

步骤五：一个简单的数值算例

考虑一个极其简单的网格世界：

  • 状态：A, B, C。C是终点，到达C获得奖励+10并结束。
  • 动作：在A和B状态，可以选择“去C”。
  • 转移：从A采取“去C”动作，有0.8概率成功到C（+10奖励），0.2概率失败留在A（0奖励）。从B采取“去C”动作，有0.5概率成功到C（+10奖励），0.5概率失败留在B（0奖励）。
  • 折扣因子 γ = 0.9。

初始化：设 \(V_0(A)=V_0(B)=V_0(C)=0\)， θ=0.01。

第一次迭代 (k=0 -> k=1)：

  • \(V_1(C) = 0\) （终点，无动作可选）
  • \(V_1(B) = \max[0.5*(10+0.9*0) + 0.5*(0+0.9*0)] = \max[5] = 5\)
  • \(V_1(A) = \max[0.8*(10+0.9*0) + 0.2*(0+0.9*0)] = \max[8] = 8\)
    \(Δ = \max(|5-0|， |8-0|， |0-0|) = 8 > θ\)

第二次迭代 (k=1 -> k=2)：
使用 \(V_1\) 的值。

  • \(V_2(C) = 0\)
  • \(V_2(B) = \max[0.5*(10+0.9*0) + 0.5*(0+0.9*5)] = \max[0.5*10 + 0.5*4.5] = \max[7.25] = 7.25\)
  • \(V_2(A) = \max[0.8*(10+0.9*0) + 0.2*(0+0.9*8)] = \max[0.8*10 + 0.2*7.2] = \max[8+1.44] = 9.44\)
    \(Δ = \max(|7.25-5|， |9.44-8|， |0-0|) = 2.25 > θ\)

继续迭代下去， \(V(A)\) 和 \(V(B)\) 的值会逐渐收敛。最终，最优策略显然是无论在A还是B，都应该选择“去C”这个动作。值迭代通过数值计算验证了这一点。

步骤六：算法的收敛性与终止准则

  • 收敛性：在折扣因子 γ < 1 且状态和动作空间有限的条件下，值迭代算法被证明能保证收敛到唯一的最优价值函数 \(V^*\)。这是因为贝尔曼最优算子是一个压缩映射，每次迭代都会使价值函数向量更接近不动点 \(V^*\)。
  • 终止准则：我们使用阈值 \(θ\) 来判断。当一次迭代中所有状态的价值变化都小于 \(θ\) 时，可以证明此时得到的价值函数 \(V\) 与真正的最优价值函数 \(V^*\) 的误差不超过 \(\frac{γθ}{1-γ}\)。这为我们提供了一个可控的精度保证。

总结：值迭代算法是一种通过反复应用贝尔曼最优方程进行迭代更新，从而求解MDP最优价值函数和策略的动态规划方法。它概念清晰，实现相对简单，是理解强化学习和序贯决策中动态规划思想的基石。其缺点是当状态空间很大时（“维数灾”），计算会变得非常昂贵。

好的，我们接下来讲解 动态规划中的值迭代算法 。 动态规划中的值迭代算法 值迭代算法是求解马尔可夫决策过程最优策略的一种经典且基础的动态规划方法。它通过迭代地更新“状态价值函数”，最终逼近最优值函数，从而导出最优策略。 为了让您彻底理解，我们将按以下逻辑展开： 理解马尔可夫决策过程的组成 明确“最优”的目标 从贝尔曼最优方程到值迭代的核心思想 值迭代算法的详细步骤 一个简单的数值算例 算法的收敛性与终止准则 步骤一：理解马尔可夫决策过程 值迭代算法解决的是 马尔可夫决策过程 问题。一个MDP通常由以下几个要素构成： 状态 (S) ：系统在某一时刻所有可能的情况的集合。例如，在棋盘游戏中，状态就是棋子在棋盘上的位置。 动作 (A) ：在每个状态下，决策者可以采取的行动的集合。例如，在某个棋格，你可以选择向上、下、左、右移动。 转移概率 (P) ：在状态 s 下采取动作 a 后，系统转移到下一个状态 s' 的概率，记为 \( P(s' | s, a) \)。 奖励函数 (R) ：在状态 s 采取动作 a 并转移到状态 s' 后，决策者立即获得的数值奖励，记为 \( r(s, a, s') \)。奖励反映了行动的即时好坏。 折扣因子 (γ) ：一个介于0和1之间的数，用于衡量未来奖励在当前的价值。γ=0表示只关心眼前利益；γ接近1表示非常看重长远回报。 简单来说，MDP描述了一个智能体如何在一个 随机的、状态可观测的 环境中，通过选择不同的动作来获取最大累积奖励的框架。 步骤二：明确“最优”的目标 我们的目标不是最大化单次动作的奖励，而是寻找一个 策略 (π) ——一个从状态到动作的映射规则（π(s)=a），使得遵循这个策略从任意初始状态出发，所获得的 折扣累积奖励的期望值 最大。 这个“折扣累积奖励的期望值”被称为 状态价值函数 \( V^π(s) \) ，它衡量了在状态 s 下，遵循策略π的长期价值。 最优策略 \( π^* \) 对应的价值函数，称为 最优价值函数 \( V^* (s) \) ，它满足对于任意状态 s ，其值都是所有可能策略中最大的。 步骤三：从贝尔曼最优方程到值迭代的核心思想 这是理解值迭代的关键。贝尔曼最优方程给出了最优价值函数 \( V^* \) 必须满足的一个自洽条件： \[ V^ (s) = \max_ {a \in A} \left[ \sum_ {s'} P(s' | s, a) \left( r(s, a, s') + \gamma V^ (s') \right) \right ] \] 这个方程的意思是： 状态 s 的最优价值，等于所有可选动作中，能带来的“即时奖励”加上“下一个状态的折扣最优价值”的期望值 的最大值 。 值迭代的思想来源于此： 如果我们不知道 \( V^* \)，我们可以先任意猜测一个价值函数 \( V \)，然后反复地用贝尔曼最优方程的右边去更新它（即执行最大化操作），这个迭代过程最终会使 \( V \) 收敛到 \( V^* \)。 步骤四：值迭代算法的详细步骤 初始化 ：为所有状态 s ，任意设定其价值函数 \( V_ 0(s) \)（例如，全部设为0）。设定一个很小的阈值 \( θ > 0 \)（如0.001），用于判断收敛。令迭代计数器 \( k = 0 \)。 价值更新（核心步骤） ：对每一个状态 \( s \in S \)，计算： \[ V_ {k+1}(s) = \max_ {a \in A} \left[ \sum_ {s'} P(s' | s, a) \left( r(s, a, s') + \gamma V_ k(s') \right) \right ] \] 这个计算是 同步的 ，意味着在计算 \( V_ {k+1} \) 时，使用的都是上一轮迭代的 \( V_ k \)，而不是本轮已经算出的新值。 检查收敛 ：计算当前迭代前后价值函数的最大变化量 \( Δ \)： \[ Δ = \max_ {s \in S} | V_ {k+1}(s) - V_ k(s) | \] 如果 \( Δ < θ \)，则算法终止，此时 \( V_ {k+1} \) 已非常接近最优价值函数 \( V^* \)。否则，令 \( k = k + 1 \)，返回步骤2。 提取最优策略 ：算法收敛后，最优策略 \( π^* \) 可以通过对每个状态 s 进行一次“贪婪”选择得到： \[ π^ (s) = \arg\max_ {a \in A} \left[ \sum_ {s'} P(s' | s, a) \left( r(s, a, s') + \gamma V^ (s') \right) \right ] \] 即，选择使得贝尔曼最优方程右边取最大值的那个动作。 核心特点 ：值迭代算法是 先求最优价值函数，再导出最优策略 。其更新过程直观体现了“反复评估并改进”的思想。 步骤五：一个简单的数值算例 考虑一个极其简单的网格世界： 状态：A, B, C。C是终点，到达C获得奖励+10并结束。 动作：在A和B状态，可以选择“去C”。 转移：从A采取“去C”动作，有0.8概率成功到C（+10奖励），0.2概率失败留在A（0奖励）。从B采取“去C”动作，有0.5概率成功到C（+10奖励），0.5概率失败留在B（0奖励）。 折扣因子 γ = 0.9。 初始化 ：设 \( V_ 0(A)=V_ 0(B)=V_ 0(C)=0 \)， θ=0.01。 第一次迭代 (k=0 -> k=1) ： \( V_ 1(C) = 0 \) （终点，无动作可选） \( V_ 1(B) = \max[ 0.5* (10+0.9 0) + 0.5 (0+0.9* 0)] = \max[ 5 ] = 5 \) \( V_ 1(A) = \max[ 0.8* (10+0.9 0) + 0.2 (0+0.9* 0)] = \max[ 8 ] = 8 \) \( Δ = \max(|5-0|， |8-0|， |0-0|) = 8 > θ \) 第二次迭代 (k=1 -> k=2) ： 使用 \( V_ 1 \) 的值。 \( V_ 2(C) = 0 \) \( V_ 2(B) = \max[ 0.5* (10+0.9 0) + 0.5 (0+0.9 5)] = \max[ 0.5 10 + 0.5* 4.5] = \max[ 7.25 ] = 7.25 \) \( V_ 2(A) = \max[ 0.8* (10+0.9 0) + 0.2 (0+0.9 8)] = \max[ 0.8 10 + 0.2* 7.2] = \max[ 8+1.44 ] = 9.44 \) \( Δ = \max(|7.25-5|， |9.44-8|， |0-0|) = 2.25 > θ \) 继续迭代下去， \( V(A) \) 和 \( V(B) \) 的值会逐渐收敛。最终，最优策略显然是无论在A还是B，都应该选择“去C”这个动作。值迭代通过数值计算验证了这一点。 步骤六：算法的收敛性与终止准则 收敛性 ：在折扣因子 γ < 1 且状态和动作空间有限的条件下，值迭代算法被证明能保证收敛到唯一的最优价值函数 \( V^* \)。这是因为贝尔曼最优算子是一个 压缩映射 ，每次迭代都会使价值函数向量更接近不动点 \( V^* \)。 终止准则 ：我们使用阈值 \( θ \) 来判断。当一次迭代中所有状态的价值变化都小于 \( θ \) 时，可以证明此时得到的价值函数 \( V \) 与真正的最优价值函数 \( V^* \) 的误差不超过 \( \frac{γθ}{1-γ} \)。这为我们提供了一个可控的精度保证。 总结 ：值迭代算法是一种通过 反复应用贝尔曼最优方程进行迭代更新 ，从而求解MDP最优价值函数和策略的动态规划方法。它概念清晰，实现相对简单，是理解强化学习和序贯决策中动态规划思想的基石。其缺点是当状态空间很大时（“维数灾”），计算会变得非常昂贵。