强化学习——时序差分算法

时序差分算法

之前介绍的马尔可夫决策过程和动态规划算法是已知的，即要求与智能体交互的环境是完全已知的（例如迷宫或者给定规则的网格世界）。DP要求我们知道环境的所有细节（即状态转移概率 P 和奖励函数 R），这被称为有模型（Model-Based）。然而在现实世界（如机器人控制、玩游戏、自动驾驶）中，我们通常不知道这些规则。我们需要通过与环境交互来学习，这就是无模型（Model-based）。

但这在大部分场景下并不现实，机器学习的主要方法都是在数据分布未知的情况下针对具体的数据点来对模型做出更新的。对于大部分强化学习现实场景（例如电子游戏或者一些复杂物理环境），其马尔可夫决策过程的状态转移概率是无法写出来的，也就无法直接进行动态规划。在这种情况下，智能体只能和环境进行交互，通过采样到的数据来学习，这类学习方法统称为无模型的强化学习（model-free reinforcement learning）。

时序差分算法（Temporal Difference, TD）是一种结合了蒙特卡洛和动态规划的强化学习算法。它通过估计当前状态的值函数来更新值函数，而不是等待到整个轨迹结束。TD算法的核心思想是，当前状态的值函数可以通过当前状态的奖励和下一个状态的值函数来估计。

算法介绍

时序差分是一种用来估计一个策略的价值函数的方法，它结合了蒙特卡洛和动态规划算法的思想。时序差分方法和蒙特卡洛的相似之处在于可以从样本数据中学习，不需要事先知道环境；和动态规划的相似之处在于根据贝尔曼方程的思想，利用后续状态的价值估计来更新当前状态的价值估计。回顾一下蒙特卡洛方法对价值函数的增量更新方式： $$ \begin{align*} V(S_t) \leftarrow V(S_t) + \alpha [G_t - V(S_t)] \end{align*} $$

这里我们将$\frac{1}{N(s)}$的替换成了α，表示对价值估计更新的步长。可以将取α为一个常数，此时更新方式不再像蒙特卡洛方法那样严格地取期望。蒙特卡洛方法必须要等整个序列结束之后才能计算得到这一次的回报G_t，而时序差分方法只需要当前步结束即可进行计算。具体来说，时序差分算法用当前获得的奖励加上下一个状态的价值估计来作为在当前状态会获得的回报，即： $$ \begin{align*} V(s_t) \leftarrow V(s_t) + \alpha [r_{t} + \gamma V(s_{t+1}) - V(s_t)] \end{align*} $$

其中，r_t是当前状态的奖励，γ是折扣因子，可以用r_t + γV(s_t + 1)来代替G_t的原因是:

$$ \begin{align*} V_\pi(s) &= \mathbb{E}_\pi[G_t|S_t=s]\\ &= \mathbb{E}_\pi[\sum_{k=0}^{\infty} \gamma^k r_{t+k+1}|S_t=s]\\ &= \mathbb{E}_\pi[R_{t} + \gamma V_\pi(S_{t+1})|S_t=s] \end{align*} $$

在这个公式中： - R_t + γV(S_t + 1)：称为 TD Target。这是我们根据刚才这一步的真实奖励 R_t 和对下一状态的预估 V(S_t + 1) 组成的“新的一手消息”。 - V(s_t)：是我们原来的估计。 - 方括号内的部分：称为 TD Error (误差)，即“新消息”和“旧估计”之间的差值。 - α：学习率（Learning Rate）。决定了我们多大程度上相信这一次的“新消息”。

因此蒙特卡洛方法将上式第一行作为更新的目标，而时序差分算法将上式最后一行作为更新的目标。于是，在用策略和环境交互时，每采样一步，我们就可以用时序差分算法来更新状态价值估计。时序差分算法用到了V(s_t + 1)的估计值，可以证明它最终收敛到策略π的价值函数.

▶

例子

假设在玩一个走格子的游戏。

1. 现状 (S_t)： 机器人站在A 格子。价值表上写着：V(A) = 10。
2. 行动： 机器人向右走了一步。
3. 反馈 (r_t)：这一步没掉陷阱也没吃到金币，环境给了个奖励 r_t = −1（每走一步消耗一点电量）。
4. 新状态 (S_t + 1)：机器人到达了B 格子。价值表上面写着 V(B) = 12。
5. 计算 TD Target：Target = r_t + γV(B) = −1 + 1.0 × 12 = 11(假设γ = 1)
6. 发现误差 (TD Error)：之前觉得 A 值 10，但根据刚刚这一步的体验，A好像应该值 11。Error = 11 − 10 = 1这说明之前低估了 A的价值。
7. 更新 (V(S_t))：不会直接把10 改成 11（因为只有一次样本，可能不准），而是稍微往 11挪一点点。假设学习率 α = 0.1：V(A)_new = 10 + 0.1 × (11 − 10) = 10.1现在，把价值表上的V(A) 更新为10.1。

收敛性的证明

由于V(S_t + 1) 本身可能就是个错误的瞎猜（初始化甚至是随机的），用一个错误的数字去更新 V(S_t)，难道不会导致误差越来越大吗？

TD 能够收敛，主要基于以下三个核心原因：

A. 真实奖励 (r_t) 的“锚定”作用这是最关键的一点。在 r_t + γV(S_t + 1) 中，r_t 是真实的、来自环境的客观反馈。哪怕 V(S_t + 1) 全是错的，只要 r_t 是真的，更新公式里就包含了一部分“真理”。在终点状态（Terminal State），V 是确定的（通常是0）。当智能体到达终点前一步时，它收到了真实的终局奖励，这一步的 V 就被修正准确了。这种“准确性”会随着时间，像波浪一样反向传播（Back-propagate）回起始点。

B. 贝尔曼算子的“压缩”性质 (Contraction Mapping)，从数学原理上讲，TD 的更新是在尝试逼近贝尔曼方程的解。贝尔曼算子有一个特性：压缩性。只要折扣因子 γ < 1，或者在有限步数的任务中，每一次利用贝尔曼方程进行更新，不管你的初始值离真值有多远，新的估计值在数学期望上都会比旧的更接近真值一点点。就像把一张纸揉成团，纸上两点的距离总是在变小，最终会收敛到一个不动点。

C. 误差的互相抵消，虽然单次更新有偏差，但在大量采样的情况下：如果 V(S_t + 1) 估计偏高了，下次可能估计偏低了。只要步长 α 足够小（并且随时间逐渐减小，满足 Robbins-Monro 条件），随机噪声就会被平均掉，留下的就是趋向于真实价值的趋势。一句话总结收敛性：就像一群人排队传话猜谜，虽然中间的人都在瞎猜，但排尾的人（终点）手里拿着谜底（真实奖励）。每一轮传话，排尾的人都会把真相告诉前一个人一点点。随着传话次数无限增多，整条队伍最终都能知道准确的谜底。

▶

Robbins-Monro 条件

Robbins-Monro 条件（Robbins-MonroConditions）是随机逼近理论中的一个数学准则。在强化学习中，它主要用来回答一个关于“学习率”（步长α）的关键问题：“为了保证算法最终能收敛到正确答案，步长α应该如何设置？”.简单来说，这两个条件规定了：随着训练的进行，步长 α必须逐渐变小，但又不能变得太快。

数学定义假设 α_t 是第 t步时的学习率（步长）。Robbins-Monro 条件包含以下两个式子： -条件一：总步长必须是无限的,保证了无论初始猜测离真实值多远，我们都有能力走到那里。$$\sum_{t=1}^{\infty} \alpha_t =\infty$$ -条件二：步长的平方和必须是有限的,保证了步长减小的速度足够快，以便消除随机噪声的影响，最终停下来$$\sum_{t=1}^{\infty} \alpha_t^2 <\infty$$

Sarsa 算法

既然我们可以用时序差分方法来估计价值函数，那一个很自然的问题是，我们能否用类似策略迭代的方法来进行强化学习。策略评估已经可以通过时序差分算法实现，那么在不知道奖励函数和状态转移函数的情况下该怎么进行策略提升呢？答案是时可以直接用时序差分算法来估计动作价值函数Q： $$ \begin{align*} Q(s_t, a_t) \leftarrow Q(s_t, a_t) + \alpha [r_{t} + \gamma Q(s_{t+1}, a_{t+1}) - Q(s_t, a_t)] \end{align*} $$ 然后我们用贪婪算法来选取在某个状态下动作价值最大的那个动作，即 max_{a ∈ 𝒜}Q(s, a) 。用贪婪算法根据动作价值选取动作来和环境交互，再根据得到的数据用时序差分算法更新动作价值估计。

然而这个简单的算法存在两个需要进一步考虑的问题。

• 第一，如果要用时序差分算法来准确地估计策略的状态价值函数，我们需要用极大量的样本来进行更新。但实际上我们可以忽略这一点，直接用一些样本来评估策略，然后就可以更新策略了。我们可以这么做的原因是策略提升可以在策略评估未完全进行的情况进行，这其实是广义策略迭代（generalized policy iteration）的思想。

• 第二，如果在策略提升中一直根据贪婪算法得到一个确定性策略，可能会导致某些状态动作对永远没有在序列中出现，以至于无法对其动作价值进行估计，进而无法保证策略提升后的策略比之前的好。简单常用的解决方案是不再一味使用贪婪算法，而是采用一个ϵ-贪婪策略：有的概率采用动作价值最大的那个动作，另外有的概率从动作空间中随机采取一个动作，其公式表示为：

$$ \begin{align*} \pi(a|s) = \begin{cases} 1 - \epsilon + \epsilon / |\mathcal{A}| & \text{if } a = \arg\max_{a' \in \mathcal{A}} Q(s, a') \\ \epsilon / |\mathcal{A}| & \text{otherwise} \end{cases} \end{align*} $$ 现在，我们就可以得到一个实际的基于时序差分方法的强化学习算法。这个算法被称为 Sarsa，因为它的动作价值更新用到了当前状态s_t、当前动作a_t、获得的奖励r_t、下一个状态s_t + 1和下一个动作a_t + 1，将这些符号拼接后就得到了算法名称。Sarsa 的具体算法如下：

▶

Sarsa 算法

初始化：建立一张 Q表（Q-Table），所有值设为 0。

开始回合：初始化状态 S。

选择动作：根据当前 Q 表，用ϵ-greedy 策略选出一个动作A。 循环直到回合结束：

• 执行：执行动作 A，观测到奖励 R 和新状态 S^′。
• 再次选择（关键）：在新的状态 S^′，立刻再次使用策略（如ϵ-greedy）选出下一步动作 A^′。
• 更新 Q 值： $$\begin{align*}Q(S, A) \leftarrow Q(S, A) + \alpha [R + \gamma Q(S', A') - Q(S, A)]\end{align*}$$
• 推进：把 S^′当作现在的 S，把 A^′ 当作现在的 A。(S ← S^′, A ← A^′)(注意：下一轮循环时，不需要再选动作了，因为A 已经是刚才选好的那个 A^′ 了)

多步Sarsa算法

蒙特卡洛方法利用当前状态之后每一步的奖励而不使用任何价值估计，时序差分算法只利用一步奖励和下一个状态的价值估计。那它们之间的区别是什么呢？总的来说，蒙特卡洛方法是无偏（unbiased）的，但是具有比较大的方差，因为每一步的状态转移都有不确定性，而每一步状态采取的动作所得到的不一样的奖励最终都会加起来，这会极大影响最终的价值估计；时序差分算法具有非常小的方差，因为只关注了一步状态转移，用到了一步的奖励，但是它是有偏的，因为用到了下一个状态的价值估计而不是其真实的价值。那有没有什么方法可以结合二者的优势呢？答案是多步时序差分！多步时序差分的意思是使用n步的奖励，然后使用之后状态的价值估计。用公式表示，将 $$ \begin{align*} G_t = r_t + \gamma Q(s_{t+1}, a_{t+1}) \end{align*} $$ 替换为 G_t = r_t + γr_t + 1 + γ²r_t + 2 + ⋯ + γⁿQ(s_t + n, a_t + n) 其中，r_t是当前状态的奖励，γ是折扣因子，Q(s_t + n, a_t + n)是第n步后的状态动作对的价值估计。多步时序差分算法可以结合二者的优势，既具有无偏性，又具有较小的方差。于是，相应存在一种多步 Sarsa 算法，它把 Sarsa 算法中的动作价值函数的更新公式 $$ \begin{align*} Q(s_t, a_t) \leftarrow Q(s_t, a_t) + \alpha [r_t + \gamma Q(s_{t+1}, a_{t+1}) - Q(s_t, a_t)] \end{align*} $$ 替换为 $$ \begin{align*} Q(s_t, a_t) \leftarrow Q(s_t, a_t) + \alpha [r_t + \gamma r_{t+1} + \gamma^2 r_{t+2} + \cdots + \gamma^n Q(s_{t+n}, a_{t+n}) - Q(s_t, a_t)] \end{align*} $$

Q-learning

Q-Learning 最大的特点是实现了 行为策略 (Behavior Policy) 和 目标策略 (Target Policy) 的分离。

• 你在做什么 (Behavior)：你可能正在用 ϵ-greedy 策略到处乱撞，试图探索世界。
• 你在学什么 (Target)：但在更新 Q 表时，你假设自己下一步绝对会选最好的那个动作，完全不管你下一秒实际上会不会乱撞。

这就是 Off-Policy：我实际走的路（有探索）和我学习的路（全最优）是不一样的。核心公式对比Sarsa (看现实): $$ \begin{align*} Q(s, a) \leftarrow Q(s, a) + \alpha [R + \gamma Q(s', a') - Q(s, a)] \end{align*} $$ 注意：这里的 a^′ 是你下一步真正要执行的那个动作。Q-Learning (看理想): $$ \begin{align*} Q(s, a) \leftarrow Q(s, a) + \alpha [R + \gamma \max_{a'} Q(s', a') - Q(s, a)] \end{align*} $$ 注意：这里没有 a^′。不管下一步要干嘛，我只看 s^′ 那个状态下，所有可能的动作里得分最高的那一个。这就像在说：“我虽然不知道下一步会怎么走，但我知道如果我走到了 s^′，我应该选哪个动作最好。”

▶

Q-Learning 算法

算法步骤：

初始化：建立 Q 表，全为 0。

开始回合：初始化状态 S。

循环直到回合结束：

• 第一步：选动作基于当前状态 S，用 ϵ-greedy 策略选出一个动作 A。
• 第二步：执行执行动作 A，观测到奖励 R 和新状态 S^′。
• 第三步：偷看一眼“完美未来”（关键差异）不管下一轮要怎么走，先看一眼Q 表中 S^′这一行。找到最大值：max_a^′Q(s^′, a^′)。用这个最大值作为S^′的价值估计。
• 第四步：更新 $$\begin{align*}Q(s, a) \leftarrow Q(s, a) + \alpha [R + \gamma \max_{a'} Q(s', a') -Q(s, a)]\end{align*}$$
• 第五步：状态跳转S ← S^′。(注意：这里不用像Sarsa 那样把 A’ 也传下去。下一轮开始时，会重新在第一步里选动作。)

一个具体的例子是悬崖漫步。机器人现在在悬崖边 (S)，动作 A 是“向右走”，结果到了 S^′（还是悬崖边，非常危险）。在 S^′，最优动作是“向上远离悬崖”（价值 10 分）。但是，因为有 ϵ 的概率探索，机器人实际上下一秒可能会“向左跳进悬崖”（价值 -100 分）。

• Sarsa 的思考方式：“我下一秒真的可能会跳崖（选到了 A^′= 跳崖）。既然下一步这么惨，那现在的 S 也不咋地。我要调低 Q(S, A)。” 结果： Sarsa 变得很保守，哪怕 S 本身是安全的，只要离危险近，它就害怕。

• Q-Learning 的思考方式：“我到了 S^′。虽然我下一秒可能会犯傻跳崖，但在理论上，我可以选择‘向上走’拿到 10 分啊！我就按这 10 分来更新现在的 Q(S, A)。至于我下一秒是不是真的跳崖？那是下一轮的事，不管！”结果： Q-Learning 非常大胆。它会学出一条紧贴着悬崖边缘的最优路径。虽然在训练过程中它会因为经常掉下去而显得很蠢，但 Q 表里记录的却是完美的走法。

Sarsa 估计当前ϵ-贪婪策略的动作价值函数。需要强调的是，Q-learning 的更新并非必须使用当前贪心策略max_aQ(s, a)采样得到的数据，因为给定任意(r, s, a, s^′)都可以直接根据更新公式来更新Q，为了探索，我们通常使用一个ϵ-贪婪策略来与环境交互。Sarsa 必须使用当前ϵ-贪婪策略采样得到的数据，因为它的更新中用到的Q(s^′, a^′)的a^′是当前策略在状态s^′下的动作。我们称 Sarsa 是在线策略（on-policy）算法，称 Q-learning 是离线策略（off-policy）算法。

在线策略算法与离线策略算法

我们称采样数据的策略为行为策略（behavior policy），称用这些数据来更新的策略为目标策略（target policy）。在线策略（on-policy）算法表示行为策略和目标策略是同一个策略；而离线策略（off-policy）算法表示行为策略和目标策略不是同一个策略。Sarsa 是典型的在线策略算法，而 Q-learning 是典型的离线策略算法。判断二者类别的一个重要手段是看计算时序差分的价值目标的数据是否来自当前的策略。具体而言：

• 对于 Sarsa，它的更新公式必须使用来自当前策略采样得到的五元组(r, s, a, s^′, a^′)，因此它是在线策略学习方法；
• 对于 Q-learning，它的更新公式使用的是四元组 (r, s, a, s^′) 来更新当前状态动作对的价值 Q(s, a) ，数据中的a和s是给定的条件，s^′和r皆由环境采样得到，该四元组并不需要一定是当前策略采样得到的数据，也可以来自行为策略，因此它是离线策略算法。