马尔可夫决策过程（MDP）的值迭代与策略迭代算法原理与求解过程
字数 3817 2025-12-09 23:56:25

马尔可夫决策过程（MDP）的值迭代与策略迭代算法原理与求解过程

题目描述

马尔可夫决策过程（Markov Decision Process, MDP）是序列决策问题的数学模型。给定一个MDP，我们需要找到最优策略，使得累积回报最大化。本题目要求详细讲解求解MDP最优策略的两种经典算法：值迭代 和策略迭代。包括它们的基本原理、计算步骤、收敛性以及相互间的区别。

解题过程

1. MDP 基本要素回顾

一个MDP由以下五元组定义：

  • 状态集 \(S\): 系统可能处于的所有状态的集合。
  • 动作集 \(A\): 在每个状态可执行的所有动作的集合。
  • 转移概率 \(P(s' | s, a)\): 在状态 \(s\) 执行动作 \(a\) 后，转移到状态 \(s'\) 的概率。
  • 奖励函数 \(R(s, a, s')\): 在状态 \(s\) 执行动作 \(a\) 并转移到状态 \(s'\) 后，获得的即时奖励。
  • 折扣因子 \(\gamma \in [0, 1]\): 用于权衡未来奖励相对于当前奖励的重要性。

目标：找到一个策略 \(\pi: S \rightarrow A\)，它指定在每个状态应该采取什么动作，以最大化期望累积折扣回报：

\[G_t = R_{t+1} + \gamma R_{t+2} + \gamma^2 R_{t+3} + \dots \]

其中 \(R_{t}\) 是在时间步 \(t\) 获得的即时奖励。

2. 核心概念：状态值函数与动作值函数

  1. 状态值函数 \(V^{\pi}(s)\)：表示在状态 \(s\) 下，遵循策略 \(\pi\) 所能获得的期望累积回报。

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

  1. 最优状态值函数 \(V^{*}(s)\)：所有可能策略中能获得的最大值函数。

\[ V^{*}(s) = \max_{\pi} V^{\pi}(s) \]

  1. 动作值函数 \(Q^{\pi}(s, a)\)：表示在状态 \(s\) 下执行动作 \(a\)，之后遵循策略 \(\pi\) 所能获得的期望累积回报。

\[ Q^{\pi}(s, a) = \mathbb{E}_{\pi} \left[ \sum_{k=0}^{\infty} \gamma^k R_{t+k+1} \mid S_t = s, A_t = a \right] \]

  1. 最优动作值函数 \(Q^{*}(s, a)\)：所有可能策略中能获得的最大动作值函数。

3. 贝尔曼方程与贝尔曼最优方程

  1. 贝尔曼方程（用于评估给定策略 \(\pi\)）：

\[ V^{\pi}(s) = \sum_{a \in A} \pi(a|s) \sum_{s' \in S} P(s'|s, a) \left[ R(s, a, s') + \gamma V^{\pi}(s') \right] \]

它建立了当前状态值与后续状态值之间的递推关系。

  1. 贝尔曼最优方程（用于找到最优策略）：

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

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

最优策略 \(\pi^{*}\) 可以通过 \(Q^{*}\) 得到：\(\pi^{*}(s) = \arg\max_{a} Q^{*}(s, a)\)。

4. 策略迭代算法

策略迭代是一种通过交替进行策略评估和策略改进来找到最优策略的方法。

步骤1：初始化

  • 初始化一个任意策略 \(\pi_0\)（例如随机策略）。
  • 初始化状态值函数 \(V_0(s)\) 为任意值（例如全零）。

步骤2：策略评估（Policy Evaluation）

  • 给定当前策略 \(\pi\)，通过求解贝尔曼方程来精确计算其状态值函数 \(V^{\pi}\)。
  • 由于贝尔曼方程是一个线性方程组，可以通过迭代法求解（称为迭代策略评估）：

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

  • 迭代直到 \(V_{k+1}\) 与 \(V_{k}\) 的差距小于某个阈值 \(\theta\)，即 \(\max_s |V_{k+1}(s) - V_k(s)| < \theta\)。

步骤3：策略改进（Policy Improvement）

  • 利用上一步评估得到的状态值函数 \(V^{\pi}\)，构造一个新的贪心策略 \(\pi'\)：

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

  • 这个新策略保证了在每一个状态都选择能使“行动-状态”值最大的动作。

步骤4：检查收敛

  • 如果新策略 \(\pi'\) 与旧策略 \(\pi\) 完全相同（即对每个状态选择的动作都一样），则算法终止，\(\pi'\) 即为最优策略。
  • 否则，令 \(\pi = \pi'\)，并返回步骤2。

策略迭代的特点：每次策略评估都要求值函数收敛到当前策略的真实值，然后再进行策略改进。通常能保证在有限步内收敛到最优策略。

5. 值迭代算法

值迭代是策略迭代的一种变体，它将策略评估和策略改进合并为一步，直接迭代更新最优值函数。

步骤1：初始化

  • 初始化所有状态的值函数 \(V_0(s)\) 为任意值（例如全零）。

步骤2：值迭代更新

  • 对于每个状态 \(s\)，应用贝尔曼最优方程进行一次更新：

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

  • 这个更新可以看作：在当前的估计值函数 \(V_k\) 下，模拟执行所有可能的动作，并选择能带来最大期望回报的动作对应的值作为 \(V_{k+1}(s)\)。

步骤3：检查收敛

  • 重复步骤2，直到值函数收敛。通常当两次迭代间值函数的最大变化小于某个阈值 \(\theta\) 时停止：

\[ \max_s |V_{k+1}(s) - V_k(s)| < \theta \]

步骤4：提取最优策略

  • 一旦值函数收敛到 \(V^{*}\)，最优策略可以通过一次“贪心”计算得到：

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

值迭代的特点：它没有显式地维护和评估中间策略，而是直接迭代最优值函数。其更新公式本质上是贝尔曼最优方程的不动点迭代。

6. 两种算法的比较

  1. 计算过程：

    • 策略迭代：在“策略评估”和“策略改进”之间交替。策略评估可能需要多次迭代才能精确求解当前策略的值函数。
    • 值迭代：将策略改进的“最大化”操作内嵌到值函数更新中，一步到位地更新最优值函数的估计。

  2. 收敛速度：

    • 策略迭代通常收敛得更快（所需迭代次数更少），因为每次策略改进都基于精确的策略评估。
    • 值迭代的每次更新可以看作是一次策略评估（只迭代一次）加上一次策略改进。虽然单次迭代快，但总迭代次数可能更多。

  3. 适用场景：

    • 当状态空间不大，且策略评估可以较快速完成时，策略迭代通常更高效。
    • 值迭代在概念上更简单，且当只关心最终最优值（而非中间策略）时，实现更直接。

  4. 理论联系：

    • 两者都基于贝尔曼最优方程，且都能保证收敛到最优策略和最优值函数。
    • 可以认为值迭代是策略迭代在“策略评估只进行一次迭代”时的特例。

总结

值迭代和策略迭代是求解MDP最优策略的两种经典动态规划方法。策略迭代通过交替执行完整的策略评估和策略改进来逐步优化策略；值迭代则通过直接迭代更新最优值函数的估计，并在最后提取出最优策略。理解它们的核心在于掌握贝尔曼（最优）方程如何将全局最优问题分解为局部递归的优化问题。在实际应用中，可以根据问题的规模和特点选择合适的算法。

马尔可夫决策过程（MDP）的值迭代与策略迭代算法原理与求解过程 题目描述 马尔可夫决策过程（Markov Decision Process, MDP）是序列决策问题的数学模型。给定一个MDP，我们需要找到最优策略，使得累积回报最大化。本题目要求详细讲解求解MDP最优策略的两种经典算法： 值迭代 和 策略迭代 。包括它们的基本原理、计算步骤、收敛性以及相互间的区别。 解题过程 1. MDP 基本要素回顾 一个MDP由以下五元组定义： 状态集 \( S \): 系统可能处于的所有状态的集合。 动作集 \( A \): 在每个状态可执行的所有动作的集合。 转移概率 \( P(s' | s, a) \): 在状态 \( s \) 执行动作 \( a \) 后，转移到状态 \( s' \) 的概率。 奖励函数 \( R(s, a, s') \): 在状态 \( s \) 执行动作 \( a \) 并转移到状态 \( s' \) 后，获得的即时奖励。 折扣因子 \( \gamma \in [ 0, 1 ] \): 用于权衡未来奖励相对于当前奖励的重要性。 目标 ：找到一个策略 \( \pi: S \rightarrow A \)，它指定在每个状态应该采取什么动作，以最大化 期望累积折扣回报 ： \[ G_ t = R_ {t+1} + \gamma R_ {t+2} + \gamma^2 R_ {t+3} + \dots \] 其中 \( R_ {t} \) 是在时间步 \( t \) 获得的即时奖励。 2. 核心概念：状态值函数与动作值函数 状态值函数 \( V^{\pi}(s) \)：表示在状态 \( s \) 下，遵循策略 \( \pi \) 所能获得的期望累积回报。 \[ V^{\pi}(s) = \mathbb{E} {\pi} \left[ \sum {k=0}^{\infty} \gamma^k R_ {t+k+1} \mid S_ t = s \right ] \] 最优状态值函数 \( V^{ }(s) \)：所有可能策略中能获得的最大值函数。 \[ V^{ }(s) = \max_ {\pi} V^{\pi}(s) \] 动作值函数 \( Q^{\pi}(s, a) \)：表示在状态 \( s \) 下执行动作 \( a \)，之后遵循策略 \( \pi \) 所能获得的期望累积回报。 \[ Q^{\pi}(s, a) = \mathbb{E} {\pi} \left[ \sum {k=0}^{\infty} \gamma^k R_ {t+k+1} \mid S_ t = s, A_ t = a \right ] \] 最优动作值函数 \( Q^{* }(s, a) \)：所有可能策略中能获得的最大动作值函数。 3. 贝尔曼方程与贝尔曼最优方程 贝尔曼方程 （用于评估给定策略 \( \pi \)）： \[ V^{\pi}(s) = \sum_ {a \in A} \pi(a|s) \sum_ {s' \in S} P(s'|s, a) \left[ R(s, a, s') + \gamma V^{\pi}(s') \right ] \] 它建立了当前状态值与后续状态值之间的递推关系。 贝尔曼最优方程 （用于找到最优策略）： \[ V^{ }(s) = \max_ {a \in A} \sum_ {s' \in S} P(s'|s, a) \left[ R(s, a, s') + \gamma V^{ }(s') \right ] \] \[ Q^{ }(s, a) = \sum_ {s' \in S} P(s'|s, a) \left[ R(s, a, s') + \gamma \max_ {a' \in A} Q^{ }(s', a') \right ] \] 最优策略 \( \pi^{ } \) 可以通过 \( Q^{ } \) 得到：\( \pi^{ }(s) = \arg\max_ {a} Q^{ }(s, a) \)。 4. 策略迭代算法 策略迭代是一种通过交替进行 策略评估 和 策略改进 来找到最优策略的方法。 步骤1：初始化 初始化一个任意策略 \( \pi_ 0 \)（例如随机策略）。 初始化状态值函数 \( V_ 0(s) \) 为任意值（例如全零）。 步骤2：策略评估（Policy Evaluation） 给定当前策略 \( \pi \)，通过求解贝尔曼方程来精确计算其状态值函数 \( V^{\pi} \)。 由于贝尔曼方程是一个线性方程组，可以通过迭代法求解（称为迭代策略评估）： \[ V_ {k+1}(s) = \sum_ {a \in A} \pi(a|s) \sum_ {s' \in S} P(s'|s, a) \left[ R(s, a, s') + \gamma V_ {k}(s') \right ] \] 迭代直到 \( V_ {k+1} \) 与 \( V_ {k} \) 的差距小于某个阈值 \( \theta \)，即 \( \max_ s |V_ {k+1}(s) - V_ k(s)| < \theta \)。 步骤3：策略改进（Policy Improvement） 利用上一步评估得到的状态值函数 \( V^{\pi} \)，构造一个新的贪心策略 \( \pi' \)： \[ \pi'(s) = \arg\max_ {a \in A} \sum_ {s' \in S} P(s'|s, a) \left[ R(s, a, s') + \gamma V^{\pi}(s') \right ] \] 这个新策略保证了在每一个状态都选择能使“行动-状态”值最大的动作。 步骤4：检查收敛 如果新策略 \( \pi' \) 与旧策略 \( \pi \) 完全相同（即对每个状态选择的动作都一样），则算法终止，\( \pi' \) 即为最优策略。 否则，令 \( \pi = \pi' \)，并返回步骤2。 策略迭代的特点 ：每次策略评估都要求值函数收敛到当前策略的真实值，然后再进行策略改进。通常能保证在有限步内收敛到最优策略。 5. 值迭代算法 值迭代是策略迭代的一种变体，它将策略评估和策略改进 合并为一步 ，直接迭代更新最优值函数。 步骤1：初始化 初始化所有状态的值函数 \( V_ 0(s) \) 为任意值（例如全零）。 步骤2：值迭代更新 对于每个状态 \( s \)，应用贝尔曼最优方程进行一次更新： \[ V_ {k+1}(s) = \max_ {a \in A} \sum_ {s' \in S} P(s'|s, a) \left[ R(s, a, s') + \gamma V_ {k}(s') \right ] \] 这个更新可以看作：在当前的估计值函数 \( V_ k \) 下，模拟执行所有可能的动作，并选择能带来最大期望回报的动作对应的值作为 \( V_ {k+1}(s) \)。 步骤3：检查收敛 重复步骤2，直到值函数收敛。通常当两次迭代间值函数的最大变化小于某个阈值 \( \theta \) 时停止： \[ \max_ s |V_ {k+1}(s) - V_ k(s)| < \theta \] 步骤4：提取最优策略 一旦值函数收敛到 \( V^{ } \)，最优策略可以通过一次“贪心”计算得到： \[ \pi^{ }(s) = \arg\max_ {a \in A} \sum_ {s' \in S} P(s'|s, a) \left[ R(s, a, s') + \gamma V^{* }(s') \right ] \] 值迭代的特点 ：它没有显式地维护和评估中间策略，而是直接迭代最优值函数。其更新公式本质上是贝尔曼最优方程的不动点迭代。 6. 两种算法的比较 计算过程 ： 策略迭代 ：在“策略评估”和“策略改进”之间交替。策略评估可能需要多次迭代才能精确求解当前策略的值函数。 值迭代 ：将策略改进的“最大化”操作内嵌到值函数更新中，一步到位地更新最优值函数的估计。 收敛速度 ： 策略迭代通常收敛得更快（所需迭代次数更少），因为每次策略改进都基于精确的策略评估。 值迭代的每次更新可以看作是一次策略评估（只迭代一次）加上一次策略改进。虽然单次迭代快，但总迭代次数可能更多。 适用场景 ： 当状态空间不大，且策略评估可以较快速完成时，策略迭代通常更高效。 值迭代在概念上更简单，且当只关心最终最优值（而非中间策略）时，实现更直接。 理论联系 ： 两者都基于贝尔曼最优方程，且都能保证收敛到最优策略和最优值函数。 可以认为值迭代是策略迭代在“策略评估只进行一次迭代”时的特例。 总结 值迭代和策略迭代是求解MDP最优策略的两种经典动态规划方法。 策略迭代 通过交替执行完整的策略评估和策略改进来逐步优化策略； 值迭代 则通过直接迭代更新最优值函数的估计，并在最后提取出最优策略。理解它们的核心在于掌握贝尔曼（最优）方程如何将全局最优问题分解为局部递归的优化问题。在实际应用中，可以根据问题的规模和特点选择合适的算法。