【强化学习】3-贝尔曼最优公式
Categories: RL
目录
- 一、最优策略
- 二、贝尔曼最优公式——介绍
- 三、贝尔曼最优公式——如何处理公式右侧的max
- 四、贝尔曼最优公式——形式改写
- 五、压缩映射定理
- 六、贝尔曼最优公式——求解
- 七、贝尔曼最优公式——最优性
- 参考
一、最优策略
State Value可以用来衡量一个policy是好还是坏，如果：
\[\begin{equation} v_{\pi_1}(s) \geq v_{\pi_2}(s) \quad \text{for all } s \in \mathcal{S} \end{equation}\]那么就有policy $\pi_1$ 好于 $\pi_2$ 。
定义：如果一个策略 $\pi^*$ 对于任意 $s$ 和任意 $\pi$ 都有：$v_{\pi^*}(s) \geq v_\pi(s)$ ，则该策略是最优策略（Optimal Policy）。
这个定义引出许多问题：
- 最优策略是否存在？
- 最优策略是否唯一？
- 最优策略是随机的还是确定性的？
- 如何获得最优策略？
为了回答这些问题，需要研究贝尔曼最优方程（Bellman Optimality Equation, BOE）。
二、贝尔曼最优公式——介绍
贝尔曼公式是对某个 $\pi$ 而言的，如果对其求max，则为贝尔曼最优公式（逐元素形式）：
\[\begin{equation} \begin{aligned} v(s) &= {\color{blue}{\max_\pi} } \sum_a {\color{blue}{\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} \\ &= {\color{blue}{\max_\pi} } \sum_a {\color{blue}{\pi(a|s)} } q(s, a) \quad s \in \mathcal{S} \end{aligned} \end{equation}\]其中：
- $p(r|s, a),p(s’|s, a)$ 为已知，即system model
- $v(s),v(s’)$ 为未知，需要计算
- 对于贝尔曼公式，$\pi(s)$ 是给定的，对于贝尔曼最优公式，需要求解满足 $v(s)$ 最大的 $\pi(s)$
其向量形式为：
\[\begin{equation} v = \max_\pi (r_\pi + \gamma P_\pi v) \end{equation}\]三、贝尔曼最优公式——如何处理公式右侧的max
贝尔曼最优公式需要通过一个公式来求解两个未知项：$v$ 和 $\pi$ ，如何做到这一点？
示例1：如何通过一个等式来求解两个未知项？ 考虑两个变量： $x, a \in \mathbb{R}$ ，它们满足： \(x = \max_a (2x - 1 - a^2)\) 首先只考虑 $a$ ，不考虑 $x$ ，可知右侧的最大值是 $a=0$ 时，有 \(\max_a (2x - 1 - a^2) = 2x - 1\) 因此原等式变为 $x=2x-1$ ，得到 $x=1$ 。即 $a=0,x=1$ 是该等式的解。
以上例子中，我们首先对max的下标变量 $a$ 进行了求解，将 $x$ 视为常量。因此，对于贝尔曼最优公式，我们首先固定 $v(s’)$ ，求解 $\pi$ ：
\[\begin{equation} \begin{aligned} v(s) &= {\color{blue}{\max_\pi} } \sum_a {\color{blue}{\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} \\ &= {\color{blue}{\max_\pi} } \sum_a {\color{blue}{\pi(a|s)} } q(s, a) \quad s \in \mathcal{S} \end{aligned} \end{equation}\]示例2：如何求解 $\max_\pi \sum_a \pi(a|s) q(s, a)$ ？ 假设已知 $q_1, q_2, q_3 \in \mathbb{R}$ ，找到 $c_1^*, c_2^*, c_3^*$ 求解
\[\max_{c_1, c_2, c_3} c_1 q_1 + c_2 q_2 + c_3 q_3\]其中，$c_1 + c_2 + c_3 = 1$ 且 $c_1, c_2, c_3 \geq 0$（这里的 $c_1,c_2,c_3$ 就类比于 $\pi(a|s)$）。 在 $q_1,q_2,q_3$ 中，必定有最大值，假设 $q_3 \geq q_1, q_2$ ，容易得到最优解 $c_3^*=1,c_1^* = c_2^* = 0$ 。这是因为对任意 $c_1,c_2,c_3$ ，有
\[q_3 = (c_1 + c_2 + c_3) q_3 = c_1 q_3 + c_2 q_3 + c_3 q_3 \geq c_1 q_1 + c_2 q_2 + c_3 q_3\]
类似于示例2，由于 $\sum_a \pi(a|s) = 1$ ，有
\[\begin{equation} \max_\pi \sum_a \pi(a|s) q(s, a) = \max_{a \in A(s)} q(s, a) \end{equation}\]即只要找到最大的 $q(s, a)$ 即可，且
\[\begin{equation} \pi(a|s) = \begin{cases} 1 & \text{if } a = a^* \\ 0 & \text{if } a \neq a^* \end{cases} \end{equation}\]其中，$a^* = \arg\max_a q(s, a)$ 。
四、贝尔曼最优公式——形式改写
在上一节中，我们通过固定 $v$ ，求解了 $\pi$ ，在得到 $\pi$ 后，对于 $v = \max_\pi (r_\pi + \gamma P_\pi v)$ ，其右侧就是一个关于 $v$ 的函数，令：
\[\begin{equation} f(v):=\max_\pi (r_\pi + \gamma P_\pi v) \end{equation}\]因此有
\[\begin{equation} v = f(v) \label{eq:1} \end{equation}\]这里的 $f(v)$ 是一个向量，它对应的每个元素为：
\[\begin{equation} [f(v)]_s=\max_\pi \sum_a \pi(a|s) q(s, a) \quad s \in \mathcal{S} \end{equation}\]因此，求解贝尔曼最优公式，只需要求解公式 $\eqref{eq:1}$ 即可。
五、压缩映射定理
压缩映射定理（Contraction Mapping Theorem），也称为巴拿赫不动点定理（Banach Fixed-Point Theorem）。
概念
- 不动点（Fixed Point）：如果 $f(x)=x$ ，则称 $x \in X$ 是 $f:X \to X$ 的一个不动点
- 压缩映射（Contraction Mapping）：如果 $| f(x_1) - f(x_2) | \leq \gamma | x_1 - x_2 |$ ，则称 $f$ 为压缩映射，其中 $\gamma \in (0,1)$
例子
-
对于 $x = f(x) = 0.5x$ ，其中，$x \in \mathbb{R}$ 。容易看出 $x = 0$ 是一个不动点，因为 $0 = 0.5 \times 0$。 此外，$f(x) = 0.5x$ 是压缩映射，因为对任意 $\gamma \in [0.5, 1)$ ，有 \(\| 0.5x_1 - 0.5x_2 \| = 0.5 \| x_1 - x_2 \| \leq \gamma \| x_1 - x_2 \|\)
-
对于 $x = f(x) = Ax$ ，其中 $x \in \mathbb{R}^n$ ，$A \in \mathbb{R}^{n \times n}$ 且 $| A | \leq \gamma < 1$ 。同样，容易得出 $x = 0$ 是一个不动点。此外，由
\[\| Ax_1 - Ax_2 \| = {\color{blue}{\| A(x_1 - x_2) \| \leq \| A \| \| x_1 - x_2 \|} } \leq \gamma \| x_1 - x_2 \|\]可见，$f(x) = Ax$ 是一个压缩映射。（其中，蓝色部分源于矩阵算子范数的性质）
压缩映射定理
对任意具有 $x = f(x)$ 形式的等式，如果 $f$ 是一个压缩映射，那么：
- 存在性：存在不动点 $x^*$ 使得 $f(x^*) = x^*$ 。
- 唯一性：不动点 $x^*$ 是唯一的。
- 算法：考虑一个迭代过程，对于序列 ${x_k}$ ，有 $x_{k+1} = f(x_k)$ 。对于任意初始化的 $x_0$ ，当 $k \to \infty$ 时，$x_k \to x^*$ ，其收敛速度成指数级增长。
（不做证明）
六、贝尔曼最优公式——求解
对于贝尔曼最优公式：
\[\begin{equation} v=f(v)=\max_\pi (r_\pi + \gamma P_\pi v) \end{equation}\]$f(v)$ 是一个压缩映射，且有：
\[\begin{equation} \| f(v_1) - f(v_2) \| \leq \gamma \| v_1 - v_2 \| \end{equation}\]其中 $\gamma \in (0,1)$ 就是折扣因子。（这里同样不做证明）
根据压缩映射定理，我们知道对于 $v = f(v) = \max_\pi (r_\pi + \gamma P_\pi v)$，总是存在一个解 $v^*$，并且该解是唯一的。该解可以通过迭代求解：
\[\begin{equation} v_{k+1} = f(v_k) = \max_\pi (r_\pi + \gamma P_\pi v_k) \end{equation}\]该序列 ${v_k}$ 以指数速度收敛到 $v^*$，给定任何初始猜测值 $v_0$。收敛速度由 $\gamma$ 确定。
七、贝尔曼最优公式——最优性
假设 $v^*$ 是贝尔曼最优方程的解。那么它满足
\[\begin{equation} v^* = \max_\pi (r_\pi + \gamma P_\pi v^*) \end{equation}\]令
\[\begin{equation} \pi^* = \arg\max_\pi (r_\pi + \gamma P_\pi v^*) \end{equation}\]则实际上可以去掉max，这样就成了贝尔曼公式：
\[\begin{equation} v^* = r_{\pi^*} + \gamma P_{\pi^*} v^* \end{equation}\]即 $\pi^*$ 是一个策略，而 $v^* = v_{\pi^*}$ 是相应的State Value。可以证明 $v^*$ 就是最优的State Value，$\pi^*$ 就是最优的策略。
$\pi^*$ 是什么样的？
对于任何 $s \in S$，使用确定性的贪婪策略：
\[\begin{equation} \pi^*(a|s) = \begin{cases} 1 & a = a^*(s) \\ 0 & a \neq a^*(s) \end{cases} \end{equation}\]这里
\[\begin{equation} a^*(s) = \arg\max_a q^*(a, s) \end{equation}\]其中 $q^*(s, a) := \sum_r p(r|s, a)r + \gamma \sum_{s’} p(s’|s, a)v^*(s’)$。即总是选择Action Value最大的。