1. 回顾

上一期我们介绍了两种动态规划的强化学习算法：策略迭代算法和价值迭代算法，并且用它们来解决了悬崖漫步的问题，验证了强化学习理论的有效性。这两种算法虽然简单有效，但是适用的范围有限，要使用它们必须满足两个条件：

• 要求整个环境必须时已知的，比如上期的悬崖漫步问题，并不需要和环境交互来采样数据，所以直接使用动态规划解出最优策略，这就好比对于有监督学习任务，如果直接显式给出了数据的分布公式，那么也可以通过在期望层面上直接最小化模型的泛化误差来更新模型参数，并不需要采样任何数据点。

• 要求状态、动作空间是离散、有限的，它们无法处理连续的状态或动作空间。

不幸的是，现实中这两个条件大多时候无法满足，无法进行动态规划，这种情况下，智能体只能和环境进行交互，通过采样到的数据来学习，这类学习方法统称为无模型的强化学习（Model-Free）。

从本期开始，往后介绍的算法将都是无模型的强化学习，这是目前强化学习领域的主流，因为不需要事先知道环境的奖励函数和状态转移函数，而是直接使用和环境交互的过程中采样到的数据来学习，这使得它可以被应用到一些实际场景中。本期将介绍无模型强化学习的灵魂——时序差分算法，逐步进入强化学习和机器学习的交集。

2. 蒙特卡洛和时序差分

我们已经知道强化学习的一个核心问题是如何估计状态价值函数或者状态动作函数V(s), Q(s, a)，在环境已知的情况下，我们已经可以通过动态规划来求解它们。在环境未知的情况下，无法直接求解贝尔曼方程，我们只能通过交互采样的数据来近似估计它们，有两种方法可以做到这一点——蒙特卡洛和时序差分。在开始介绍时序差分之前，我们先简单了解一下蒙特卡洛方法。

蒙特卡洛不是本期的重点，但是介绍它有助于引入时序差分算法。

2.2 时序差分算法

时序差分（Temporal Difference, TD）是一种用来估计一个策略的价值函数的方法，它结合了蒙特卡洛和动态规划算法的思想。时序差分方法和蒙特卡洛的相似之处在于可以从样本数据中学习，不需要事先知道环境；和动态规划的相似之处在于根据贝尔曼方程的思想，利用后续状态的价值估计来更新当前状态的价值估计。回顾一下蒙特卡洛方法对价值函数的增量更新方式：

时序差分算法

3. SARSA

我们上面已经可以用时序差分算法估计状态价值函数了，也就是我们在无模型的条件下，掌握了一种策略评估的方法。上期介绍了策略迭代算法和价值迭代算法：策略评估+策略提升，我们是否也能在无模型条件下实现类似的算法？这是这节要介绍的SARSA算法。

3.1 SARSA算法

SARSA算法

3.2 算法实践

3.2.1 环境介绍——Taxi

本期环境——gym Taxi：出租车接送客，这是一个网格世界

在网格中有红、黄、蓝、绿4个特殊点。游戏开始时，出租车随机出现在网格中一个位置，乘客随机出现在4个特殊点的其中一个位置。游戏开始后，车辆要先驶向乘客所在位置，接上乘客，将乘客送往目的地——4个特殊点中除了乘客的另一个，游戏结束。

总共有6个动作

• 0，向下移动一步

• 1，向上移动一步

• 2，向右移动一步

• 3，向左移动一步

• 4，接上乘客

• 5，放下乘客

• 状态向量，(车辆所在行，车辆所在列，乘客位置，目标位置)，在网格中车辆一共有25个合法位置

• 乘客位置，0：红，1：绿，2：黄， 3：蓝，4：在车上

• 目标位置，0：红，1：绿，2：黄， 3：蓝

• 总共状态空间大小为：25 * 5 * 4 = 500

• 如果车辆用了“撞墙”的动作，那么车辆在原地不动，状态向量不变

• 成功将乘客放入目标点：+20

• 在非目标点采取放下乘客的动作或在非乘客起点采取接上乘客的动作：-10

• 除上述情况外，每在网格走一步：-1

4. Q-learning

SASAR是一种在线策略的算法，另外还有一种有名的基于时序差分的强化学习算法——Q-learning。

4.1 Q-learning算法

Q-learning与SARSA非常相似，区别在于：

Q-learning算法

5. 总结

本期介绍了在无模型条件下最重要的算法——时序差分，学习了时序差分估计价值函数的方法，并且引入了两种基于时序差分的强化学习算法：SARSA和Q-learning。这个层次的强化学习算法已经可以解决一下稍微复杂的实际问题了，但是过程中我们不难发现SARSA和Q-learning只能处理离散的状态和动作空间，对于连续高维的状态和动作束手无策，所以它们属于表格型强化学习(Tabular Method)。这是传统表格方法的最后一章，从下一期起，我们将介绍在更一般更复杂情况下如何运用强化学习，并且正式迈入深度强化学习的大门。