最优策略（Optimal Policy ）

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

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

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

最优状态值（Optimal State Value）：

对于任意状态 $s$，最优状态值 $v^*(s)$ 是所有可能策略中状态值的最大值：

\[v^*(s) = \max_{\pi} v_{\pi}(s)\]

其中 $v_{\pi}(s)$ 是策略 $\pi$ 下的状态值。

最优策略（Optimal Policy）：

如果一个策略的状态值在所有状态中均大于或等于其他策略的状态值，则该策略为最优策略：

\[\pi^* = \arg\max_{\pi} v_{\pi}(s), \forall s \in S\]

即最优策略总是选择使得状态值最大的动作。

性质：
- 存在性：最优策略总是存在。
- 唯一性：
  - 最优状态值 $v^*$ 是唯一的。
  - 最优策略 $\pi^*$ 可能不唯一，多种策略可能对应相同的最优状态值。
- 随机性或确定性：
  - 最优策略可以是随机的或确定的。
  - 总存在一个确定性的最优策略。

为了说明上述性质，我们研究贝尔曼最优方程 Bellman optimality equation（BOE）

贝尔曼最优方程（BOE）

定义

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

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

\[\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}\tag{1}\]

其中，$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$ 使得以下表达式最大
\[\sum_{i=1}^3 c_i q_i = c_1q_1 + c_2q_2 + c_3q_3\]

其中满足约束条件：$c_1 + c_2 + c_3 = 1$ 且 $c_1, c_2, c_3 \geq 0$。
不失一般性，假设 $q_3 \geq q_1, q_2$。那么最优解为：
\[c_3^* = 1, \quad c_1^* = c_2^* = 0\]

这是因为对于任意满足约束条件的 $c_1$, $c_2$, $c_3$，都有：
\[q_3 = (c_1 + c_2 + c_3)q_3 = c_1q_3 + c_2q_3 + c_3q_3 \geq c_1q_1 + c_2q_2 + c_3q_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{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}\tag{2}\]

当且仅当

\[\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$ 的函数，记为

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

其中 $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^*$为一个的不动点，如果满足

\[f(x^*)=x^*\]

Contraction mapping (or contractive function): 对于任意 $x_1,x_2$ ，$f$ 是一个Contraction mapping 如果存在一个 $γ∈(0,1)$ 满足：

\[\left\|f\left(x_1\right)-f\left(x_2\right)\right\| \leq \gamma\left\|x_1-x_2\right\|\]

💡 我们通过三个例子来演示不动点和压缩映射的概念。

示例 1: $f(x) = 0.5x, \, x \in \mathbb{R}$
很容易验证，当 $x = 0$ 时满足不动点性质，因为 $0 = 0.5 \cdot 0$。此外，$f(x) = 0.5x$ 是一个压缩映射，因为：
\[\| 0.5x_1 - 0.5x_2 \| = 0.5 \| x_1 - x_2 \| \leq \gamma \| x_1 - x_2 \| \]

其中 $\gamma \in [0.5, 1)$。

示例 2: $f(x) = Ax, \, x \in \mathbb{R}^n, \, A \in \mathbb{R}^{n \times n}, \, \|A\| \leq \gamma < 1$
同样可以验证，当 $x = 0$ 时满足不动点性质，因为 $0 = A \cdot 0$。为了验证压缩映射性质，有：
\[\| A x_1 - A x_2 \| = \| A (x_1 - x_2) \| \leq \|A\| \|x_1 - x_2\| \leq \gamma \|x_1 - x_2\| \]

因此，$f(x) = Ax$ 是一个压缩映射。

示例 3: $f(x) = 0.5 \sin(x), \, x \in \mathbb{R}$
可以很容易看出，当 $x = 0$ 时满足不动点性质，因为 $0 = 0.5 \sin(0)$。此外，根据均值定理：
\[\left| \frac{0.5 \sin(x_1) - 0.5 \sin(x_2)}{x_1 - x_2} \right| = \left| 0.5 \cos(x_3) \right| \leq 0.5, \, x_3 \in [x_1, x_2] \]

因此， $\left| 0.5 \sin(x_1) - 0.5 \sin(x_2) \right| \leq 0.5 \left| x_1 - x_2 \right|$，从而 $f(x) = 0.5 \sin(x)$是一个压缩映射。

Contraction Mapping Theorem

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

对于任何具有形式 $x=f(x)$ 的方程，如果 $f$ 是压缩映射，那么
存在：存在一个不动点 $x^∗$ 满足 $f(x^∗)=x^∗$。
唯一性：不动点 $x^∗$ 是唯一的。
算法：考虑一个迭代过程，序列 $\left\{x_k\right\}$，其中
\[ x_{k+1}=f\left(x_k\right) \]

当

$k \rightarrow \infty，x_k \rightarrow x^*$

。此时，收敛速度呈指数级。

证明参考：《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^*$ 可以通过以下公式计算：

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

将\tag{4}最优策略带入BOE 就可以得到，

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

这表明：

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

最优状态值的最优性

定理（最优性）：$v^*$ 是最优状态值，并且 $\pi^*$ 是最优策略，满足：
\[v^* = v_{\pi^*} \geq v_{\pi}, \quad \forall \pi \]

证明思路：

对任意策略 $\pi$，其状态值满足：

\[v_{\pi} = r_{\pi} + \gamma P_{\pi}v_{\pi}\]

而 $v^*$ 满足：

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

因此有，

\[v^* - v_\pi \geq (r_\pi + \gamma P_\pi v^) - (r_\pi + \gamma P_\pi v_\pi) = \gamma P_\pi (v^ - v_\pi)\]

通过对上述不等式反复迭代，我们得到：

\[v^* - v_\pi \geq \gamma P_\pi (v^* - v_\pi) \geq \gamma^2 P_\pi^2 (v^* - v_\pi) \geq \cdots \geq \gamma^n P_\pi^n (v^* - v_\pi)\]

当 $n \to \infty$ 时，由于 $\gamma < 1$ 且 $P_\pi$ 是一个非负矩阵，其所有元素都小于等于 1（因为 $P_\pi \mathbf{1} = \mathbf{1}$，即概率的总和为 1），所以有：

\[\lim_{n \to \infty} \gamma^n P_\pi^n (v^* - v_\pi) = 0.\]

因此，

\[v^* - v_\pi \geq 0.\]

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

定理（贪婪最优策略）：对于任意状态 $s\in S$，以下贪婪策略是最优的：
\[\pi^*(a|s) = \begin{cases} 1, & \text{if }\ a=a^*(s) \\ 0, & \text{if}\ \ a\ne a^*(s) \end{cases}\]

\[a^*(s) = \arg\max_{a} q^*(s, a)\]

其中
\[q^*(s, a) = \sum_{r \in R} p(r|s, a)r + \gamma \sum_{s' \in S} p(s'|s, a)v^*(s')\]

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

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

对应的 ement-wise形式的最优策略可以写为：

\[\pi^(s) = \arg \max_{\pi \in \Pi} \sum_{a \in A} \pi(a|s) \underbrace{\left( \sum_{r \in R} p(r|s, a)r + \gamma \sum_{s' \in S} p(s'|s, a)v^(s') \right)}_{q^*(s,a)}， s\in S\]

显然，$\sum_{a \in A} \pi(a|s) q^(s, a)$ 在 $\pi(s)$选择使 $q^(s, a)$ 最大的动作时达到最大值。因此，最优策略 $\pi^*(s$) 的选择规则是：

\[\pi^*(s) \text{ 选择使 } q^*(s, a) \text{ 最大的动作 } a。 \]

这说明最优策略总是选择在当前状态下能带来最大收益的动作。

解的唯一性

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

影响最优策略的因素

折扣因子 $\gamma$ 的影响

长远性与短视性：
- 较大的 $\gamma$（如 0.9）：策略更长远，可能冒险以获取更大的长期回报。
- 较小的 $\gamma$（如 0.5）：策略更短视，避免风险，专注于立即回报。
- 当 $\gamma = 0$ 时，策略完全短视，仅选择即时奖励最大的动作。
状态值的空间分布：
- 离目标状态越近，状态值越大；离目标状态越远，状态值越小。
- 这种分布是由于折扣因子的作用，远离目标的状态值会因折扣而变小。

奖励值 $r$ 的影响

奖励值的绝对大小：
- 增大“禁止区域”的惩罚（如 $r_{\text{forbidden}} = -10$）会使策略避免走入这些区域。
- 减小惩罚可能导致策略选择穿越“禁止区域”以缩短路径。
奖励值的仿射变换：

如果对奖励值 $r\in R$ 进行仿射变换 $\alpha r +\beta$，其中 $\alpha,\beta\in\mathbb{R}, \alpha >0$, 此时的最优策略不会改变，但最优状态值 $v^\prime$ 会随之做一个仿射变换：

\[v' = \alpha v^* + \frac{\beta}{1 - \gamma}\]

避免无意义绕路的避免

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

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

Reference

3 - Chapter 3 Optimal State Values and Bellman Optimality Equation.pdf

Bellman Optimality Equation

#

!

贝尔曼最优方程(Bellman Optimality Equation)