贝尔曼最优方程（Bellman Optimality Equation

Feb 24, 2025
2 views
Reinforcement Learning
# Reinforcement Learning

最优策略（Optimal Policy ）

之前在 贝尔曼方程中说过，状态值可以用来评估一个策略是好是坏，这里给出正式的概念：

\[ v_{\pi_1}(s) \geq v_{\pi_2}(s) \quad \text { for all } s \in \mathcal{S} \]

那么此时\(\pi_1\) 比 \(\pi_2\)”更好“

  • 最优状态值（Optimal State Value）：
  • 最优策略（Optimal Policy）：
  • 性质：
    为了说明上述性质， 我们研究贝尔曼最优方程 Bellman optimality equation（BOE）

贝尔曼最优方程（BOE）

定义

分析最优策略和最优状态值的工具是贝尔曼最优方程（BOE）。通过求解此方程，我们可以获得最优策略和最优状态值。

对于每个\(s∈S\)，BOE 的element-wise表达式为:

\[ \begin{equation}\begin{aligned}v(s) & = \max _{\pi(s) \in \Pi(s)} (\mathbb{E}\left[R_{t+1} \mid S_t=s\right]+\gamma \mathbb{E}\left[G_{t+1} \mid S_t=s\right]) \\& = \max _{\pi(s) \in \Pi(s)} \sum_{a \in \mathcal{A}} \pi(a \mid s)\left(\sum_{r \in \mathcal{R}} p(r \mid s, a) r+\gamma \sum_{s^{\prime} \in \mathcal{S}} p\left(s^{\prime} \mid s, a\right) v\left(s^{\prime}\right)\right) \\& =\max _{\pi(s) \in \Pi(s)} \sum_{a \in \mathcal{A}} \pi(a \mid s) q(s, a),\end{aligned}\end{equation} \]

其中，\(v(s)\) 和 \(v\left(s^{\prime}\right)\) 是待求解的未知变量，\(π(s)\) 表示状态 \(s\)的策略，而 \(Π(s)\) 是\(s\) 所有可能策略的集合。此时有，

\[ q\left( {s,a}\right) \doteq \mathop{\sum }\limits_{{r \in \mathcal{R}}}p\left( {r \mid s,a}\right) r + \gamma \mathop{\sum }\limits_{{{s}^{\prime } \in \mathcal{S}}}p\left( {{s}^{\prime } \mid s,a}\right) v\left( {s}^{\prime }\right) \]

最大化 BOE 右侧

这里我们讨论如何解决 BOE。在实践中，我们需要处理矩阵-向量形式，因为这是我们面临的问题。但是，由于矩阵中的每一行实际上是一个逐元素形式的向量，所以我们从元素形式开始。

实际上，我们可以将问题转化为“在右侧求解最优的 \(π\)”。让我们先看一个例子：

💡 例. 给定实数 \(q_1, q_2, q_3\)，我们要找到最优值 \(c_1, c_2, c_3\) 使得以下表达式最大

受上面示例的启发，BOE 右侧的最大化问题。BOE（element-wise）可以写成：

\[ v(s)=\max _{\pi(s) \in \Pi(s)} \sum_{a \in \mathcal{A}} \pi(a \mid s) q(s, a), \quad s \in \mathcal{S} . \]

受上述示例的启发，考虑到\(\sum_a \pi(a \mid s)=1\)，我们有

\[ \begin{equation}\begin{aligned} v(s) &= \max _\pi \sum_a \pi(a \mid s) q(s, a) \\&= \max _{a \in \mathcal{A}(s)} q(s, a) \end{aligned}\end{equation} \]

，当且仅当

\[ \pi(a \mid s)= \begin{cases}1 & a=a^* \\ 0 & a \neq a^*\end{cases} \]

时达到最优，其中\(a^*=\arg \max _a q(s, a)\)。

现在我们知道 BOE 的解是最大化右侧，我们也知道如何做到这一点——只需选择具有最大动作值的动作。但我们目前不知道动作值或状态值，所以这种方法不起作用。

实际上，BOE 的解来源于矩阵-向量形式的巴拿赫不动点定理（又称为压缩映射原理， contraction mapping theorem）。那是一种迭代方法（见后文）

所以为什么在这里引入(2) ？原因是在每次迭代期间，对于每个状态 \(s\)，动作值已经已知，因此我们可以使用 (2) 来获取最大化的右侧，这就是最大化的\(v(s)\) ！

BOE 矩阵形式：

利用巴拿赫不动点定理，我们将矩阵-向量形式表示为 \(v = f(v)\)。

由于 \(π\) 的最优值由 \(v\) 决定，BOE（矩阵-向量形式）的右侧是 \(v\) 的函数，记为

\[ \begin{equation} f(v) \triangleq \max _{\pi \in \Pi} \left(r_\pi+\gamma P_\pi v\right) . \end{equation} \]

其中 \(v \in \mathbb{R}^{|\mathcal{S}|}\) 且对 \(\max_{\pi}\) 按元素进行操作。\(r_{\pi}\) 和 \(P_{\pi}\) 的结构与普通贝尔曼方程的矩阵-向量形式相同：

\[ [r_{\pi}]_s \doteq \sum_{a \in \mathcal{A}} \pi(a|s) \sum_{r \in \mathcal{R}} p(r|s,a)r \]
\[ [P_{\pi}]_{s,s'} = p(s'|s) \doteq \sum_{a \in \mathcal{A}} \pi(a|s)p(s'|s,a) \]

然后，BOE 可以简洁地表示为

\[ v=f(v) \]

Contraction mapping theorem

现在将矩阵-向量形式表示为非线性方程 \(v=f(v)\)，接下来我们引入Contraction mapping theorem来分析它。

Fixed point and Contraction mapping

  • Fixed point: 对于函数\(f(x)\) , 其中，\(x∈\mathbb{R}^d\) , \(f:\mathbb{R}^d→\mathbb{R}^d\)，\(x^*\)为一个的不动点，如果满足
  • Contraction mapping (or contractive function): 对于任意 \(x_1,x_2\) ，\(f\) 是一个Contraction mapping 如果存在一个 \(γ∈(0,1)\) 满足：
    💡 我们通过三个例子来演示不动点和压缩映射的概念。

Contraction Mapping Theorem

不动点与压缩映射性质之间的关系由以下经典定理刻画。

对于任何具有形式 \(x=f(x)\) 的方程，如果 \(f\) 是压缩映射，那么

证明参考：《Mathematical Foundations of Reinforcement Learning》Box 3.1

Contraction property of BOE

\(f(v)\) 在 (3) 中是一个压缩映射，满足

\[ \left\|f\left(v_1\right)-f\left(v_2\right)\right\| \leq \gamma\left\|v_1-v_2\right\| \]

，其中 \(γ∈(0,1)\)是折扣率， \(‖⋅‖_∞\) 是最大范数，即向量元素的绝对值最大值。

证明参考：《Mathematical Foundations of Reinforcement Learning》Box 3.2

BOE方程求解

求解最优状态值 \(v^*\)** **

贝尔曼最优方程可以表示为：

\[ v^* = \max_{\pi \in \Pi} \left( r_{\pi} + \gamma P_{\pi}v^* \right) \]

\(v^*\) 是 BOE 的解，同时也是一个不动点，即满足 \(v^* = f(v^*)\)。

方程右侧是一个收缩映射，根据收缩映射定理，就会得到下面的结论

定理 （存在性、唯一性与算法），对于BOE \(v = f(v)=\max_{\pi \in \Pi} \left( r_{\pi} + \gamma P_{\pi}v \right)\), 总存在唯一BOE 的解 \(v^*\) 总是存在， 并且可以通过迭代算法求解， 即

$$
v_{k+1} = \max_{\pi \in \Pi} \left( r_{\pi} + \gamma P_{\pi}v_k \right), \quad k = 0, 1, 2, \dots

$$

  • 初始值 \(v_0\) 可以是任意的状态值向量。
  • 迭代过程会快速收敛到唯一的不动点 \(v^*\)。
  • 收敛速度是指数级的，即误差 \(\|v_k - v^*\|\) 随迭代次数 \(k\) 指数级减小。
  • 该方法称为值迭代算法（Value Iteration）

求解最优策略 \(\pi^*\)

一旦求得最优状态值 \(v^*\)，最优策略 \(\pi^*\) 可以通过以下公式计算：

\[ \begin{equation}\pi^* = \argmax_{\pi \in \Pi} \left( r_{\pi} + \gamma P_{\pi}v^* \right)\end{equation} \]

将(4) 式 最优策略带入BOE 就可以得到，

\[ v^* = r_{\pi^*} + \gamma P_{\pi^*}v^* \]

这表明：

  1. \(v^*\) 是最优策略 \(\pi^*\) 的状态值 \(v_{\pi^*}\)。
  2. BOE 是一个特殊的贝尔曼方程，其对应的策略是最优的。

最优状态值的最优性

定理 （最优性）：\(v^*\) 是最优状态值，并且 \(\pi^*\) 是最优策略， 满足：

🧾 证明思路：

由于 \(v^* - v_\pi \geq 0\)，说明对于任意策略 \(\pi\)，最优值函数 \(v^*\) 总是大于等于策略值函数 \(v_\pi\)。这表明最优策略的性能优于或等于任何其他策略。

定理（贪婪最优策略）：对于任意状态 \(s\in S\)，以下贪婪策略是最优的：

🧾 最优策略的矩阵-向量形式为：

解的唯一性

  • 虽然最优状态值 \(v^*\) 是唯一的，但最优策略 \(\pi^*\) 可能不唯一。
  • 不同的策略可能对应相同的最优状态值。例如，某些状态可能有多个动作具有相同的 \(q^*(s, a)\)。

影响最优策略的因素

折扣因子 \(\gamma\) 的影响

  • 长远性与短视性：
  • 状态值的空间分布：

奖励值 \(r\) 的影响

  • 奖励值的绝对大小：
  • 奖励值的仿射变换：

避免无意义绕路的避免

如果我们希望最优策略在到达目标之前能够避免无意义的弯路，那么我们是不是应该在每一步都增加一个负奖励，让Agent尽快到达目标呢？ 回答是不需要，

  • 首先，每一步都引入额外的负奖励是奖励的仿射变换，不会改变最优策略。
  • 其次，折扣率 \(\gamma\) 可以自动鼓励代理尽快达到目标。 这是因为无意义的弯路会增加轨迹长度并减少折扣的回报。

Reference

🔖 https://github.com/MathFoundationRL/Book-Mathematical-Foundation-of-Reinforcement-Learning/blob/main/3%20-%20Chapter%203%20Optimal%20State%20Values%20and%20Bellman%20Optimality%20Equation.pdf

🔖 https://lyk-love.cn/2024/01/07/bellman-optimality-equation/