强化学习的数学原理（三）：贝尔曼最优公式
在强化学习中，我们的最终目标是寻找一个最优策略（Optimal Policy），使得智能体（Agent）在与环境交互时能够获得最大的累积奖励。贝尔曼最优性方程是实现这一目标的基础工具，它为我们定义了最优价值函数，并指明了通向最优策略的道路。
一、最优策略与最优价值函数
1. 核心概念 (Core Concepts)
- 最优状态价值函数 (Optimal State value): $v^*(s)$
- 最优策略 (Optimal Policy): $\pi^*$
2. 最优策略的定义 (Optimal Policy)
如何判断一个策略比另一个策略更优？
如果对于所有状态 $s \in S$，策略 $\pi_1$ 的状态价值函数 $v_{\pi_1}(s)$ 始终大于或等于策略 $\pi_2$ 的状态价值函数 $v_{\pi_2}(s)$，那么我们称策略 $\pi_1$ “优于” $\pi_2$。 $$\text{if } v_{\pi_1}(s) \ge v_{\pi_2}(s) \text{ for all } s \in S, \text{ then } \pi_1 \text{ is “better” than } \pi_2.$$ 定义: 如果一个策略 $\pi^*$ 对于任何其他策略 $\pi$ 都满足 $v_{\pi^*}(s) \ge v_{\pi}(s)$（对所有状态 $s$ 成立），那么 $\pi^*$ 就是一个 最优策略。
3. 几个基本问题 (Some Questions)
- 最优策略是否存在？
- 最优策略是否唯一？
- 最优策略是确定性的还是随机性的？
- 如何获得最优策略？
贝尔曼最优性方程将帮助我们解答以上问题。
二、贝尔曼最优性方程 (Bellman Optimality Equation, BOE)
贝尔曼最优性方程给出了最优价值函数的直接计算方式。
1. 元素形式 (Element-wise Form)
最优状态价值函数 $v^*(s)$ 等于在所有可能的动作中，选择那个能够带来最大期望回报的动作所对应的价值。
$$ \begin{aligned} v^*(s) &= \max_{\pi} \sum_a \pi(a|s) \left( \sum_r p(r|s,a)r + \gamma \sum_{s’} p(s’|s,a)v^*(s’) \right), \quad \forall s \in S \ &= \max_a \sum_a \pi(a|s) q^*(s,a) \end{aligned} $$
其中 $q^*(s,a)$ 是最优动作价值函数。
注解 (Remarks):
- 我们假设环境动态 $p(r|s,a)$ 和 $p(s’|s,a)$ 是已知的，这属于 基于模型 (Model-based) 的情况。
- $v^*(s)$ 和 $v^*(s’)$ 是待求解的未知量。
- 策略 $\pi(a|s)$ 同样是待计算的未知量。
2. 矩阵-向量形式 (Matrix-vector Form)
我们可以将贝尔曼最优性方程表示为更紧凑的矩阵向量形式。
Let $\vec{v}^* = \max_{\pi} (\vec{r}_{\pi} + \gamma P_{\pi} \vec{v}^*)$
其中：
- $[\vec{r}_{\pi}]_s \triangleq \sum_a \pi(a|s) \sum_r p(r|s,a)r$
- $[P_{\pi}]_{s,s’} \triangleq \sum_a \pi(a|s) \sum_{s’} p(s’|s,a)$
我们的目标是求解两个量：最优价值向量 $\vec{v}^*$ 和最优策略 $\pi^*$。
三、求解贝尔曼最优性方程
1. 固定 $v^*(s’)$ 求解 $\pi$
假设我们已经知道了最优的 $v^*(s’)$，那么求解最优策略就变得很简单。对于每个状态 $s$，最优策略会选择能使期望回报最大化的动作 $a$。
$$v^*(s) = \max_a \sum_a \pi(a|s)\left( \sum_r p(r|s,a)r + \gamma \sum_{s’} p(s’|s,a)v^*(s’) \right)$$
$$v^*(s) = \max_a q^*(s,a)$$
由于 $\sum_a \pi(a|s) = 1$，最大化 $\sum_a \pi(a|s)q^*(s,a)$ 的方法是给 $q^*(s,a)$ 值最大的那个动作 $a^*$ 分配全部概率。
此时，最优策略是一个确定性策略： $$\pi^*(a|s) = \begin{cases} 1 & \text{if } a = a^* \\ 0 & \text{if } a \neq a^* \end{cases}$$ 其中： $$a^* = \arg\max_{a \in A(s)} q^*(s,a)$$
2. 利用不动点理论求解
贝尔曼最优性方程的求解可以看作一个寻找不动点（Fixed Point）的过程。
引入一些概念:
- 不动点 (Fixed Point): 点 $x \in X$ 是函数 $f: X \to X$ 的一个不动点，如果 $f(x) = x$。
- 压缩映射 (Contraction Mapping): 如果存在一个常数 $\gamma \in [0, 1)$，使得对于任意 $x_1, x_2$，都有 $||f(x_1) - f(x_2)|| \le \gamma ||x_1 - x_2||$，则称函数 $f$ 是一个压缩映射。
压缩映射定理 (Contraction Mapping Theorem): 对于任何形如 $x = f(x)$ 的方程，如果 $f$ 是一个压缩映射，则：
- 存在性 (Existence): 存在一个不动点 $x^*$，使得 $f(x^*) = x^*$。
- 唯一性 (Uniqueness): 这个不动点 $x^*$ 是唯一的。
- 算法 (Algorithm): 迭代序列 $x_{k+1} = f(x_k)$ 会收敛到 $x^*$，即 $x_k \to x^*$ as $k \to \infty$。
利用压缩映射定理求解 BOE:
我们定义一个贝尔曼最优算子 $f$: $$f(\vec{v}) = \max_{\pi} (\vec{r}_{\pi} + \gamma P_{\pi}\vec{v})$$ 可以证明，$f(\vec{v})$ 是一个压缩映射。因此，贝尔曼最优性方程 $\vec{v} = f(\vec{v})$ 必然存在唯一的解 $\vec{v}^*$，但最优 State value 对应的策略不一定是唯一的，可能会有多个trajectory走到最优解。
我们可以通过迭代的方式找到这个解： $$\vec{v}_{k+1} = f(\vec{v}_k) = \max_{\pi} (\vec{r}_{\pi} + \gamma P_{\pi}\vec{v}_k)$$ 这个迭代过程称为 价值迭代 (value Iteration)，序列 ${\vec{v}_k}$ 最终会收敛到最优价值函数 $\vec{v}^*$。
结论:
贝尔曼最优性方程是贝尔曼期望方程的特殊情况。通过压缩映射定理可以证明，它存在一个唯一的最优价值函数$\vec{v}^*$，通过最优state value可以得到最优策略。