Dynamic Programming

悬崖漫步 (Cliff Walking) 环境

悬崖漫步是一个非常经典的强化学习环境，它要求一个智能体从起点出发，避开悬崖行走，最终到达目标位置. 对于一个网格世界，每一个网格表示一个状态，智能体在每一个状态都可以采取 $4$ 种动作：上、下、左、右. 如果智能体采取动作后触碰到边界墙壁则状态不发生改变，否则就会相应到达下一个状态. 环境中有一段悬崖，智能体掉入悬崖或到达目标状态都会结束动作并回到起点，也就是说掉入悬崖或者达到目标状态是终止状态. 智能体每走一步的奖励是 $-1$，掉入悬崖的奖励是 $-100$

策略迭代算法

一个通过不断循环交替策略评估和策略提升两个步骤，知道最后得到最优策略的算法

策略评估

考虑Markov Decision Process, MDP中的 Bellman 期望方程

$$\begin{array}{rl}{V}^{\pi }(s)& ={\mathbb{E}}_{\pi }[R_t+\gamma V^{\pi }(S_{t+1})|S_t=s]\\ & =\sum _{a\in A}\pi (a|s)\left(r(s,a)+\gamma \sum _{s^{\prime }\in S}p(s^{\prime }|s,a)V^{\pi }(s^{\prime })\right)\end{array}$$

可知当我们知道奖励函数和状态转移函数的时候，我们可以根据下一个状态的价值来计算当前状态的价值. 因此，根据动态规划的思想，可以把计算下一个可能状态的价值当成一个子问题，把计算当前状态的价值看作当前问题. 在得知子问题的解后，就可以求解当前问题. 更一般的，考虑所有的状态，就变成了用上一轮的状态价值函数来计算当前这一轮的状态价值函数，即

$$\begin{array}{r}{V}^{k+1}(s)=\sum _{a\in A}\pi (a|s)\left(r(s,a)+\gamma \sum _{s^{\prime }\in S}p(s^{\prime }|s,a)V^k(s^{\prime })\right)\end{array}$$

故可以选定任意初始值$V^0$，然后根据上述方程不断更新$V^k$, 并随着$k$的增大不断趋于真实的期望值$V^{\pi }$. 在实际实现的过程中，如果某一轮中的$\underset{s\in \mathcal{S}}{\max }\left|V^{k+1}(s)-V^k(s)\right|$的值非常小，就可以认为已经逼近真实期望值，并提前结束策略评估以节省时间

策略提升

使用策略评估计算得到当前策略的状态价值函数之后，我们可以据此来改进该策略. 假设此时对于策略$\pi$，我们已经知道其价值$V^{\pi }$，也就是知道了在策略$\pi$下从每一个状态$s$出发最终得到的期望回报.

假设智能体在状态$s$下采取动作$a$, 之后的动作依旧遵循策略$\pi$, 那么此时得到的期望回报就是动作价值$Q^{\pi }(s,a)$. 如果有$Q^{\pi }(s,a)>V^{\pi }(s)$，则说明在状态$s$下采取动作$a$会比原来的策略$\pi (a|s)$得到更高的期望回报. 把这个拓展到任意状态，假设存在一个确定性策略 ${\pi }^{\prime }$使得在任意状态$s$下满足

$$Q^{\pi }(s,{\pi }^{\prime }(s))\ge V^{\pi }(s)$$

于是有

$$V^{{\pi }^{\prime }}(s)\ge V^{\pi }(s),\forall s\in \mathcal{S}$$

这便是策略提升定理（policy improvement theorem）. 于是我们可以直接贪心地在每一个状态选择动作价值最大的动作，也就是

$${\pi }^{\prime }(s)=\arg \underset{a}{\max }{Q}^{\pi }(s,a)=\arg \underset{a}{\max }\{r(s,a)+\gamma \sum _{s^{\prime }}P(s^{\prime }|s,a)V^{\pi }(s^{\prime })\}$$

我们发现构造的贪心策略${\pi }^{\prime }$满足策略提升定理的条件，所以策略${\pi }^{\prime }$能够比策略$\pi$更好或者至少与其一样好. 这个根据贪心法选取动作从而得到新的策略的过程称为策略提升. 当策略提升之后得到的策略${\pi }^{\prime }$和之前的策略$\pi$一样时，说明策略迭代达到了收敛，此时和就是最优策略.

策略迭代算法

1. 对当前的策略进行策略评估，得到其状态价值函数
2. 根据该状态价值函数进行策略提升以得到一个更好的新策略
3. 接着继续评估新策略、提升策略……
4. 直至最后收敛到最优策略

$$\begin{array}{rl}& \text{Algorithm }\text{策略迭代算法}\\ & \text{随机初始化策略 }\pi (s)\text{ 和价值函数 }V(s)\\ & \text{While }\Delta >\theta \text{ do:}\\ & \Delta \leftarrow 0\\ & \text{对于每一个状态 }s\in \mathcal{S}\\ & v\leftarrow V(S)\\ & V(s)\leftarrow r(s,\pi (s))+\gamma \sum _{s^{\prime }}P(s^{\prime }|s,\pi (s))V(s^{\prime })\\ & \Delta \leftarrow \max (\Delta ,|v-V(s)|)\\ & \text{end while}\\ & {\pi }_{\text{old}}\leftarrow \pi \\ & \text{对于每一个状态 }s\in \mathcal{S}\\ & \pi (s)\leftarrow \arg \underset{a}{\max }r(s,a)+\gamma \sum _{s^{\prime }}P(s^{\prime }|s,a)V(s^{\prime })\\ & \text{若 }{\pi }_{\text{old}}=\pi \text{, 则停止算法并返回 }V\text{ 和 }\pi \\ & \text{否则重新回到策略评估循环}\end{array}$$

价值迭代算法

在实验中发现，策略迭代中的策略评估需要进行很多轮才能收敛得到某一策略的状态函数，这需要很大的计算量，尤其是在状态和动作空间比较大的情况下. 我们是否必须要完全等到策略评估完成后再进行策略提升呢？试想一下，可能出现这样的情况：虽然状态价值函数还没有收敛，但是不论接下来怎么更新状态价值，策略提升得到的都是同一个策略. 如果只在策略评估中进行一轮价值更新，然后直接根据更新后的价值进行策略提升，这样是否可以呢？答案是肯定的，这其实就是本节将要讲解的价值迭代算法，它可以被认为是一种策略评估只进行了一轮更新的策略迭代算法. 需要注意的是，价值迭代中不存在显式的策略，我们只维护一个状态价值函数.

[TODO]

冰湖环境

见 Frozen Lake (FL) Environment