Policy Evaluation
Bellman Optimal Equation 是在 Bellman Equation 的基础上演变而来。Bellman Equation 阐述了在一只策略和环境的情况下，State Value 所满足的公式。有了State Value之后可以做什么呢？Policy Evaluation! （毕竟强化学习的目标是寻找最优的策略）
下面定义什么是好的策略，如果对于两个策略$\pi_{1}$, $\pi_{2}$ ，下面的式子恒成立：
\[
v_{\pi_1}(s) > v_{\pi_2}(s), \forall s \in \mathcal{S}
\]
则称$\pi_{1}$是比$\pi_{2}$更优的策略。强化学习的目标是寻找最优的策略，而最优的策略又依赖于选择最合适的状态作为下一次迁移的目标（依赖于State Value），这就需要把 State Value 和 Policy 同时优化，这就是 Bellman Optimal Equation.
Bellman Optimal Equation
Bellman Equation 如下：
\[
\begin{align}
v_{\pi}(s)
& = \sum \limits_{a}^{} \pi(a | s) \left[\sum \limits_{r} r \cdot p(r | s, a) + \gamma \sum \limits_{s’} v_{\pi}(s’) p(s’|s, a)\right] \\
\end{align}
\]
Bellman Optimal Equation 如下：
\[
\begin{align}
v_{\pi}(s)
& = \max \limits_{\pi} \sum \limits_{a}^{} \pi(a | s) \left[\sum \limits_{r} r \cdot p(r | s, a) + \gamma \sum \limits_{s’} v_{\pi}(s’) p(s’|s, a)\right] \\
& = \max \limits_{\pi} \sum \limits_{a}^{} \pi(a | s) \cdot q(s, a) \\
\end{align}
\]
其实就是进行了一步优化，它表达的是在最优策略下的 State Value 之间的关系。这里面有两个未知量，一个是策略$\pi$，一个是 State Value, 现在要对这两个未知量同时优化。
首先要解决的是如果已知 Action Value, 如何找到最合适的策略的问题，这就是一个简单的线性规划问题。这里我们以 3 种 Action 的情况为例。
\[
\begin{align}
\max\limits_{\pi(a_i | s)} \pi(a_1 | s)q(s, a_1) + \pi(a_2 | s)q(s, a_2) + \pi(a_3 | s)q(s, a_3) \\
\mathrm{s.t.} \ \pi(a_1 | s) + \pi(a_2 | s) + \pi(a_3 | s) = 1
\end{align}
\]
如果 Action Value 给定，且已知：
\[
q(s, a_1) \geq q(s, a_2) \geq q(s, a_3)
\]
那么，显然最优解在 $\pi(a_1 | s) = 1$, $\pi(a_j | s) = 0 (j = 2,3) $ 处取到。因此我们把这种办法（其实是一种deterministic policy）称为 Greedy Policy. 即：
\[
\begin{align}
\begin{cases}
\pi(a|s) = 1 \ \ (a = a^*) \\
\pi(a|s) = 0 \ \ (a \neq a^*) \\
\end{cases}
\end{align}
\]
式中，$a^*= \mathrm{arg} \max \limits_{a} q(s,a) $，那么 Bellman Optimal Equation 可以重新写作：
\[
\begin{align}
v_{\pi}(s)
& = \max\limits_{a \in \mathcal{A}} q(s, a) \\
& = q(s, a^*) \\
\end{align}
\]