5.chapter

第五章：时序差分（Temporal Difference, TD）价值迭代

时序差分更新与回合更新的区别在于，时需差分更新汲取了动态规划方法中“自益”的思想，用现有的价值估计值来更新价值估计，不需要等到回合结束也可以更新价值估计。时序差分更新也包括同策和异策，同时还能分为单步更新和多步更新。

一、同策时序差分更新

$\pi$ 的情况下动作价值的定义出发，则有下式：

\begin{equation} \begin{split} q_\pi(s,a) &= E_\pi (G_t \mid S_t=s,A_t=a) \\ &= E_\pi (R_{t+1} + \gamma G_{t+1} \mid S_t=s,A_t=a) \\ &= E_\pi (R_{t+1} + \gamma q_\pi(S_{t+1},A_{t+1}) \mid S_t=s,A_t=a) \qquad s \in \mathcal S, a \in \mathcal A(s) \\ \end{split} \end{equation} \label{eq:1}

$\eqref{eq:1}$ $U_t=R_{t+1} + \gamma q_\pi(S_{t+1}, \cdot)$ $G_t$ $U_t$ 表示使用自益得到的有偏回报样本。

根据以上分析，可以定义时序差分目标：

$U_{t:t+1}^{(q)} = R_{t+1} + \gamma q(S_{t+1},A_{t+1})$
$U_{t:t+1}^{(v)} = R_{t+1} + \gamma v(S_{t+1})$

$U_{t:t+1}^{(q)}$ $t:t+1$ $(S_{t+1},A_{t+1})$ $(S_t,A_t)$ 。再推广到多步时序差分目标：

$\displaystyle U_{t:t+n}^{(q)} = \sum_{i=1}^{n} \gamma^{i-1} R_{t+i} + \gamma^n q(S_{t+n},A_{t+n}) = R_{t+1}+\gamma U_{t+1:t+n}^{(q)}$ $U_t^{(q)}$ $U_t$
$\displaystyle U_{t:t+n}^{(v)} = \sum_{i=1}^{n} \gamma^{i-1} R_{t+i} + \gamma^n v(S_{t+n}) = R_{t+1}+\gamma U_{t+1:t+n}^{(v)}$ $U_t^{(v)}$ $U_t$

$\displaystyle q(S_t,A_t) \leftarrow q(S_t,A_t) + \frac{1}{c(S_t,A_t)}[G_t-q(S_t,A_t)]$ $G_t$ $U_t$ $\displaystyle \frac{1}{c(S_t,A_t)}$ $\alpha \in (0,1]$ $\alpha$ ，在有些问题中，让学习率巧妙地变化能得到更好的效果。

那么可以得到时序差分更新价值的表达式：

q(S_t,A_t) \leftarrow q(S_t,A_t) + \alpha[U_t-q(S_t,A_t)] \\ v(S_t) \leftarrow v(S_t) + \alpha[U_t-v(S_t)] \label{eq:2}

$\eqref{eq:2}$ 可以得到单步时序差分更新评估策略的动作（状态）价值算法：

\; \\ \; \\ \large \textbf{算法 5-1 单步时序差分更新评估策略的动作（或状态）价值} \\ \begin{split} \rule[5pt]{10mm}{0.1em} &\rule[5pt]{265mm}{0.1em} \\ &\text{输入：环境（无数学描述） ，策略 $\pi$ 。} \\ &\text{输出：价值函数 $q(s,a),\; s \in \mathcal S, a \in \mathcal A$ ，（或 $v(s),\; s \in \mathcal S$ ）。} \\ &\text{参数：优化器（隐含学习率 $\alpha$ ），折扣因子 $\gamma$ ，控制回合数和回合内步数的参数。} \\ &\text{1.（初始化）初始化价值估计 $q(s,a) \leftarrow$ 任意值，$s \in \mathcal S, a \in \mathcal A$ ，（或 $v(s) \leftarrow$ 任意值，$s \in \mathcal S$ ）。} \\ &\qquad \text{如果有终止状态，令 $q(s_终,a) \leftarrow 0,\; a \in \mathcal A$ ，（或 $v(s_终) \leftarrow 0$ ）。} \\ &\text{2.（时序差分更新）对于每个回合执行以下操作：} \\ &\qquad \text{2.1（初始化状态动作对（或状态））选择状态 $S$ ，再根据输入策略 $\pi$ 确定动作 $A$ ，（或选择状态 $S$ ）。} \\ &\qquad \text{2.2 $\;\,$如果回合未结束（如未达最大步数、$S' \ne s_终$ ），执行以下操作：} \\ &\qquad \qquad \text{2.2.1（采样）执行动作 $A$ ，观测得到的奖励 $R$ 和新状态 $S'$ ，再用输入策略 $\pi$ 确定动作 $A'$ ，} \\ &\qquad \qquad \qquad \;\, \text{（或根据输入策略 $\pi$ 确定动作 $A$ ，再执行动作 $A$ ，观测得到的奖励 $R$ 和新状态 $S'$ ）；} \\ &\qquad \qquad \text{2.2.2（计算回报的估计值）$U \leftarrow R + \gamma q(S',A')$ ，（或$U \leftarrow R + \gamma v(S')$ ）；} \\ &\qquad \qquad \text{2.2.3（更新价值）更新 $q(S,A)$（或 $v(S)$ ）以减小 $[U-q(S,A)]^2$（或 $[U-v(S)]^2$ ），} \\ &\qquad \qquad \qquad \;\, \text{如 $q(S,A) \leftarrow q(S,A) + \alpha[U-q(S,A)]$ ，（或 $v(S) \leftarrow v(S) + \alpha[U-v(S)]$ ）；} \\ &\qquad \qquad \text{2.2.4 $\;\, S \leftarrow S'$ ， $A \leftarrow A'$ ，（或 $S \leftarrow S'$ ）。} \\ \rule[-5pt]{10mm}{0.1em} &\rule[-5pt]{265mm}{0.1em} \end{split} \; \\ \; \\

$U_t$ $(S_{t+1},A_{t+1})$ ），如果环境真的是 Markov 决策过程，那么自益能够更加有效的使用轨迹样本；若环境不是 Markov 决策过程，那么自益反而会导致错误的估计，而回合更新只使用了当前状态的样本，并不会产生错误的估计。

将单步时序差分算法推广到多步，即可得到算法 5-2 ：

\; \\ \; \\ \large \textbf{算法 5-2 n 步时序差分更新评估策略的动作（或状态）价值} \\ \begin{split} \rule[5pt]{10mm}{0.1em} &\rule[5pt]{265mm}{0.1em} \\ &\cdots \quad \text{同算法 5-1 ，但加一个参数：步数 n 。} \quad \cdots \\ &\text{2.（时序差分更新）对于每个回合执行以下操作：} \\ &\qquad \text{2.1（采样）用 $\pi$ 生成轨迹 $S_0,A_0,R_1,\cdots,R_n,S_n$（令终止状态之后的奖励均为 0，状态均为 $S_终$ ）。} \\ &\qquad \text{2.2 $\;\,$ 对于 $t=0,1,2,\cdots$ 依次执行以下操作，直到 $S_t=s_终$：} \\ &\qquad \qquad \text{2.2.1（更新时序差分目标）$U_{t:t+n}^{(q)} \leftarrow R_{t+1} + \gamma R_{t+2} + \cdots + \gamma^{n-1}R_{t+n} + \gamma^n q(S_{t+n},A_{t+n})$ ，} \\ &\qquad \qquad \qquad \;\, \text{（或 $U_{t:t+n}^{(v)} \leftarrow R_{t+1} + \gamma R_{t+2} + \cdots + \gamma^{n-1}R_{t+n} + \gamma^n v(S_{t+n})$ ）；} \\ &\qquad \qquad \text{2.2.2（更新价值）更新 $q(S_t,A_t)$（或 $v(S_t)$ ）以减小 $[U-q(S_t,A_t)]^2$（或 $[U-v(S_t)]^2$ ）；} \\ &\qquad \qquad \text{2.2.3 $\;\,$若 $S_{t+n} \ne s_终$ ，则执行 $A_{t+n}$ （或根据 $\pi(\cdot \mid S_{t+n})$ 决定动作 $A_{t+n}$ 并执行），得到奖励} \\ &\qquad \qquad \qquad \;\, \text{$R_{t+n+1}$ 和下一状态 $S_{t+n+1}$ ；若 $S_{t+n} = s_终$ ，令 $R_{t+n+1} \leftarrow 0$ ，$S_{t+n+1} \leftarrow s_终$ 。} \\ \rule[-5pt]{10mm}{0.1em} &\rule[-5pt]{265mm}{0.1em} \end{split} \; \\ \; \\

$\varepsilon$ $\pi$ 总是柔性策略，且中间过程的策略既可以显式更新和存储，也可以不显式存储：

\; \\ \; \\ \large \textbf{算法 5-3 SARSA 算法求解最优策略} \\ \begin{split} \rule[5pt]{10mm}{0.1em} &\rule[5pt]{265mm}{0.1em} \\ &\text{输入：环境（无数学描述）。} \\ &\text{输出：最优策略估计 $\pi(a \mid s)$ 和最优动作价值估计 $q(s,a)$ ，$s \in \mathcal S, a \in \mathcal A$ 。} \\ &\text{参数：优化器（隐含学习率 $\alpha$ ），折扣因子 $\gamma$ ，策略改进的参数（如 $\varepsilon$ ），控制回合数和回合内步数的参数。} \\ &\text{1.（初始化）$q(s,a) \leftarrow$ 任意值，如果有终止状态，令 $q(s_终,a) \leftarrow 0$ ，$s \in \mathcal S, a \in \mathcal A(s)$ ；如果是显式更新} \\ &\qquad \text{和存储策略，则用动作价值 $q(s,a)$ 确定策略 $\pi$（如 $\varepsilon$ 贪心策略）。} \\ &\text{2.（时序差分更新）对于每个回合执行以下操作：} \\ &\qquad \text{2.1（初始化状态动作对）选择状态 $S$ ，用动作价值 $q(S,\cdot)$ 确定的策略决定动作 $A$（如 $\varepsilon$ 贪心策略）；} \\ &\qquad \qquad \text{若为显式存储策略，则用策略 $\pi$ 确定动作 $A$ 。} \\ &\qquad \text{2.2 $\;\,$如果回合未结束，执行以下操作：} \\ &\qquad \qquad \text{2.2.1（采样）执行动作 $A$ ，观测得到的奖励 $R$ 和新状态 $S'$ ；} \\ &\qquad \qquad \text{2.2.2 $\;\,$用 $q(S',\cdot)$ 确定的策略决定动作 $A'$ ；若为显式存储策略，则用策略 $\pi$ 确定动作 $A'$ ；} \\ &\qquad \qquad \text{2.2.3（计算回报的估计值）$U \leftarrow R + \gamma q(S',A')$ ，（或$U \leftarrow R + \gamma v(S')$ ）；} \\ &\qquad \qquad \text{2.2.4（更新价值）更新 $q(S,A)$ 以减小 $[U-q(S,A)]^2$ ；} \\ &\qquad \qquad \text{2.2.5（若为显示存储策略则进行策略改进）根据 $q(S,\cdot)$ 修改 $\pi(\cdot \mid S)$（如 $\varepsilon$ 贪心策略）；} \\ &\qquad \qquad \text{2.2.6 $\;\, S \leftarrow S'$ ， $A \leftarrow A'$ 。} \\ &\qquad \text{2.3（若不为显式存储策略）由最优动作价值估计 $q(s,a)$ 确定最优策略估计 $\pi(a \mid s)$ ，$s \in \mathcal S, a \in \mathcal A$ 。} \\ \rule[-5pt]{10mm}{0.1em} &\rule[-5pt]{265mm}{0.1em} \end{split} \; \\ \; \\

在 SARSA 算法中采用多步时序差分目标，即可得到多步 SARSA 算法，类似于从算法 5-1 到 5-2 ，该算法可由算法 5-3 修改得到，此处略。

期望 SARSA 算法 $U_t$ 时，不使用基于动作价值的时序差分目标，而使用基于状态价值的时序差分目标，再利用 Bellman 方程有：

U_{t:t+1}^{(v)} = R_{t+1} + \gamma v(S_{t+1}) = R_{t+1} + \gamma \sum_{a \in \mathcal A(S_{t+1})} \pi(a \mid S_{t+1})q(S_{t+1},a)

$\sum_a\pi(a \mid S_{t+1})q(S_{t+1},a)$ ，虽然计算量增大，但这样的期望运算减小了 SARSA 算法中出现的个别不恰当决策，因此期望 SARSA 常常有比 SARSA 更大的学习率，在很多情况下，期望 SARSA 的效果会比 SARSA 稍微好一些。算法 5-4 给出了期望 SARSA 算法：

\; \\ \; \\ \large \textbf{算法 5-4 期望 SARSA 求解最优策略} \\ \begin{split} \rule[5pt]{10mm}{0.1em} &\rule[5pt]{265mm}{0.1em} \\ &\text{1.（初始化） $q(s,a) \leftarrow$ 任意值，如果有终止状态，令 $q(s_终,a) \leftarrow 0$ ，$s \in \mathcal S, a \in \mathcal A$ ；} \\ &\qquad \text{再用动作价值 $q(s,a)$ 确定策略 $\pi$（如 $\varepsilon$ 贪心策略）。} \\ &\text{2.（时序差分更新）对于每个回合执行以下操作：} \\ &\qquad \text{2.1（初始化状态）选择状态 $S$ 。} \\ &\qquad \text{2.2 $\;\,$如果回合未结束，执行以下操作：} \\ &\qquad \qquad \text{2.2.1 $\;\,$用动作价值 $q(S,\cdot)$ 确定的策略 $\pi$ 来确定动作 $A$ ；} \\ &\qquad \qquad \text{2.2.2（采样）执行动作 $A$ ，观测得到的奖励 $R$ 和新状态 $S'$ ；} \\ &\qquad \qquad \text{2.2.3（用期望计算回报的估计值）$U \leftarrow R + \gamma \sum_{a \in \mathcal A(S')} \pi(a \mid S') q(S',a)$ ；} \\ &\qquad \qquad \text{2.2.4（更新价值）更新 $q(S,A)$ 以减小 $[U-q(S,A)]^2$ ；} \\ &\qquad \qquad \text{2.2.5 $\;\, S \leftarrow S'$。} \\ \rule[-5pt]{10mm}{0.1em} &\rule[-5pt]{265mm}{0.1em} \end{split} \; \\ \; \\

期望 SARSA 算法同样也有多步版本，与前面的多步算法类似，可由单步版本修改得到，此处略。

二、异策时序差分更新

前面已经介绍过异策算法是基于重要性采样的，将该方法整合到时序差分策略评估动作价值算法或 SARSA 算法中，即可得到它们的重要性采样版本，算法 5-5 给出了多步时序差分的版本：

\; \\ \; \\ \large \textbf{算法 5-5 重要性采样 n 步时序差分策略评估动作价值或 SARSA 算法} \\ \begin{split} \rule[5pt]{10mm}{0.1em} &\rule[5pt]{265mm}{0.1em} \\ &\text{输入：环境（无数学描述） ，策略 $\pi$ 。} \\ &\text{输出：价值函数 $q(s,a),\; s \in \mathcal S, a \in \mathcal A(s)$ ，若是最优策略控制则还要输出策略 $\pi$ 。} \\ &\text{参数：步数 n ，优化器（隐含学习率 $\alpha$ ），折扣因子 $\gamma$ ，控制回合数和回合内步数的参数。} \\ &\text{1.（初始化） $q(s,a) \leftarrow$ 任意值，如果有终止状态，令 $q(s_终,a) \leftarrow 0$ ，$s \in \mathcal S, a \in \mathcal A$ ；若是最优策略控制，} \\ &\qquad \text{还应用 $q(s,a)$ 确定策略 $\pi$（如 $\varepsilon$ 贪心策略）。} \\ &\text{2.（时序差分更新）对于每个回合执行以下操作：} \\ &\qquad \text{2.1（行为策略）指定行为策略 $b$ 使得 $\pi \ll b$ 。} \\ &\qquad \text{2.2（采样）用 $b$ 生成轨迹 $S_0,A_0,R_1,\cdots,R_n,S_n$（令终止状态之后的奖励均为 0，状态均为 $S_终$ ）} \\ &\qquad \text{2.3 $\;\,$ 对于 $t=0,1,2,\cdots$ 依次执行以下操作，直到 $S_t=s_终$：} \\ &\qquad \qquad \text{2.3.1 $\;\,$若 $S_{t+n} \ne s_终$ ，则根据 $\pi(\cdot \mid S_{t+n})$ 决定动作 $A_{t+n}$ ；} \\ &\qquad \qquad \text{2.3.2（更新时序差分目标）$U_{t:t+n}^{(q)} \leftarrow R_{t+1} + \gamma R_{t+2} + \cdots + \gamma^{n-1}R_{t+n} + \gamma^n q(S_{t+n},A_{t+n})$ ;} \\ &\qquad \qquad \text{2.3.3（计算重要性采样比率）$\rho_{t+1:t+n-1} \leftarrow \prod_{\tau=t+1}^{\min\{t+n,T\}-1} \frac{\pi(A_\tau \mid S_\tau)}{b(A_\tau \mid S_\tau)}$ ；} \\ &\qquad \qquad \text{2.3.4（更新价值）更新 $q(S_t,A_t)$ 以减小 $\rho [U-q(S_t,A_t)]^2$ ；} \\ &\qquad \qquad \text{2.3.5（更新策略）如果是最优策略求解算法，需要根据 $q(S,\cdot)$ 修改 $\pi(\cdot \mid S)$ ；} \\ &\qquad \qquad \text{2.3.6 $\;\,$若 $S_{t+n} \ne s_终$ ，则执行 $A_{t+n}$ ，得到奖励 $R_{t+n+1}$ 和下一状态 $S_{t+n+1}$ ；若 $S_{t+n} = s_终$ ，} \\ &\qquad \qquad \qquad \;\, \text{则令 $R_{t+n+1} \leftarrow 0$ ，$S_{t+n+1} \leftarrow s_终$ 。} \\ \rule[-5pt]{10mm}{0.1em} &\rule[-5pt]{265mm}{0.1em} \end{split} \; \\ \; \\

单步版本也可以由前面的算法修改得到，另外还可以类似的方法将重要性采样运用到时序差分状态价值估计和期望 SARSA 算法中，此处略。

$\displaystyle U_t = R_{t+1} + \gamma \max_{a \in \mathcal A(S_{t+1})} q(S_{t+1},a)$ $q(S_{t+1},\cdot)$ 改进后的策略来更新，使得可以更接近最优价值。因此 Q 学习的更新式不是基于当前的策略，而是基于另外一个不一定要使用的确定性策略来更新动作价值，从这个意义上来看，Q 学习是一个异策算法：

\; \\ \; \\ \large \textbf{算法 5-6 Q 学习算法求解最优策略} \\ \begin{split} \rule[5pt]{10mm}{0.1em} &\rule[5pt]{265mm}{0.1em} \\ &\text{1.（初始化） $q(s,a) \leftarrow$ 任意值，如果有终止状态，令 $q(s_终,a) \leftarrow 0$ ，$s \in \mathcal S, a \in \mathcal A$ 。} \\ &\text{2.（时序差分更新）对于每个回合执行以下操作：} \\ &\qquad \text{2.1（初始化状态）选择状态 $S$ 。} \\ &\qquad \text{2.2 $\;\,$如果回合未结束，执行以下操作：} \\ &\qquad \qquad \text{2.2.1 $\;\,$用动作价值 $q(S,\cdot)$ 确定的策略 $\pi$ 来确定动作 $A$（如 $\varepsilon$ 贪心策略） ；} \\ &\qquad \qquad \text{2.2.2（采样）执行动作 $A$ ，观测得到的奖励 $R$ 和新状态 $S'$ ；} \\ &\qquad \qquad \text{2.2.3（用改进后的策略计算回报的估计值）$U \leftarrow R + \gamma \max_{a \in \mathcal A(S')} q(S',a)$ ；} \\ &\qquad \qquad \text{2.2.4（更新价值和策略）更新 $q(S,A)$ 以减小 $[U-q(S,A)]^2$ ；} \\ &\qquad \qquad \text{2.2.5 $\;\, S \leftarrow S'$。} \\ \rule[-5pt]{10mm}{0.1em} &\rule[-5pt]{265mm}{0.1em} \end{split} \; \\ \; \\

$\displaystyle U_t= R_{t+1} + \gamma R_{t+2} + \cdots + \gamma^{n-1}R_{t+n} + \gamma^n \max_{a \in \mathcal A(S_{t+n})} q(S_{t+n},a)$ ，此处略。

$\max_aq(S_{t+1},a)$ 双重 Q 学习 $q^{(0)}(\cdot,\cdot)$ $q^{(1)}(\cdot,\cdot)$ $q^{(0)}(S_{t+1},\arg\max_a q^{(1)}(S_t+1,a))$ $q^{(1)}(S_{t+1},\arg\max_a q^{(0)}(S_t+1,a))$ $\max_aq(S_{t+1},a)$ $q^{(0)}$ $q^{(1)}$ $E[q^{(0)}(S_t+1,A^*)]=q(S_{t+1},A^*)$ $A^*=\arg\max_a q^{(1)}(S_{t+1},a)$ $q^{(0)}$ $q^{(1)}$ 都需要逐渐更新，一种方法是在每步的学习中以等概论选择两个更新中的任意一个：

\; \\ \; \\ \large \textbf{算法 5-7 双重 Q 学习算法求解最优策略} \\ \begin{split} \rule[5pt]{10mm}{0.1em} &\rule[5pt]{265mm}{0.1em} \\ &\text{1.（初始化） $q^{(i)}(s,a) \leftarrow$ 任意值，如果有终止状态，令 $q^{(i)}(s_终,a) \leftarrow 0$ ，$s \in \mathcal S, a \in \mathcal A, i \in \{0,1\}$ 。} \\ &\text{2.（时序差分更新）对于每个回合执行以下操作：} \\ &\qquad \text{2.1（初始化状态）选择状态 $S$ 。} \\ &\qquad \text{2.2 $\;\,$如果回合未结束，执行以下操作：} \\ &\qquad \qquad \text{2.2.1 $\;\,$用动作价值 $(q^{(0)}+q^{(1)})(S,\cdot)$ 确定的策略 $\pi$ 来确定动作 $A$（如 $\varepsilon$ 贪心策略） ；} \\ &\qquad \qquad \text{2.2.2（采样）执行动作 $A$ ，观测得到的奖励 $R$ 和新状态 $S'$ ；} \\ &\qquad \qquad \text{2.2.3（随机选择更新）以等概率选择 $q^{(0)}$ 或 $q^{(1)}$ 作为更新对象，记选中的为 $q^{(i)},i \in \{0,1\}$ ；} \\ &\qquad \qquad \text{2.2.4（用改进后的策略计算回报的估计值）$U \leftarrow R + \gamma q^{(1-i)}(S',\underset{a}{\arg\max}\; q^{(i)}(S',a))$ ；} \\ &\qquad \qquad \text{2.2.5（更新价值）更新 $q^{(i)}(S,A)$ 以减小 $[U-q^{(i)}(S,A)]^2$ ；} \\ &\qquad \qquad \text{2.2.6 $\;\, S \leftarrow S'$。} \\ \rule[-5pt]{10mm}{0.1em} &\rule[-5pt]{265mm}{0.1em} \end{split} \; \\ \; \\

$q^{(0)}$ $q^{(1)}$ $q^{(0)}+q^{(1)}$ 的，该简化计算并不影响结果。

三、资格迹

资格迹是一种让时序差分学习更加有效的机制，它能够在回合更新和单步时序差分更新之间折中，并且实现简单，运行有效。在介绍资格迹之前，先介绍以下内容：

$\lambda \in [0,1]$ $\pmb\lambda$ 回报 $\lambda$ $U_{t:t+1},U_{t:t+2},\cdots$ $(1-\lambda),(1-\lambda)\lambda,\cdots$ 加权平均的结果。对于连续性任务有：

U_t^\lambda = (1-\lambda)\sum_{n=1}^{+\infty} \lambda^{n-1}U_{t:t+n}

$t+n \ge T$ $U_{t:t+n}=G_t$ ，故有：

U_t^\lambda = (1-\lambda)\sum_{n=1}^{T-t-1} \lambda^{n-1}U_{t:t+n}+\lambda^{T-t-1}G_t \label{eq:5}

$G_t$ $U_{t:t+1}$ $\lambda=1$ $U_t^1 = G_t$ $\lambda=0$ $U_t^0=U_{t:t+1}$ 就是单步时序差分目标。

$\pmb\lambda$ 回报算法 $\lambda$ $U_t^\lambda$ $[U_t^\lambda-q(S_t,A_t)]^2$ $[U_t^\lambda-v(S_t)]^2$ $t=0,1,2,\cdots$ $U_t^\lambda$ 离线算法 $G_t$ $U_{t:t+1}$ 之间做了折中，所以其效果可能比单独使用这两个目标都要好。

$\lambda$ 算法也有明显的缺点：

$U_t^\lambda$ ，所以无法使用该算法；
$U_t^\lambda$ ，计算量巨大。

$TD(\lambda)$ $\lambda$ $\lambda$ $(S_t,A_t)$ $U_{t-n:t}$ $q(S_{t-n},A_{t-n})$ $n=1,2,\cdots,t$ $e_t(s,a)$ $t$ $U_{t:t+1}$ $(s,a)$ $s \in \mathcal S, a \in \mathcal A(s)$ 需要更新的权重，资格迹（eligibility）定义如下：

e_t(s,a)= \left \{ \begin{aligned} \begin{split} &0, &t=0 \\ &1 + \beta\gamma\lambda e_{t-1}(s,a) \qquad &S_t=s,A_t=a \\ &\gamma\lambda e_{t-1}(s,a) &其他 \qquad \end{split} \end{aligned} \right .

$\beta \in [0,1]$ $(S_t,A_t)$ ，它的更新权重则要进行某种强化，其取值常有以下几种：

累积迹 $\beta=1$ ；
荷兰迹 $\beta=1-\alpha$ $\alpha$ 为学习率；
替换迹 $\beta=0$ 。

$\lambda$ $\eqref{eq:6}$ $U_\tau^\lambda$ $(1-\lambda)$ $(S_\tau,A_\tau)$ $U_{\tau:t}$ $U_\tau^\lambda$ $(1-\lambda)\lambda^{t-\tau-1}$ $U_{\tau:t}=R_{\tau+1}+\cdots+\gamma^{t-\tau-1}U_{t-1:t}$ $U_{t-1:t}$ $(1-\lambda)(\lambda\gamma)^{t-\tau-1}$ $U_\tau^\lambda$ $\gamma\lambda$ 倍。（总的来说，对于历史记录越久的状态动作对，资格迹越小，更新力度越小；历史记录越新的状态动作对，资格迹越大，更新力度越大。参考资料：莫烦python：什么是 Sarsa(lambda)）

\begin{equation} \begin{split} &U_0^\lambda 的项 &U_1^\lambda 的项 &\cdots &U_{n-1}^\lambda 的项 \\ n=1: \quad &(1-\lambda) U_{0:1} \\ n=2: \quad &(1-\lambda)\lambda U_{0:2} &(1-\lambda)U_{1:2} & \\ \vdots \\ n: \quad &(1-\lambda)\lambda^{n-1} U_{0:n} \quad &(1-\lambda)\lambda^{n-2}U_{1:n} \quad &\cdots \quad &(1-\lambda) U_{n-1:n} \\ \end{split} \end{equation} \label{eq:6}

$TD(\lambda)$ $\lambda$ $\lambda$ $\lambda$ $\lambda$ ) 的状态价值评估可结合算法 5-1 修改得到，此处略。

\; \\ \; \\ \large \textbf{算法 5-8 TD($\lambda$) 的动作价值评估或 SARSA($\lambda$) 学习} \\ \begin{split} \rule[5pt]{10mm}{0.1em} &\rule[5pt]{265mm}{0.1em} \\ &\text{输入：环境（无数学描述） ，若评估动作价值则需输入策略 $\pi$ 。} \\ &\text{输出：动作价值估计 $q(s,a),\; s \in \mathcal S, a \in \mathcal A$ 。} \\ &\text{参数：资格迹参数 $\beta,\lambda$ ，优化器（隐含学习率 $\alpha$ ），折扣因子 $\gamma$ ，控制回合数和回合内步数的参数。} \\ &\text{1.（初始化） $q(s,a) \leftarrow$ 任意值，如果有终止状态，令 $q(s_终,a) \leftarrow 0$ ，$s \in \mathcal S, a \in \mathcal A$ 。} \\ &\text{2. $\;\,$对于每个回合执行以下操作：} \\ &\qquad \text{2.1（初始化资格迹）$e(s,a) \leftarrow 0,\; s \in \mathcal S,a \in \mathcal A$ 。} \\ &\qquad \text{2.1（初始化状态动作对）选择状态 $S$ ，再根据策略 $\pi$ 或动作价值 $q$ 确定动作 $A$ 。} \\ &\qquad \text{2.2 $\;\,$如果回合未结束，执行以下操作：} \\ &\qquad \qquad \text{2.2.1（采样）执行动作 $A$ ，观测得到的奖励 $R$ 和新状态 $S'$ ；} \\ &\qquad \qquad \text{2.2.2 $\;\,$根据策略 $\pi$ 动作价值 $q$ 确定动作 $A'$ ；} \\ &\qquad \qquad \text{2.2.3（更新资格迹）$e(s,a) \leftarrow \gamma\lambda e(s,a),\; s\in \mathcal S, a \in \mathcal A$ ，$e(S,A) \leftarrow 1 + \beta e(S,A)$ ；} \\ &\qquad \qquad \text{2.2.4（计算回报的估计值）$U \leftarrow R + \gamma q(S',A')$ ；} \\ &\qquad \qquad \text{2.2.5（更新价值）$q(s,a) \leftarrow q(s,a) + \alpha e(s,a)[U-q(S,A)],\; s \in \mathcal S, a \in \mathcal A$ ；} \\ &\qquad \qquad \text{2.2.6 $\;\, S \leftarrow S'$ ， $A \leftarrow A'$ 。} \\ \rule[-5pt]{10mm}{0.1em} &\rule[-5pt]{265mm}{0.1em} \end{split} \; \\ \; \\

$\lambda$ $q(s,a)$ $S_0 \ne S_1$ ，考虑两步，则有

\begin{split} t=0，&U_{0:1} = R_1&+\gamma q(S_1,A_1)\; 更新\; q(S_0,A_0)\; 以及其他所有动作状态对，有 \\ &q(S_0,A_0) &= q(S_0,A_0)+\alpha(U_{0:1}-q(S_0,A_0)) = \alpha U_{0:1}； \\ t=1，&U_{1:2} = R_2&+\gamma q(S_2,A_2)\; 更新\; q(S_0,A_0)\; 以及其他所有动作状态对，有 \\ &q(S_0,A_0) &= q(S_0,A_0) + \alpha\lambda\gamma(U_{1:2}-q(S_0,A_0)) \\ &&= (1-\alpha\lambda\gamma)q(S_0,A_0) + \alpha\lambda\gamma U_{1:2} \\ && = (1-\alpha\lambda\gamma)\alpha U_{0:1} + \alpha\lambda(U_{0:2}-R_1) \\ && = \alpha[(1-\alpha\lambda\gamma)U_{0:1} + \lambda(U_{0:2}-R_1)]\\ && = \alpha[(1-\alpha\lambda\gamma)R_1 + \lambda\gamma R_2 + (1-\alpha\lambda\gamma)\gamma q(S_1,A_1) + \lambda\gamma^2 q(S_2,A_2)] \\ \\ 离线 \lambda 回报： &q(S_0,A_0) &=q(S_0,A_0) + \alpha(U_0^\lambda -q(S_0,A_0)) \\ &&=\alpha[(1-\lambda)U_{0:1} + (1-\lambda)\lambda U_{0:2}] \\ &&=\alpha[(1-\lambda^2)R_1 + (1-\lambda)\lambda\gamma R_2 + (1-\lambda)\gamma q(S_1,A_1) + (1-\lambda)\lambda\gamma^2 q(S_2,A_2)] \end{split}

从两者的展开计算结果可以看到，所有的加权项是相同的，只是加权权重不同。）

四、案例：出租车调度（Taxi-v3）

本节使用 gym 库里的出租车调度问题（Taxi-v3），该问题在一个 5x5 方格表示的地图上，有 4 个出租车停靠点，函数 env.render() 会显示如下所示的地图：

+ - - - - - - - + \\ \begin{split} &|\; R\;&: \quad &\;| \quad &: \quad &: G \;&| \\ &|\; &: &\;| &: &: &| \\ &|\; &: &: &: &: &| \\ &|\; &| &: &| &: &| \\ &|\; Y &| &: &|\; B &: &| \\ \end{split} \\ + - - - - - - - + \\ \text{出租车调度问题地图，其中 R、G、B、Y 是四个上下车点}

其中，有一个乘客会随机出现在 4 个出租车停靠点中的一个（将显示为蓝色），并想在任意一个停靠点下车（将显示为洋红色）；出租车会随机出现在 25 个位置的任意一个（黄色高亮显示，当乘客在出租车上时，会变成绿色高亮显示），出租车只能在地图范围内移动一格，且有竖线阻拦的地方不能横向移动；任务为出租车移动到乘客位置，邀请上车，然后移动到目的地，再让乘客下车。

$[0, 500)$ 的 int 型数值，该数值唯一的表示了整个环境的状态，可使用 env.decode() 函数将该数值转化为长度为 4 的元组（taxirow, taxical, passloc, destidx），其各元素也都是 int 型变量，取值和含义如下：

taxirow 和 taxicol 取值为 {0, 1, 2, 3, 4} ，表示当前出租车的位置；
passloc 取值为 {0, 1, 2, 3, 4} ，表示乘客的位置，0~3 表示在出租车停靠点，4 表示在车上；
destidx 取值为 {0, 1, 2, 3} ，表示目的地位置。

全部状态的总数为（5 x 5）x 5 x 4 = 500 。元素取值与地图的对应如下表所示：

`passloc` 或 `destidx`	0	1	2	3
地图中对应的字母	R	G	Y	B
地图上的坐标	(0, 0)	(0, 4)	(4, 0)	(4, 3)

这个问题中的动作取值为 {0, 1, 2, 3, 4, 5} ，其含义与对应的奖励值如下表所示：

动作数值	0	1	2	3	4	5
含义	试图往下	试图往上	试图往右	试图往左	请乘客上车	请乘客下车
执行后的奖励	-1	-1	1	-1	正确 -1 或错误 -10	正确 +20 或错误 -10

本节代码将把各个算法实现为一个类，将该类实例化为一个智能体，使用该智能体与环境进行交互。考虑到以上的算在确定动作与环境交互的顺序上略有不同，这里在不改变逻辑的情况下，在代码中进行统一，函数 run_episode 实现了该统一：


xxxxxxxxxx
23
1
def run_episode(env, agent=None, train=False, render=False):
2
    episode_reward = 0
3
    state = env.reset()
4
    if agent is None:
5
        action = env.action_space.sample()
6
    else:
7
        action = agent.choose_action(state)
8
    while True:
9
        if render:
10
            env.render()
11
        next_state, reward, done, _ = env.step(action)
12
        if agent is None:
13
            next_action = env.action_space.sample()
14
        else:
15
            next_action = agent.choose_action(next_state)
16
            if train:
17
                agent.learn(state, action, reward, next_state, done, next_action)
18
19
        episode_reward += reward
20
        if done:
21
            break
22
        state, action = next_state, next_action
23
    return episode_reward

$\varepsilon$ Agent $\varepsilon$ 贪心策略：


xxxxxxxxxx
14
1
class Agent():
2
    def __init__(self, env, gamma=0.9, learning_rate=0.1, epsilon=0.01):
3
        self.gamma = gamma
4
        self.learning_rate = learning_rate
5
        self.epsilon = epsilon
6
        self.action_n = env.action_space.n
7
        self.q = np.zeros((env.observation_space.n, env.action_space.n))
8
9
    def choose_action(self, state):
10
        if np.random.uniform() > self.epsilon:
11
            action = self.q[state].argmax()
12
        else:
13
            action = np.random.randint(self.action_n)
14
        return action

那么根据各个算法的价值更新步骤，很容易得到对应的智能体类，例如 SARSA 和 QLearning，其中 QLearing 的方法 learn 的参数 *args 是为了兼容 run_episode 下 agent.learn(...) 的传参调用：


xxxxxxxxxx
9
1
class SARSA(Agent):
2
    def learn(self, state, action, reward, next_state, done, next_action):
3
        u = reward + self.gamma * self.q[next_state][next_action] * (1 - done)
4
        self.q[state][action] += self.learning_rate * (u - self.q[state][action])
5
6
class QLearning(Agent):
7
    def learn(self, state, action, reward, next_state, done, *args):
8
        u = reward + self.gamma * self.q[next_state].max() * (1 - done)
9
        self.q[state][action] += self.learning_rate * (u - self.q[state][action])

有了以上这些，就能够实例化智能体算法，并将其放入环境进行训练与测试了：


xxxxxxxxxx
12
1
#agent = SARSA(env)
2
agent = QLearning(env)
3
# 智能体的训练
4
for i in range(episodes):
5
    episode_rewards.append(run_episode(env, agent, train=True))
6
plt.plot(episode_rewards)
7
# 智能体的测试
8
agent.epsilon = 0
9
episode_rewards = [run_episode(env, agent) for _ in range(100)]
10
print("平均回合奖励 = {} / {} = {}".format(sum(episode_rewards), \
11
        len(episode_rewards), np.mean(episode_rewards)))
12
plt.show()

$\lambda$ ) 这类有部分不同参数的算法，可以继承并改写基类的方法：


xxxxxxxxxx
34
1
class DoubleQLearning(Agent):
2
    def __init__(self, env, gamma=0.9, learning_rate=0.1, epsilon=0.01):
3
        super().__init__(env, gamma=gamma, learning_rate=learning_rate, epsilon=epsilon)
4
        self.q1 = np.zeros((env.observation_space.n, env.action_space.n))
5
6
    def choose_action(self, state):
7
        if np.random.uniform() > self.epsilon:
8
            action = (self.q[state] + self.q1[state]).argmax()
9
        else:
10
            action = np.random.randint(self.action_n)
11
        return action
12
13
    def learn(self, state, action, reward, next_state, done, *args):
14
        if np.random.randint(2):
15
            self.q, self.q1 = self.q1, self.q
16
        a = self.q[next_state].argmax()
17
        u = reward + self.gamma * self.q1[next_state][a] * (1 - done)
18
        self.q[state][action] += self.learning_rate * (u - self.q[state][action])
19
20
class SARSALambda(Agent):
21
    def __init__(self, env, lamb=0.5, beta=1, gamma=0.9, learning_rate=0.1, epsilon=0.01):
22
        super().__init__(env, gamma=gamma, learning_rate=learning_rate, epsilon=epsilon)
23
        self.lamb = lamb
24
        self.beta = beta
25
        self.e = np.zeros((env.observation_space.n, env.action_space.n))
26
27
    def learn(self, state, action, reward, next_state, done, next_action):
28
        self.e *= (self.lamb * self.gamma)
29
        self.e[state][action] = 1 + self.beta * self.e[state][action]
30
        u = reward + self.gamma * self.q[next_state][next_action] * (1 - done)
31
        self.q += self.learning_rate * self.e * (u - self.q[state][action])
32
        # self.q += self.learning_rate * self.e * (u - self.q)
33
        if done:    # 为下一回合初始化资格迹
34
            self.e *= 0

在该问题中，最大化偏差不明显，所以双重 Q 学习往往不能得到好处。本章的算法在该问题上性能各不相同，其中的原因比较复杂，可能是算法本身的问题，也可能是参数选择的问题，但没有一个算法是对所有的任务都有效的。

$\lambda$ $q(s,a) \leftarrow q(s,a) + \alpha e(s,a)[U-q(S,A)],\; s \in \mathcal S, a \in \mathcal A$ self.q += self.learning_rate * self.e * (u - self.q[state][action]) $q(s,a) \leftarrow q(s,a) + \alpha e(s,a)[U-q(s,a)],\; s \in \mathcal S, a \in \mathcal A$ self.q += self.learning_rate * self.e * (u - self.q) $q(s,a)$ $q(S,A)$ $[U-q(S,A)]$ $q(s,a)$ $q(S,A)$ 。