贝尔曼方程提供了价值函数的递归关系。特别是贝尔曼最优方程,定义了最佳可能价值函数($V^$ 或 $Q^$)。那么,如何找到那个最优价值函数及其对应的最优策略 $\pi^*$ 呢?动态规划(DP)提供了一类算法,可以在我们拥有环境的完整模型的前提下,计算出最优策略。这意味着我们需要了解所有状态 $s$、动作 $a$、下一个状态 $s'$ 和奖励 $r$ 的转移概率 $p(s', r | s, a)$。这是一个很强的假设,在实践中通常不满足(这就是为什么我们稍后会学习无模型方法!),但DP提供了一个坚实的理论依据。一个基本的DP方法是策略迭代。它通过在评估当前策略和改进策略这两个主要步骤之间交替进行,来找到最优策略。我们来详细分析一下。假设您从某个任意策略开始,我们称之为 $\pi_0$。它可能是完全随机的,也可能是基于某种简单的启发式方法。策略迭代旨在迭代地改进此策略,直到它收敛到最优策略 $\pi^*$。过程如下所示:$\pi_0 \xrightarrow{\text{评估}} V^{\pi_0} \xrightarrow{\text{改进}} \pi_1 \xrightarrow{\text{评估}} V^{\pi_1} \xrightarrow{\text{改进}} \pi_2 \xrightarrow{\text{评估}} \dots \xrightarrow{\text{改进}} \pi^* \xrightarrow{\text{评估}} V^*$这包括在循环中重复的两个核心组成部分:策略评估: 给定一个策略 $\pi$,计算其状态价值函数 $V^\pi$。策略改进: 使用计算出的 $V^\pi$,通过相对于 $V^\pi$ 贪婪地采取行动,生成一个新的、可能更好的策略 $\pi'$。这个循环持续进行,直到策略在迭代之间不再改变,表明我们已经找到了最优策略。策略评估:当前策略有多好?在此步骤中,我们采用当前策略 $\pi$ 并计算所有状态 $s$ 的状态价值函数 $V^\pi(s)$。回想一下 $V^\pi$ 的贝尔曼期望方程:$$ V^\pi(s) = \sum_a \pi(a|s) \sum_{s', r} p(s', r | s, a) [r + \gamma V^\pi(s')] $$对于一个有限MDP,此方程为我们提供了一个线性方程组,每个状态对应一个方程。如果存在 $|S|$ 个状态,我们就有 $|S|$ 个方程和 $|S|$ 个未知数(每个 $s$ 的 $V^\pi(s)$)。我们可以直接求解此系统。然而,一个通常更简单且更普适的方法,尤其是在策略迭代的迭代性质中,是迭代地计算 $V^\pi$。我们从一个任意价值函数 $V_0$(例如,全零)开始,并重复应用贝尔曼期望方程作为更新规则:$$ V_{k+1}(s) \leftarrow \sum_a \pi(a|s) \sum_{s', r} p(s', r | s, a) [r + \gamma V_k(s')] \quad \text{对于所有 } s \in S $$我们遍历所有状态,根据上一次迭代的值($V_k$)更新它们的值。当 $k \to \infty$ 时,此过程保证收敛到真实的 $V^\pi$。在实践中,当价值函数在迭代之间的变化变得非常小(即当 $|V_{k+1} - V_k|_{\infty} < \theta$ 对于某个小阈值 $\theta$)时,我们停止。这种迭代方法本质上是重复应用贝尔曼算子。策略改进:我们能做得更好吗?一旦我们对当前策略 $\pi$ 的 $V^\pi$ 有了相当准确的估计,我们就会问:“我们能改进这个策略吗?” 策略改进定理为我们提供了实现此目的的方法。对于给定状态 $s$,我们可以向前看一步,并考虑如果我们选择一个动作 $a$(可能不同于 $\pi(a|s)$),然后遵循现有策略 $\pi$ 之后的预期回报。这正是动作价值函数 $Q^\pi(s, a)$ 的定义:$$ Q^\pi(s, a) = \sum_{s', r} p(s', r | s, a) [r + \gamma V^\pi(s')] $$现在,假设对于某个状态 $s$,我们发现一个动作 $a$,使得 $Q^\pi(s, a) > V^\pi(s)$。这意味着在状态 $s$ 中只采取动作 $a$,然后遵循 $\pi$,比从一开始就只遵循 $\pi$ 要好。策略改进定理指出,如果我们构建一个新策略 $\pi'$,它在状态 $s$ 中选择这个“更好”的动作 $a$(并在其他地方遵循 $\pi$,或者更好的是,在任何地方都贪婪地采取行动),那么新策略 $\pi'$ 将严格优于或等于 $\pi$。改进策略最常用的方法是使其相对于 $V^\pi$ 是贪婪的。也就是说,对于每个状态 $s$,新策略 $\pi'(s)$ 确定性地选择使 $Q^\pi(s, a)$ 最大化的动作 $a$:$$ \pi'(s) \leftarrow \underset{a}{\mathrm{argmax}} , Q^\pi(s, a) = \underset{a}{\mathrm{argmax}} \sum_{s', r} p(s', r | s, a) [r + \gamma V^\pi(s')] $$这个新的贪婪策略 $\pi'$ 保证至少和 $\pi$ 一样好。如果 $V^{\pi'} = V^\pi$,那么我们已经达到了最优价值函数 $V^$ 和最优策略 $\pi^$,因为我们满足贝尔曼最优方程。如果 $V^{\pi'} \neq V^\pi$,那么 $\pi'$ 严格更好,我们循环回评估这个改进后的策略。策略迭代算法综合起来,策略迭代算法步骤如下:初始化:选择一个任意的初始策略 $\pi(s)$,对于所有 $s \in S$。选择一个任意的初始价值函数 $V(s)$,对于所有 $s \in S$(例如,$V(s)=0$)。策略评估循环:重复直到 $V$ 收敛:$\Delta \leftarrow 0$对于每个状态 $s \in S$:$v \leftarrow V(s)$$V(s) \leftarrow \sum_a \pi(a|s) \sum_{s', r} p(s', r | s, a) [r + \gamma V(s')]$ (右侧使用前一次迭代的 $V$ 值,如果原地更新则使用最新可用值)$\Delta \leftarrow \max(\Delta, |v - V(s)|)$如果 $\Delta < \theta$(一个小的正阈值):跳出评估循环。策略改进:policy_stable $\leftarrow$ true对于每个状态 $s \in S$:old_action $\leftarrow \pi(s)$ (为简化起见,假设是确定性策略)$\pi(s) \leftarrow \underset{a}{\mathrm{argmax}} \sum_{s', r} p(s', r | s, a) [r + \gamma V(s')]$如果 old_action $\neq \pi(s)$:policy_stable $\leftarrow$ false重复或终止:如果 policy_stable 为真:停止。当前策略 $\pi$ 和价值函数 $V$ 是最优的($\pi^$ 和 $V^$)。否则:返回步骤2(策略评估)。digraph PolicyIteration { rankdir=TD; node [shape=box, style=rounded, fontname="helvetica", fontsize=10]; edge [fontname="helvetica", fontsize=10]; init [label="任意初始化 V(s)\n任意初始化策略 π(s)"]; eval [label="策略评估:\n迭代计算 V^π\n使用贝尔曼期望方程\n直到收敛", shape=parallelogram, style=filled, fillcolor="#a5d8ff"]; improve [label="策略改进:\n相对于 V^π 贪婪地更新 π:\nπ'(s) ← argmax_a Q^π(s,a)", shape=parallelogram, style=filled, fillcolor="#b2f2bb"]; check [label="π 是否稳定?", shape=diamond, style=filled, fillcolor="#ffec99"]; stop [label="最优策略 π*\n最优价值 V*", shape=octagon, style=filled, fillcolor="#ced4da"]; init -> eval; eval -> improve; improve -> check; check -> eval [label=" 否"]; check -> stop [label=" 是"]; }策略迭代中策略评估和策略改进的循环。该过程持续进行,直到在改进步骤后策略不再改变。策略迭代保证在有限MDP中通过有限次数的迭代收敛到最优策略 $\pi^*$。这是因为只有有限数量的可能策略,并且每个策略改进步骤都会产生一个严格更好的策略(除非它已经是最优的)。由于与每个策略相关的价值函数增加或保持不变,并且值是有界的,因此该过程必须终止。“主要缺点是什么?每一步,特别是策略评估,计算成本可能很高,可能需要多次遍历整个状态空间。此外,它严重依赖于拥有完整的MDP模型($p(s', r | s, a)$),这在实际问题中通常不可用。这个限制促使我们在后续章节中讨论无模型方法。”