贝尔曼最优公式

Goat_Yang2026/1/19约 883 字大约 3 分钟

贝尔曼最优公式（Bellman Optimality Equation）

状态价值可用于评估策略的优劣：若对所有状态 $s \in \mathcal{S}$ ，都满足

v_{\pi_1}(s) \geq v_{\pi_2}(s)

则策略 $\pi_1$ 优于 $\pi_2$ 。

若对所有状态 $s$ 和任意其他策略 $\pi$ ，都满足 $v_{\pi^*}(s) \geq v_{\pi}(s)$ ，则策略 $\pi^*$ 是 最优策略。

\begin{aligned} 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 s \in \mathcal{S} \\ &= \max_{\pi} \sum_{a} \pi(a \mid s)\, q(s,a), \quad s \in \mathcal{S} \end{aligned}

v = \max_{\pi} \left( r_{\pi} + \gamma P_{\pi} v \right)

未知量有 $v(s), \pi(a|s),v(s')$

由于 $\sum_a \pi(a|s)=1$ , 有

\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 \mathcal{S} \\ &= \max_{\pi} \sum_a \pi(a|s)\, q(s,a) \\ &= \max_{a \in \mathcal{A}(s)} q(s,a). \end{aligned}

其中，当且仅当

\pi(a|s)= \begin{cases} 1, & a=a^* \\ 0, & a \neq a^* \end{cases}

时达到最优。这里

a^*=\arg\max_a q(s,a).

令

f(v) := \max_{\pi} \left( r_{\pi} + \gamma P_{\pi} v \right).

则 Bellman 最优方程可写为

v = f(v).

其中

[f(v)]_s = \max_{\pi} \sum_a \pi(a|s)\, q(s,a), \quad s \in \mathcal{S}.

定理： 算子 $f(v)$ 是一个压缩映射，满足

\lVert f(v_1)-f(v_2)\rVert \le \gamma \lVert v_1-v_2\rVert,

其中 $\gamma$ 为折扣因子。

对于 Bellman 最优方程

v = f(v) = \max_{\pi} \left( r_{\pi} + \gamma P_{\pi} v \right),

总是存在一个解 $v^*$ ，且该解是唯一的。

该解可以通过如下迭代方式求得：

v_{k+1} = f(v_k) = \max_{\pi} \left( r_{\pi} + \gamma P_{\pi} v_k \right), \tag{1}

对任意初始猜测 $v_0$ ，序列 $\{v_k\}$ 都将以指数速度收敛到 $v^*$ 。
其收敛速度由折扣因子 $\gamma$ 决定。

假设 $v^*$ 是 Bellman 最优方程的解，则其满足

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

再假设

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

则有

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

因此， $\pi^*$ 是一个策略，且 $v^*=v_{\pi^*}$ 为该策略对应的状态价值函数。

设 $v^*$ 是方程 $v=\max_{\pi}\left(r_{\pi}+\gamma P_{\pi}v\right)$ 的唯一解，且对任意给定策略 $\pi$ ， $v_{\pi}$ 为满足 $v_{\pi}=r_{\pi}+\gamma P_{\pi}v_{\pi}$ 的状态价值函数，则有

v^* \ge v_{\pi}, \quad \forall\, \pi.

对任意 $s \in \mathcal{S}$ ，定义确定性的贪心策略

\pi^*(a|s)= \begin{cases} 1, & a=a^*(s), \\ 0, & a\neq a^*(s), \end{cases}

则该策略是求解 Bellman 最优方程的一个最优策略。

其中

a^*(s)=\arg\max_a q^*(a,s),

而

q^*(s,a) = \sum_r p(r|s,a)\, r + \gamma \sum_{s'} p(s'|s,a)\, v^*(s').