强化学习 3.表格型方法（理论部分）

发表于 2026-03-16 更新于 2026-03-24

前言

从零开始学习ai文章系列计划是个人在《动手学深度学习》和《磨菇书》两本书的学习中的个人笔记，文章也会以课本中的章节分开，即每个章节一片笔记。我会尽量的把主要内容以及遇到的难点进行记录与解决，如果哪里有错误的欢迎指正。或者不清晰的可以直接查看原文部分。

《蘑菇书》原文（课本）：https://datawhalechina.github.io/easy-rl/#/

（由于有时候公式太多，可能会直接贴图片）

蘑菇书的文章结构不会跟之前《动手学深度学习》按照原文章节进行，个人会适当调节。

策略最简单的表示是查找表（look-up table），即表格型策略（tabular policy）。

使用查找表的强化学习方法称为表格型方法（tabular method），如蒙特卡洛、Q学习和Sarsa。本章通过最简单的表格型方法来讲解如何使用基于价值的方法求解强化学习问题。

1.有模型与免模型

1.1 有模型

如果我们知道环境的状态转移概率和奖励函数，就可以认为这个环境是已知的，因为我们用这两个函数来描述环境。如果环境是已知的，我们其实可以用动态规划算法去计算。

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

1.2 免模型

强化学习可以应用于完全未知的和随机的环境。

强化学习像人类一样学习，人类通过尝试不同的路来学习，通过尝试不同的路，人类可以慢慢地了解哪个状态会更好。

免模型强化学习方法没有获取环境的状态转移和奖励函数，而是让智能体与环境进行交互，采集大量的轨迹数据，智能体从轨迹中获取信息来改进策略，从而获得更多的奖励。

2. Q 表格

在野外遇到熊的时候，我们可以选择装死或者逃跑，在多次尝试和熊打交道之后，我们就可以对熊的不同的状态做出判断，用状态动作价值来表达在某个状态下某个动作的好坏。

如图 3.6 所示，如果 Q 表格是一张已经训练好的表格，这张表格就像是一本生活手册。

我们再举个例子。悬崖行走问题是强化学习的一个经典问题，如图 3.9 所示，该问题需要智能体从出发点 S 出发，到达目的地 G，同时避免掉进悬崖（cliff），每走一步就有 −1分的惩罚，掉进悬崖会有 −100 分的惩罚，但游戏不会结束，智能体会回到出发点，游戏继续，直到到达目的地结束游戏。

智能体需要尽快地到达目的地。为了到达目的地，智能体可以沿着例如蓝线和红线的路线行走。

在悬崖行走问题的环境中，我们怎么计算状态动作价值/Q值（未来的总奖励）呢？

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

第二章我们讲过价值的计算如下，其原因也之前说过因此不再累述 \[ G_t = r_{t+1}+\gamma r_{t+2} +\gamma^2 r_{t+3}+... \] 以图中红色线路为例。如果 γ=0.6，如图 3.10c 所示。我们可以利用如下公式从后往前推。 \[ G_t=r_{t+1}+\gamma G_{t+1} \]

我们得到了该路线上所有状态对应动作走右边的价值，即Q(s,右)的值。

最后我们要求解的就是一张 Q 表格，类似于图 3.11，它的行数是所有状态的数量，一般可以用坐标来表示格子的状态，也可以用 1、2、3、4、5、6、7 来表示不同的位置。Q 表格的列表示上、下、左、右4个动作。

3. 免模型预测 (价值评估)

3.1 蒙特卡洛策略评估

蒙特卡洛方法是基于采样的方法，给定策略 π，我们让智能体与环境进行交互，可以得到很多轨迹。每个轨迹都有对应的回报： \[ G_t = r_{t+1}+\gamma r_{t+2} +\gamma^2 r_{t+3}+... \] 我们求出所有轨迹的回报的平均值，就可以知道某一个策略对应状态的价值，即

蒙特卡洛仿真是指我们可以采样大量的轨迹，计算所有轨迹的真实回报，然后计算平均值。蒙特卡洛方法使用经验平均回报（empirical mean return）的方法来估计，它不需要马尔可夫决策过程的状态转移函数和奖励函数，并且不需要像动态规划那样用自举的方法。

此外，蒙特卡洛方法有一定的局限性，它只能用在有终止的马尔可夫决策过程中。

接下来，我们对蒙特卡洛方法进行总结。为了得到评估 V(s)，我们采取了如下的步骤。

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

• 状态s 的 访问数N(s) 增加 1，$N(s)←N(s)+1$。

• 状态s 的 总的回报S(s) 增加 $G_t$，$S(s)←S(s)+G_t$。

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

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

假设现在有样本 $x_1,x_2,⋯ ,x_t$我们可以把经验均值（empirical mean）转换成增量均值（incremental mean）的形式：

通过这种转换，我们就可以把上一时刻的平均值与现在时刻的值建立联系，即 \[ u_t=u_{t-1}+\frac{1}{t}{(x_t-u_{t-1})} \] 我们可以把蒙特卡洛方法更新的方法写成增量式蒙特卡洛（incremental MC）方法。我们采集数据，得到一个新的轨迹 (s1,a1,r1,…,st)。对于这个轨迹，我们采用增量的方法进行更新：

我们可以直接把 $\frac{1}{N(s_t)}$ 换成$\alpha$ （学习率），即 \[ V(s_t) \leftarrow V(s_{t})+\alpha(G_t-V(s_{t})) \] 其中，α 代表更新的速率，我们可以对其进行设置。

为什么可以把 $\frac{1}{N(s_t)}$ 换成$\alpha$ （学习率）？

原因是：在强化学习中，我们往往不需要严格的“统计平均真值”，而是希望：

在数据不断变化的环境（非平稳环境）中持续学习

更重视新数据（因为策略在变）

允许一定偏差，用于更快收敛

如果我们去除公式 $V(s_t) \leftarrow V(s_{t})+\alpha(G_t-V(s_{t}))$ 中的括号并重新整合，我们得到如下公式 \[ V(s_t) \leftarrow (1-\alpha)V(s_{t})+\alpha G_t \] 其本质是指数加权移动平均，参考动手学深度学习 7.4 动量法

我们再来看一下动态规划方法和蒙特卡洛方法的差异。

动态规划也是常用的估计价值函数的方法。在动态规划方法里面，我们使用了自举的思想。自举就是我们基于之前估计的量来估计一个量。此外，动态规划方法使用贝尔曼期望备份（Bellman expectation backup），通过上一时刻的值 $V_{i-1}(s')$ 来更新当前时刻的值 $V_i(s)$ ，即

将其不停迭代，最后可以收敛。

蒙特卡洛方法通过一个回合的经验平均回报（实际得到的奖励）来进行更新，即 \[ V(s_t) \leftarrow V(s_{t})+\alpha(G_t-V(s_{t})) \] 如图 3.13 所示，我们使用蒙特卡洛方法得到的轨迹对应树上蓝色的轨迹，轨迹上的状态已经是决定的，采取的动作也是已经决定的。

我们现在只更新这条轨迹上的所有状态，与这条轨迹没有关系的状态都不进行更新。

蒙特卡洛方法适用于环境未知的情况，而动态规划只适合有模型的方法。
蒙特卡洛方法只需要更新一条轨迹的状态，而动态规划方法需要更新所有的状态。状态数量很多的时候（比如100万个、200万个），我们使用动态规划方法进行迭代，速度是非常慢的。这也是基于采样的蒙特卡洛方法相对于动态规划方法的优势。

3.2 时序差分

时序差分是介于蒙特卡洛和动态规划之间的方法，它是免模型的，不需要马尔可夫决策过程的转移矩阵和奖励函数。

此外，时序差分方法可以从不完整的回合中学习，并且结合了自举的思想。

接下来，我们对时序差分方法进行总结。

时序差分方法的目的是对于某个给定的策略 π，在线（online）地算出它的价值函数 $V_\pi$ ，即一步一步地（step-by-step）算。

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

估计回报 $r_{t+1}+\gamma V(s_{t+1})$) 被称为时序差分目标（TD target），时序差分目标是带衰减的未来奖励的总和。

时序差分目标由两部分组成：

我们走了某一步后得到的实际奖励 $r_{t+1}$
我们利用了之前的估计 $V(s_{t+1})$ ，并且加了折扣因子，即 $\gamma V(s_{t+1})$

时序差分误差（TD error）: \[ \delta = r_{t+1}+\gamma V(s_{t+1})-V(s_t) \]

我们对比一下蒙特卡洛方法和时序差分方法。

在蒙特卡洛方法里面, $G_t$ 是实际得到的值（可以看成目标），因为它已经把一条轨迹跑完了，可以算出每个状态实际的回报。

时序差分不等轨迹结束，往前走一步，就可以更新价值函数。

时序差分方法可以在线学习（online learning），每走一步就可以更新，效率高。蒙特卡洛方法必须等游戏结束时才可以学习。

时序差分方法可以从不完整序列上进行学习。蒙特卡洛方法只能从完整的序列上进行学习。

时序差分方法可以在连续的环境下（没有终止）进行学习。蒙特卡洛方法只能在有终止的情况下学习。

时序差分方法利用了马尔可夫性质，在马尔可夫环境下有更高的学习效率。蒙特卡洛方法没有假设环境具有马尔可夫性质，利用采样的价值来估计某个状态的价值，在不是马尔可夫的环境下更加有效。

如图 3.18 所示，我们可以把时序差分方法进行进一步的推广。之前是只往前走一步，即TD(0)。

我们可以调整步数（step），变成 n步时序差分（n-step TD）。比如 TD(2)，即往前走两步，利用两步得到的回报，使用自举来更新状态的价值。

n步，指的是执行了n次动作a。

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

n步时序差分可写为

如果T是终点，那么V(T)一般是0。带入公式中也符合。

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

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

动态规划方法没有使用采样，它是直接用贝尔曼期望方程来更新状态价值的。

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

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

4. 免模型控制

4.1 广义策略迭代（generalized policy iteration，GPI）

在我们不知道马尔可夫决策过程模型的情况下，如何优化价值函数，得到最佳的策略呢？

我们可以把策略迭代进行广义的推广，使它能够兼容蒙特卡洛和时序差分的方法，即带有蒙特卡洛方法和时序差分方法的广义策略迭代（generalized policy iteration，GPI）。

策略迭代由两个步骤组成:

我们根据给定的当前策略 π 来估计价值函数。
得到估计的价值函数后，我们通过贪心的方法来改进策略。

这里有一个问题：当我们不知道奖励函数和状态转移时，如何进行策略的优化？

我们对策略评估部分进行修改，使用蒙特卡洛的方法代替动态规划的方法估计 Q 函数。

我们首先进行策略评估，使用蒙特卡洛方法来估计策略 $Q=Q_\pi$ ，然后进行策略更新，即得到 Q 函数后，我们就可以通过贪心的方法去改进它：

图 3.25 所示为蒙特卡洛方法估计 Q 函数的算法。

为了确保蒙特卡洛方法能够有足够的探索，我们使用了 ε-贪心（ε-greedyε-greedy）探索。

ε-贪心是指我们有ε的概率随机决定动作，通常 ε 就设一个很小的值， 1−ε 可能是 0.9，也就是 0.9 的概率会按照Q函数来决定动作，但是我们有 0.1 的概率是随机的。

通常在实现上，ε 的值会随着时间递减。在最开始的时候，因为我们还不知道哪个动作是比较好的，所以会花比较多的时间探索。接下来随着训练的次数越来越多，我们已经比较确定哪一个动作是比较好的，就会减少探索，把 ε 的值变小。主要根据 Q函数来决定动作，比较少随机决定动作，这就是 ε-贪心。

基于 ε-贪心探索的蒙特卡洛方法如图 3.26 所示。

与蒙特卡洛方法相比，时序差分方法有如下几个优势：低方差，能够在线学习，能够从不完整的序列中学习。所以我们可以把时序差分方法也放到控制循环（control loop）里面去估计Q表格，再采取 ε-贪心探索改进。这样就可以在回合没结束的时候更新已经采集到的状态价值

偏差（bias）：描述的是预测值（估计值）的期望与真实值之间的差距。偏差越高，越偏离真实数据，如图 3.27 第2行所示。

方差（variance）：描述的是预测值的变化范围、离散程度，也就是离其期望值的距离。方差越高，数据的分布越分散，如图 3.27 右列所示。

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

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

Sarsa 所做出的改变很简单，它将原本时序差分方法更新 V 的过程，变成了更新 Q，即

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

为了理解式(3.4)，如图 3.28 所示，我们先把 $r_{t+1}+\gamma Q(s_{t+1},a_{t+1})$ 当作目标值，即 $Q(s_{t},a_{t})$ 想要逼近的目标值。

(这里 $R_{t+1}$ 指的是在 $s_t$ 执行了动作 $a_t$ 后获得的奖励，一般我使用 $R_t$ 表示)

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

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

Sarsa 属于单步更新算法，每执行一个动作，就会更新一次价值和策略。

我们考虑 n 步的回报（n=1,2,⋯ ,∞），如式(3.5)所示。

如果不进行单步更新，而是采取 n 步更新或者回合更新，即在执行 n 步之后再更新价值和策略，这样我们就得到了 n 步 Sarsa（n-step Sarsa）。

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

4.3 特殊的回报(return)： TD(λ)/λ-return

sarsa 的 $Q^n_t$ 指的是在同一策略控制下获取的 action，构造起来的 $(s_1,a_1,r_1),(s_2,a_2,r_2),...,(s_n,a_n,r_n)$ 链的n步回报（return）

如果给 $Q^n_t$ 加上衰减参数（decay-rate parameter for eligibility traces）λ 并进行求和，即可得到 Sarsa(λ) 的 Q 回报 \[ Q^{\lambda}_t=(1-\lambda)\sum^{\infty}_{n=1}{\lambda^{n-1}Q^n_t} \]

λ-Return 做的事情是：把所有能用的 n-step 回报组合起来，对远期回报给更小的权重

为什么权重是 $(1-\lambda)\lambda^{n-1}$ 呢？

因为这是一个归一化因子，几何级数的和为：

他的权重和为1，即如果参数全部为1，其加权和为1。

同时 $\lambda^{n-1}$ 中，n实现了越远的回报权重越低的功能。

• λ 越小 → 趋向于使用短期的 1-step 回报（接近普通 Sarsa）；

• λ 越大 → 趋向于使用长期的多步回报（接近蒙特卡洛）。

首先我们来理解 $Q^{\lambda}_t=(1-\lambda)\sum^{\infty}_{n=1}{\lambda^{n-1}Q^n_t}$ 的计算，以3时间步举例，得到计算如下

其中

现在我们再来解释

• λ 越小 → 趋向于使用短期的 1-step 回报（接近普通 Sarsa）

首先我们得了解λ = 0时的计算，如下

因此λ = 0时等于 Sarsa.

当 λ = 0.5 或 λ = 0.9 时， $(1-\lambda)\lambda^{n-1}$ 的计算结果如下

我们能发现前n步的权重占比变大了。λ越接近1，每第n项的权重也越来越接近1

因此

• λ 越大 → 趋向于使用长期的多步回报（接近蒙特卡洛）

但我们知道我们有 (1−λ) 的限制在，因此只能无限接近1，也就是无限接近蒙特卡洛（因为n=2开始的每项权重不可能为1）

最后在来谈其意义：不再对某一单一步过分依赖，避免高方差的整回合估计，也能利用更多真实奖励信息，减少偏差。

4.4 资格迹

我们在如下 λ-Return 的计算公式中能发现，每一个 $Q^{\lambda}_t$ 都需要等待所有的 $Q^n_t$ 的结果出来后才能够计算。因此，这个定义下的λ-Return也被称为： 前向视角下的λ-Return 或 离线 TD(λ)（因为必须等完整 episode 结束） \[ Q^{\lambda}_t=(1-\lambda)\sum^{\infty}_{n=1}{\lambda^{n-1}Q^n_t} \] 资格迹是实现 TD(λ)/λ-return 的一种在线机制。在 TD(λ) 的 forward view（前向视角）中，λ-return 原本需要未来信息。

通过引入资格迹。我们能够从 backward view（后向视角）进行实现。

资格迹是一个总的概念，其有累计迹 / 替换迹两种具体实现方式。

4.4.1 公共计算内容

首先我们回顾之前说的TD误差： \[ \delta_t = r_{t+1}+\gamma V(s_{t+1})-V(s_t) \] 举个例子，存在以下轨迹

计算每个步骤中的TD误差 \[ \begin{align*} δ_0 = r_1 + γQ(s_1,a_1) - Q(s_0,a_0)\\ δ_1 = r_2 + γQ(s_2,a_2) - Q(s_1,a_1)\\ δ_2 = r_3 + γQ(s_3,a_3) - Q(s_2,a_2)\\ δ_3 = r_4 + γQ(s_4,a_4) - Q(s_3,a_3) \end{align*} \] 那么我们在 $t=0$ 时刻，在状态 $s_0$ 处能得到如下的公式 \[ Q_{s_0}^λ - Q(s_0,a_0)= (γλ)^0δ_0 + (γλ)^1δ_1 + (γλ)^2δ_2 + (γλ)^3δ_3 + ... \] 与之前sarsa中更新Q值公式图对比，我们能发现 $Q_{s_0}^λ - Q(s_0,a_0)$ 其实就是下面的软更新部分（软更新部分其实就是与原来Q(s_0,a_0)之间的偏差，后面用$\Delta Q(s,a)$ 表示）。（$Q_{s_0}^λ$ 是目标值，而 $Q(s_0,a_0)$ 是当前值）

4.4.2 累计迹

在累计迹中，我们有如下定义

累计迹： \[ E(s,a) \leftarrow \gamma\lambda E(s,a) +1_{st=s,at=a} \]

TD误差： \[ \delta_t = r_{t+1}+\gamma V(s_{t+1})-V(s_t) \] 在Q表中： \[ \delta_t = r_{t+1}+\gamma Q(s_{t+1},a_{t+1})-Q(s_t,a_t) \]

计算公式 \[ \Delta Q(s,a) = \alpha \sum^{T-1}_{t=0}{\delta_tE_t(s,a)} \]

实际算法中的更新公式： \[ Q(s,a) \leftarrow Q(s,a)+\alpha \delta_tE_t(s,a) \] 这个是什么意思呢

还是以之前的轨迹链举例

每一组（s,a）都维持了一个E(s,a)。以 $E(s_0,a_0)$ 举例。（初始 $E(s_0,a_0)$ 为0）

当t=0时，我们执行 $(s_0,a_0)$ , 状态动作与 $E(s_0,a_0)$ 一致，因此 $E(s_0,a_0) = \gamma\lambda*0+1 =1$

t=1时，我们执行 $(s_1,a_1)$ ,状态动作与 $E(s_0,a_0)$ 不一致，因此 $E(s_0,a_0) = \gamma\lambda*1 =\gamma\lambda$ 。

同理，

t=2时， $E(s_0,a_0) = \gamma\lambda*\gamma\lambda =（\gamma\lambda)^2$

t=3时， $E(s_0,a_0) = \gamma\lambda*（\gamma\lambda)^2 =（\gamma\lambda)^3$

我们假设，在执行完 $(s_3,a_3)$ 后，我们再次到达了状态 $s_0$ ，然后我们再次执行了动作 $a_0$ ，那么我们此时的 $E(s_0,a_0)$ 变成如下

\[ E(s_0,a_0)=\gamma\lambda*（\gamma\lambda)^3+1 =（\gamma\lambda)^4+1 \] 我们不断操作此过程，然后将得到的各个时刻t阶段的 $E(s_0,a_0)$ 带入如下公式中 \[ \Delta Q(s,a) = \alpha \sum^{T-1}_{t=0}{\delta_tE_t(s,a)} \] 展开来看其实就是我们之前写的 \[ Q_{s_0}^λ - Q(s_0,a_0)=\Delta Q(s,a) = (γλ)^0δ_0 + (γλ)^1δ_1 + (γλ)^2δ_2 + (γλ)^3δ_3 + ... \] 但在实际应用中我们不可能等全部计算出来再求 $\Delta Q(s,a)$ ，因此我们每执行一步，就更新一次 $\Delta Q(s,a)$ ，即 \[ Q(s,a) \leftarrow Q(s,a)+\alpha \delta_tE_t(s,a) \]

更新

我想了个例子来说明累计迹的来由

第一步：$s_1$ 执行 $a_1$ ，到达 $s_2$，同策略下获得下一动作 $a_2$ 。根据公式 $\delta_t = r_{t+1}+\gamma Q(s_{t+1},a_{t+1})-Q(s_t,a_t)$ 得到 $\delta_1$ 。此时

$(E_1=1,E_2=0,E_3=0)$

$Q(s_1,a_1)=\alpha*\delta_1*1$

第二步：$s_2$ 执行 $a_2$ ，到达 $s_1$，同策略下获得下一动作 $a_1$ ，根据公式获得 $\delta_2$ 。此时

$(E_1=\gamma\lambda,E_2=1,E_3=0)$ ，

$Q(s_1,a_1)=[_1*1] + [_2*] $

第三步：$s_1$ 执行 $a_1$ ，到达 $s_3$，同策略下获得下一动作 $a_3$ ，根据公式获得 $\delta_3$ 。此时

$(E_1=(\gamma\lambda)^2,E_2=\gamma\lambda,E_3=1)$ ，

$Q(s_1,a_1)=[\alpha*\delta_1*1] + [\alpha*\delta_2*\gamma\lambda] +[\alpha*\delta_3*(\gamma\lambda)^2+\alpha*\delta_3*1]$

我们很明显看到第三步从重复的 $(s_1,a_1)$ 处更新的时候，我们的公式为 \[ \alpha*\delta_3*(\gamma\lambda)^2+\alpha*\delta_3*1=\alpha*\delta_3*[(\gamma\lambda)^2+1] \] 其中 $(\gamma\lambda)^2+1$ 就是我们因为重复而产生的权重，也就是我们的累计迹。

4.4.3 替换迹

在累计迹中，每次遇到相同的 $(s_0,a_0)$ 我们就会在 $E(s_0,a_0)$ 中 $+1$ ，而在替换迹中，我们直接将其变为1，即 \[ E(s,a) \leftarrow max(\gamma\lambda E(s,a) ,1_{st=s,at=a}) \]

虽然只是一个简单的改动，但是我们在工程中往往使用的是替换迹而不是累计迹，因为实际训练中它的效果更好。

累计迹的问题：累计迹会把同一个状态的访问次数不断叠加，访问越多，权重越大。这样容易导致某些状态被“过度更新”，尤其在有循环路径时，数值会变大，训练不稳定甚至震荡。

替换迹的改进：替换迹不会累加，而是每次访问直接把权重设为 1，相当于“只记最近一次”。这样每个状态的影响都有上限，避免重复放大。

虽然替换迹不严格等价前向视角（会有一点偏差），但它大幅降低了方差，让训练更稳定。在实际（尤其是函数逼近、神经网络）中，这种稳定性比严格等价更重要。

当然，资格迹除了以上两种，也有的形式：

如果是相同的(s,a)，我们用累计迹的方式进行加和。同时，同状态s下其他的动作a对应的E(s,a),我们对其清零。其他不同的状态s下的E(s,a)则是正常计算。这种改变是由实验结果得出来的，即经过大量实验后发现这种变化能更加快速的收敛。

来源《Reinforcement Learning, Second Edition : An Introduction》（1998）

4.5 累计迹与 λ-return的等式证明

（最初是纸上写的，太多式子，因此直接贴图了）

即证明以下等式两边成立： \[ Q_{s_0}^λ - Q(s_0,a_0)=\Delta Q(s,a) = (γλ)^0δ_0 + (γλ)^1δ_1 + (γλ)^2δ_2 + (γλ)^3δ_3 + ... \] 首先我们定义存在轨迹

接下来将理论公式展开

其中，其中后面的添加项为

将该添加项提取出来，整合成如下

这里我们先着重关注 $Q^n-Q(s_0,a_0)$ 的计算（下面的V其实是 $\gamma$ ，跟奖励r太像了，因此直接写成了V）

最终我们原本的公式变成

接下来我们需要将双层嵌套循环进行转换，我们将k放在外层，n放在内层

我们再计算内层公式

最终我们原本的公式变成如下

完整计算如图

4.6 累计迹的意义

在理解公式后，我们需要再理解 $(γλ)^0δ_0$ 是什么，或者说 $\sum^{\infty}_{k=0}(\lambda^k\gamma^k\delta_k)$ 意味着什么。

举例我们需要计算 $s_0$ 所在位置的软更新时：$Q_0^λ - Q(s_0,a_0)$

我们发现 $δ_0$ 在所有步骤中都涉及到。

我们如果套入原本如下的公式中

对于 $δ_0$ ，我们能得到

对于 $δ_1$，我们能发现仅从第二步开始才参与 $Q_0^λ - Q(s_0,a_0)$ 的更新

再次套入公式中我们能得到

同理我们可以得到其他的 $\delta$

那么我们可以简单总结，$\delta$ 表示参与 $Q_0^λ - Q(s_0,a_0)$ 更新计算的误差值，而 $\lambda\gamma$ 则是表示 $\delta$ 在更新计算中的占比多少或者说占 $Q_0^λ - Q(s_0,a_0)$ 计算中的权重多少。

$δ_0$ 由于全程参与，因此该权重为1，而 $δ_1$ 通过计算得出其权重占比为 $\lambda\gamma$ ，同理 $δ_2$ 的权重为 $(\lambda\gamma)^2$ 。

4.7 λ-return 在有限步下的变化

接下来我们讨论有限步骤的情况。

我们之前讨论的理论公式中可以看出，n是趋于无穷大的。这是因为我们要符合将所有权重相加为1的条件。 \[ Q^{\lambda}_t=(1-\lambda)\sum^{\infty}_{n=1}{\lambda^{n-1}Q^n_t} \] 这里的权重是一个归一化因子，几何级数的和为：

在有限步骤中，最后一项的参数中去除了1-λ

举例3步到达终点的情况。 $s_1 \rightarrow s_2 \rightarrow s_3 \rightarrow s_T$。其计算公式如下

在前向视角（forward view）下，是以不同步长的 return（如 $G_1,G_2,...,G_n$ ）为单位进行加权求和，本质上是在对不同时间尺度的回报进行加权。

这些权重为： \[ (1−λ),(1−λ)λ,(1−λ)λ^2,… \] 在无限步的理想情况下，这些权重之和为 1，因此可以看作是一个完整的加权平均。

但在有限轨迹（episode 会终止）的情况下，假设最多只能到第 m 步，那么后续更长步长的 return 不再存在。此时，原本分配给更远未来的权重（即 $(1-\lambda)\lambda^m$ 及之后的部分）不会消失，而是自然合并到最后一个可计算的 return $G^{(m)}$ 上。

因此，最后一项的权重变为： \[ λ^{m−1} \] 而不再带有 $1−λ$，从而保证所有权重之和仍然为 1。

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

Sarsa 是一种同策略（on-policy）算法，它优化的是它实际执行的策略，它直接用下一步会执行的动作去优化 Q 表格。

同策略在学习的过程中，只存在一种策略，它用一种策略去做动作的选取，也用一种策略去做优化。所以 Sarsa 知道它下一步的动作有可能会跑到悬崖那边去，它就会在优化自己的策略的时候，尽可能离悬崖远一点。这样子就会保证，它下一步哪怕是有随机动作，它也还是在安全区域内

Q学习是一种异策略（off-policy）算法。

异策略在学习的过程中，有两种不同的策略：目标策略（target policy）和行为策略（behavior policy）。

目标策略是我们需要去学习的策略，一般用 π 来表示。目标策略就像是在后方指挥战术的一个军师，它可以根据自己的经验来学习最优的策略，不需要去和环境交互。
行为策略是探索环境的策略，一般用 μ 来表示。行为策略可以大胆地去探索到所有可能的轨迹，采集轨迹，采集数据，然后把采集到的数据“喂”给目标策略学习。而且“喂”给目标策略的数据中并不需要 $a_{t+1}$ ，而 Sarsa 是要有 $a_{t+1}$ 的。

行为策略像是一个战士，可以在环境里面探索所有的动作、轨迹和经验，然后把这些经验交给目标策略去学习。比如目标策略优化的时候，Q学习不会管我们下一步去往哪里探索，它只选取奖励最大的策略。

我们在sarsa中，我们使用策略π获取了轨迹。在如下更新的公式中，我们的下一状态的动作 $a_{t+1}$ 是由策略π在状态 $s_{t+1}$ 产生的。因此sarsa被称为同策略。

而在Q学习中。我们还是先用策略π获取了轨迹。但我们更新公式改为如下，我们的下一状态的动作 $a_{t+1}$ 并不是由策略π在状态 $s_{t+1}$ 产生的，而是直接查询状态 $s_{t+1}$ 下能获得最大值的动作a。

在该例子中

行为策略：我们获取轨迹的策略π。
目标策略：直接查询状态 $s_{t+1}$ 下能获得最大值的动作a。与策略π无关。

因此Q学习被称为异策略。