RL 学习笔记 #2 贝尔曼公式

在上一节中，我们介绍了强化学习的基本概念，其中提到了用于评估「某状态的长期价值」的价值函数（Value Function）。

在本节中，我们将其定义为状态值（State Value）：从某一状态出发，沿着某个策略所能获得的奖励回报的期望值（Expected Return）。之所以是期望值，是因为该策略对应的轨迹可能有多条（因为一个状态下可能会采取不同动作，或者采取动作后可能会转移到多个不同状态）。而最终状态值越高，说明对应的策略越好。

状态值函数 | State Value Function

如上所述，状态值 \(v\) 与状态 \(s\) 和策略 \(\pi\) 存在对应关系，因此可以表示为 \(v_\pi(s)\)，也就是状态值函数。具体而言： \[ \begin{aligned} v_\pi(s) &= \mathbb{E}_\pi\left[G_t \mid S_t = s\right]\\ &= \mathbb{E}_\pi \left[\sum_{k=0}^\infty \gamma^k r_{t+k} \mid S_t = s \right]\\ \end{aligned} \] 其中：

• \(G_t\) 是累计奖励回报，\(S_t\) 是第 \(t\) 步开始前的状态；
• \(\gamma \in [0, 1]\) 是折扣因子，用于衡量未来奖励的衰减程度；
• \(r_t\) 是第 \(t\) 步的即时奖励。

假设一个简单的策略轨迹如下：\(s_1 \to s_2 \to s_3 \to s_4 \to s_1\)，则对于状态 \(s_i\) 的状态值 \(v_i\)，可以通过递推公式表示为： \[ \begin{aligned} v(s_i) &= r_i + \gamma r_{i+1} + \gamma^2 r_{i+2} + \cdots \\ &= r_i + \gamma \left( r_{i+1} + \gamma r_{i+2} + \cdots \right) \\ &= r_i + \gamma v(s_{i+1})\\ \end{aligned} \]

可以看出，状态之间的 Return 可以是相互依赖的，这种现象也被称为自举（Bootstrap）。如果将一组式子列出来，可以得到： \[ \underbrace{\left[\begin{array}{c} v_1 \\ v_2 \\ v_3 \\ v_4 \end{array}\right]}_{\mathbf{v}}=\left[\begin{array}{l} r_1 \\ r_2 \\ r_3 \\ r_4 \end{array}\right]+\left[\begin{array}{l} \gamma v_2 \\ \gamma v_3 \\ \gamma v_4 \\ \gamma v_1 \end{array}\right]=\underbrace{\left[\begin{array}{c} r_1 \\ r_2 \\ r_3 \\ r_4 \end{array}\right]}_{\mathbf{r}}+\gamma \underbrace{\left[\begin{array}{cccc} 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \\ 1 & 0 & 0 & 0 \end{array}\right]}_{\mathbf{P}} \underbrace{\left[\begin{array}{c} v_1 \\ v_2 \\ v_3 \\ v_4 \end{array}\right]}_{\mathbf{v}} \] 即： \[ \mathbf{v}=\mathbf{r}+\gamma \mathbf{P}\mathbf{v} \] 其中，\(\mathbf{P}\) 是状态转移概率矩阵，\(\mathbf{P}_{ij}\) 表示状态 \(s_i\) 转移到状态 \(s_j\) 的概率（策略 \(\pi\) 的选择已蕴含在 \(\mathbf{P}\) 中）。

这个式子就是贝尔曼公式的矩阵向量形式，只需变形即可求解： \[ \mathbf{v} = (\mathbf{I} - \gamma \mathbf{P})^{-1} \mathbf{r} \]

贝尔曼公式 | Bellman Equation

向量形式是贝尔曼公式的具体表现，它描述了所有状态值之间的递归关系。

这里我们正式介绍，对于任意策略 \(\pi\)，状态值函数满足： \[ \begin{aligned} v_\pi(s) &= \mathbb{E}_\pi\left[G_t \mid S_t = s\right]\\ &= \mathbb{E}_\pi\left[R_{t+1}+\gamma G_{t+1} \mid S_t = s\right]\\ &= \mathbb{E}_\pi\left[R_{t+1} \mid S_t = s\right] + \gamma \mathbb{E}_\pi\left[G_{t+1} \mid S_t = s\right]\\ \end{aligned} \] 其中，第一项表示即时奖励的期望： \[ \begin{aligned} \mathbb{E}\left[R_{t+1} \mid S_t=s\right] & =\sum_a \pi(a \mid s) \mathbb{E}\left[R_{t+1} \mid S_t=s, A_t=a\right] \\ & =\sum_a \pi(a \mid s) \sum_r p(r \mid s, a) r \end{aligned} \] 第二项表示未来奖励的期望（利用马尔可夫性质）： \[ \begin{aligned} \mathbb{E}\left[G_{t+1} \mid S_t=s\right] & =\sum_{s^{\prime}} \mathbb{E}\left[G_{t+1} \mid S_t=s, S_{t+1}=s^{\prime}\right] p\left(s^{\prime} \mid s\right) \\ & =\sum_{s^{\prime}} \mathbb{E}\left[G_{t+1} \mid S_{t+1}=s^{\prime}\right] p\left(s^{\prime} \mid s\right) \\ & =\sum_{s^{\prime}} v_\pi\left(s^{\prime}\right) p\left(s^{\prime} \mid s\right) \\ & =\sum_{s^{\prime}} v_\pi\left(s^{\prime}\right) \sum_a p\left(s^{\prime} \mid s, a\right) \pi(a \mid s)\\ & = \sum_a \pi(a \mid s) \sum_{s^{\prime}} p\left(s^{\prime} \mid s, a\right) v_\pi\left(s^{\prime}\right) \end{aligned} \] 整合后可得一般形式的贝尔曼公式： \[ v_\pi(s)=\sum_a \pi(a \mid s) \left[ \sum_r p(r \mid s, a) r + \gamma \sum_{s^{\prime}} p\left(s^{\prime} \mid s, a\right) v_\pi\left(s^{\prime}\right) \right] \] 其中：

• \(v_\pi(s)\) 和 \(v_\pi\left(s^{\prime}\right)\) 是待求解对象，也就是 Bootstrap 的目标；
• \(p(r \mid s, a)\) 和 \(p\left(s^{\prime} \mid s, a\right)\) 代表了模型（model-based），这里我们假设模型已知——之后还会介绍无模型（model-free）算法。

上式可以直观地理解为：状态值是当前状态下，所有可采取的动作，带来的即时奖励和未来状态值的折现和。

策略评估 | Policy Evaluation

上述贝尔曼公式不仅仅是一个单独的式子，而是对所有 \(\forall s \in S\) 都成立的。策略评估（Policy Evaluation）就是通过一组贝尔曼公式求解状态值函数的过程。只有通过评价策略的好坏，才能进一步地改进策略，最终找到最优策略。

第一种方法是，通过矩阵形式 \(\mathbf{v} = (\mathbf{I} - \gamma \mathbf{P})^{-1} \mathbf{r}\) 直接求解精确解。但对于高维状态空间，求逆矩阵的计算量过大，这种方法通常不可行。

第二种方法是，基于 Bootstrap 特性，可以采用迭代法（称为贝尔曼期望方程迭代）：

1. 初始化状态值函数 \(v_\pi(s)\) 为一个猜测值 \(v_\pi^{(0)}(s)\) ；

2. 不断更新： \[ v_\pi^{(k+1)}(s) = r_\pi(s) + \gamma P_\pi \cdot v_\pi^{(k)}\left(s\right) \]

3. 直到 \(v_\pi\) 收敛，即 \(\lVert v_\pi^{(k+1)} - v_\pi^{(k)} \rVert < \epsilon\)。

动作价值 | Action Value

除了状态值函数 \(v_\pi(s)\)，另一个非常重要的概念是动作价值函数（Action Value Function），记为 \(q_\pi(s, a)\)。它不仅仅考虑某个状态的长期价值，还具体评估在该状态下选择某一动作的长期价值。

状态价值虽然建立起了策略的评估体系，但是策略关注的根本问题是「当前状态下需要选择哪个动作」。这个时候动作价值将动作选择与策略评估进一步结合，其是构建策略迭代、Q-learning 等核心算法的基础。

这里我们正式介绍，在策略 \(\pi\) 下，从状态 \(s\) 开始选择动作 \(a\) 后，动作价值函数满足： \[ \begin{aligned} q_\pi(s, a) &= \mathbb{E}_\pi\left[G_t \mid S_t = s, A_t = a\right]\\ &= \mathbb{E}_\pi \left[ \sum_{k=0}^\infty \gamma^k r_{t+k} \mid S_t = s, A_t = a \right]\\ \end{aligned} \] 基于上式，我们可以写出动作价值函数与状态值函数的数学关系： \[ \begin{aligned} v_\pi(s) &= \mathbb{E}_\pi\left[G_t \mid S_t = s\right]\\ &=\sum_a \mathbb{E}_\pi\left[G_t \mid S_t = s, A_t = a\right]\pi(a \mid s) \\ &= \sum_a \pi(a \mid s) q_\pi(s, a)\\ \end{aligned} \] 这意味着状态值是动作价值的加权平均，而权重由策略 \(\pi(a \mid s)\) 决定。

此外，观察和比较状态值函数的一般化贝尔曼公式，也可以进一步写出： \[ q_\pi(s, a) =\sum_r p(r \mid s, a) r + \gamma \sum_{s^{\prime}} p\left(s^{\prime} \mid s, a\right) v_\pi\left(s^{\prime}\right) \] 这些式子告诉我们：

• 如果知道模型和当前策略的所有状态值，就能计算出所有的动作价值。
• 如果知道当前状态的所有动作价值，就能计算出当前策略的状态值。

注意：当前策略未必能涵盖所有动作，只不过计算时 \(\pi(a \mid s)=0\) 而被忽略了。而未被涵盖的动作价值其实不一定为 \(0\)，甚至可能更高——这决定了策略优化的方向（但不一定直接就是最优策略，因为此时其他状态值可能还未收敛）。

除了先计算状态值再计算动作价值，也可以通过 Model-free 的方法，用数据来估计。

贝尔曼最优公式 | BOE

每一个贝尔曼公式都对应了一个策略，而贝尔曼最优公式（Bellman Optimality Equation）作为一个特殊的贝尔曼公式，则对应最优策略（Optimal Policy）和最优状态值（Optimal State Value）——沿着最优策略能够得到最大状态值。

对于两个策略 \(\pi_1\) 和 \(\pi_2\)，若满足：\(v_{\pi_1}(s) \ge v_{\pi_2}(s),\;\; \forall s \in S\)，则认为 \(\pi_1\) 优于 \(\pi_2\)。

进一步地，当一个策略 \(\pi^*\) 满足：\(v_{\pi^*}(s) \ge v_{\pi}(s),\;\; \forall s \in S \land \forall \pi \ne \pi^*\)，则称 \(\pi^*\) 为最优策略。

接下来，我们就需要回答一系列问题：

• 最优策略 \(\pi^*\) 是否存在？
• 最优策略 \(\pi^*\) 是否唯一？
• 最优策略 \(\pi^*\) 是确定性的还是随机性的？
• 最优策略 \(\pi^*\) 如何得到？

为了回答这些问题，我们先引入贝尔曼最优公式的一般形式： \[ \begin{aligned} v(s) &= \max_\pi \sum_a \pi(a \mid s) \left[ \sum_r p(r \mid s, a) r + \gamma \sum_{s^{\prime}} p\left(s^{\prime} \mid s, a\right) v\left(s^{\prime}\right) \right]\\ &= \max_\pi\sum_a \pi(a \mid s) q(s, a)\\ \end{aligned} \] 其中：

• 已知模型 \(p(r \mid s, a)\) 和 \(p\left(s^{\prime} \mid s, a\right)\)，已知环境参数 \(r\)，已知常量 \(\gamma\)；
• 待求解状态值函数 \(v(s)\) 和 \(v(s^{\prime})\)，待求解策略 \(\pi(s)\)。

当然，我们也可以有矩阵向量形式，但这里暂时不需要： \[ \mathbf{v}= \max_\pi (\mathbf{r}_\pi+\gamma \mathbf{P}_\pi\mathbf{v}) \]

BOE 的化简过程

此时等式右侧是一个最优化问题，但有两个未知量需要求解。由于 \(\pi\) 是最优化问题的变量，可以先确定 \(\pi(a \mid s)\) 再去求解剩下的未知量。

对于一次多项式而言，我们希望将最大的 \(q(s, a)\) 分配最大权重。显然，当 \(\pi(a \mid s)\) 是确定性策略时，即 \(\pi(a \mid s) = 1\) 仅针对最优动作 \(a^* = \arg\max_a q(s, a)\) 时，能实现最大化。于是，最优策略满足： \[ \pi^*(a \mid s) = \begin{cases} 1 & \text{if } a = a^*, \\ 0 & \text{otherwise}. \end{cases} \] 此时我们有状态值： \[ v(s)= \max_\pi\sum_a \pi(a \mid s) q(s, a)=\max_{a\in A(s)} q(s, a) \]

通过重新整理，贝尔曼最优公式可表示为： \[ v_*(s) = \max_a \left[ \sum_r p(r \mid s, a) r + \gamma \sum_{s'} p(s' \mid s, a) v_*(s') \right] \] 这是一个递归定义，其中右侧仅依赖于 \(v_*\) 本身，可以写作： \[ v_* = f(v_*) \] 其中，\(f(v)\) 是一个映射，将当前估计的值函数更新为更接近实际的值函数。

不动点与收敛性：Contraction Mapping

我们需要解的是 \(v = f(v)\) 的不动点（Fixed Point），即在 \(f\) 的作用下不再发生变化的 \(v\)。在强化学习中，值函数的迭代计算会逐渐逼近这个不动点。

如果 \(f(v)\) 是一个收缩映射（Contraction Mapping），即满足以下性质： \[ \lVert f(v_1) - f(v_2) \rVert \leq \gamma \lVert v_1 - v_2 \rVert, \quad \gamma \in [0, 1) \] 则可以保证了值函数迭代的收敛性。

收缩映射规定参数 \(\gamma\) 是严格小于 \(1\) 的数字，这样才能确保在映射过程中 \(v_1\) 和 \(v_2\) 相互靠近。

例如：对于 \(x=f(x)=0.5x,\;\; x \in \mathbb{R}\)，我们可以很容易的发现 \(x=0\) 是一个不动点。此外，\(f(x)=0.5x\) 是一个收缩映射，因为： \[ \lVert 0.5x_1 - 0.5x_2 \rVert = 0.5 \lVert x_1 - x_2 \rVert = \leq \gamma \lVert x_1 - x_2 \rVert, \;\; \text{for any } \gamma \in [0, 1) \] 又例如：对于 \(x=f(x)=Ax,\;\;x \in \mathbb{R}, \;\; A \in \mathbb{R}^{n\times n}\)，其中 \(\lVert A \rVert \le \gamma < 1\)，同样也可以证明 \(x=0\) 是一个不动点，且 \(f(x)\) 是一个收缩映射。

这里再介绍一下收缩映射定理（Contraction Mapping Theorem）。对于一个形如 \(x=f(x)\) 的等式，如果 \(f\) 是一个收缩映射，则：

• 有且仅有一个不动点 \(x^*\) 使得 \(f(x^*)=x^*\)；
• 可以通过迭代式算法 \(x_{k+1}=f(x_k)\) 求解不动点：当 \(k\to \infty\) 时，\(x_k \to x^*\)，且收敛速率呈指数倍。

证明 \(f(x)\) 是收缩映射 [选读]

为了证明 \(f(v)\) 是一个收缩映射，我们先对任意状态 \(s\)，计算 \(f(v_1)(s) - f(v_2)(s)\) 的绝对值： \[ \begin{aligned} \left| f(v_1)(s) - f(v_2)(s) \right| &= \left| \max_a \left[ \sum_r p(r \mid s, a) r + \gamma \sum_{s'} p(s' \mid s, a) v_1(s') \right] \right. \\ & \quad \left. - \max_a \left[ \sum_r p(r \mid s, a) r + \gamma \sum_{s'} p(s' \mid s, a) v_2(s') \right] \right| \end{aligned} \] 由于最大值运算是一个非扩张运算（Non-Expansive），对于任意两个实数序列 \(x_i\) 和 \(y_i\)，有： \[ \left| \max_i x_i - \max_i y_i \right| \leq \max_i \left| x_i - y_i \right| \] 因此，可以将上式改写为： \[ \left| f(v_1)(s) - f(v_2)(s) \right| \leq \max_a \left| \gamma \sum_{s'} p(s' \mid s, a) v_1(s') - \gamma \sum_{s'} p(s' \mid s, a) v_2(s') \right| \] 将 \(\gamma\) 提取出来，利用状态转移概率 \(p(s' \mid s, a)\) 的线性性： \[ \left| f(v_1)(s) - f(v_2)(s) \right| \leq \gamma \max_a \sum_{s'} p(s' \mid s, a) \left| v_1(s') - v_2(s') \right| \] 状态转移概率 \(p(s' \mid s, a)\) 是一个和为 \(1\) 的分布，因此 \(\sum_{s'} p(s' \mid s, a) \left| v_1(s') - v_2(s') \right|\) 是 \(\left| v_1(s') - v_2(s') \right|\) 的加权平均值，不超过 \(\lVert v_1 - v_2 \rVert_\infty\)。因此： \[ \left| f(v_1)(s) - f(v_2)(s) \right| \leq \gamma \lVert v_1 - v_2 \rVert_\infty \] 取 \(\lVert \cdot \rVert_\infty\) 范数的全局最大值后，得到： \[ \lVert f(v_1) - f(v_2) \rVert_\infty \leq \gamma \lVert v_1 - v_2 \rVert_\infty \] 由于 \(\gamma \in [0, 1)\)，我们证明了 \(f(v)\) 是一个收缩映射。根据 Banach 不动点定理，收缩映射在完备空间上（如 \(\mathbb{R}^n\) 下的 \(\lVert \cdot \rVert_\infty\) 范数空间）有唯一的不动点。因此，贝尔曼最优公式的解 \(v_*\) 唯一存在，并可以通过迭代方法（如值迭代法）收敛到该解。

BOE 的性质

现在，我们可以回答前面提到的一系列问题：

• 最优策略 \(\pi^*\) 是否存在？答：存在，且对应最优状态 \(v_*\)，并且可证明策略最优性（此处不赘述）。
• 最优策略 \(\pi^*\) 是否唯一？答：最优状态 \(v_*\) 唯一存在，但最优策略 \(\pi^*\) 可能有多个。
• 最优策略 \(\pi^*\) 是确定性的还是随机性的？答：确定性策略，贪心选择 \(a^*\)。
• 最优策略 \(\pi^*\) 如何得到？答：可通过迭代法求解，将在下一章介绍。

这里补充一些影响最优策略的因素：

• 当 \(\gamma\) 接近 \(1\)，智能体越关注长期收益，可能会做出当下看来不利的动作，例如进入违禁区；
• 当 \(\gamma\) 降低，智能体则更关注短期奖励，起点附近的状态值会较低，高状态值集中在终点附近；
• 当 \(\gamma\) 降到 \(0\)，智能体完全短视，只关注即时奖励，只有终点或边界清晰的地方有决策，其他地方会随机选取动作，从很多状态出发甚至到达不了重点；
• 当 \(\gamma\) 接近 \(1\) 但改变部分 \(r\)，例如增大违禁区的惩罚，也会导致智能体减少不利动作；
• 而当所有 \(r\) 修改为 \(ar+b\) 时，此时的最优策略不会变化，而最优状态值则变为：

\[ v^{\prime}=a v^*+\frac{b}{1-\gamma} \mathbf{1} \]

最后是一个关于最短路径的分析：初学者往往会给 Agent 的每个步骤加上基础惩罚（代表能量消耗），来避免出现绕路（meaningless detour）的现象。但实际上无需这种惩罚 Agent 也会走最短路径，因为还有 \(\gamma\) 作为约束——绕路意味着到达目标状态越晚，而 \(\gamma\) 带来的折扣就越大！