最优策略（Optimal Policy ）

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

那么此时${\pi }_1$ 比 ${\pi }_2$”更好“

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

贝尔曼最优方程（BOE）

定义

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

对于每个$s\in S$，BOE 的element-wise表达式为:

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

最大化 BOE 右侧

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

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

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

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

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

，当且仅当

时达到最优，其中$a^{\ast }=\arg {\max }_{a}q(s,a)$。

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

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

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

BOE 矩阵形式：

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

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

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

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

Contraction mapping theorem

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

Fixed point and Contraction mapping

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

Contraction Mapping Theorem

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

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

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

Contraction property of BOE

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

，其中 $\gamma \in (0,1)$是折扣率， $\Vert \cdot {\Vert }_{\infty }$ 是最大范数，即向量元素的绝对值最大值。

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

BOE方程求解

求解最优状态值 **$v^{\ast }$ **

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

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

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

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

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

**求解最优策略 **${\pi }^{\ast }$

一旦求得最优状态值 $v^{\ast }$，最优策略 ${\pi }^{\ast }$ 可以通过以下公式计算：

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

这表明：

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

最优状态值的最优性

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

🧾 证明思路：

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

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

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

解的唯一性

• 虽然最优状态值 $v^{\ast }$* 是唯一的，但最优策略 *${\pi }^{\ast }$ 可能不唯一。
• 不同的策略可能对应相同的最优状态值。例如，某些状态可能有多个动作具有相同的 $q^{\ast }(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/