[RL Notes] 策略改进
通过迭代策略评估得到给定策略下的价值函数后，就可以据此对策略进行改进，以得到更好的策略。
假设已知某个策略 $\pi$ 的价值函数 $v_\pi$，我们希望知道如果在某个状态 $s$ 上选择一个不同于策略 $\pi$ 的动作 $a \neq \pi(s)$，是否会带来改善。已知在状态 $s$ 上继续遵守策略 $\pi$ 的价值为 $v_\pi(s)$；考虑在状态 $s$ 选择动作 $a$，然后继续遵循现有策略 $\pi$，这种策略的值为
\begin{align}
q_\pi(s, a) &\doteq \mathbb{E}[R_{t+1} + \gamma v_\pi(S_{t+1}) | S_t = s, A_t = a] \\
&= \sum_{s’, r} p(s’,r|s,a) \big[ r + \gamma v_\pi(s’) \big] \tag{1}
\end{align}
如果上式的值大于 $v_\pi(s)$，说明在 $s$ 选择动作 $a$、然后继续使用策略 $\pi$ 比一直使用策略 $\pi$ 更优，由此就得到了一个新的更优的策略。
更一般地，策略改进定理表明，对于任意的两个策略 $\pi$ 和 $\pi’$ 和任意状态 $s \in \mathcal S$，如果
\begin{equation}
q_\pi(s, \pi'(s)) \geq v_\pi(s) \tag{2}
\end{equation}
则称策略 $\pi’$ 相比于 $\pi$ 一样好或更好。即对任意状态 $s \in \mathcal S$，$\pi’$ 肯定能得到与 $\pi$ 一样或更好的期望回报
\begin{equation}
v_{\pi’}(s) \geq v_\pi(s) \tag{3}
\end{equation}
如果式 $(2)$ 中的不等式在某个状态下是严格不等的，则式 $(3)$ 在这个状态下也是严格不等的。
前面讨论了在已有策略中只修改在一个状态下的特定动作所带来的改变。更进一步地，如果在每个状态 $s$ 下根据 $q_\pi(s, a)$ 选择一个最优的动作，就得到了一个贪心策略 $\pi’$
\begin{align}
\pi'(s) &\doteq \underset{a}{\arg\max} \; q_\pi(s, a) \\
&= \underset{a}{\arg\max} \; \mathbb{E}[R_{t+1} + \gamma v_\pi(S_{t+1}) | S_t = s, A_t = a] \\
&= \underset{a}{\arg\max} \; \sum_{s’, r} p(s’, r | s, a) \big[ r + \gamma v_\pi(s’) \big] \tag{4}
\end{align}
这个策略采取短期内最优的动作，相当于根据 $v_\pi$ 向前做了一步搜索。这样构造出来的贪心策略满足策略改进定理，确保了新策略 $\pi’$ 和原策略 $\pi$ 一样好或更好。像这样根据原策略的价值函数执行贪心算法，来构造一个更好的策略的过程，称为策略改进。
使用上面的方法不断进行迭代，就可以得到一系列越来越好的策略。如果新的贪心策略 $\pi’$ 和原策略 $\pi$ 一样好，即有 $v_\pi = v_{\pi’}$，对于任意 $s \in \mathcal S$，有
\begin{align}
v_{\pi’}(s) &= \max_{a} \; q_{\pi’}(s, a) \\
&= \max_{a} \; \mathbb{E}[R_{t+1} + \gamma v_{\pi’}(S_{t+1}) | S_t = s, A_t = a] \\
&= \max_{a} \; \sum_{s’,r} p(s’, r | s, a) \big[ r + \gamma v_{\pi’}(s’) \big] \tag{5}
\end{align}
注意式 $(5)$ 和贝尔曼最优方程具有相同的形式，说明 $v_{\pi’}$ 是与 $v_*$ 相同，且 $\pi$ 与 $\pi’$ 都是最优策略。可见除了在原策略已经是最优策略的情况下，策略改进一定会给出一个更优的策略。