3.贝尔曼最优公式

课程笔记 →

Bellman Optimal Equation (BOE)

Optimality#

“更优性”定义：如果存在两个策略 $\pi_1, \pi_2$，满足对任何状态 $s \in \mathcal{S}$，都有 $v_{\pi_1}(s) \ge v_{\pi_2}(s)$，（其中 $v(s)$ 为 $s$ 的 state value，）则称 $\pi_1$ 优于 $\pi_2$.

“最优性”定义：如果策略 $\pi^*$ 满足对任何策略 $\pi$，都有 $\pi^*$ 优于 $\pi$，则称 $\pi^*$ 是最优的。

这个定义引出了一系列问题：

• 最优策略是否一定存在？
• 最优策略存在时，是否唯一？
• 最优策略是 stochastic 还是 deterministic？
• 如何得到最优策略？

这些问题可以通过研究 BOE 得到回答。

---

Definition#

$$\begin{align*} v(s) &= \max_\pi \sum_a \pi(a \mid s)\left(\sum_r p(r \mid s,a)r + \gamma \sum_{s'}p(s' \mid s,a)v(s')\right),\quad \forall s \in \mathcal{S}\\ &\triangleq \max_\pi \sum_a \pi(a \mid s) q(s,a),\quad s \in \mathcal{S} \end{align*}$$

以上是贝尔曼最优公式的 elementwise 形式。它和贝尔曼公式的联系就是：将 $v_\pi$ 替换为 $v$，然后对所有 $\pi$ 取一个最大值。（将 $v_\pi$ 替换为 $v$，保证了最优性的递归。）

在 BOE 中，$v(s)$ 不再与 $\pi$ 有关，而只与状态 $s$、状态转移模型、奖励模型有关。

通过定义一些符号，我们可以写出 BOE 的 matrix-vector 形式：

$$\boldsymbol{v} = \max_\pi (\boldsymbol{r}_\pi + \gamma \boldsymbol{P}_\pi \boldsymbol{v})$$

其中 $[\boldsymbol{r}_\pi]_s \triangleq \sum_a \pi(a \mid s) \sum_r p(r \mid s,a)r$，$[\boldsymbol{P}_\pi]_{s,s'} = p(s' \mid s) \triangleq \sum_a \pi(a \mid s)\sum_{s'} p(s' \mid s,a)$.

---

Analysis#

由于上述不动点方程 $\boldsymbol{v} = \max_\pi (\boldsymbol{r}_\pi + \gamma \boldsymbol{P}_\pi \boldsymbol{v})$ 右侧是一个压缩映射，根据压缩映射定理，解存在且唯一，并可以通过迭代算法收敛求解。

证明：$f(v) = \max_\pi (\boldsymbol{r}_\pi + \gamma \boldsymbol{P}_\pi \boldsymbol{v})$ 是一个压缩映射

只需证明 $\| f(v_1) - f(v_2) \|_\infty \le \gamma \| v_1 - v_2\|_\infty,\quad |\gamma| < 1,\quad \forall v_1, v_2 \in \mathbb{R}^{\lvert \mathcal{S} \rvert}$.

此处范数任取，因为有限维空间的范数等价（详见 ChatGPT - 理解范数等价 ↗），而取 $L_\infty$ 将会简化证明。

记 $\pi_1 = \arg \max_\pi(\boldsymbol{r}_\pi + \gamma \boldsymbol{P}_\pi \boldsymbol{v}_1),\ \pi_2 = \arg \max_\pi(\boldsymbol{r}_\pi + \gamma \boldsymbol{P}_\pi \boldsymbol{v}_2)$，则有：

$$\begin{align*} f(v_1) = \boldsymbol{r}_{\pi_1} + \gamma \boldsymbol{P}_{\pi_1} \boldsymbol{v}_1 \ge \boldsymbol{r}_{\pi_2} + \gamma \boldsymbol{P}_{\pi_2} \boldsymbol{v}_1\\\\ f(v_2) = \boldsymbol{r}_{\pi_2} + \gamma \boldsymbol{P}_{\pi_2} \boldsymbol{v}_2 \ge \boldsymbol{r}_{\pi_1} + \gamma \boldsymbol{P}_{\pi_1} \boldsymbol{v}_2\\ \end{align*}$$

其中 $\ge$ 是逐元素比较算子。于是：

$$\begin{align*} f(v_1) - f(v_2) &= \boldsymbol{r}_{\pi_1} + \gamma \boldsymbol{P}_{\pi_1} \boldsymbol{v}_1 - (\boldsymbol{r}_{\pi_2} + \gamma \boldsymbol{P}_{\pi_2} \boldsymbol{v}_2)\\ &\le \boldsymbol{r}_{\pi_1} + \gamma \boldsymbol{P}_{\pi_1} \boldsymbol{v}_1 - (\boldsymbol{r}_{\pi_1} + \gamma \boldsymbol{P}_{\pi_1} \boldsymbol{v}_2)\\ &= \gamma \boldsymbol{P}_{\pi_1}(\boldsymbol{v}_1 - \boldsymbol{v}_2) \end{align*}$$

同理可得 $f(v_2) - f(v_1) \le \gamma \boldsymbol{P}_{\pi_2}(\boldsymbol{v}_2 - \boldsymbol{v}_1)$. 结合起来即：

$$\gamma \boldsymbol{P}_{\pi_2}(\boldsymbol{v}_1 - \boldsymbol{v}_2) \le f(v_1) - f(v_2) \le \gamma \boldsymbol{P}_{\pi_1}(\boldsymbol{v}_1 - \boldsymbol{v}_2)$$

不妨定义

$$z = \max \left\{ \lvert\gamma \boldsymbol{P}_{\pi_1}(\boldsymbol{v}_1 - \boldsymbol{v}_2)\rvert, \lvert\gamma \boldsymbol{P}_{\pi_2}(\boldsymbol{v}_1 - \boldsymbol{v}_2)\rvert \right\} \in \mathbb{R}^{\lvert\mathcal{S}\rvert}$$

以上 $\le,\ \max,\ \lvert \cdot \rvert$ 均为逐元素算符。
已知 $z > 0$，并且一方面，

$$-z \le f(v_1) - f(v_2) \le z$$

即

$$\lvert f(v_1) - f(v_2)\rvert \le z$$

这就导致了

$$\lVert f(v_1) - f(v_2) \rVert_\infty \le \lVert z \rVert_\infty$$

另一方面，记 $p_i^T,\ q_i^T$ 分别是 $\boldsymbol{P}_{\pi_1}, \boldsymbol{P}_{\pi_2}$ 的第 $i$ 行，$z_i$ 为 $z$ 的第 $i$ 个分量。

则有

$$z_i = \max \left\{ \lvert\gamma p_i^T(\boldsymbol{v}_1 - \boldsymbol{v}_2)\rvert, \lvert\gamma q_i^T(\boldsymbol{v}_1 - \boldsymbol{v}_2)\rvert \right\}$$

注意到 $p_i$ 的元素均非负且和为 $1$，有

$$\lvert\gamma p_i^T (v_1 - v_2)\rvert \ \le\ \gamma p_i^T \lvert v_1 - v_2\rvert \ \le\ \gamma \lVert v_1 - v_2 \rVert_\infty$$

同理可得 $\lvert\gamma q_i^T (v_1 - v_2)\rvert \ \le\ \gamma \lVert v_1 - v_2 \rVert_\infty$，于是引出

$$\rVert z \rVert_\infty \ =\ \max_i \lvert z_i\rvert \ \le\ \gamma \lVert v_1 - v_2 \rVert_\infty$$

这就证明了

$$\lVert f(v_1) - f(v_2) \rVert_\infty \ \le\ \gamma \lVert v_1 - v_2 \rVert_\infty$$

也即，$f(v)$ 是压缩映射。

---

Solution#

使用迭代法求解 $\boldsymbol{v}$：

$$v_{t+1}(s) = \max_\pi \sum_a \pi(a \mid s) q_t(s,a),\quad s \in \mathcal{S}$$

其中 $\displaystyle{q_t(s,a) = \sum_r p(r \mid s,a)r + \gamma \sum_{s'}p(s' \mid s,a)v_t(s')}$.

迭代时，等式右侧的 $q_t$ 已知，只需要确定 $\pi$ 的取值。

而 $\forall s \in \mathcal{S},\quad \sum_a \pi(a \mid s) = 1$，因此使得 $\sum_a \pi(a \mid s) q_t(s,a)$ 最大的 $\pi$ 的形式一定是：

$$\pi(a \mid s) = \begin{cases} 1, & a = \arg \max_{\mathscr{a}} q_t(s,\mathscr{a}),\\ 0, & \text{otherwise}. \end{cases}$$

这被称为 Greedy Optimal Policy.

该结论指出，实际求解时，我们不需要真正枚举所有 $\pi$，而只需要对每个状态依次计算最佳动作（逐状态可分）。且必然存在 deterministic 的最佳动作。

---

Proof of Optimality#

可以证明，BOE 的解 $v^*$，以及其对应的 $\pi^*$，满足 $\forall \pi,\ v^* = v_{\pi^*} \ge v_\pi$.
这就是说，通过 BOE 求解出来的 $v^*$ 及 $\pi^*$，确实是最优的策略。

下面证明：

对任何 policy $\pi$，有 $v_\pi = r_\pi + \gamma P_\pi v_\pi$.

与此同时，对于 BOE 的解，有：

$$v^* = \max_\pi(r_\pi + \gamma P_\pi v^*) = r_{\pi^*} + \gamma P_{\pi^*} v^* \ge r_{\pi} + \gamma P_{\pi} v^*$$

因此，

$$v^* - v_\pi \ge \gamma P_\pi (v^* - v_\pi)$$

由于 $\gamma > 0$，且 $P_\pi^n\ (\forall n \in \mathbb{N}^+)$ 为元素均不大于 $1$ 的非负矩阵，故可两边同时左乘 $\gamma P_\pi$，得到不等式链：

$$v^* - v_\pi \ge \gamma P_\pi (v^* - v_\pi) \ge \gamma^2 P_\pi^2 (v^* - v_\pi) \ge \cdots \ge \gamma^n P_\pi^n (v^* - v_\pi)$$

这就可以导出：

$$v^* - v_\pi = \lim_{n \to \infty} (v^* - v_\pi)\ \ge\ \lim_{n \to \infty} \gamma^n P_\pi^n (v^* - v_\pi) = 0$$

---

Optimal Policy Invariance#

考虑 MDP，其最优 state value 已求出：$v^* = \max_{\pi \in \Pi}\left(r_\pi + \gamma P_\pi v^*\right)$. 如果将所有奖励 $r$ 应用同一个仿射变换 $r' = \alpha r + \beta,\ \alpha, \beta \in \mathbb{R},\ \alpha > 0$，则新的最优 state value $v'$ 也将由 $v^*$ 的一个仿射变换确定：

$$v' = \alpha v^* + {\beta \over 1 - \gamma}\boldsymbol{1}$$

由此可见，最优策略 $\pi^*$ 对仿射变换不敏感，变换前后最优策略还是最优策略。

直观理解较为简单，第一项表示「reward 增大几倍，state value 就增大几倍」；第二项表示「reward 统一增大一个数，state value 就统一增大其 discounted 之后的量」。

证明

新的 BOE 变为

$$v' = \max_\pi (r'_\pi + \gamma P_\pi v') = \max_\pi (\alpha r_\pi + \beta \boldsymbol{1} + \gamma P_\pi v')$$

接下来先猜测 $v' = \alpha v + c \boldsymbol{1}$ 的形式，并尝试进行正向变换或者直接带入化简。此处以正向变换为例。

$$\begin{align*} {v' \over \alpha} &= \max_\pi\left(r_\pi + {\beta \over \alpha} \boldsymbol{1} + \gamma P_\pi {v' \over \alpha}\right)\\ {v' \over \alpha} &= \max_\pi\left(r_\pi + \left({1 \over 1 - \gamma} - {\gamma \over 1 - \gamma}\right){\beta \over \alpha} \boldsymbol{1} + \gamma P_\pi {v' \over \alpha}\right)\\ {v' \over \alpha} - {1 \over 1 - \gamma}{\beta \over \alpha} \boldsymbol{1} &= \max_\pi\left(r_\pi + \gamma\left( P_\pi {v' \over \alpha} - {1 \over 1 - \gamma}{\beta \over \alpha} \boldsymbol{1}\right)\right)\\ \end{align*}$$

又由于 $P_\pi \boldsymbol{1} = \boldsymbol{1}$，故

$${v' \over \alpha} - {1 \over 1 - \gamma}{\beta \over \alpha} \boldsymbol{1} = \max_\pi\left(r_\pi + \gamma P_\pi \left({v' \over \alpha} - {1 \over 1 - \gamma}{\beta \over \alpha} \boldsymbol{1}\right)\right)$$

这就是说，

$$v^* = {v' \over \alpha} - {1 \over 1 - \gamma}{\beta \over \alpha} \boldsymbol{1}$$

即

$$v' = \alpha v^* + {\beta \over 1 - \gamma}\boldsymbol{1}$$

最后，由于仿射变换不改变相对大小，适用于 $v^*$ 的最佳策略也适用于 $v'$，因此最佳策略不变。

---

后记#

BOE 的目标和 RL 的目标有所区别。具体来说，

RL Objective: 最大化初始状态（或者初始状态分布）下的 expected return；

Bellman Optimality: 求所有状态下的 $v^*$.

可以看到，BOE 的讨论更加一般化，并且最优策略的存在性有保证，因此理论上往往研究 BOE.

此外，目前为止涉及的 MDP 方法，是高度理想的模型，更像是随机过程 + 动态规划 + 线性代数。其假设状态空间、策略空间均有限，转移概率和奖励能被精确估计。这种条件下，问题的核心是解 Bellman 方程。