时序差分算法

1. 时序差分方法

在动态规划中，我们定义了两个完全已知的场景：悬崖漫步和冰湖环境，来实验我们的动态规划方法。但是，实际上我们在做simulation或者sim2real的时候，环境是未知的，这导致我们无法直接得出马尔可夫决策过程的状态转移概率。此时，智能体只能和环境进行交互，通过采样到的数据来学习，这类学习方法统称为无模型的强化学习（model-free reinforcement learning）。 因此，我们需要一种不依赖于环境模型的方法来评估和改进策略，这就是时序差分（Temporal Difference, TD）方法。

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

$$V(S_t) \leftarrow V(S_t) + \alpha[G_t - V(S_t)]$$

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

$$V(S_t) \leftarrow V(S_t) + \alpha[R_{t+1} + \gamma V(S_{t+1}) - V(S_t)]$$

其中 $\delta_t = R_{t+1} + \gamma V(S_{t+1}) - V(S_t)$ 通常被称为时序差分（temporal difference，TD）误差（error），时序差分算法将其与步长的乘积作为状态价值的更新量。可以用 $R_{t+1} + \gamma V(S_{t+1})$ 来代替 $G_t$ 的原因是：

$$\begin{aligned} V_\pi(s) &= \mathbb{E}_\pi[G_t | S_t = s] \\ &= \mathbb{E}_\pi[R_{t+1} + \gamma R_{t+2} + \gamma^2 R_{t+3} + \cdots | S_t = s] \\ &= \mathbb{E}_\pi[R_{t+1} + \gamma (R_{t+2} + \gamma R_{t+3} + \cdots) | S_t = s] \\ &= \mathbb{E}_\pi[R_{t+1} + \gamma G_{t+1} | S_t = s] \\ &\approx \mathbb{E}_\pi[R_{t+1} + \gamma V_\pi(S_{t+1}) | S_t = s] \end{aligned}$$

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

2. Sarsa 算法

既然我们可以用时序差分方法来估计价值函数，那一个很自然的问题是，我们能否用类似策略迭代的方法来进行强化学习。策略评估已经可以通过时序差分算法实现，那么在不知道奖励函数和状态转移函数的情况下该怎么进行策略提升呢？答案是我们可以直接用时序差分算法来估计动作价值函数 $Q(s,a)$：

$$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)]$$

然后我们用贪婪算法来选取在某个状态下动作价值最大的那个动作，即 $\pi(s) = \arg\max_a Q(s,a)$。这样似乎已经形成了一个完整的强化学习算法：用贪婪算法根据动作价值选取动作来和环境交互，再根据得到的数据用时序差分算法更新动作价值估计。

然而这个简单的算法存在两个需要进一步考虑的问题。第一，如果要用时序差分算法来准确地估计策略的状态价值函数，我们需要用极大量的样本来进行更新。但实际上我们可以忽略这一点，直接用一些样本来评估策略，然后就可以更新策略了。我们可以这么做的原因是策略提升可以在策略评估未完全进行的情况进行，回顾一下，价值迭代（参见 4.4 节）就是这样，这其实是广义策略迭代（generalized policy iteration）的思想。第二，如果在策略提升中一直根据贪婪算法得到一个确定性策略，可能会导致某些状态动作对 $(s,a)$ 永远没有在序列中出现，以至于无法对其动作价值进行估计，进而无法保证策略提升后的策略比之前的好。我们在第 2 章中对此有详细讨论。简单常用的解决方案是不再一味使用贪婪算法，而是采用一个 $\epsilon$-贪婪策略：以 $1-\epsilon$ 的概率采用动作价值最大的那个动作，另外有 $\epsilon$ 的概率从动作空间中随机采取一个动作，其公式表示为：

$$\pi(a|s) = \begin{cases} 1 - \epsilon + \frac{ \epsilon}{|A(s)|} & \text{if } a = \arg\max_{a'} Q(s, a') \\ \frac{\epsilon}{|A(s)|} & \text{otherwise} \end{cases}$$

现在，我们就可以得到一个实际的基于时序差分方法的强化学习算法。这个算法被称为 Sarsa，因为它的动作价值更新用到了当前状态 $S_t$、当前动作 $A_t$、获得的奖励 $R_{t+1}$、下一个状态 $S_{t+1}$ 和下一个动作 $A_{t+1}$，将这些符号拼接后就得到了算法名称。Sarsa 的具体算法如下：

算法：Sarsa（在线策略时序差分控制）

• 初始化 $Q(s,a)$，对于所有 $s \in \mathcal{S}, a \in \mathcal{A}(s)$
• 设置参数 $\alpha$（步长），$\epsilon$（探索率），$\gamma$（折扣因子）
• for 每个回合（episode） do：
  • 得到初始状态 $S$
  • 用 $\epsilon$-greedy 策略根据 $Q$ 选择当前状态 $S$ 下的动作 $A$
  • for 每个时间步 do：
    • 执行动作 $A$，得到环境反馈的奖励 $R$ 和下一个状态 $S'$
    • 用 $\epsilon$-greedy 策略根据 $Q$ 选择下一个状态 $S'$ 下的动作 $A'$
    • 更新动作价值函数：$Q(S,A) \leftarrow Q(S,A) + \alpha[R + \gamma Q(S',A') - Q(S,A)]$
    • $S \leftarrow S'$, $A \leftarrow A'$
  • until $S$ 是终止状态
• end for

3. 多步 Sarsa 算法

蒙特卡洛方法利用当前状态之后每一步的奖励而不使用任何价值估计，时序差分算法只利用一步奖励和下一个状态的价值估计。那它们之间的区别是什么呢？总的来说，蒙特卡洛方法是无偏（unbiased）的，但是具有比较大的方差，因为每一步的状态转移都有不确定性，而每一步状态采取的动作所得到的不一样的奖励最终都会加起来，这会极大影响最终的价值估计；时序差分算法具有非常小的方差，因为只关注了一步状态转移，用到了一步的奖励，但是它是有偏的，因为用到了下一个状态的价值估计而不是其真实的价值。那有没有什么方法可以结合二者的优势呢？答案是多步时序差分！多步时序差分的意思是使用 $n$ 步的奖励，然后使用之后状态的价值估计。用公式表示，将 $G_t$ 替换为 $n$ 步回报：

$$G_t^{(n)} = R_{t+1} + \gamma R_{t+2} + \gamma^2 R_{t+3} + \cdots + \gamma^{n-1} R_{t+n} + \gamma^n V(S_{t+n})$$

于是，相应存在一种多步 Sarsa 算法，它把 Sarsa 算法中的动作价值函数的更新公式（参见 5.3 节）：

$$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)]$$

替换为基于 $n$ 步回报的更新形式：

$$Q(S_t, A_t) \leftarrow Q(S_t, A_t) + \alpha[G_t^{(n)} - Q(S_t, A_t)]$$

其中 $n$ 步动作价值回报定义为：

$$G_t^{(n)} = R_{t+1} + \gamma R_{t+2} + \cdots + \gamma^{n-1} R_{t+n} + \gamma^n Q(S_{t+n}, A_{t+n})$$

这种多步学习方法在偏差和方差之间提供了一个平衡点：当 $n=1$ 时就是标准的时序差分方法（低方差但有偏），当 $n$ 趋近于无穷大时就是蒙特卡洛方法（无偏但高方差）。通过选择合适的 $n$ 值，我们可以在两种极端情况之间找到一个较好的折衷。

4. Q-learning 算法

除了 Sarsa，还有一种非常著名的基于时序差分算法的强化学习算法——Q-learning。Q-learning 和 Sarsa 的最大区别在于 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)]$$

Q-learning 算法的具体流程如下：

算法：Q-learning（离线策略时序差分控制）

• 初始化 $Q(s,a)$，对于所有 $s \in \mathcal{S}, a \in \mathcal{A}(s)$
• 设置参数 $\alpha$（步长），$\epsilon$（探索率），$\gamma$（折扣因子）
• for 每个回合（episode） do：
  • 得到初始状态 $S$
  • for 每个时间步 do：
    • 用 $\epsilon$-greedy 策略根据 $Q$ 选择当前状态 $S$ 下的动作 $A$
    • 执行动作 $A$，得到环境反馈的奖励 $R$ 和下一个状态 $S'$
    • 更新动作价值函数：$Q(S,A) \leftarrow Q(S,A) + \alpha[R + \gamma \max_{a'} Q(S', a') - Q(S,A)]$
    • $S \leftarrow S'$
    • until $S$ 是终止状态
  • end for end for

我们可以用价值迭代的思想来理解 Q-learning，即 Q-learning 是直接在估计最优动作价值函数 $Q^*$，因为动作价值函数的贝尔曼最优方程是：

$$Q^*(s,a) = \mathbb{E}[R_{t+1} + \gamma \max_{a'} Q^*(S_{t+1}, a') | S_t = s, A_t = a]$$

而 Sarsa 估计当前 $\epsilon$-贪婪策略的动作价值函数。需要强调的是，Q-learning 的更新并非必须使用当前贪心策略采样得到的数据，因为给定任意 $(S_t, A_t, R_{t+1}, S_{t+1})$ 都可以直接根据更新公式来更新 $Q(S_t, A_t)$，为了探索，我们通常使用一个 $\epsilon$-贪婪策略来与环境交互。Sarsa 必须使用当前 $\epsilon$-贪婪策略采样得到的数据，因为它的更新中用到的 $A_{t+1}$ 是当前策略在 $S_{t+1}$ 下的动作。我们称 Sarsa 是在线策略（on-policy）算法，称 Q-learning 是离线策略（off-policy）算法，这两个概念在强化学习中非常重要。

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

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)]$
• 必须使用来自当前策略采样得到的五元组 $(S_t, A_t, R_{t+1}, S_{t+1}, A_{t+1})$
• $A_{t+1}$ 必须是根据当前策略在状态 $S_{t+1}$ 下选择的动作
• 就像一个"言行一致"的人，用自己实际行动的结果来修正自己的价值观

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)]$
• 只需要四元组 $(S_t, A_t, R_{t+1}, S_{t+1})$ 来更新当前状态动作对的价值
• 数据中的 $A_t$ 和 $S_{t+1}$ 可以由任意行为策略产生，不一定是当前目标策略
• 就像一个"博采众长"的观察者，可以从他人的经验中学习，不受限于自身的行动方式

这种区别使得 Q-learning 更加灵活，能够利用历史数据或其他策略收集的数据进行学习，而 Sarsa 则更加注重当前策略的实际表现，在学习过程中更加谨慎。

5. Q-Learning 收敛性证明

假设一个随机过程 $\{\Delta_t\}$ 的形式为：

$$\Delta_{t+1}(x) = (1 - \alpha_t(x))\Delta_t(x) + \alpha_t(x)F_t(x)$$

如果满足以下条件，那么它将收敛到 0：

(1) $\sum_t \alpha_t(x) = \infty$，$\sum_t \alpha_t^2(x) < \infty$；

(2) $\|\mathbb{E}[F_t(x)|\mathcal{F}_t]\|_W \leq \gamma \|\Delta_t\|_W$，其中 $\gamma < 1$；

(3) $\text{Var}[F_t(x)|\mathcal{F}_t] \leq C(1 + \|\Delta_t\|_W)^2$，其中 $C > 0$ 是一个常数。

在时间步 $t$ 给定一个数据 $(s_t, a_t, r_t, s_{t+1})$，Q-learning 的更新公式可以写成：

$$Q_{t+1}(s_t, a_t) = Q_t(s_t, a_t) + \alpha_t[s_t, a_t]\left(r_t + \gamma \max_{a'} Q_t(s_{t+1}, a') - Q_t(s_t, a_t)\right)$$

其中，更新步长 $\alpha_t$ 与时间有关，并且满足 $\sum_t \alpha_t = \infty$，$\sum_t \alpha_t^2 < \infty$。我们将其重写成以下形式：

$$Q_{t+1}(s_t, a_t) = (1 - \alpha_t)Q_t(s_t, a_t) + \alpha_t\left(r_t + \gamma \max_{a'} Q_t(s_{t+1}, a')\right)$$

假设 $Q^*$ 是最优动作价值函数，令 $\Delta_t = Q_t - Q^*$。在上式等号左右两边减去 $Q^*$，然后令 $F_t = r_t + \gamma \max_{a'} Q_t(s_{t+1}, a') - Q^*(s_t, a_t)$，于是有：

$$\Delta_{t+1}(s_t, a_t) = (1 - \alpha_t)\Delta_t(s_t, a_t) + \alpha_t F_t$$

基于环境状态转移的概率分布，可以求得其期望值为：

$$\mathbb{E}[F_t|\mathcal{F}_t] = r_t + \gamma \mathbb{E}[\max_{a'} Q_t(s_{t+1}, a')] - Q^*(s_t, a_t)$$

定义 Bellman 最优算子 $\mathcal{T}$：

$$(\mathcal{T}Q)(s,a) = \mathbb{E}[r_t + \gamma \max_{a'} Q(s_{t+1}, a') | s_t = s, a_t = a]$$

于是有：

$$\mathbb{E}[F_t|\mathcal{F}_t] = (\mathcal{T}Q_t)(s_t,a_t) - Q^*(s_t,a_t)$$

对于最优动作函数 $Q^*$，根据定义，它满足 Bellman 最优方程：

$$Q^* = \mathcal{T}Q^*$$

所以：

$$\mathbb{E}[F_t|\mathcal{F}_t] = (\mathcal{T}Q_t)(s_t,a_t) - (\mathcal{T}Q^*)(s_t,a_t)$$

可以证明 $\mathcal{T}$ 是一个 $\gamma$-压缩算子，所以有：

$$\|\mathbb{E}[F_t|\mathcal{F}_t]\|_\infty \leq \gamma \|Q_t - Q^*\|_\infty = \gamma \|\Delta_t\|_\infty$$

接下来，根据随机近似理论，我们可以进一步推导方差条件。因为奖励函数 $r_t$ 是有界的，所以存在一个常数 $C$，使得：

$$\text{Var}[F_t|\mathcal{F}_t] \leq C(1 + \|\Delta_t\|_\infty)^2$$

因此，根据引理，$\Delta_t$ 能收敛到 0，这意味着 $Q_t$ 能够收敛到 $Q^*$。