区分Continuing Task和Episodic Task

前一节我们已经解释了什么是episode，episode即为从初始的状态到终止状态的整个过程。那么什么是Continuing Task？什么是Episodic Task呢？其实，两者最根本的区别就是Continuing Task是无法确认最终的终止状态，其动作状态会一直发生下去的即为Continuing Task。与此相反，Episodic Task是拥有有限长度的状态，也就是知道最终的结束状态。

强化学习分类

强化学习基本上可以分为两大类。第一类是有模型的强化学习，另一类为无模型的强化学习。模型可以简单地理解为transition-state probability。而动态规划(Dynamic Programming)就是一个基于有模型的强化学习方法。分类图如下所示：

强化学习分类

动态规划(Dynamic Programming)

根据前面推导出来的Value Functions的表达公式，我们可以看出当前状态的值可以通过接下来的状态值计算出来。但是，这两个状态的值函数我们都不知道。因此，该算法也被称为自举(bootstrapping)。接下来我们先看看动态规划方法如何对policy来进行评估的。

策略评估(Policy Evaluation)

如何来评估策略的好坏呢？这时候我们需要从数学的角度出发，也就是要通过数值的方式来对策略进行评估。数值大代表策略好，数值小代表策略不是很好，我们很容易就会想到Value Functions。

根据Bellman Equation我们得到state value的计算公式如下：

iterative policy evaluation

于是，我们就可以通过一次次的迭代来得到该policy的state value了。其伪代码如下：

policy evaluation 伪代码

从伪代码中，我们可以知道Policy Evaluation是对一个Policy进行计算的。当我们更新的state value值几乎不变时，就可以让其停止迭代了。

列1: 我们有一个Gridworld的游戏，其中有2个终点，1-14数字分别代表14个不同的状态(state)，我们可以朝四个方向走(上下左右)，也就是代表了我们的动作(action)，每一次状态的改变都会得到-1的奖励。游戏如下图所示：

Gridworld Game

通过Iterative Policy Evaluation方法进行迭代，我们得到前两次迭代的state value矩阵。如下所示：

policy evaluation example

我们来看一下k=2时，-1.7是怎么计算出来的。因为我们可以采取4个动作，所以每个动作的概率都为0.25, 而在状态1的位置上，其可以向左、向右、向下和原地不动。因此，其state value就等于(0.0 * 0.25) + (-1 * 0.25) + (-1 * 0.25) + (-1 * 0.25) = -1.75，四舍五入即为-1.7。

策略提升(Policy Improvement)

我们进行策略评估的目的就是为了找到最优的策略。还是拿列1来举例，当k=2时，我们已经计算出了各个状态下的state value，比如我们在状态2的情况下，为了转换到更好的状态，我们就朝四个方向观察一番，发现通过向左走可以得到更多(-1.7 > -2.0)的奖励，于是我们便采取向左的动作，使状态转换到了状态1。这就是策略提升。

通过例子，我们可以知道我们在状态不好的情况下采取相应行动转换到比较好的状态的值(也就是action value)一定会大于当前状态不好的值(state value)。通过公式推导，我们只需要选择state value值大的地方执行策略即可。公式推导如下：