本系列是学习《动手学强化学习》 过程中做的摘抄。
基于动态规划的两种强化学习算法（策略迭代和价值迭代）要求事先知道环境的状态转移函数和奖励函数，也就是需要知道整个马尔科夫决策过程。但是，现实中的白盒环境很少，无法将其运用在很多实际场景中。另外，策略迭代和价值迭代通常只适用于有限马尔科夫决策过程，即状态空间和动作空间是离散且有限的。
公式回顾：
$$ \begin{equation*} \begin{aligned} & V^{\pi}(s) = \sum_{a \in \mathcal{A}} \pi(a | s) Q^{\pi}(s,a) \\ & Q^{\pi}(s,a)= r(s, a) + \gamma \sum_{s' \in \mathcal{S}} P(s'|s, a) V^{\pi} (s') \\ \\ & V^{\pi}(s) = \sum_{a \in \mathcal{A}} \pi(a|s) \left( r(s,a)+\gamma \sum_{s' \in \mathcal{S}} P(s'|s, a) V^{\pi}(s') \right) \\ & Q^{\pi} (s,a) = r(s,a) + \gamma \sum_{s' \in \mathcal{S}} P(s'|s, a) \sum_{a' \in \mathcal{A}} \pi(a' | s') Q^{\pi}(s', a') \\ \\ & V^{*}(s)=\max_{a \in \mathcal{A}} \{r(s,a)+\gamma \sum_{s' \in \mathcal{S}}P(s'|s,a)V^{*}(s') \} \\ & Q^{*}(s,a)=r(s,a) + \gamma \sum_{s' \in \mathcal{S}} P(s'|s,a) \max_{a' \in \mathcal{A}} Q^{*}(s',a') \end{aligned} \end{equation*} $$
3.1 策略迭代算法#
策略迭代（policy iteration）是策略评估（policy evaluation）和策略提升（policy improvement）不断循环交替，直至最后得到最优策略 \(\pi^{*}\) 的过程。
$$ \pi^{0} \rightarrow V^{\pi^{0}} \rightarrow \pi^{1} \rightarrow V^{\pi^{1}} \rightarrow \pi^{2} \rightarrow V^{\pi^{2}} \rightarrow \cdots \rightarrow \pi^{*} $$3.1.1 策略评估#
策略评估这一过程使用贝尔曼期望方程来计算一个策略的状态价值函数 \(V^{\pi}(s)\)。考虑所有的状态，用上一轮的状态价值函数来计算当前这一轮的状态价值函数，即
$$ V^{k+1}(s) = \sum_{a \in \mathcal{A}} \pi(a | s) \left( r(s,a) + \gamma \sum_{s' \in \mathcal{S}} P(s'|s,a) V^{k}(s') \right) $$可以选定任意初始值 \(V^{0}\)，根据贝尔曼期望方程，可以得知 \(V^{k}=V^{\pi}\) 是以上更新公式的一个不动点。在实际的实现过程中，如果某一轮 \( \max_{s \in \mathcal{S}} |V^{k+1}(s) - V^{k}(s)| \) 的值非常小，可以提前结束策略评估。
3.1.2 策略提升#
策略提升定理：假设存在一个确定性策略 \( \pi' \)，在任意一个状态 \(s\) 下，都满足 \( Q^{\pi}(s, \pi'(s)) \geq V^{\pi}(s) \)，于是在任意状态 \(s\) 下，有 \(V^{\pi'}(s) \geq V^{\pi}(s)\)。
于是可以直接贪心地在每一个状态选择动作价值最大的动作，也就是
$$ \pi'(s) = \arg \max_a Q^{\pi}(s, a) = \arg \max_a \{r(s, a) + \gamma \sum_{s'} P(s'|s, a) V^{\pi} (s')\} $$我们发现构造的贪心策略 \(\pi'\) 满足策略提升定理的条件，所以 \(\pi'\) 比 \(\pi\) 更好或者至少与其一样好。当策略提升之后的策略和之前的策略一样时（\(\pi'=\pi\)），说明策略迭代达到了收敛，此时 \(\pi\) 和 \(\pi'\) 就是最优策略。
3.2 价值迭代算法#
价值迭代（value iteration）过程中不存在显式的策略，只维护一个状态价值函数 \(V(s)\)。价值迭代算法利用的是贝尔曼最优方程，将其写成迭代更新的方式：
$$ V^{k+1}(s) = \max_{a \in \mathcal{A}} \{ r(s,a)+\gamma \sum_{s' \in \mathcal{S}}P(s'|s,a)V^{k}(s') \} $$等到 \(V^{k+1}\) 和 \(V^{k}\) 相同时，它就是贝尔曼最优方程的不动点，此时对应着最优状态价值函数 \(V^{*}(s)\)。然后利用 \(\pi(s)=\arg \max_{a} \{r(s,a) + \gamma \sum_{s'} P(s'|s,a) V^{k+1}(s')\}\) 从中恢复出最优策略即可。
价值迭代中的循环次数远少于策略迭代。