强化学习——贝尔曼最优公式（三）

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

state value 可以用来评估策略的好坏，但如何选出最好的策略，那就需要 BOE。

1 最优策略（Optimal Policy）

在每个状态下，该策略的 state value 都大于其它策略的。即$v^*>v_\pi$。

2 贝尔曼最优公式

未知量为$\pi(a|s),v_\pi(s),v_\pi(s')$，包含了最优策略和最优状态值。

2.1 Elementwise Form

$v_\pi(s)=\displaystyle \max_\pi \sum_a \pi(a|s)\left(\sum_r p(r|s,a) r + \gamma \sum_{s'} p(s'|s,a) v_\pi(s')\right)$

2.2 Matrix-Vector Form

$v_\pi=\displaystyle \max_\pi (r_\pi + \gamma P_\pi v_\pi)$

3 BOE 求解

3.1 策略求解

为了求得最大的 state value，就先求出使其最大的策略$\pi$也就是$\pi(a|s)$。使其最大化的策略一定是确定性的（deterministic）。

$$\pi(a|s)= \left \{ \begin{array}{c} 0, & a \neq a^*\\ 1, & a = a^* \end{array} \right .$$

3.2 state value 求解

为了解得最优的 state value，需要借助 Contraction Mapping Theorem。如果一个函数$f$符合 Contraction Mapping（$|f(v_1)-f(v_2)| \leq \gamma |v_1-v_2|$）,那么它有三个性质：

1. 对于数列$v_{k+1}=f(v_k)$，存在不动点，即$v_{k+1}=v_k$。
2. 而且这个不动点$v^*$是唯一的。
3. 当$k \to \infty$，$v_k \to v*$。

已知 BOE 可以写成$v=f(v)$，而且符合 Contraction Mapping（证明略），则可以通过

$$v_{k+1}(s)=\displaystyle \max_\pi \sum_a \pi(a|s)\left(\sum_r p(r|s,a) r + \gamma \sum_{s'} p(s'|s,a) v_{k}(s')\right)\\或\\v_{k+1}=\displaystyle \max_\pi (r_\pi + \gamma P_\pi v_k)$$

不断迭代，当$k \to \infty$，$v_k \to v*$，$v^*$就是最优值。（此时依然不能证明$v^*$就是最优值）

3.3 最优策略求解

当$v取v^*$时，根据不动点的性质$v^*=f(v^*)=\displaystyle \max_\pi(r_\pi+\gamma P_\pi v^*)=r_{\pi^*}+\gamma P_{\pi^*} v^*=\max_a q^*$，最优策略就是$\pi^* = \displaystyle \argmax_\pi(r_\pi+\gamma P_\pi v^*)$，证明如下：

所以$v^*就是最优值，\pi^*就是最优策略$