Dynamic Programming for MDP (18)

上一讲我们定义了MDP，并得到了一个核心的数学关系——贝尔曼方程 (Bellman Equation)，它描述了最优状态价值的递归性质。这一讲的核心问题是：我们如何通过计算来求解这些贝尔曼方程，从而最终找到最优策略 π*？

由于贝尔曼方程是一组非线性的联立方程，直接求解非常困难。因此，我们采用动态规划 (Dynamic Programming) 的思想，通过迭代的方式逐步逼近最优的效用值和策略。这一讲介绍了两种实现这一思想的经典算法。

策略迭代 (Policy Iteration)

在介绍策略迭代之前，我们先引入一个概念——策略评估 (Policy Evaluation)。策略评估的目标是计算给定策略 π 的状态价值函数 V(π)。

上一讲我们提到贝尔曼方程分为贝尔曼最优方程和贝尔曼期望方程，策略评估的目标是计算给定策略 π 的状态价值函数 V(π)，即贝尔曼期望方程。

策略评估

策略评估的基本思路是从任意一个状态价值函数开始，依据给定的策略，结合贝尔曼期望方程、状态转移概率和奖励同步迭代更新状态价值函数，直至其收敛，得到该策略下最终的状态价值函数。

假设在第 t 轮迭代已经计算出了所有状态的状态价值 V^t(s’)，那么在第 t+1 轮可以利用第 t 轮计算出的状态价值计算出第 t+1 轮的状态价值 V^{t+1}(s)。这是通过贝尔曼期望方程来完成的，即通过 Bellman expectation backup 进行迭代

V^t + 1(s) = ∑_a ∈ Aπ(a|s)(R(s, a) + γ∑_{s^′ ∈ S}P(s^′|s, a) ⋅ V^t(s^′))

理解迭代过程

首先, 上面的迭代公式由贝尔曼期望方程得到:

V^π(s) = ∑_a ∈ Aπ(a|s)(R(s, a) + γ∑_{s^′ ∈ S}P(s^′|s, a) ⋅ V^π(s^′))

这是一个陈述或一个平衡状态的定义。它描述了一个事实：对于一个给定的策略 π，其”真实”的价值函数 V^π 必须满足这种自洽性。

这个公式可以看作是一个由 N 个方程组成的方程组（N是状态的数量）。在方程的左边和右边出现的 V^π 是同一个未知数。它表达的是：“一个状态的真实价值（左边），等于遵循策略后所有可能后续状态的期望价值（右边）”。

而迭代方程则将V^π(s) 替换为 V^t + 1(s) ，得到：

V^t + 1(s) = ∑_a ∈ Aπ(a|s)(R(s, a) + γ∑_{s^′ ∈ S}P(s^′|s, a) ⋅ V^t(s^′))

根本原因在于, 贝尔曼算子（由第一个式子的右半部分定义）是一个压缩映射(符合迭代收敛的条件), 这个数学性质保证了，我们可以通过第二个式子描述的迭代方法，来找到第一个式子定义的那个唯一解。

随着 k 越来越大，我们计算出的估计值 V^k(s) 会收敛 (converge) 到那个”真实”的价值 V^π(s)。

当 k → ∞ 时，V^k(s) → V^π(s)。我们把一个寻找平衡点的问题，转化成了一个保证能走到平衡点的计算流程。

压缩映射定理保证了，只要一个算子是压缩的，那么它有且仅有一个不动点（即 v_pi 是唯一存在的）; 从任何初始点（任何初始猜测 v_0）开始，反复应用这个算子，最终都必定会收敛到这个唯一的不动点。

示例分析

下面通过一个具体的示例理解策略评估的过程。

这是一个经典的Grid World的例子。有一个4x4的16宫格。只有左上和右下的格子是终止格子。

• 状态 (S): 14个可移动的格子。左上角 (0,0) 和右下角 (3,3) 是终止状态。

• 动作 (A): {上, 下, 左, 右}。

• 策略 (π): 一个固定的随机策略。在任何一个非终止状态下，智能体都以均等的概率（各25%）选择上、下、左、右四个动作中的一个。

• 奖励 (R): 每次移动的即时奖励为 -1。

• 折扣因子 (γ): γ=1。这意味着未来的惩罚和当前的惩罚同等重要。

• 目标: 我们的目标是评估这个随机策略，即计算出在这个策略下，从每一个格子出发，到达终点所期望的累积总回报（也就是状态价值函数 V^π(s)）。

图片左侧展示了价值函数从 k=0 开始的迭代计算过程。这个计算的核心是反复使用贝尔曼期望方程进行更新。对于这个特定的例子，更新公式为：

V^k + 1(s) = −1 + (0.25 ⋅ V^k(s_up^′) + 0.25 ⋅ V^k(s_down^′) + 0.25 ⋅ V^k(s_left^′) + 0.25 ⋅ V^k(s_right^′))

其中，s_up^′, s_down^′ 等表示上一迭代中四个邻居格子的价值。

下面展示k = 0 时的迭代:

• 初始化所有非终止状态的价值为 0。这是一个任意的起点。
• 此时，因为所有格子的价值都一样，所以看不出任何格子的好坏。

k = 1 时的迭代:

• 对所有非终止格子应用一次更新公式, 利用上一步的价值计算这一步的价值。
• 计算: V¹(s) = −1 + (0.25 ⋅ V⁰(...) + ...) = −1 + (0.25 ⋅ 0 + ...) = −1
• 所有的非终止格子的价值都变成了 -1。这代表了”走一步”所付出的代价。此时，我们只考虑了即时奖励，还没有考虑未来的奖励。

k = 2 时的迭代:

• 使用 k=1 的价值来计算 k=2 的价值。价值的差异开始出现。

• 计算示例 (以第(0,1)格为例):

  • 四个邻居状态：
    • (0,0): 终止状态，价值为0
    • (1,1): 价值为-1
    • (0,2): 价值为-1
    • (0,1): 往左撞墙，价值为-1

  V²(0, 1) = −1 + [0.25 ⋅ V¹(0, 0) + 0.25 ⋅ V¹(1, 1) + 0.25 ⋅ V¹(0, 2) + 0.25 ⋅ V¹(0, 1)]

  V²(0, 1) = −1 + [0.25 ⋅ 0 + 0.25 ⋅ (−1) + 0.25 ⋅ (−1) + 0.25 ⋅ (−1)] = −1 − 0.75 = −1.7

• 分析: 靠近终止状态（价值为0）的格子，其价值变得”不那么负”，因为它们有25%的概率一步就”逃离”并停止付出代价。而离终止状态远的格子，比如中心位置，其价值会变得更负（-2.0），因为它周围都是需要继续付出代价的格子。

k = 3 时的迭代:

• 随着迭代的继续，价值信息会像波一样从终止状态向远处传播。
• 迭代次数越多，价值函数就考虑得越”长远”。一个格子的价值反映了从它出发，在随机策略下平均需要走多少步才能到达终点。例如，在 k=∞ 时，中心的四个格子价值收敛为-20，表示从那里出发平均需要”走”20步才能结束。而紧邻终点的格子价值为-14，因为它们离”出口”更近。

回到策略迭代

既然我们已经根据策略评估计算出了价值函数，那么我们就可以根据价值函数来改进策略。这就是策略迭代的过程。

如何调整呢？最简单的方法就是贪婪法。考虑一种如下的贪婪策略：个体在某个状态下选择的行为是其能够到达后续所有可能的状态中状态价值最大的那个状态。如上面的图右边。当计算出最终的状态价值后发现，第二行第一个格子周围的价值分别是0,-18,-20，此时用贪婪法，调整行动策略为向状态价值为0的方向移动，而不是随机移动。也就是图中箭头向上。而此时第二行第二个格子周围的价值分别是-14,-14,-20, -20。那么整行动策略为向状态价值为-14的方向移动，也就是图中的向左向上。

图片右侧展示的内容就是策略迭代 (Policy Iteration) 思想的实际运用。这一列的箭头表示，如果我们根据左侧计算出的当前价值 v_k来做出“贪心”决策，我们应该选择哪个方向。所谓“贪心”，就是选择能移动到的那个价值最高的邻居格子。

演变过程如下:

• k = 0: 因为所有邻居价值都是0，所以往哪走都一样，策略是随机的。

• k = 1: 邻居中只有终止状态的价值（0）高于其他格子（-1），所以所有邻近终止状态的格子，其贪心策略都指向了终止状态。

• k = 2, 3…: 随着价值函数的精确化，贪心策略也变得越来越明确。箭头开始清晰地指向通往最近的终止状态的最短路径。

• k = 10, ∞: 此时，贪心策略已经稳定下来，不再改变。这个最终稳定下来的策略，就是该问题的最优策略 π*

因此策略迭代分为两步:

1. 策略评估 (Policy Evaluation)

对于当前固定的策略 π，我们需要计算出它所对应的真实的状态价值函数 V^π(s)。这个过程本身是一个迭代计算，通过反复应用贝尔曼期望方程的更新规则来进行，直到价值函数收敛。

计算公式 (迭代形式):

V^k + 1(s) ← ∑_a ∈ Aπ(a|s)(R(s, a) + γ∑_{s^′ ∈ S}P(s^′|s, a) ⋅ V^k(s^′))

在这个内循环中，我们不断用上一轮的价值估计 V^k 来计算新一轮的价值估计 V^k + 1，直到 V^k 和 V^k + 1 之间的差异足够小（小于某个阈值 θ）。

2. 策略改进 (Policy Improvement)

我们利用上一步评估出的价值函数 V^π(s)，对每一个状态的动作选择进行贪心 (Greedy) 的优化。

首先, 对于每个状态 s，我们先计算出所有可能的动作 a 的动作价值 Q^π(s, a)。这个q值代表了，如果仅在当前这一步选择动作 a，然后后续继续遵循旧策略 π，所能带来的期望总回报。

Q^π(s, a) = R(s, a) + γ∑_{s^′ ∈ S}P(s^′|s, a) ⋅ V^π(s^′)

然后，我们为状态 s 选择那个能够带来最大 q 值的动作，作为我们新策略 π_new 的选择。

π_new(s) ← arg max_aQ^π(s, a)

价值迭代 (Value Iteration)

价值迭代算法的目标非常纯粹：它旨在直接计算出每个状态的最优价值 U^*(s)。它认为，只要我们知道了每个状态的“终极价值”，那么在任何状态下，选择能通往更高价值邻居的动作，自然就是最优策略。

价值迭代的引擎只有一个，就是反复执行贝尔曼最优方程 (Bellman Optimality Equation) 的更新操作。

V^i + 1(s) ← max_a ∈ A(R(s, a) + γ∑_{s^′ ∈ S}P(s^′|s, a) ⋅ Vⁱ(s^′))

然后直接提取最优策略 π:

π^*(s) ← arg max_a (R(s, a) + γ∑_{s^′ ∈ S}P(s^′|s, a) ⋅ V_end(s^′))

最后, 我们总结这一讲的两种策略:

• 值迭代是在价值空间中进行搜索。它通过贝尔曼更新，逐步将效用函数逼近最优效用函数。

• 策略迭代则是在策略空间中进行搜索。它通过“评估-改进”的循环，一步步地跳向更优的策略。

他们都涉及到了动态规划的本质：利用问题的最优子结构（一个状态的价值依赖于其后继状态的价值），并通过迭代的方式，将后继状态的价值信息“备份”回当前状态，最终求解出全局最优解。

另一方面, 这两个算法都假设我们完全知道MDP的模型（即转移函数 T 和奖励函数 R）。它们是所谓的“基于模型的”方法。这为后续学习强化学习奠定了基础。

强化学习研究的核心问题之一就是：当智能体不知道这些模型时，如何通过与环境的交互来学习到最优策略。我们将会看到，强化学习中的许多算法，都可以被看作是值迭代或策略迭代的无模型 (model-free) 版本。