【EasyRL学习笔记】第三章 表格型方法（Q-Table、Sarsa、Q-Learning）

---

策略最简单的表示是查找表（look-up table），即表格型策略（tabular policy）。
使用查找表的强化学习方法称为表格型方法（tabular method），如：

• 蒙特卡洛
• Q学习
• Sarsa

本章通过最简单的表格型方法来讲解如何使用基于价值的方法求解强化学习问题。

一、马尔可夫决策过程

强化学习是一个与时间相关的序列决策的问题。如下图所示，在t-1时刻，我看到熊对我招手，下意识的动作就是逃跑。熊看到有人逃跑，就可能觉得发现了猎物，并开始发动攻击。
而在 t 时刻，我如果选择装死的动作，可能熊咬咬我、摔几下就觉得挺无趣的，可能会走开。这个时候我再逃跑，可能就成功了，这就是一个序列决策过程。

1.1 有模型

有模型：环境的状态转移概率和奖励函数已知

如下图所示，我们把这些可能的动作和可能的状态转移的关系画成树状。它们之间的关系就是从 $s_t$ 到 $a_t$ ，再到 $s_{t+1}$ ，再到 $a_{t+1}$ ，再到 $s_{t+2}$ 的过程。我们与环境交互时，只能走一条完整的通路，这里面产生了一系列决策的过程，我们与环境交互产生了经验。

如果我们知道概率函数和奖励函数，马尔可夫决策过程就是已知的，我们可以通过策略迭代和价值迭代来找最佳的策略。

比如，在熊发怒的情况下，我如果选择装死，假设熊看到人装死就一定会走开，我们就称这里面的状态转移概率是 1。但如果在熊发怒的情况下，我选择逃跑而导致可能成功以及失败两种情况，转移到跑成功情况的概率大概 0.1，跑失败的概率大概是 0.9。

如果我们知道环境的状态转移概率和奖励函数，就可以认为这个环境是已知的，因为我们用这两个函数来描述环境。如果环境是已知的，我们其实可以用动态规划算法去计算，如果要逃脱，那么能够逃脱的概率最大的最佳策略是什么。

1.2 免模型

免模型：环境的状态转移概率、奖励函数是未知的，即环境是未知的

很多强化学习的经典算法都是免模型的，也就是环境是未知的。
因为现实世界中人类第一次遇到熊时，我们根本不知道能不能逃脱，所以 0.1、0.9 的概率都是虚构出来的概率。熊到底在什么时候往什么方向转变，我们通常是不知道的。

当然强化学习可以应用于完全未知的和随机的环境。
强化学习像人类一样学习，人类通过尝试不同的路来学习，通过尝试不同的路，人类可以慢慢地了解哪个状态会更好。
下图展示了免模型的试错探索图：

1.3 有模型与免模型的区别

策略迭代和价值迭代都需要得到环境的转移和奖励函数，所以在这个过程中，智能体没有与环境进行交互。如下图所示：

当马尔可夫决策过程的模型未知或者模型很大时，我们可以使用免模型强化学习的方法。
免模型强化学习方法没有获取环境的状态转移和奖励函数，而是让智能体与环境进行交互，采集大量的轨迹数据，智能体从轨迹中获取信息来改进策略，从而获得更多的奖励。

总结：

• 有模型：状态转移概率和奖励函数已知，无需与环境进行交互
• 免模型：状态转移概率、奖励函数未知，需要与环境交互，不断试错，采集轨迹数据，从而获得更多奖励

---

二、Q表格

Q表格就像一本生活手册，我们在和熊打交道后，可以记录它的生活习性到Q表格中，当记录足够多时，我们就足够了解熊了。
我们通过查看这本手册，就能知道在熊发怒的时候，装死的价值会高一点；在熊离开的时候，我们偷偷逃跑会比较容易获救。

这张表格里面 Q 函数的意义就是我们选择了某个动作后，最后能不能成功，就需要我们去计算在某个状态下选择某个动作，后续能够获得多少总奖励。

Q: 为什么我们可以用未来的总奖励来评价当前动作是好是坏?
A：因为只看当下的奖励是不明智的。例如，我们会为了将来找到更好的工作，放弃一些娱乐的时间用于学习；救护车会为了救人而闯红灯等等

但有的时候我们把目光放得太长远并不好。如果任务很快就结束，那么考虑到最后一步的奖励无可厚非。

但如果任务是一个持续的没有尽头的任务，即持续式任务（continuing task），我们把未来的奖励全部相加作为当前的状态价值就很不合理。股票就是一个典型的例子：

我们关注的是累积的股票奖励，可是如果10年之后股票才有一次大涨大跌，我们肯定不会把10年后的奖励也作为当前动作的考虑因素。
这个时候，我们就可以引入折扣因子 $\gamma$ 来计算末来总奖励， $\gamma \in [0,1]$ ，越往后 ${\gamma }^n$ 就会越小，越后面的奖励对当前价值的影响就会越小。

悬崖行走问题是强化学习的一个经典问题。该问题需要智能体从出发点 S 出发，到达目的地 G，同时避免掉进悬崖（cliff），每走一步就有 −1分 的惩罚，掉进悬崖会有 −100 分的惩罚，但游戏不会结束，智能体会回到出发点，游戏继续，直到到达目的地结束游戏。
智能体需要尽快地到达目的地。 为了到达目的地，智能体可以沿着例如蓝线和红线的路线行走。

在悬崖行走问题的环境中，我们怎么计算状态动作价值（未来的总奖励）呢？
我们可以选择一条路线，计算出这条路线上每个状态动作的价值。
在悬崖行走问题里面，智能体每走一步都会拿到 -−1 分的奖励，只有到达目的地之后，智能体才会停止。

• 如果 $\gamma =0$ ，我们考虑的就是单步的奖励，我们可以认为它是目光短浅的计算的方法。 上走是 $-15$ ，它知道往右走的价值更大，它就会往右走。
• 如果 $\gamma =1$ ，就等于把后续所有的奖励全部加起来，我们可以认为它是目光过于长远的方法。如果当小乌龟在 −12 的时候，往右走是 −11，往上走是 -15，它知道往右走的价值更大，它就会往右走。
• 如果 $\gamma =0.6$ ，我们的目光没有放得太长远，计算结果如下所示。我们可以利用公式 $G_t=r_{t+1}+\gamma G_{t+1}$ 从后往前推。
  $$\begin{array}{rl}& G_{13}=0\\ & G_{12}=r_{13}+\gamma G_{13}=-1+0.6\times 0=-1\\ & G_{11}=r_{12}+\gamma G_{12}=-1+0.6\times (-1)=-1.6\\ & G_{10}=r_{11}+\gamma G_{11}=-1+0.6\times (-1.6)=-1.96\\ & G_9=r_{10}+\gamma G_{10}=-1+0.6\times (-1.96)=-2.176\approx -2.18\\ & G_8=r_9+\gamma G_9=-1+0.6\times (-2.176)=-2.3056\approx -2.3\end{array}$$

最后我们要求解的就是一张 Q 表格，它的行数是所有状态的数量，一般可以用坐标来表示格子的状态，也可以用 1、2、3、4、5、6、7 来表示不同的位置。

Q 表格的列表示上、下、左、右4个动作。
最开始的时候，Q 表格会全部初始化为0。智能体会不断和环境交互得到不同的轨迹，当交互的次数足够多的时候，我们就可以估算出每一个状态下，每个动作的平均总奖励，进而更新 Q 表格。
Q表格的更新就是接下来要引入的强化概念。
下图展示了初始化全为0的Q表格：

强化： 是指我们可以用下一个状态的价值来更新当前状态的价值，其实就是强化学习里面自举的概念。

在强化学习里面，我们可以每走一步更新一次 Q 表格，用下一个状态的 Q 值来更新当前状态的 Q 值，这种单步更新的方法被称为时序差分方法。

---

三、免模型预测

在无法获取马尔可夫决策过程的模型情况下，我们可以通过蒙特卡洛方法和时序差分方法来估计某个给定策略的价值。

3.1 蒙特卡洛方法

3.1.1 蒙特卡洛方法特点

• 是基于采样的方法，给定策略$\pi$，我们让智能体与环境进行交互，可以得到很多轨迹。每个轨迹都有对应的回报：$G_t=r_{t+1}+\gamma r_{t+2}+{\gamma }^2{r}_{t+3}+\dots$。我们求出所有轨迹的回报的平均值，就可以知道某一个策略对应状态的价值。又称之为经验平均回报（empirical mean return）

3.1.2 蒙特卡洛方法步骤

为了得到评估 $V(s)$ ，采取如下的步骤：

（1）在每个回合中，如果在时间步 $t$ 状态 $s$ 被访问了，那么

• 状态 $s$ 的访问数 $N(s)$ 增加 $1，N(s)\leftarrow N(s)+1$ 。
• 状态 $s$ 的总的回报 $S(s)$ 增加 $G_t,S(s)\leftarrow S(s)+G_t$ 。

（2）状态 $s$ 的价值可以通过回报的平均来估计，即 $V(s)=S(s)/N(s)$ 。

根据大数定律，只要我们得到足够多的轨迹，就可以趋近这个策略对应的价值函数。当 $N(s)\to \infty$ 时， $V(s)\to V_{\pi }(s)$ 。

假设现在有样本 $x_1,x_2,\cdots ,x_t$ ，我们可以把经验均值 (empirical mean) 转换成增量均值 (incremental mean) 的形式:：

$$\begin{array}{rl}{\mu }_t& =\frac{1}{t}\sum _{j-1}^t{x}_j\\ & =\frac{1}{t}\left(x_t+\sum _{j-1}^{t-1}{x}_j\right)\\ & =\frac{1}{t}\left(x_t+(t-1){\mu }_{t-1}\right)\\ & =\frac{1}{t}\left(x_t+t{\mu }_{t-1}-{\mu }_{t-1}\right)\\ & ={\mu }_{t-1}+\frac{1}{t}\left(x_t-{\mu }_{t-1}\right)\end{array}$$

通过这种转换，我们就可以把上一时刻的平均值与现在时刻的平均值建立联系：

$${\mu }_{t-1}+\frac{1}{t}\left(x_t-{\mu }_{t-1}\right)$$

其中， $x_t-{\mu }_{t-1}$ 是残差， $\frac{1}{t}$ 类似于学习率 (learning rate) 。当我们得到 $x_t$ 时，就可以用上一时刻的值来更新现在的值。

$$\begin{array}{rl}& N\left(s_t\right)\leftarrow N\left(s_t\right)+1\\ & V\left(s_t\right)\leftarrow V\left(s_t\right)+\frac{1}{N\left(s_t\right)}\left(G_t-V\left(s_t\right)\right)\end{array}$$

我们可以直接把 $\frac{1}{N\left(s_t\right)}$ 变成 $\alpha$ (学习率)，即

$$V\left(s_t\right)\leftarrow V\left(s_t\right)+\alpha \left(G_t-V\left(s_t\right)\right)$$

其中， $\alpha$ 代表更新的速率，我们可以对其进行设置。 通过上一时刻的值 $V_{i-1}\left(s^{\prime }\right)$ 来更新当前时刻的值 $V_i(s)$ ，即

$$V_i(s)\leftarrow \sum _{a\in A}\pi (a\mid s)\left(R(s,a)+\gamma \sum _{s^{\prime }\in S}P\left(s^{\prime }\mid s,a\right)V_{i-1}\left(s^{\prime }\right)\right)$$

将其不停迭代，最后可以收敛。如下图所示，贝尔㬅期望备份有两层加和，即内部加和和外部加和，计算两次期望，得到一个更新。

蒙特卡洛方法通过一个回合的经验平均回报 (实际得到的奖励) 来进行更新，即

$$V\left(s_t\right)\leftarrow V\left(s_t\right)+\alpha \left(G_{i,t}-V\left(s_t\right)\right)$$

如下图所示，我们使用蒙特卡洛方法得到的轨迹对应树上监色的轨迹，轨迹上的状态已经是决定的，采取的动作也是已经决定的。我们现在只更新这条轨迹上的所有状态，与这条轨迹没有关系的状态都不进行更新。

3.1.3 蒙特卡洛方法优点

• 它不需要马尔可夫决策过程的状态转移函数和奖励函数，适用于环境未知的情况
• 只需要更新一条轨迹的状态，不需要像动态规划那样用自举的方法更新所有的状态，运算速度快

3.1.4 蒙特卡洛方法缺点

• 有一定的局限性，它只能用在有终止的马尔可夫决策过程中
• 只能从完整的序列上进行学习
• 必须等游戏结束时才可以学习

3.2 时序差分方法

我们先了解一下巴甫洛夫的条件反射实验，如下图所示：

巴甫洛夫效应揭示的是，当中性刺激（铃声）与无条件刺激（食物）相邻反复出现的时候，中件刺激也可以引起无条件刺激引起的唾液分泌，然后形成条件刺激。

小狗本来不觉得铃声有价值的，经过强化之后，小狗就会慢慢地意识到铃声也是有价值的，它可能带来食物。

更重要的是当一种条件反射巩固之后，我们再用另外一种新的刺激和条件反射相结合，还可以形成第二级条件反射，同样地还可以形成第三级条件反射。

在介绍时序差分之前，大家可以先看看时序差分算法的动画演示：时序差分学习网格世界演示

• 在训练的过程中，小黄球在不断地试错，在探索中会先迅速地发现有奖励的格子
• 最开始的时候，有奖励的格子才有价值
• 当小黄球不断地重复走这些路线的时候，有价值的格子可以慢慢地影响它附近的格子的价值
• 反复训练之后，有奖励的格子周围的格子的状态就会慢慢被强化
• 强化就是价值最终收敛到最优的情况之后，小黄球就会自动往价值高的格子走，就可以走到能够拿到奖励的格子

3.2.1 时序差分方法特点

• 时序差分是介于蒙特卡洛和动态规划之间的方法，它是免模型的，不需要马尔可夫决策过程的转移矩阵和奖励函数。
• 此外，时序差分方法可以从不完整的回合中学习，并且结合了自举的思想。

3.2.2 时序差分方法步骤

接下来，我们对时序差分方法进行总结。时序差分方法的目的是对于某个给定的策略$\pi$，在线（online）地算出它的价值函数$V_{\pi }$，即一步一步地（step-by-step）算。

最简单的算法是一步时序差分（one-step TD），即TD(0)。每往前走一步，就做一步自举，用得到的估计回报 (estimated return) ：$r_{t+1}+\gamma V\left(s_{t+1}\right)$ 来更新上一时刻的值 $V\left(s_t\right)$ :

$$V\left(s_t\right)\leftarrow V\left(s_t\right)+\alpha \left(r_{t+1}+\gamma V\left(s_{t+1}\right)-V\left(s_t\right)\right)$$

估计回报 $r_{t+1}+\gamma V\left(s_{t+1}\right)$ 被称为时序差分目标（TD target)，时序差分目标是带衰减的末来奖励的总和。时序差分目标由两部分组成：

（1）我们走了某一步后得到的实际奖励 $r_{t+1}$;
（2）我们利用了自举的方法，通过之前的估计来估计 $V\left(s_{t+1}\right)$ ，并且加了折扣因子，即 $\gamma V\left(s_{t+1}\right)$ 。

时序差分目标是估计有两个原因:

（1）时序差分方法对期望值进行采样；
（2）时序差分方法使用当前估计的 $V$ 而不是真实的 $V_{\pi }$ 。

时序差分误差 (TD error) $\delta =r_{t+1}+\gamma V\left(s_{t+1}\right)-V\left(s_t\right)$ 。 类比增量式蒙特卡洛方法，给定一个回合 $i$ ，我们可以更新 $V\left(s_t\right)$ 来逼近真实的回报 $G_t$ ，具体更新公式为

$$V\left(s_t\right)\leftarrow V\left(s_t\right)+\alpha \left(G_{i,t}-V\left(s_t\right)\right)$$

上式体现了强化的概念

时序差分和蒙特卡洛方法区别讲解：

例如，我们想获得开车去公司的时间，每天上班开车的经历就是一次采样。假设我们今天在路口 A 遇到了堵车， 时序差分方法会在路口 A 就开始更新预计到达路口 B、路口 C ⋯⋯，以及到达公司的时间； 而蒙特卡洛方法并不会立即更新时间，而是在到达公司后，再更新到达每个路口和公司的时间。

时序差分方法能够在知道结果之前就开始学习，相比蒙特卡洛方法，其更快速、灵活。

此外，我们可以把时序差分方法进行进一步的推广。之前是只往前走一步，即TD(0)。
我们可以调整步数（step），变成n步时序差分（n-step TD）。比如 TD(2)，即往前走两步，利用两步得到的回报，使用自举来更新状态的价值。

这样我们就可以通过步数来调整算法需要的实际奖励和自举。

$$\begin{array}{rl}n=1(\text{ TD })& G_t^{(1)}=r_{t+1}+\gamma V\left(s_{t+1}\right)\\ n=2& G_t^{(2)}=r_{t+1}+\gamma r_{t+2}+{\gamma }^{2}V\left(s_{t+2}\right)\\ n=\infty (\mathrm{MC})& G_t^{\infty }=r_{t+1}+\gamma r_{t+2}+\dots +{\gamma }^{T-t-1}{r}_T\end{array}$$

如上式所示，通过调整步数，可以进行蒙特卡洛方法和时序差分方法之间的权衡。如果 $n=\infty$ ，即整个游戏结束后，再进行更新，时序差分方法就变成了蒙特卡洛方法。
$n$ 步时序差分可写为

$$G_t^n=r_{t+1}+\gamma r_{t+2}+\dots +{\gamma }^{n-1}{r}_{t+n}+{\gamma }^{n}V\left(s_{t+n}\right)$$

得到时序差分目标之后，我们用增量式学习 (incremental learning) 的方法来更新状态的价值:

$$V\left(s_t\right)\leftarrow V\left(s_t\right)+\alpha \left(G_t^n-V\left(s_t\right)\right)$$

3.2.3 时序差分算法优点

• 不需要马尔可夫决策过程的状态转移函数和奖励函数，适用于环境未知的情况
• 可以从不完整序列上进行学习
• 结合了自举的思想
• 可以在线学习（online learning），每走一步就可以更新，效率高
• 可以在连续的环境下（没有终止）进行学习
• 利用了马尔可夫性质，在马尔可夫环境下有更高的学习效率

3.3 动态规划方法、蒙特卡洛方法以及时序差分方法的自举和采样

自举是指更新时使用了估计。
蒙特卡洛方法没有使用自举，因为它根据实际的回报进行更新。 动态规划方法和时序差分方法使用了自举。

采样是指更新时通过采样得到一个期望。
蒙特卡洛方法是纯采样的方法。 动态规划方法没有使用采样，它是直接用贝尔曼期望方程来更新状态价值的。 时序差分方法使用了采样。

时序差分目标由两部分组成，一部分是采样，一部分是自举。

动态规划方法直接计算期望，它把所有相关的状态都进行加和，即

$$V\left(s_t\right)\leftarrow {\mathbb{E}}_{\pi }\left[r_{t+1}+\gamma V\left(s_{t+1}\right)\right]$$

蒙特卡洛方法在当前状态下，采取一条支路，在这条路径上进行更新，更新这条路径上的所有状态，即

$$V\left(s_t\right)\leftarrow V\left(s_t\right)+\alpha \left(G_t-V\left(s_t\right)\right)$$

时序差分从当前状态开始，往前走了一步，关注的是非常局部的步骤，即

$$\mathrm{TD}(0):V\left(s_t\right)\leftarrow V\left(s_t\right)+\alpha \left(r_{t+1}+\gamma V\left(s_{t+1}\right)-V\left(s_t\right)\right)$$

如果时序差分方法需要更广度的更新，就变成了 动态规划方法（因为动态规划方法是把所有状态都考虑进去来进行更新）。
如果时序差分方法需要更深度的更新，就变成了蒙特卡洛方法。
下图右下角是穷举搜索的方法（exhaustive search），穷举搜索的方法不仅需要很深度的信息，还需要很广度的信息。

---

四、免模型控制

4.1 广义策略迭代方法

Q:在我们不知道马尔可夫决策过程模型的情况下，如何优化价值函数，得到最佳的策略呢？
A:可以把策略迭代进行广义的推广，使它能够兼容蒙特卡洛和时序差分的方法，即带有蒙特卡洛方法和时序差分方法的广义策略迭代（generalized policy iteration，GPI）。

Q:当我们不知道奖励函数和状态转移时，如何进行策略的优化？
A:采用广义的策略迭代的方法。对策略评估部分进行修改，使用蒙特卡洛的方法代替动态规划的方法估计 Q 函数。我们首先进行策略评估，使用蒙特卡洛方法来估计策略$Q=Q_{\pi }$，然后进行策略更新，即得到 Q 函数后，我们就可以通过贪心的方法去改进它：

$$\pi (s)=\underset{a}{\mathrm{argmax}}Q(s,a)$$

4.2 基于探索性开始的蒙特卡洛方法

下图所示为蒙特卡洛方法估计 Q 函数的算法。
一个保证策略迭代收敛的假设是回合有探索性开始（exploring start）。 假设每一个回合都有一个探索性开始，探索性开始保证所有的状态和动作都在无限步的执行后能被采样到，这样才能很好地进行估计。

算法通过蒙特卡洛方法产生很多轨迹，每条轨迹都可以算出它的价值。然后，我们可以通过平均的方法去估计 Q 函数。Q 函数可以看成一个Q表格，我们通过采样的方法把表格的每个单元的值都填上，然后使用策略改进来选取更好的策略。 如何用蒙特卡洛方法来填 Q 表格是这个算法的核心。

4.3 基于$\epsilon$-贪心探索的蒙特卡洛方法

为了保证蒙特卡洛方法有足够的探索，可以使用$\epsilon$-贪心探索。
$\epsilon$-贪心是指我们有$1-\epsilon$的概率按照Q函数来决定动作，一般$\epsilon$为一个较小值，$1-\epsilon$可能是0.9。
通常，$\epsilon$的值会随着时间递减（类似模拟退火过程，随着迭代进行减少随机性）

4.4 Sarsa：同策略时序差分控制

与蒙特卡洛方法相比，时序差分方法有如下几个优势：

• 低方差，能够在线学习
• 能够从不完整的序列中学习。

所以我们可以把时序差分方法也放到控制循环（control loop）里面去估计Q表格，再采取$\epsilon$-贪心探索改进。这样就可以在回合没结束的时候更新已经采集到的状态价值。

时序差分方法是给定一个策略，然后我们去估计它的价值函数。接着我们要考虑怎么使用时序差分方法的框架来估计Q函数，也就是 Sarsa 算法。

它将原本时序差分方法更新 $V$ 的过程，变成了更新 $Q$ ，即

$$Q\left(s_t,a_t\right)\leftarrow Q\left(s_t,a_t\right)+\alpha \left[r_{t+1}+\gamma Q\left(s_{t+1},a_{t+1}\right)-Q\left(s_t,a_t\right)\right]$$

上式是指我们可以用下一步的 $\mathrm{Q}$ 值 $Q\left(s_{t+1},a_{t+1}\right)$ 来更新这一步的 $\mathrm{Q}$ 值 $Q\left(s_t,a_t\right)$ 。
Sarsa 直接估计 $\mathrm{Q}$ 表格，得到 $\mathrm{Q}$ 表格后，就可以更新策略。

我们想要计算的就是 $Q\left(s_t,a_t\right)$ 。因为最开始 $Q$ 值都是随机初始化或者是初始化为 0 ，所以它需要不断地去逼近它理想中真实 的 $\mathrm{Q}$ 值 (时序差分目标)， $r_{t+1}+\gamma Q\left(s_{t+1},a_{t+1}\right)-Q\left(s_t,a_t\right)$ 就是时序差分误差。

我们用 $Q\left(s_t,a_t\right)$ 来逼近 $G_t$ ，那么 $Q\left(s_{t+1},a_{t+1}\right)$ 其实就是近似 $G_{t+1}$ 。我们就可以用 $Q\left(s_{t+1},a_{t+1}\right)$ 近似 $G_{t+1}$ ，把 $r_{t+1}+\gamma Q\left(s_{t+1},a_{t+1}\right)$ 当成目标值。 $Q\left(s_t,a_t\right)$ 要逼近目标值，我们用软更新的方式来逼近。软更新的方式就是每次我们只更新一点点， $\alpha$ 类似于学习率。最终 $Q$ 值是可以慢蜀地逼近真实的目标值的。这样更新公式只需要用到当前时刻的 $s_t、a_t$ ，还有获取的 $r_{t+1}、s_{t+1}、a_{t+1}$ 。

该算法由于每次更新值函数时需要知道当前的状态 (state) 、当前的动作 (action) 、奖励 (reward)、下一步的状态 (state) 、下一步的动作 (action)，即 $\left(s_t,a_t,r_{t+1},s_{t+1},a_{t+1}\right)$ 这几个值，因此得名 Sarsa 算法。它走了一步之后，获取 了 $\left(s_t,a_t,r_{t+1},s_{t+1},a_{t+1}\right)$ 之后，就可以做一次更新。

Sarsa 的更新公式可写为

$$Q(S,A)\leftarrow Q(S,A)+\alpha \left(R+\gamma Q\left(S^{\prime },A^{\prime }\right)-Q(S,A)\right)$$

Sarsa的更新公式与时序差分方法的公式是类似的。 $S^{\prime }$ 就是 $s_{t+1}$ 。我们就是用下一步的 $\mathrm{Q}$ 值 $Q\left(S^{\prime },A^{\prime }\right)$ 来更新这一步的 $\mathrm{Q}$ 值 $Q(S,A)$ ，不断地强化每一个 $\mathrm{Q}$ 值。

$$\begin{array}{rl}n=1(\text{ Sarsa) }{Q}_t^1& =r_{t+1}+\gamma Q\left(s_{t+1},a_{t+1}\right)\\ n=2Q_t^2& =r_{t+1}+\gamma r_{t+2}+{\gamma }^{2}Q\left(s_{t+2},a_{t+2}\right)\\ ⋮& \\ n=\infty (\mathrm{MC})Q_t^{\infty }& =r_{t+1}+\gamma r_{t+2}+\dots +{\gamma }^{T-t-1}{r}_T\end{array}$$
我们考虑 $n$ 步的回报 $(n=1,2,\cdots ,\infty )$ ，如上式所示。Sarsa 属于单步更新算法，每执行一个动作，就会更新一次价值 和策略。如果不进行单步更新，而是采取 $n$ 步更新或者回合更新，即在执行 $n$ 步之后再更新价值和策略，这样我们就得到了 $n$ 步 Sarsa ( $n$-step Sarsa)。

比如 2 步 Sarsa 就是执行两步后再来更新 Q函数的值。对于 Sarsa，在 $t$ 时刻的价值为

$$Q_t=r_{t+1}+\gamma Q\left(s_{t+1},a_{t+1}\right)$$

而对于 $n$ 步 Sarsa，它的 $n$ 步 Q 回报为

$$Q_t^n=r_{t+1}+\gamma r_{t+2}+\dots +{\gamma }^{n-1}{r}_{t+n}+{\gamma }^{n}Q\left(s_{t+n},a_{t+n}\right)$$

如果给 $Q_t^n$ 加上资格迹衰减参数 (decay-rate parameter for eligibility traces) $\lambda$ 并进行求和，即可得到 $\mathrm{Sarsa}(\lambda )$ 的 $\mathrm{Q}$ 回报

$$Q_t^{\lambda }=(1-\lambda )\sum _{n-1}^{\infty }{\lambda }^{n-1}{Q}_t^n$$

因此， $n$ 步 Sarsa $(\lambda )$ 的更新策略为

$$Q\left(s_t,a_t\right)\leftarrow Q\left(s_t,a_t\right)+\alpha \left(Q_t^{\lambda }-Q\left(s_t,a_t\right)\right)$$

总之，Sarsa 和 $\mathrm{Sarsa}(\lambda )$ 的差别主要体现在价值的更新上。

了解单步更新的基本公式之后，代码实现就很简单了。如下图所示，右边是环境，左边是智能体。智能体每与环境交互一次 之后，就可以学习一次，向环境输出动作，从环境当中获取状态和奖励。智能体主要实现两个方法:
（1） 根据 $\mathrm{Q}$ 表格选择动作，输出动作;
（2） 获取 $\left(s_t,a_t,r_{t+1},s_{t+1},a_{t+1}\right)$ 这几个值更新 $\mathrm{Q}$ 表格。

4.5 Q学习：异策略时序差分控制

Sarsa 是一种同策略（on-policy）算法，它优化的是它实际执行的策略，它直接用下一步会执行的动作去优化 Q 表格。
同策略在学习的过程中，只存在一种策略，它用一种策略去做动作的选取，也用一种策略去做优化。所以 Sarsa 知道它下一步的动作有可能会跑到悬崖那边去，它就会在优化自己的策略的时候，尽可能离悬崖远一点。

Q学习是一种异策略（off-policy）算法。
异策略在学习的过程中，有两种不同的策略：目标策略（target policy）和行为策略（behavior policy）。
目标策略就是我们需要去学习的策略，相当于后方指挥的军师，它不需要直接与环境进行交互
行为策略是探索环境的策略，负责与环境交互，然后将采集的轨迹数据送给目标策略进行学习，而且为送给目标策略的数据中不需要$a_{t+1}$，而Sarsa是要有$a_{t+1}$的。
Q学习不会管我们下一步去往哪里探索，它只选取奖励最大的策略

异策略学习的好处:

• 可以利用探索策略来学到最佳的策略，学习效率高
• 可以让我们学习其他智能体的动作，进行模仿学习，学习人或者其他智能体产生的轨迹
• 可以让我们重用旧的策略产生的轨迹，探索过程需要很多计算资源，这样可以节省资源

$\mathrm{Q}$ 学习有两种策略：行为策略和目标策略。目标策略 $\pi$ 直接在 $\mathrm{Q}$ 表格上使用贪心策略，取它下一步能得到的所有状态，即

$$\pi \left(s_{t+1}\right)=\underset{a^{\prime }}{\mathrm{argmax}}Q\left(s_{t+1},a^{\prime }\right)$$

行为策略 $\mu$ 可以是一个随机的策略，但我们采取 $\epsilon$-贪心策略，让行为策略不至于是完全随机的，它是基于 $Q$ 表格逐渐改进的。
我们可以构造 $Q$ 学习目标， $Q$ 学习的下一个动作都是通过 arg max 操作选出来的，于是我们可得

$$\begin{array}{rl}{r}_{t+1}+\gamma Q\left(s_{t+1},A^{\prime }\right)& =r_{t+1}+\gamma Q\left(s_{t+1},\arg \max Q\left(s_{t+1},a^{\prime }\right)\right)\\ & =r_{t+1}+\gamma \underset{a^{\prime }}{\max }Q\left(s_{t+1},a^{\prime }\right)\end{array}$$

接着我们可以把 $\mathrm{Q}$ 学习更新写成增量学习的形式，时序差分目标变成了 $r_{t+1}+\gamma {\max }_{a}Q\left(s_{t+1},a\right)$ ，即

$$Q\left(s_t,a_t\right)\leftarrow Q\left(s_t,a_t\right)+\alpha \left[r_{t+1}+\gamma \underset{a}{\max }Q\left(s_{t+1},a\right)-Q\left(s_t,a_t\right)\right]$$

4.6 Sarsa与Q学习的区别

• Sarsa 是一个典型的同策略算法，它只用了一个策略 $\pi$ ，它不仅使用策略 $\pi$ 学习，还使用策略 $\pi$ 与环境交互产生经验。如果策略采用 $\epsilon$-贪心算法，它需要兼顾探索，为了兼顾探索和利用，它训练的时候会显得有点“胆小”。它在解决悬崖行走问 题的时候，会尽可能地远离悬崖边，确保哪怕自己不小心探索了一点儿，也还是在安全区域内。此外，因为采用的是 $\epsilon$-贪心 算法，策略会不断改变（ $\epsilon$ 值会不断变小），所以策略不稳定。
• $\mathrm{Q}$ 学习是一个典型的异策略算法，它有两种策略------目标策略和行为策略，它分离了目标策略与行为策略。Q学习可以大 胆地用行为策略探索得到的经验轨迹来优化目标策略，从而更有可能探索到最佳策略。行为策略可以采用 $\epsilon$-贪心 算法，但目标策略采用的是贪心算法，它直接根据行为策略采集到的数据来采用最佳策略，所以 Q学习不需要兼顾探索。
• 比较一下Q学习和 Sarsa 的更新公式，就可以发现 Sarsa 并没有选取最大值的最大化操作。因此，Q学习是一个非常激进的方法，它希望每一步都获得最大的利益; Sarsa 则相对较为保守，它会选择一条相对安全的迭代路线。

Sarsa 和 Q学习的更新公式是一样的，区别只在目标计算的部分，Sarsa 是 $r_{t+1}+\gamma Q\left(s_{t+1},a_{t+1}\right)，\mathrm{Q}$ 学习是 $r_{t+1}+$ $\gamma {\max }_{a}Q\left(s_{t+1},a\right)$ 。

Sarsa 用自己的策略产生了 $S,A,R,S^{\prime },A^{\prime }$ 这条轨迹，然后用 $Q\left(s_{t+1},a_{t+1}\right)$ 去更新原本的 $\mathrm{Q}$ 值 $Q\left(s_t,a_t\right)$。

但是 $Q$ 学习并不需要知道我们实际上选择哪一个动作，它默认下一个动作就是 $Q$ 值最大的那个动作。Q学习知道实际上行为策略可能会有 $0.1$ 的概率选择别的动作，但 $Q$ 学习并不担心受到探索的影响，它默认按照最佳的策略去优化目标策略，所以 它可以更大胆地去寻找最优的路径，它表现得比 Sarsa 大胆得多。

我们对 $\mathrm{Q}$ 学习进行逐步拆解，Q学习与 Sarsa 唯一不一样的就是并不需要提前知道 $A_2$ ，就能更新 $Q\left(S_1,A_1\right)$。

在一个回合的训练当中，Q学习在学习之前也不需要获取下一个动作 $A^{\prime }$ ，它只需要前面的 $\left(S,A,R,S^{\prime }\right)$ ，这与 Sarsa 很不一样。

---

五、表格型方法总结

---

六、关键词总结

• 概率函数和奖励函数：概率函数定量地表达状态转移的概率, 其可以表现环境的随机性。但是实际上, 我们经常处于一个末知的环境中, 即概率函数和奖励函数是末知的。
• $\mathrm{Q}$ 表格: 其表示形式是表格, 其中表格的横轴为动作 (智能体的动作), 纵轴为环境的状态, 每一个 坐标点对应某时刻智能体和环境的状态, 并通过对应的奖励反馈选择被执行的动作。一般情况下, - $Q$ 表格 是一个已经训练好的表格, 不过我们也可以每执行一步, 就对 $Q$ 表格进行更新, 然后用下一个状态的 $Q$ 值来更新当前状态的 Q 值（即时序差分方法)。
• 时序差分 (temporal difference, TD) 方法: 一种 $Q$ 函数（Q 值）的更新方式, 流程是使用下一步的 $\mathrm{Q}$ 值 $Q\left(s_{t+1},a_{t+1}\right)$ 来更新当前步的 $\mathrm{Q}$ 值 $Q\left(s_t,a_t\right)$ 。完整的计算公式如下: $Q\left(s_t,a_t\right)\leftarrow Q\left(s_t,a_t\right)+\alpha [r_{t+1}+$ $\gamma Q\left(s_{t+1},a_{t+1}\right)-Q\left(s_t,a_t\right)]$ 。
• Sarsa 算法: 一种更新前一时刻状态的单步更新的强化学习算法, 也是一种同策略学习算法。该算法 由于每次更新 $\mathrm{Q}$ 函数时需要知道前一步的状态、动作、奖励以及当前时刻的状态、将要执行的动作, 即 $s_t、a_t、r_{t+1}、s_{t+1}、a_{t+1}$ 这几个值, 因此被称为 Sarsa 算法。智能体每进行一次循环, 都会用 $s_t、a_t、r_{t+1}$ 、 $s_{t+1}、a_{t+1}$ 对前一步的 $\mathrm{Q}$ 值 (函数) 进行一次更新。

---

七、习题

3-1 构成强化学习的马尔可夫决策过程的四元组有哪些变量?
3-2 请通俗地描述强化学习的 “学习” 流程。
3-3 请描述基于 Sarsa 算法的智能体的学习过程。
3-4 Q 学习算法和 Sarsa 算法的区别是什么?
3-5 同策略和异策略的区别是什么?

---

八、面试题

3-1 友善的面试官：同学, 你能否简述同策略和异策略的区别呢?
3-2 友善的面试官：能否细致地讲一下 $\mathrm{Q}$ 学习算法, 最好可以写出其 $Q(s,a)$ 的更新公式。另外, 它 是同策略还是异策略, 原因是什么呢?
3-3 友善的面试官：好的, 看来你对于 $\mathrm{Q}$ 学习算法很了解, 那么能否讲一下与 $\mathrm{Q}$ 学习算法类似的 Sarsa 算法呢, 最好也可以写出其对应的 $Q(s,a)$ 更新公式。另外, 它是同策略还是异策略, 为什么?
3-4 友善的面试官：请问基于价值的方法和基于策略的方法的区别是什么?
3-5 友善的面试官：请简述一下时序差分方法。
3-6 友善的面试官：请问蒙特卡洛方法和时序差分方法是无偏估计吗? 另外谁的方差更大呢? 为什么?
3-7 友善的面试官：能否简单说一下动态规划方法、蒙特卡洛方法和时序差分方法的异同点?

---

九、Python代码实战

9.1 Sarsa算法求解悬崖行走问题

【强化学习】Sarsa算法求解悬崖行走问题 + Python代码实战

9.2 Q-Learning算法求解悬崖行走问题

【强化学习】Q-Learning算法求解悬崖行走问题 + Python代码实战