TD Learning 时序差分学习

我们已经通过MC方法学到了Sampling的概念，学会了用on policy的方式来完成control任务。我们不再需要了解全部的场景信息（model-free），而是直接和环境进行交互，通过交互过程中采样到的数据来学习。

在on policy MC ES control中，我们在计算G的时候，完全按照实际采样进行计算。比方说，如果我们在迷宫中撞了两次墙，扣了2分，那么我们的总回报G中就会扣掉这两份。换句话说，实际经历什么，就用什么来更新Q表。在off policy MC中，我们使用Importance Sampling Ratio来为实际采样的G进行折扣。

本章我们将介绍TD learning的概念，并介绍两种非常经典的TD学习方法：

On policy的SARSA
Off policy的Q-learning

从MC到TD的推导

Bootstrapping

“用现在的 Q 估计去更新过去的 Q 估计”的行为在强化学习中叫自举（Bootstrapping）。

时序差分结合了蒙特卡洛和动态规划的思想：

不需要事先知道环境
根据贝尔曼方程的思想，利用后续状态的价值估计来更新当前状态的价值估计

我们回顾一下MC方法：使用真实的累积回报 \(G_t\)。它不相信任何人的预测，只相信最后的结果。

\[ V(S_t) \leftarrow V(S_t) + \alpha [ \underbrace{G_t}_{\text{目标值}} - V(S_t) ] \]

无论是on policy MC还是off policy MC，它们的更新逻辑都遵照上述增量更新公式。这里要注意，目标值我们记为\(G_t\) (Return): 从时间步 \(t\) 开始，一直到游戏结束的 真实累积奖励 （即 \(R_{t+1} + \gamma R_{t+2} + \dots\)）。

在MC方法中，我们直接使用实际采样的值对V或Q表进行更新。而在TD中，我们使用下一步的奖励 + 对未来的估计值 。它相信“预测可以修正预测”。简单来说：

MC使用实际发生的数据
TD使用估计的数据

比方说，在grid world中：

start = (0, 0)
goal = (2, 2)

reward = [
    [-1, -1, -1],
    [-1, -1, -1],
    [-1, -1, 10]
]

actions = {
    'up':    (-1,  0),  # dr, dc
    'down':  (1,  0),
    'right': (0,  1),
    'left':  (0, -1)
}

假设 Agent 刚完成了一次移动：从 \((0,0)\) 移动到了 \((0,1)\)。

\(S_t\) (cur_state) : 刚才所在的格子，即 \((0,0)\)。
\(A_t\) (cur_action) : 刚才做出的决定，即 'right'。
\(R_{t+1}\) (reward) : 刚才这一步拿到的奖励，即 \(-1\)。
\(S_{t+1}\) (next_state) : 现在落脚的格子，即 \((0,1)\)。
\(A_{t+1}\) (next_action) : 接下来准备在 \((0,1)\) 做的动作（注意：在 Q-learning 中，我们通常直接取 \((0,1)\) 里 \(Q\) 值最大的那个动作）。

在 TD 中，Agent 迈出一步到达 next_state 后，会立刻回头评价“刚才那一发出的好不好”。

当前事实 (\(R_{t+1}\)) : \(-1\) (实打实拿到的钱)。
手中情报 (\(Q(S_{t+1}, A_{t+1})\)) : \(-5\) (这是你对 next_state 未来的估计)。
得出的新结论 (TD Target) : \(Target = -1 + (-5) = -6\)。

Agent 认为：既然在 \((0,0)\) 往右走能拿到 \(-1\)，且到达的 \((0,1)\) 以后还能值 \(-5\)，那么“在 \((0,0)\) 往右走”这整件事，现在看来就值 \(-6\) 分。

我们要更新的是 \(Q(S_t, A_t)\) ，即刚才那个格子的动作价值：

\[ Q(S_t, A_t) \leftarrow Q(S_t, A_t) + \alpha [ \underbrace{(R_{t+1} + \gamma Q(S_{t+1}, A_{t+1}))}_{\text{TD Target (新结论)}} - \underbrace{Q(S_t, A_t)}_{\text{旧偏见}} ] \]

带入上面的例子：

\[ Q(0,0, \text{'right'}) \leftarrow 0 + \alpha [ \underbrace{(-1 + (-5))}_{-6} - 0 ] \]

我们要注意：

评估时机： 必须 迈出这一步之后 ，站在 next_state \((0,1)\) 处回头评估。
评估对象： 评估的是 cur_state \((0,0)\) 和 cur_action 'right' 。因为只有走完了，你才知道这一步给多少钱，以及把你带到了哪个新地方。

我们整理一下思路，假设我们从a走到b：

我们用b的实际reward
结合b现有的q值
更新a的q值

即：

\[ Q(a, \text{action}) \leftarrow Q(a, \text{action}) + \alpha [ \underbrace{(R_b + \gamma Q(b, \text{next\_action}))}_{\text{由 } b \text{ 带来的新证据}} - Q(a, \text{action}) ] \]

这就是“引导”（Bootstrapping）：没有等到整局游戏结束，而是用 \(b\) 这个格子的“现有评价”来给 \(a\) 这个格子“背书”。

这里的Q(b, next_action)有点让人晕。这种晕来自于V表和Q表的不同：

\(V\) 表 ：每个格子（状态）只有一个数字。比如 \(V(b) = -5\)。
\(Q\) 表 ：每个格子（状态）里包含 4 个动作的分数 （上下左右）。

当你想要“结合 \(b\) 现有的 \(Q\) 值”来更新 \(a\) 时，你会发现你手里没法直接拿出一个数字，因为 \(b\) 有四个分数 ！这时候你必须做一个决定： 我到底拿 \(b\) 里的哪一个动作的分数，来代表 \(b\) 的身价呢？

这里的 next_action 其实就是你在 \(b\) 的抽屉里 挑选出来的那个“代表” 。后面我们会知道，根据挑选代表不同的方式，我们会走向两种不同的方向：

把b中Q值最大的那一步拿出来，即假设以后会走最聪明的那一步。这里无论下一步怎么走，总是选择那个看起来最好的，这就是off policy Q-learning。（因为epsilon-greedy的缘故，下一步不一定选择最优Q值作为行动）
看实际上下一步打算在b做什么，如果下一步准备在b选择往右走，那么我们就在这里选择往右走来作为next_action；这里用的是实际执行的动作，这就是on policy SARSA

折扣因子

在许多强化学习任务中，并没有一个明确的终点（例如让机器人永远在工厂巡逻）。

如果不打折 (\(\gamma = 1\)) ：如果任务永远持续下去，累积的回报 \(G_t\) 就会变成无穷大。
如果打折 (\(0 \le \gamma < 1\)) ：数学上可以保证这一串无穷相加的数字最终会收敛到一个有限的常数。这让计算机能算得动，算法也能稳定下来。

假设你还是那个在 Grid World 里的机器人，现在有两个选择：

选项 A ：现在立刻给你 10 分。
选项 B ：1000 步之后给你 10 分。

你肯定选 A。为什么？因为在到达那 1000 步之前，可能会发生很多意外：程序可能崩溃、可能断电、或者环境可能发生变化。 越遥远的奖励，其实现的可能性就越低 。\(\gamma\) 就像是一个“信任度系数”，每往后推一步，我们就对那个奖励的信任度打一个折扣。

在你的 Grid World 中，每走一步都要扣 1 分。

如果你设置 \(\gamma = 0\) ：机器人会变得极其短视，它只在乎下一格能拿多少钱，完全不看长远。
如果你设置 \(\gamma = 1\) ：机器人会觉得“现在的 -1 分”和“100 步后的 -1 分”一模一样，它可能会在迷宫里漫无目的地闲逛，因为它不觉得浪费时间是一种损失。

引入 \(\gamma < 1\) 的意义在于 ：它迫使 Agent 意识到， 早一点拿到奖励比晚一点拿到要好 。这会自动引导 Agent 去寻找路径最短的最优解。

贝尔曼方程

贝尔曼方程如下：

\[ V = \mathbb{E}[R + \gamma V'] \]

上式是理论完美形态，也是强化学习的灵魂。它用一种“套娃”式的递归逻辑，把复杂的未来简化成了简单的“今天+明天”：

\[ \underbrace{V}_{\substack{\text{当前的价值} \\ \text{(今天的账面价值)}}} = \underbrace{\mathbb{E}}_{\substack{\text{求平均} \\ \text{(考虑所有可能性)}}} [ \underbrace{R}_{\substack{\text{即时奖励} \\ \text{(今天到手的钱)}}} + \underbrace{\gamma}_{\substack{\text{折扣率} \\ \text{(未来的钱要打折)}}} \underbrace{V'}_{\substack{\text{下一个状态的价值} \\ \text{(明天的预期收益)}}} ] \]

这个方程描述的是一种“理想的平衡状态”：

如果你的认知是完美的，那么你现在所处位置的“总价值”（\(V\)），应该正好等于你迈出这一步拿到的“真金白银”（\(R\)），加上你对落脚点未来价值的“折现估计”（\(\gamma V'\)）。
在学习初期，你的 \(V\) 是瞎猜的，等号两边肯定不相等。算法的目标就是不断调整 \(V\)，直到等号成立。
它说明了价值函数在时间上是自相贯通的——今天的价值是由明天决定的，明天的价值是由后天决定的，以此类推。

其中的每个元素都有很深刻的含义：

\(V\) (Current Value)： 你对当前状态 \(s\) 的评价。比如：站在终点前一步，这个 \(V\) 应该很高。
\(\mathbb{E}\) (Expectation)： 现实中你走一步可能去往不同的地方（环境有随机性），所以我们要算一个平均值。
\(R\) (Immediate Reward)： 这一步给你的甜头或惩罚。它是这个方程里唯一的“真实物质”，其他的 \(V\) 都是估计出来的。
\(\gamma\) (Discount Factor)： 如果 \(\gamma = 0.9\)，意味着明天的 100 块钱在今天只值 90 块。它强迫智能体不要光想远期目标，也要顾及眼下。
\(V'\) (Next Value)： 这是最精妙的地方。我们不用算后面一辈子的账，直接查一下“落脚点”的价值表就行了。

我们可以记住贝尔曼方程的精髓思想：

现在的评估 = 现在的收获 + 未来的评估

在强化学习中，我们的目标是学习一个 状态价值函数 \(V_\pi(s)\)* ，它代表了在状态 *\(s\) 下，遵循策略 \(\pi\) 所能获得的未来累计奖励的期望，即：

\[ 状态s的价值 = 从该状态开始往后所有收益的平均值（期望） \]

在下式中，\(G_t\)是MC方法中实际到手的奖励总和，我们在编程中用一个track变量去追踪，然后episode结束后再计算\(G\)：

\[ V_\pi(s) = \mathbb{E}_\pi[G_t | S_t = s] \]

式子中每个符号的含义如下：

\[ \underbrace{V_{\pi}(s)}_{\substack{\text{在策略 } \pi \text{ 下} \\ \text{状态 } s \text{ 的价值}}} = \underbrace{\mathbb{E}_{\pi}}_{\substack{\text{基于策略 } \pi \\ \text{计算期望（平均值）}}} [ \underbrace{G_t}_{\substack{\text{从此刻起一直到} \\ \text{结束的累计收益}}} | \underbrace{S_t = s}_{\substack{\text{给定前提：} \\ \text{现在处于状态 } s \text{}}} ] \]

展开累计收益 \(G_t\)。这里我们加上折扣因子\(\gamma^k\)，这是为了让离现在更近的奖励获得更大的权重，换言之：“明天的钱没有今天的钱值钱”：

\[ V_\pi(s) = \mathbb{E}_\pi[\sum_{k=0}^{\infty} \gamma^k R_{t+k} | S_t = s] \]

提取即时奖励：（把\(G_t\)拆为当下奖励和未来奖励两项）

\[ V_\pi(s) = \mathbb{E}_\pi[R_t + \gamma \sum_{k=0}^{\infty} \gamma^k R_{t+k+1} | S_t = s] \]

观察上式右边的部分：

\[ \sum_{k=0}^{\infty} \gamma^k R_{t+k+1} = R_{t+1} + \gamma R_{t+2} + \gamma^2 R_{t+3} + \dots \]

这串式子其实就是从 \(t+1\) 时刻（也就是下一个未来的时刻）开始算起的全部累计奖励。他其实就等于 \(G_{t+1}\) （\(t+1\) 时刻的收益）。因此，我们可以把提取即时奖励后的式子简写成：

\[ V_\pi(s) = \mathbb{E}_\pi [R_t + \gamma G_{t+1} | S_t = s] \]

我们在一开始已经知道：

\[ \mathbb{E}[G_{t+1}] = V_\pi(S_{t+1}) \]

所以我们就可以直接把式子写为：

\[ V_\pi(s) = \mathbb{E}_\pi[R_t + \gamma V_\pi(S_{t+1}) | S_t = s] \]

这本质上就是一个贝尔曼方程。

TD(0)方法

经过上面的推导，我们可以知道：

\[ V_\pi(s) = \mathbb{E}_\pi[G_t | S_t = s] \]

\[ = \mathbb{E}_\pi[R_t + \gamma V_\pi(S_{t+1}) | S_t = s] \]

蒙特卡罗方法将第一行作为更新的目标，而时序差分方法将第二行作为更新的目标。从数学原理我们也能看出两种算法的不同思路：MC追求的是最直接、最完整的期望结果，而TD则是基于贝尔曼方程的递归形式。

至此，我们应当理解“时序差分”的含义：

\[ \text{TD} = \underbrace{\text{Temporal}}_{\text{时刻 } t \text{ 到 } t+1 \text{}} + \underbrace{\text{Difference}}_{\text{目标值} - \text{当前值} \text{}} \]

Temporal 时序，指的是时间步的跨越，即算法关注两个不同的时间点：当前时刻\(t\)和下一时刻\(t+1\)。TD只需要走一步，就能进行计算。
Difference 差分，指的是计算误差，即算法的核心更新依据是TD Error，也即新估计（Target）和旧估计之间的差值：

\[ \underbrace{Q}_{\text{新值}} \leftarrow \underbrace{Q}_{\text{旧值}} + \underbrace{\alpha}_{\text{步长}} \times \underbrace{(Target - Q)}_{\text{差分（误差）}} \]

不同算法的切换，其实就在于差分的处理方法：

SARSA的差分来自于下一步的实际选择
Q-learning的差分来自于下一步的理论最优选择

我们可以发现，不同的差分处理方法在数学上来自于Target目标值的方法。换句话说，无论算法怎么变，TD(0)的核心底层逻辑都是这个公式：

\[ V(S_t) \leftarrow V(S_t) + \alpha [ \underbrace{R_{t+1} + \gamma V(S_{t+1})}_{\text{TD Target (目标值)}} - V(S_t) ] \]

我们需要区分TD Target和TD Error的区别：

TD Target (目标值): \(R_{t+1} + \gamma V(S_{t+1})\)。这是我们“新看到的真相”：走了一步拿到的钱，加上对剩下路程的估算。
TD Error (TD 误差): \(\delta_t = \text{Target} - V(S_t)\)。这代表了“现实”与“预期”之间的差距。

因此，不同的算法在数学处理上，其实就是Target的不同：

如果是MC，则Target是累积回报\(G_t = \sum_{k=0}^{\infty} \gamma^k R_{t+k+1}\)
如果是Q-learning，则\(Target = R_{t+1} + \gamma \max_a Q(S_{t+1}, a)\)
如果是SARSA，则\(Target = R_{t+1} + \gamma Q(S_{t+1}, A_{t+1})\)

SARSA

on policy SARSA

\[ Q(S_t, A_t) \leftarrow Q(S_t, A_t) + \alpha [ R_{t+1} + \gamma Q(S_{t+1}, A_{t+1}) - Q(S_t, A_t) ] \]

关键点： 这里的 \(A_{t+1}\) 是你根据当前策略实际选出的下一个动作。

Q-learning

off policy Q-learning

\[ Q(S_t, A_t) \leftarrow Q(S_t, A_t) + \alpha [ R_{t+1} + \gamma \max_a Q(S_{t+1}, a) - Q(S_t, A_t) ] \]

关键点： 它不管你实际走哪一步，它在更新时永远假设下一步会选 最好的那招 。