贝尔曼最优公式

Bellman Optimality Equation

动机

对于策略 ${\pi }_2$，$\gamma =0.9$，有：

$$\begin{array}{l}{q}_{\pi }(s_1,a_1)=-1+\gamma v_{\pi }\left(s_1\right)=6.2\\ q_{\pi }(s_1,a_2)=-1+\gamma v_{\pi }\left(s_2\right)=8\\ q_{\pi }(s_1,a_3)=0+\gamma v_{\pi }\left(s_3\right)=9\\ q_{\pi }(s_1,a_4)=-1+\gamma v_{\pi }\left(s_1\right)=6.2\\ q_{\pi }(s_1,a_5)=0+\gamma v_{\pi }\left(s_1\right)=7.2\end{array}$$

当该策略不够好时，如何优化它？

答案：利用动作价值（action-value）

目前的策略可以表示为：

$$\pi (a\mid s_1)=\{\begin{array}{ll}1& a=a_2\\ 0& a\ne a_2\end{array}$$

我们发现，$q_{\pi }(s_1,a_3)$ 的值最大，那么新的策略在 $s_1$ 时会选择执行动作 $a_3$ 替换掉原先的 $a_2$

即：

$${\pi }_{\text{new}}(a\mid s_1)=\{\begin{array}{ll}1& a=a^{\ast }\\ 0& a\ne a^{\ast }\end{array}$$$$a^{\ast }={\text{argmax}}_a{q}_{\pi }(s_1,a)=a_3$$

最优策略

定义策略 ${\pi }_1$ 比 策略 ${\pi }_2$ 更优：

$$v_{{\pi }_1}(s)\ge v_{{\pi }_2}(s)\text{for all }s\in \mathcal{S}$$

那么最优策略可以定义为：

$${\pi }^{\ast },v_{{\pi }^{\ast }}(s)\ge v_{\pi }(s)$$

贝尔曼最优公式

贝尔曼最优公式定义如下：

$$v(s)=\underset{\pi }{max}\sum _a\pi (a\mid s)[\sum _{r}p(r\mid s,a)r+\gamma \sum _{s^{\prime }}p(s^{\prime }\mid s,a)v\left(s^{\prime }\right)],\mathrm{\forall }s\in \mathcal{S}$$

或者：

$$v(s)=\underset{\pi }{max}\sum _a\pi (a\mid s)q(s,a),\mathrm{\forall }s\in \mathcal{S}$$

或者：

$$v=\underset{\pi }{max}(r_{\pi }+\gamma {\mathbf{P}}_{\pi }v)$$

其中有两个未知量：$v$ 和 $\pi$

求解

step 1

TIP

考虑到两个变量$x,a\in \mathbb{R}$，假设它们满足：

$$x=\underset{a}{max}(2x-1-a^2)$$

显然等式右边 $\underset{a}{max}(2x-1-a^2)$ 当且仅当 $a=0$ 时取得最大，此时等式右边为 $2x-1$。

进一步的，此时等式变为：$x=2x-1$，容易解得：$x=1$

即：$x=1,a=0$ 为此方程的解。

考虑贝尔曼最优公式右侧：

$$\underset{\pi }{max}\sum _a\pi (a\mid s)q(s,a)$$

如果给定一个初始值 $v_0$，则 $v(s{)}^{\prime }$ 变成已知量，即 $q(s,a)$ 已知。接下来需要确定 $\pi (a\mid s)$。

TIP

假设已知 $q_1,q_2,q_3\in \mathbb{R}$，求

$$\underset{c_1,c_2,c_3}{max}{c}_1{q}_1+c_2{q}_2+c_3{q}_3$$

的解 $c_1^{\ast },c_2^{\ast },c_3^{\ast }$，其中 $c_1+c_2+c_3=1,c_1,c_2,c_3\ge 0$。

假设 $q_3\ge q_1,q_2$，显然有：

$$q_3=(c_1+c_2+c_3=1)q_3=c_1{q}_3+c_2{q}_3+c_3{q}_3\ge c_1{q}_1+c_2{q}_2+c_3{q}_3$$

解为：$c_3^{\ast }=1,c_1^{\ast }=c_2^{\ast }=0$

考虑到：$\sum _a\pi (a\mid s)=1$，有：

$$\underset{\pi }{max}\sum _a\pi (a\mid s)q(s,a)=\underset{a\in \mathcal{A}(s)}{max}q(s,a)$$

当

$$\pi (a\mid s)=\{\begin{array}{ll}1& a=a^{\ast }\\ 0& a\ne a^{\ast }\end{array}$$$$a^{\ast }={\text{argmax}}_{a}q(s,a)$$

时达到最优。

step 2

对于贝尔曼最优公式：

$$v=\underset{\pi }{max}(r_{\pi }+\gamma {\mathbf{P}}_{\pi }v)$$

由于上一步中 $\pi$ 已经确定下来，可以令：

$$f(v)=\underset{\pi }{max}(r_{\pi }+\gamma {\mathbf{P}}_{\pi }v)$$

贝尔曼最优公式可以变为：

$$f(v)=v$$

当：

$$[f(v){]}_s=\underset{\pi }{max}\sum _a\pi (a\mid s)q(s,a),s\in \mathcal{S}$$

由于对于 $\mathrm{\forall }{v}_1,v_2\in {\mathbb{R}}^{|\mathcal{S}|}$：

$$\Vert f(v_1)-f(v_2)\Vert \le \gamma \Vert v_1-v_2\Vert$$

即 $f(v)=v$ 满足压缩映射，根据压缩映射定理（Contractive Mapping Theorem），一定存在且仅存在一个不动点（解） $v^{\ast }$，满足：

$$v_{k+1}=f(v_k)=\underset{\pi }{max}(r_{\pi }+\gamma {\mathbf{P}}_{\pi }{v}_k)$$$$k\to \mathrm{\infty },v_k\to v^{\ast }$$

step 3

$v^{\ast }$是贝尔曼最优公式的解，且满足：

$$v^{\ast }=\underset{\pi }{max}(r_{\pi }+\gamma {\mathbf{P}}_{\pi }{v}^{\ast })$$

假设：

$${\pi }^{\ast }={\text{argmax}}_{\pi }(r_{\pi }+\gamma {\mathbf{P}}_{\pi }{v}^{\ast })$$

有：

$$v^{\ast }=r_{{\pi }^{\ast }}+\gamma {\mathbf{P}}_{{\pi }^{\ast }}{v}^{\ast }$$

此时 ${\pi }^{\ast }$ 为最优策略。

即：

$${\pi }^{\ast }(a\mid s)=\{\begin{array}{ll}1& a=a^{\ast }\\ 0& a\ne a^{\ast }\end{array}$$$$a^{\ast }={\text{argmax}}_a{q}^{\ast }(s,a)$$$$q^{\ast }=\sum _{r}p(r\mid s,a)r+\gamma \sum _{s^{\prime }}p(s^{\prime }\mid s,a)v^{\ast }\left(s^{\prime }\right)$$

步骤总结

1. 初始化：

   设定初始值 $v_0(s)$ （如全 0 或随机值），设定收敛阈值 $ϵ$

2. 迭代：

   对于每次迭代：

   $$v_{k+1}=\underset{\pi }{max}(r_{\pi }+\gamma {\mathbf{P}}_{\pi }{v}_k)$$

3. 收敛判断：

   当 $\Vert v_{k+1}-v_k\Vert <ϵ$ 时停止，获得 $v^{\ast }$

4. 获得最优策略：

   $${\pi }^{\ast }(a\mid s)=\{\begin{array}{ll}1& a=a^{\ast }\\ 0& a\ne a^{\ast }\end{array}$$$$a^{\ast }={\text{argmax}}_a{q}^{\ast }(s,a)$$$$q^{\ast }=\sum _{r}p(r\mid s,a)r+\gamma \sum _{s^{\prime }}p(s^{\prime }\mid s,a)v^{\ast }\left(s^{\prime }\right)$$

全局最优

Q：为什么是全局最优？

A：

• 压缩映射

  根据压缩映射定理，贝尔曼最优方程存在唯一解（不动点）$v^{\ast }$，当折扣因子 $\gamma <1$ 时，值迭代过程必然收敛到 $v^{\ast }$。

• 递推结构

  每个状态的最优值 $v^{\ast }(s)$ 的计算不仅考虑当前动作的即时奖励 $r(s)$，还通过转移概率 $p(s^{\prime }\mid s,a)$ 显示关联了后续状态的最优值 $v^{\ast }\left(s^{\prime }\right)$。

  值迭代过程中，最优值信息从终止状态（或高奖励状态）逆向传播到所有可能的前驱状态，最终覆盖整个状态空间。

Q：为什么要研究这个公式？

A：贝尔曼最优公式的解对应了最优状态值和最优策略