首页 强化学习（时序差分法）
文章
取消

强化学习（时序差分法）

发表于 2022/12/18 更新于 2025/03/29
作者 sirlis
57 分钟阅读

本文首先引入了随机近似理论，然后通过比较动态规划和蒙特卡洛，引出结合二者优势的时序差分法。通过分析可知，时序差分法是随机近似理论的一个特例。随后详细介绍了同轨策略下的时序差分控制（SARSA）、离轨策略下的时序差分控制（Q-Learning）和期望SARSA。最后介绍了基于价值的深度强化学习方法：Deep Q-Network（DQN）。

1. 引言

回顾强化学习的目标：价值估计（预测问题）和策略寻优（控制问题）。在前面的的介绍中，我们分别介绍了两种基于价值的方法，动态规划法和蒙特卡洛法：

  • 动态规划法（DP）：是基于模型的方法，包含策略评估和策略改进两步，策略评估用来进行价值估计（即预测问题），策略改进用来进行策略优化（控制问题）。
  • 蒙特卡洛法（MC）：是无模型的方法，我们无法得到具体模型（动态特性）时，通过采样完整序列后，通过计算 $G_t$ 的均值来近似价值函数。

本节介绍第三种基于价值的方法：时序差分法（TD）。首先回顾一下价值函数的等式：

\[\begin{aligned} v_\pi(s) &= \mathbb{E}_\pi[G_t\vert S_t=s] & {MC}\\ &= \mathbb{E}_\pi[R_{t+1}+\gamma v_\pi(S_{t+1})\vert S_t=s] & {TD}\\ &= \sum_a\pi(a\vert s) \sum_{s^\prime,r}p(r^\prime,r \vert s,a)(r+\gamma v_\pi(s^\prime)) & {DP}\ \end{aligned}\]

可以看出，基于价值的方法可以根据价值函数的等式不同来划分，其中：

  • 动态规划（DP）：是一种自举的方法。更新 $v_{k+1}$ 时采用上一步的 $v_k$ 进行组装，缺点：环境动态特性必须已知；
  • 蒙特卡洛（MC）：是一种采样的方法。依据大数定律，让样本均值逼近期望，缺点：必须完整采集一回合；
  • 时序差分（TD）：本章节介绍的方法。

2. 随机近似理论

2.1. 求期望的增量更新式

在蒙特卡洛中介绍增量更新时，我们给出了根据每次采样得到的新 $G_t$ 求取 $G(S_t)$ 均值的增量更新形式如下：

\[\begin{cases} N &\leftarrow N+1\\ G(S_t) &\leftarrow G(S_t) - \frac{1}{N} (G(S_t) - G_t) \end{cases}\]

将 $\frac{1}{N(S_t)}$ 替换为 $\alpha$，将待求量 $G(S_t)$ 写为 $w$，将即时获取的量记作 $x_k$，我们可以将其写为更加简洁的一般的形式

\[w_{k+1} \leftarrow w_k - \textcolor{red}{\alpha} (w_k - x_k)\]

其中，$\alpha$ 为步长参数，用来控制更新的速度。随着迭代次数 $k$ 的增加，$w_k$ 逐渐逼近 $x_k$ 的期望 $\mathbb{E}[X]$。

这种算法的优势在于它是渐进式的。一旦收到一个样本，就可以立即获得平均值估计值。然后，平均估算值就可以立即用于后续其他计算。在第 $k$ 步的时候，我不需要把前面所有的样本全部加起来再求平均，只需要通过上式一步的计算就可以得到一个新的平均数。

但是，在更新开始的时候因为数据量比较小，$w_k$ 难以非常精确的逼近 $\mathbb{E}[X]$。即由于样本不足，平均值估计在开始时并不准确。不过，有总比没有好，总比一直等到最后才能有一个数来得到一个平均数要强。在这个过程中就算不精确，也可以先凑合用着。随着样本的增多，数据越来越大，只要保证逐渐能够逼近期望就行。

随之而来的问题是：

  • 上述计算是否仍能保证收敛至 $\mathbb{E}[X]$？；
  • 上述计算属于什么类型的算法？

这里可以告诉大家，上述计算是 随机近似理论（Stochastic Approximation, SA） 的一个特殊形式，也是 随机梯度下降（Stochastic Gradient Descent, SGD） 的一个特殊形式。我们将在分别后面详细介绍。

2.2. Robbins-Monro（RM） 算法

2.2.1. 算法推导

随机近似理论是解决寻根（方程求解）或优化问题的一大类随机迭代算法的总称。与许多其他寻根（方程求解）算法（如基于梯度的方法，梯度下降或梯度上升）相比，其的强大之处在于它不需要知道目标函数的表达式，也不需要知道目标函数梯度的表达式。

其中，Robbins-Monro（RM）算法，是随机近似理论中的先驱性工作，它由 John Robbins 和 Paul Monro 在 1951 年提出。著名的随机梯度下降算法则是 RM 算法的一个特殊形式。该算法也可用来分析上述提到的均值估计的收敛性。

【问题描述】：假设需要求解 $g(w) = 0$ 的根，其中 $w\in\mathbb{R}, g:\mathbb{R}\rightarrow \mathbb{R}$。注意到：

  • 这个简单的寻根问题是许多其他复杂问题的最终形式，如假设 $J(w)$ 是一个待优化的目标函数，我们需要求解 $J(w)$ 的极值，问题就转化为 $g(w) = \nabla_w J(w)=0$（必要条件）；
  • 对于 $g(w)=c$ 这类问题的寻根也可转化为 $g(w) - c = 0$ 的寻根问题。

如果函数 $g$ 的表达式已知，那么采取很多数值方法就可以求解。但如果函数表达式未知，比如是一个神经网络，那么问题就变成我输入什么样的 $w$ 能够使神经网络的输出为 0 ？

【RM 算法】：是一种迭代式算法，的求解方法为

\[w_{k+1} = w_k-\alpha \tilde{g}(w_k,\eta_k), \quad k=1,2,\ldots\]

其中

  • $w_k$ 是第 $k$ 步的根的估计值；
  • $\tilde{g}(w_k,\eta_k) = g(w_k) + \eta_k$ 为第 $k$ 步的含噪观测；
  • $\alpha$ 为正的步长参数。

注意，上述求解过程不涉及 $g(w)$ 的表达式，他是一个黑箱。与之相对，算法的求解依赖数据，即

  • 输入序列：${w_k}$
  • 测量到的含噪输出序列：${\tilde{g}(w_k,\eta_k)}$

例：求解 $g(w) = \tanh(w-1)$ 真实根易知为 $w=1$ 采用 RM 算法，假设 $w_1=3,a_k=\frac{1}{k},\eta_k=0$，不含噪便于简化分析。那么迭代式如下

\[w_{k+1} = w_k-\frac{1}{k} g(w_k)\]

迭代结果如图所示，可以发现确实能收敛到真实根

RM算法迭代结果

2.2.2. 收敛性分析

下面给出收敛性证明的严格数学推导。如果满足以下三条约束，那么，RM 算法中 $w_k$ 可依概率（with probability 1, w.p.1）收敛至方程 $g(w^\star) = 0$ 的根 $w^\star$。

（1）梯度约束：

\[0<c_1\leq \nabla_w g(w)\leq c_2\]

  • 对于梯度约束，其要求梯度为某一个正值区间内，此时 $g(w)$ 单调递增， $g(w)=0$ 的根存在且唯一（注意，类似 $g(w) = e^w$ 是不满足此条件的，因为其导数在 $w\rightarrow -\infty$ 时趋于零，对于任意 $c_1>0$ 总能找到其导数小于 $c_1$ 的情况）；

  • 单调递增是一个严格约束，对于神经网络而言，假设 $J(w)$ 是一个待优化的目标函数，我们需要求解 $J(w)$ 的极值，问题就转化为 $g(w) = \nabla_w J(w)=0$，则梯度要求为 $\nabla_w^2 J(w) > 0$ 即 Hessian 矩阵是正定矩阵，对应原始函数是凹函数（不同约定下也可能定义为凸函数，本质上是单调且存在极值解的）；

（2）系数约束

\[\sum_{k=1}^{\infty} \alpha_k=\infty,\;\sum_{k=1}^{\infty}\alpha_k^2<\infty\]
  • $\sum_{k=1}^{\infty} \alpha_k^2<\infty$ 要求在 $k\rightarrow \infty$ 时系数 $a_k\rightarrow 0$ 即收敛至零；
    • 对于 RM 算法迭代式进行移项：$w_{k+1} - w_k = -\alpha_k\tilde{g}(w_k,\eta_k)$
    • 只有 $a_k\rightarrow 0$ 才能保证 $a_k\tilde{g}(w_k,\eta_k) \rightarrow 0$
    • 即 $w_{k+1} - w_k \rightarrow 0$
  • $\sum_{k=1}^{\infty} \alpha_k = \infty$ 要求系数 $\alpha_k\rightarrow 0$ 的收敛速度不能太快；
    • 对于 RM 算法迭代式进行移项累加后有：$w_{\infty} - w_1 = -\sum_{k=1}^\infty \alpha_k\tilde{g}(w_k,\eta_k)$
    • 假设 $w_{\infty}=w^\star$，那么若 $\sum_{k=1}^{\infty} \alpha_k < \infty$ 表明上式右项是有界的（若 $g(w)$ 恰好也有界）
    • 如果初始猜测 $w_1$ 距离根 $w^\star$ 特别远，$w_{\infty} - w_1$ 就会超出上面的界限，产生矛盾
    • 因此要求 $\sum_{k=1}^{\infty} \alpha_k = \infty$，保证我们可以任意选取 $w_1$
  • 最常见的可选系数序列是调和级数：$\alpha_k = \frac{1}{k}$

（3）误差约束：

\[\mathbb{E}[\eta_k\vert\mathcal{H}_k]=0,\;\mathbb{E}[\eta_k^2\vert\mathcal{H}_k]< \infty,\quad \mathcal{H}_k=\{w_k, w_{k-1},\cdots\}\]

  • 要求误差的均值是0，且方差是有界的；

  • 常见的观测误差是一系列独立同分布（iid）的随机噪声序列中进行采样，但不要求噪声是高斯的。

即使不满足上述三条约束中的某一条，RM 算法也可能有效，但是不能保证一定收敛，如：

  • 对于 $g(w) = w^3-5$ 不满足第一条梯度约束，但如果初始猜测比较好，算法依然能够（局部）收敛；
  • 在强化学习算法中经常令 $a_k$ 等于一个很小的值（学习率）而不是调和级数，显然不满足第二条系数约束，但是算法依然有效。

RM 算法收敛性证明需要用到更加古老的 Dvoretzky 收敛定理。其表述如下：

考虑一个随机过程 $w_{k+1} = (1-\alpha_k)w_k+\beta_k\eta_k$，其中

\[\{\alpha_k\}_{k=1}^{\infty},\{\beta_k\}_{k=1}^{\infty},\{\eta\}_{k=1}^{\infty}\]

都是随机序列，且 $\alpha_k\geq 0, \beta_k \geq 0$，那么当满足以下约束时，$w_k$ 依概率收敛至 0。

（1）系数约束：

\[\sum_{k=1}^{\infty} \alpha_k = \infty,\; \sum_{k=1}^{\infty} \alpha_k^2 < \infty,\; \text{and} \sum_{k=1}^{\infty} \beta_k^2 < \infty\; \text{uniformly w.p.1}\]

（2）误差约束：

\[\mathbb{E}[\eta_k\vert \mathcal{H}_k]=0,\;\mathbb{E}[\eta_k^2\vert \mathcal{H}_k] \leq C\; \text{w.p.1},\quad \mathcal{H}_k=\{w_k, w_{k-1},\cdots, \eta_{k-1},\cdots, \alpha_{k-1},\cdots,\eta_{k-1}\}\]

证明略，可参考如下链接。

Stochastic Approximation 随机近似方法的详解之（三）Dvoretzky’s convergence theorem 网页链接：https://blog.csdn.net/weixin_37726222/article/details/129306871

2.2.3. 回顾增量更新

考虑一个简单的均值估计问题，我们想要从一组独立统分不采样得到的样本 ${x}_i\in X$ 中计算均值

\[w = \mathbb{E}[X]\]

将原始问题转变为如下寻根问题，定义函数

\[g(w) \doteq w - \mathbb{E}[X]\]

我们的目标是求解 $g(w) = 0$，如果可以求解，相当于变相求出了期望。

由于期望是未知的，我们只能够获取到状态量的具体测量 $x$，那么定义对函数 $g(w)$ 的含噪观测为

\[\tilde g(w,x) \doteq w - x\]

注意到，上式可以进行如下变换

\[\begin{aligned} \tilde g(w,x) &\doteq w - x \\ &= w-x+\mathbb{E}[X]-\mathbb{E}[X]\\ &= (w-\mathbb{E}[X])+(\mathbb{E}[X]-x)\\ &= g(w) + \eta\\ &= \tilde{g}(w,\eta) \end{aligned}\]

根据 RM 算法，求解方程 $g(w)=0$ 的根可以通过如下迭代式进行

\[w_{k+1} = w_k - \alpha \tilde g(w_k,\eta_k) = w_k - \alpha_k (w_k - x_k)\]

观察发现其正好就是均值估计的增量更新算法迭代式。所以均值估计的增量更新算法是一种 RM 算法的特殊形式，自然收敛。

2.3. 随机梯度下降（SGD）

2.3.1. SGD 算法推导

考虑一个如下的一般优化问题

\[\min_w J(w) = \mathbb{E}[f(w,X)]\]

其中 $f(w,X)$ 的输出为标量，$X$ 是输入随机变量，$w$ 是待优化参数。求期望符号是针对 $X$ 的，即希望找到某个参数使得期望最小。

使用 梯度下降法（Gradient Descent, GD）进行求解

\[w_{k+1} = w_k - \alpha \nabla_w \mathbb{E}[f(w,X)] = w_k - \alpha \mathbb{E}{[\nabla_w f(w,X)]}\]

其中 $\alpha$ 是控制步长的参数。注意到求期望的本质就是求和，因此求梯度符号可以移到期望符号内。

上述求解过程的难点在于对梯度求期望，如果我们没有映射函数的显示表达式，那么我们无法直接求解。因此我们需要借助数据，采用批量梯度下降法或随机梯度下降法进行求解。

使用 批量梯度下降法（Batch Gradient Descent, BGD），梯度的期望可以近似表示如下

\[\begin{aligned} \mathbb{E}{[\nabla_w f(w,X)]} &\approx \frac{1}{N}\sum_{i=1}^N \nabla_w f(w_k,x_i)\\ w_{k+1} &= w_k-\alpha_k \frac{1}{N}\sum_{i=1}^N \nabla_w f(w_k,x_i) \end{aligned}\]

上述求解过程仍然唇在一个不足，即需要采样 $N$ 次获得梯度数据才能迭代计算一步。我们进一步采用随机梯度下降法解决这个不足。

使用 随机梯度下降法（Stochastic Gradient Descent, SGD），直接移除 $N$ 个梯度样本的求和，直接使用单个样本的梯度进行迭代

\[w_{k+1} = w_k-\alpha_k \nabla_w f(w_k,x_k)\]

可以看出，随机梯度下降是批量梯度下降取 $N=1$ 的一种特殊情况，相当于将真实梯度的期望替换为单个样本（随机）梯度。

2.3.2. SGD 收敛性分析

对于如下的一般优化问题

\[\min_w J(w) = \mathbb{E}[f(w,X)]\]

我们称 $g(w) = \mathbb{E}[\nabla_w f(w,X)]$ 为 true gradient，称其某次采样 $\nabla_w f(w_k,x_k)$ 为 stochastic gradient。易知，原始优化问题可以转化为一个梯度等于零 $g(w) = 0$ 这个方程求根问题，因为后者是前者能取到最优解的必要条件。

由于我们不知道 $\nabla_w f(w,X)$ 的表达式，我们可以测量到其含噪近似（本质就是 stochastic gradient）

\[\begin{aligned} \tilde{g}(w,\eta) &= \nabla_w f(w,x)\\ &=\textcolor{blue}{\mathbb{E}[\nabla_w f(w,X)]} + \textcolor{red}{\nabla_w f(w,x) - \mathbb{E}[\nabla_w f(w,X)]}\\ &= \textcolor{blue}{g(w)} + \textcolor{red}{\eta} \end{aligned}\]

根据 RM 算法，求根问题的迭代解法如下

\[w_{k+1} = w_k - \alpha_k \tilde{g}(w_k,\eta_k)\]

而前面说了 $\tilde{g}(w,\eta)$ 就是随机梯度，那么上式就是 SGD 的迭代表达式，因此 SGD 是一个特殊的 RM 算法，当满足三条约束时可收敛。

定义其第 $k$ 步迭代时的相对误差为

\[\delta_k = \frac{\vert \nabla_w f(w_k,x_k) - \mathbb{E}[\nabla_w f(w_k,X)]\vert}{\vert \mathbb{E}[\nabla_w f(w_k,X)] \vert}\]

又因为 $\mathbb{E}[\nabla_w f(w^\star,X)]=0$，代入得到

\[\delta_k = \frac{\vert\nabla_w f(w_k,x_k) - \mathbb{E}[\nabla_w f(w_k,X)]\vert}{\vert\mathbb{E}[\nabla_w f(w_k,X)]-\mathbb{E}[\nabla_w f(w^\star,X)] \vert} = \frac{\vert\nabla_w f(w_k,x_k) - \mathbb{E}[\nabla_w f(w_k,X)]\vert}{\vert\mathbb{E}[\nabla_w^2 f(\tilde{w}_k,X)(w_k-w^\star)] \vert}\]

其中，分母部分的变换利用了中值定理，使得 $w_k-w^\star$ 项出现。

中值定理：$f(x_1) - f(x_2) = f^\prime(x_3)(x_1 - x_2)$ 其中 $x_3\in[x_1, x_2]$

假设分母的二阶梯度 $\nabla_w^2f(w_k,X)\geq c >0$，其中 $c$ 是一个正的常值。那么分母可进一步化简得

\[\begin{aligned} \vert\mathbb{E}[\nabla_w^2 f(\tilde{w}_k,X)(w_k-w^\star)] \vert &= \vert\mathbb{E}[\nabla_w^2 f(\tilde{w}_k,X)]\cdot (w_k-w^\star) \vert\\ &= \vert\mathbb{E}[\nabla_w^2 f(\tilde{w}_k,X)]\vert \cdot \vert w_k-w^\star \vert\\ &\geq c \cdot \vert w_k-w^\star \vert \end{aligned}\]

带如相对误差的表达式有

\[\delta_k \leq \frac{\overbrace{\vert\nabla_w f(w_k,x_k)}^{\text{stochastic gradient}} - \overbrace{\mathbb{E}[\nabla_w f(w_k,X)]\vert}^{\text{true gradient}}}{\underbrace{c \cdot \vert w_k-w^\star \vert}_{\text{distance to optimal solutiion}}}\]

上式给出了 SGD 算法有趣的收敛模式：

  • 如果 $w_k$ 距离最优解 $w^\star$ 越远，那么相对误差 $\delta_k$ 越小，即 SGD 算法的收敛速度越快；
  • 如果 $w_k$ 距离最优解越近，那么相对误差 $\delta_k$ 越大，即 SGD 算法的收敛速度越慢。

这意味着，初始时刻 SGD 算法与 GD 算法很类似，随机梯度与真实梯度之间的相对误差较小，SGD 算法会快速收敛到最优解附近；随着迭代次数的增加，$w_k$ 收敛至最优解 $w^\star$ 时 SGD 的收敛速度反而变慢，收敛过程的随机性增加。

2.3.3. 回顾增量更新

考虑如下优化问题

\[\min_w J(w) = \mathbb{E}[f(w,X)]=\mathbb{E}\left[\frac{1}{2}\vert\vert w-X \vert\vert^2\right]\]

令梯度 $\nabla_w J(w)$ 等于零，考虑到 $w$ 不是随机变量，显然有 $\mathbb{E}[w-x]=0 \Rightarrow w^\star = \mathbb{E}[X]$。

如果假设不知道函数的显示表达式，使用 GD 和 SGD 来求解，有

\[\begin{aligned} GD: \quad &w_{k+1} = w_k - \alpha \nabla_w \mathbb{E}[f(w,X)] = w_k - \alpha \mathbb{E}[w_k-X]\\ SGD: \quad &w_{k+1} = w_k - \alpha \nabla_w f(w,x_i) = w_k - \alpha [w_k-x_k] \end{aligned}\]

观察发现第二式其正好就是均值估计的增量更新迭代式，所以均值估计的增量更新算法是 SGD 算法的特殊形式，自然收敛。

2.3.4. SGD 的确定性形式

在前述 SGD 定义中，我们涉及到随机变量 $X$ 及其期望 $\mathbb{E}[X]$，而我们在实际任务中会经常遇到另一种很类似但是不涉及随机变量的确定形式。考虑如下一般的优化问题

\[\min_w J(w) = \frac{1}{N}\sum_{i=1}^N f(w,x_i),\quad x_i\in\{x_i\}_{i=1}^N\]

其中，$x_i$ 是一组确定的样本，不再是随机变量的采样。

又假设样本数据集中没取出一个数代价很大（很慢或者很耗费成本），我们每次只能取出一个数进行计算，那么我们可以将迭代求解的形式写为

\[w_{k+1} = w_k - \alpha \nabla_w f(w_k,x_k)\]

上述过程和 SGD 形式几乎完全一样，只是 $x_i$ 从随机变量变为了确定的样本。此时有如下几个问题思考：

  • 上面的迭代式是否是 SGD？
  • 每次采样一个样本时需要对其进行大小排列后采样，还是随机采样？

实际上，我们可以人为引入一个定义在样本数据集 ${x_i}_{i=1}^N$ 上的随机变量 $X$ 且其概率分布为均匀分布（$p(X=x_i)=\frac{1}{N}$），此时确定性优化问题就转变为一个随机优化问题

\[\min_w J(w) =\frac{1}{N}\sum_{i=1}^N f(w,x_i) = \mathbb{E}[f(w,X)]\]

其中，

  • 后一个等式是严格成立的而不是近似，因此上述确定性形式的问题就是 SGD 算法；
  • 随机变量 $X$ 需要从样本集中均匀随机抽取。

2.3.5. BGD、MBGD 和 SGD

在 SGD 的算法推导中我们按照 GD、BGD 到 SGD 的过程逐步推导。现在我们进一步分析其中 BGD 与 SGD 和一种新的 Mini-batch Gradient Descent（MBGD）算法的关系。

考虑如下一般形式的优化问题

\[\min_w J(w) = \mathbb{E}[f(w,X)]\]

使用 BGD、SGD 和 MBGD 算法求解上述问题的迭代式分别如下：

\[\begin{aligned} \text{BGD}:\quad w_{k+1} &= w_k - \alpha \nabla_w \frac{1}{n} \sum_{i=1}^n f(w_k,x_i)\\ \text{MBGD}:\quad w_{k+1} &= w_k - \alpha \nabla_w \frac{1}{m} \sum_{j\in\mathcal{I}_k} f(w_k,x_k)\\ \text{SGD}:\quad w_{k+1} &= w_k - \alpha \nabla_w f(w_k,x_k) \end{aligned}\]

其中，MBGD 中的 $\mathcal{I}_k$ 是样本空间的一个子集，是从样本空间中独立随机采样 $m$ 次得到的样本集合。

  • 相比 SGD，MBGD 因为用到了更多的样本数据，从而使其随机性更小。当 $m=1$ 时 MBGD 就退化成了 SGD；
  • 相比 BGD，MBGD 由于采样的样本数目更少，因此其效率更高；
  • 注意，当 $m=n$ 时 MBGD 并不等同于 BGD，因为 MBGD 的数据是从原始样本集中均匀随机采样的（某样本可能没被采样到也可能被使用多次），而 BGD 是对所有样本数据都仅使用一次。

下面分别采用上述三种方法，给出对 $ x,y\in [-10, +10] $ 区间的 100 个样本（均值为 $(0,0)$ 的随机撒点）求均值的结果示意图。其中左图是三种方法的迭代收敛路径，有图为三种方法迭代过程中预测值与真实均值的距离变化情况。需要关注的是不同方法的收敛速度。

bgd-mbgd-sgd-comparison.jpg

3. 时序差分法

3.1. 时序差分思想（Temporal Difference）

3.1.1. 从蒙特卡洛的角度分析

根据前面的章节我们知道，即使采用增量更新技巧，蒙特卡洛方法也必须要等整个回合采样结束之后才能计算得到这一次的回报 $G_{t}$。那么有没有一种方法能够无须完整采样一个回合就能更新价值函数呢？我们以状态价值函数为例，观察回报的定义式：

\[\begin{aligned} G_t \doteq \sum_{k=0}^{\infty} \gamma^k R_{t+k+1} &= R_{t+1}+\sum_{k=0}^{\infty} \gamma^{k} R_{t+k+2}\\ &= R_{t+1}+\gamma V_{t+1} \end{aligned}\]

然后带入蒙特卡洛的价值函数增量更新策略，即

\[\begin{aligned} \text{MC}:\quad & v(S_t) \leftarrow v(S_t)+\alpha({\color{red}G_t}-v(S_t)) \\ \text{TD}:\quad & v(S_t) \leftarrow v(S_t)+\alpha({\color{red}R_{t+1}+\gamma v(S_{t+1})}-v(S_t)) \end{aligned}\]

上述第二行递推式就是本章所要介绍的 时序差分法（Temporal Difference Learning, TD）。

可以发现，时序差分法只需要采样一次，即可利用下一时刻下一状态的状态价值函数，来更新我们当前时刻当前状态的状态价值函数，注意这里涉及到了两种关于时间的概念（当前时刻 vs 下一时刻、当前状态 vs 下一状态），为避免混淆，详细展开如下：

  • 当前时刻 $t$，每一个当前状态 $S_t$ 对应状态价值函数 $V(s_t)$；
  • 下一时刻 $t+1$，每一个下一时刻状态 $S_{t+1}$ 对应状态价值函数 $V(s_{t+1})$；
  • 在当前时刻从某个具体状态 $S_t=s_t$ 出发，下一时刻转移至 $S_{t+1}=s_{t+1}$ 后，使用 $v_{\textcolor{red}{t}}(\textcolor{blue}{s_{t+1}})$ 来计算 $v_{\textcolor{red}{t+1}}(\textcolor{blue}{s_t})$；
  • 其他不涉及状态转移的状态，他们的价值函数保持不变，即 $v_{t+1}(s)=v_{t}(s),\; s\neq s_t$

综上，经过一些移项，时序差分法的迭代公式为

\[\begin{cases} v_{t+1}(s_t) = v_t(s_t)-\alpha_t(s_t)\big[v_t(s_t)-[r_{t+1}+\gamma v_t(s_{t+1})]\big]\\ v_{t+1}(s) = v_t(s),\; s\neq s_t \end{cases}\tag{1}\]

我们将时序差分法迭代式的各个部分做如下标注

\[\underbrace{v_{t+1}(s_t)}_{\text{new estimate}} = \underbrace{v_t(s_t)}_{\text{old estimate}}-\alpha_t(s_t)\big[\overbrace{v_t(s_t)-[\underbrace{r_{t+1}+\gamma v_t(s_{t+1})}_{\text{TD target }\bar{v}_t}}^{\text{TD error }\delta_t}]\big]\]
  • TD Target

时序差分法的迭代式中，迭代目的就是将 $v(s_t)$ 朝着 $\bar{v}_t$ 的方向改进，所以称其为 TD Target。

将迭代式改写如下

\[\begin{aligned} &v_{t+1}(s_t) = v_t(s_t)-\alpha_t(s_t)[v_t(s_t) - \bar{v}_t]\\ \Rightarrow \; &v_{t+1}(s_t) - \textcolor{red}{\bar{v}_t} = v_t(s_t)-\textcolor{red}{\bar{v}_t}-\alpha_t(s_t)[v_t(s_t) - \bar{v}_t]\\ \Rightarrow \; &v_{t+1}(s_t) - \textcolor{red}{\bar{v}_t}= [1-\alpha_t(s_t)] \cdot [v_t(s_t) - \textcolor{red}{\bar{v}_t}]\\ \Rightarrow \; &\vert v_{t+1}(s_t) - \textcolor{red}{\bar{v}_t}\vert = \vert 1-\alpha_t(s_t)\vert\cdot \vert v_t(s_t) - \textcolor{red}{\bar{v}_t}\vert\\ \end{aligned}\]

由于 $0<1-\alpha_t(s_t)<1$，所以有

\[\vert v_{t+1}(s_t) - \textcolor{red}{\bar{v}_t}\vert \leq \vert v_t(s_t) - \textcolor{red}{\bar{v}_t}\vert\]

也即 $v_{t+1}(s_t)$ 距离 TD Target 更近！

  • TD Error

TD Error 定义为

\[\delta_t = v_t(s_t)-[r_{t+1}+\gamma v_t(s_{t+1})]\]

其反应了两个连续时刻前后状态的价值函数的差分（difference）。

更进一步，我们需要分析该差分随着迭代的变化。假设在当前策略 $\pi$ 下我们已经迭代收敛，价值函数已经收敛至 $v_\pi(s)$，将 TD Error 定义式的下标进行改写，有

\[\delta_{\pi,t} = v_\pi(s_t) - [r_{t+1}+\gamma v_\pi(s_{t+1})]\]

分别对上式左右两边求期望，有

\[\mathbb{E}[\delta_{\pi,t}] = v_\pi(s_t) - \mathbb{E}[r_{t+1} + \gamma v_\pi(s_{t+1})] = 0\]

右侧等号成立的原因是因为，对于收敛的状态价值函数，其定义式就是

\[v_{\pi}(s_t) = \mathbb{E}[r_{t+1} + \gamma v_\pi(s_{t+1})]\]

因此，TD Error 衡量了 $v_t$ 和 $v_\pi$ 的偏差，同时其也反应了一步采样后从序列 $(s_t, r_{t+1}, s_{t+1})$ 中得到的新的信息，这个新的信息与当前旧的估计之间存在偏差，就可以利用这个偏差来更新 $v_t$。

3.1.2. 从 RM 算法的角度分析

可以证明时序差分算法迭代计算的状态价值函数 $v(s)$ 最终收敛至 $v_{\pi}(s)$，这需要用到我们前述介绍的 RM 算法，具体分析如下：

考虑如下的期望估计问题

\[w = \mathbb{E}[R+\gamma v(X)]\]

其中 $R,X$ 都是随机变量，$\gamma$ 是一个常数（折扣因子），$v(\cdot)$ 是一个函数（状态价值函数）。

假设我们能够采样得到样本 ${x}\in X,{r}\in R$，可定义函数 $g(w)$ 和其含噪观测 $g(w,\eta)$ 如下

\[\begin{aligned} g(w) &= w-\mathbb{E}[R+\gamma v(X)]\\ \tilde{g}(w,\eta) &= w-[r+\gamma v(x)]\\ &=(w-\mathbb{E}[R+\gamma v(x)])+(\mathbb{E}[R+\gamma v(x)])-[r+\gamma v(x)]\\ &\doteq g(w) + \eta \end{aligned}\]

上述问题变为方程 $g(w)=0$ 的寻根问题，对应的 RM 算法求解如下

\[w_{k+1} = w_{k} - \alpha_k \tilde{g}(w_k,\eta_k) = w_k - \alpha_k[w_k-(r_k+\gamma v(x_k))]\tag{2}\]

对比式（1）与式（2）可以发现形式完全一样，因此 TD 算法是收敛的。

3.1.3. 从贝尔曼期望方程的角度分析

虽然前面我们通过一个特殊形式的期望估计问题推导出 TD 算法是一种特殊形式的 RM 算法，并得到了收敛性保证，但我们并没有明确其一定能够收敛至 $v_\pi(s)$。下面我们从贝尔曼期望方程的角度分析 TD 算法的收敛性，只有通过贝尔曼期望方程才能严格证明这一点。

对于状态价值函数，贝尔曼期望方程如下

\[v_\pi(s) = \mathbb{E}[R+\gamma v_\pi(S^\prime)\vert s], \;s\in S\]

使用 RM 算法求解贝尔曼期望方程，需要转化为 $g(v(s))=0$ 的求根问题 ，其中函数 $g(v(s))$ 如下

\[g(v(s)) = v(s) - \mathbb{E}[R+\gamma v_\pi(S^\prime)\vert s]\]

我们仅能采样得到 $s,r, s^\prime$，则含噪观测 $g(v(s),\eta)$ 如下

\[\begin{aligned} \tilde{g}(v(s),\eta) &= v(s) - [r+\gamma v_\pi(s^\prime)]\\ &= v(s) - \mathbb{E}[R+\gamma v_\pi(s^\prime)\vert s] + \mathbb{E}[R+\gamma v_\pi(s^\prime)\vert s] - [r+\gamma v_\pi(s^\prime)]\\ &= g(v(s)) + \eta \end{aligned}\]

那么 RM 算法的迭代式如下

\[\begin{aligned} v_{k+1}(s) &= v_k(s) - \alpha_k \tilde{g}(v_k(s),\eta_k)\\ &= v_k(s) - \alpha_k [v_k(s) - [\textcolor{blue}{r_k}+\gamma \textcolor{blue}{v}_{\textcolor{red}{\pi}}(\textcolor{blue}{s^\prime_k})]] \end{aligned}\]

虽然上述迭代式已经和 TD 算法的迭代式很相似，但是需要注意以下两点不同：

  • 在每一步迭代中，我们需要频繁采样多次同样的序列 $(s,r, s^\prime)$ 才能完成对状态 $v(s)$ 的更新（蓝色标记）；
  • 在每一步迭代中，注意式中要求 $v_\pi(s^\prime)$ 是已知的，但实际上是不知道的！（红色标记）。

对于第一个假设，我们实际采样一个回合后，对于其中每一个片段 $(r_t, r_{t+1},s_{t+1})$ 替代 $(s,r, s^\prime)$，采到谁我们就更新谁的价值函数。

对于第二个假设，我们就用当前时刻的 $v_k(s^\prime_k)$ 替换掉 $v_\pi(s^\prime)$（开放式思考，替换后能保证收敛么？）。

TD 算法的严格收敛证明依赖 RM 算法，此处略。

最后我们可以发现，TD 算法就是用于求解贝尔曼期望方程的一种特殊的 RM 算法。

3.1.4. TD 与 MC 的比较

  • 在线与离线：
    • TD 方法：在线；
    • MC 方法：离线；
  • 无限采样与有限采样：
    • TD 方法：支持无限采样；
    • MC 方法：仅支持有限采样；
  • 自举与否：
    • TD 方法：自举；
    • MC 方法：非自举；
  • 方差与偏差：
    • TD 方法：高偏差，低方差。因为 TD 方法只需要一次采样，其中涉及到的随机变量少，随机性少，因此方差小。但是由于其依赖初值估计，如果估计不准会带来很大的偏差，虽然最终随着采样次数的增多也能收敛到正确的值。
    • MC 方法：低偏差，高方差。因为 MC 方法不涉及任何初值估计，其均值的估计是对期望的无偏估计，因此在迭代过程中偏差比较小，但因为他每一次采样都是“天马行空”的，因此不同的采样可能差距非常大，方差就会很大。

3.2. 同策略时序差分（SARSA）

3.2.1. SARSA

前述 TD 算法针对状态价值函数进行估计，将其推广至状态-动作价值函数估计后，得到本节介绍的时序差分方法的一个具体算法，即 SARSA 算法：

\[q(s_t,a_t) \leftarrow q(s_t,a_t)-\alpha\{q(s_t,a_t)-[r_{t+1}+\gamma q(s_{t+1},a_{t+1})]\}\\\]

注意到，上述迭代式需要与进行两次动作采样才能得到足够的经验数据进行一步迭代：

\[s_t\mathop{\longrightarrow}\limits^{\pi}a_t\mathop{\longrightarrow}\limits^{\text{model}}r_t,s_{t+1}\mathop{\longrightarrow}\limits^{\pi}a_{t+1}\]

观察经验数据的一般形式 $(S_t,A_t, R_{t+1}, S_{t+1}, A_{t+1})$，取首字母放在一起命名本方法。

  • 行为策略

经验获取过程需要进行两次动作采样，对于 SARSA 而言，两次动作采样时使用的策略是相同的。延续我们之前在 Monte Carlo 方法中讨论的结果，策略一般选取为 $\varepsilon$-greedy 策略，兼顾探索和利用。由于这个策略的第一次采样需要实际执行产生环境交互，因此称其为 行为策略。具体而言：

  • 只在第一步策略采样后实际执行动作，即 $s_t\mathop{\longrightarrow}\limits^{\pi}a_t\mathop{\longrightarrow}\limits^{\text{model}}r_t,s_{t+1}$ 过程；
  • 第二步策略采样只是为了能够得到具体的 $Q(S_{t+1},A_{t+1})$ 用于迭代式的求解，并不实际执行采样得到的 $A_{t+1}$。

上述迭代式仍然是一个策略评估过程，即在 给定策略 $\pi$ 的条件下，给出当前策略下 $q_\pi(s,a)$ 的估计。将其与特定的策略改进方法结合可以得到完整的 TD 形式的方法。

  • 目标策略

我们定义策略改进时被改进的策略叫 目标策略，那么对于 SARSA 而言，目标策略和行为策略是同一个策略。也就是说，SARSA 算法的自然流程表明，策略改进是针对前面的 $\varepsilon$-greedy 行为策略进行改进。

有人可能会问，为什么目标策略和行为策略是相同的？能不同么？ 大家可以尝试脑补一下：

  • 上一轮迭代已有旧的 $Q$ 函数；
  • 在策略评估阶段，基于 $\varepsilon$-greedy 行为策略采集经验更新 $Q$ 函数；
  • 在策略改进阶段，如果更新一个新的目标策略，可选的无非就是 greedy 策略；
  • 在下一时刻策略评估阶段，再次基于 $\varepsilon$-greedy 行为策略采集经验，这时需要用到新的 $Q$ 函数按照 $\varepsilon$ 概率来选择动作，不就相当于隐式更新了 $\varepsilon$-greedy 行为策略自身么？额外更新的 greedy 策略没有任何意义；

所以，并不是人们强行设定 SARSA 在策略改进时，必须针对 行为策略=目标策略 来改进，而是整个算法自然的流程导致的结果如此。

总结如下：

  • 行为策略：
    • 第一次动作采样： $\varepsilon$-greedy 策略
    • 第二次动作采样： 相同的 $\varepsilon$-greedy 策略
  • 目标策略：
    • 相同的 $\varepsilon$-greedy 策略

最终形成 SARSA 方法的伪代码如下：

  • Initialize $q(s,a)$ arbitrarily, choose start state $s$, given a behaviour policy $\pi_t$ (e.g., $\varepsilon$-greedy)
  • Repeat (for each episode):
    • Repeat (if $s$ is not terminal state):
      • collect experience:
        • choose $a$ at $s$ following $\pi_t$
        • take action $a$, get $r$, transfer to $s^\prime$
        • choose $a^\prime$ at $s^\prime$ following $\pi_t$
      • policy evaluation:
        • ${q(s,a)\leftarrow q(s,a)-\alpha[q(s,a) - (r+\gamma q(s^\prime,a^\prime))]}$
      • policy improvement:
        • (update same $\varepsilon$-greedy as target policy)
        • $\pi_{t+1}(a\vert s) = 1-\frac{\varepsilon}{\vert \mathcal{A} \vert}(\mathcal{A}-1)$ if $a=\arg\max_a q(s,a)$
        • $\pi_{t+1}(a\vert s) = \frac{\varepsilon}{\vert \mathcal{A} \vert}$ otherwise
        • ${s\leftarrow}s^\prime; a\leftarrow a^\prime$
      • $t \leftarrow t+1$

使用 SARSA 方法在 Grid World 中进行实验。设定初始状态为左上角格子，相关参数设置为 $r_{target}=0, r_{forbidden}=r_{boundary} = -10, r_{other}=-1,\gamma = 0.9,\alpha = 0.1$，迭代 500 步如下图所示：

sarsa-result

  • 左子图表明，
    • 经过 500 步迭代，从左上角格子出发已经找到了对应的较优的路径；
    • 除了左上角格子外，其他格子对应的策略明显不是最优的，需要经过更多步探索才能收敛到最优策略。
  • 右子图表明，
    • 随着迭代次数的增加，每个 episode 探索的步长逐渐降低，对应的总奖励逐渐升高；
    • 总奖励值依然为负数，因为采用 $\varepsilon$-greedy 策略会引入大量非最优探索，导致状态价值的估计偏低。

3.2.2. Expected SARSA

我们可以对 SARSA 的策略评估部分进行改进，不再进行采样得到动作 $a^\prime$，而是使用 $q$ 的期望（也就是 $v$），此时的迭代式即为 期望 SARSA

\[\begin{aligned} q(s,a) &\leftarrow q(s,a)-\alpha\{q(s,a)-(r+\gamma \mathbb{E}_\pi[q(s^\prime,A)])\}\\ q(s,a) &\leftarrow q(s,a)-\alpha[q(s,a)-(r+\gamma V(s^\prime))]\\ \end{aligned}\]
  • 优势：偏差更小（因为只需要 $(s,a,r,s^\prime)$，不需要做第二次动作采样得到 $a^\prime$，随机性更小）
  • 劣势：计算量大幅增加（因为需要计算多个 $q$ 值后取平均）。

期望 SARSA 本质上是求解如下贝尔曼期望方程

\[q_\pi(s,a) = \mathbb{E}[R+\gamma v_\pi(s^\prime)\vert s,a]\]

3.2.3. n-step SARSA

SARSA 的策略评估部分是一种一步更新的方法，即每次更新只使用一步的采样数据。我们可以将 SARSA 的策略评估部分泛化到 $n$ 步更新，即每次更新使用 $n$ 步的采样数据。这本质上是将 SARSA 和 MC 方法进行融合。考虑回报的不同展开形式

\[\begin{aligned} \text{SARSA} \; \leftarrow \; G_t^{(1)} &= R_{t+1}+\gamma Q(S_{t+1},A_{t+1})\\ G_t^{(2)} &= R_{t+1}+\gamma R_{t+2}+\gamma^2 Q(S_{t+2},A_{t+2})\\ \vdots\\ \text{n-step SARSA} \; \leftarrow \; 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})\\ \vdots\\ \text{MC} \; \leftarrow \; G_t^{(\infty)} &= R_{t+1}+\gamma R_{t+2}+\cdots+\gamma^{n-1} R_{t+n}+\cdots \end{aligned}\]

将上述不同的回报展开形式代入 $q(s,a)$ 关于回报的定义式，然后再代入期望 SARSAR 迭代式，可以得到 $\boldsymbol{n}$-step SARSA 这种介于 SARSA 和 MC 方法之间的迭代式

\[q_\pi(s,a)\leftarrow q_\pi(s,a)-\alpha[q_\pi(s,a) - G_t^{(n)}]\]
  • 当 $n=1$ 时，$n$-step SARSA 等价于 SARSA（很显然）；
  • 当 $n=\infty$ 时，$n$-step SARSA 等价于 MC 方法（请尝试推导，需要额外定义 $\alpha=1$）。

3.3. 异策略时序差分（Q-Learning）

3.3.1. Q-Learning

在 SARSAR 算法的行为策略是 $\varepsilon$-greedy 策略，但在第二次动作采样时，我们只是为了计算后续 $Q$ 值而并不需要与环境进行交互。此时继续采用 $\varepsilon$-greedy 策略并不会对探索产生影响。

实际上，在下一时刻状态 $s^\prime$ 下，明显存在一个理论更优的确定性策略（也即贪婪策略）可供我们选择动作

\[a^*=\pi(s^\prime) = \arg\max_a\; q(s^\prime, a)\]

此时我们不需要进行第二次动作采样，而是直接找到下一时刻状态下已知的最大 $q(s^\prime, a)$，就使用这个值对应的 $a$ 来更新 $q(s,a)$。这种方法即为 Q-Learning。对应的策略评估迭代式如下

\[q(s,a) \leftarrow q(s,a)-\alpha\{q(s,a)-[r+\gamma \arg\max_a q(s^\prime,a)]\}\\\]

经过上述操作，迭代式就不再是求关于某个策略 $\pi$ 的状态-动作价值函数值 $q_\pi(s,a)$，而是直接求 状态-动作价值函数的最优值 $q_\star(s,a)$ 的估计，直接对应全局最优策略（贪婪策略）。因此，Q-Learning 在策略改进时更新的 目标策略 自然就是 贪婪策略。

注意到，上述内容只是围绕第二次动作采样展开的，并没有对第一次动作采样使用的 行为策略 做出任何约束，我们可以沿用 SARSA 的 $\varepsilon$-greedy 策略，也可以使用一些别的策略，如均匀随机采样策略，甚至直接使用人类决策来进行采样都可以。

总结如下：

  • 行为策略（第一次动作采样）：$\varepsilon$-greedy 策略、uniform 策略、人类等；
  • 第二次动作选取：greedy 策略
  • 目标策略：greedy 策略

Q-Learning 的伪代码如下：

  • Initialize $Q(s,a)$ arbitrarily, choose start state $s$, given a behaviour policy $\textcolor{red}{\pi_b}$ (e.g., $\varepsilon$-greedy, uniform, human, etc)
  • Repeat (for each episode):
    • Repeat (if $s$ is not terminal state):
      • collect experience:
        • choose $a$ at $s$ following $\textcolor{red}{\pi_b}$
        • take action $a$, get $r$, transfer to $s^\prime$
        • choose $a^\prime= \arg\max_a q(s^\prime, a)$
      • policy evaluation:
        • ${q(s,a)\leftarrow q(s,a)-\alpha[q(s,a) - (r+\gamma q(s^\prime,a^\prime))]}$
      • policy improvement:
        • (update greedy policy as target policy)
        • $\pi_{t+1}(a\vert s) = 1$ if $a=\arg\max_a q(s,a)$
        • $\pi_{t+1}(a\vert s) = 0$ otherwise
        • ${s\leftarrow}s^\prime; a\leftarrow a^\prime$
      • $t \leftarrow t+1$

标红的部分即为 Q-Learning 与 SARSA 算法伪代码中的区别所在，这使得二者分属不同的时序差分方法，这将在下一节详细分析。

注意到，Q-Learning 是 off-policy 方法，因此伪代码中 policy improvement 实际上是不必要的，其目标策略是贪婪策略，当 $q(s,a)$更新时自然会被更新，不需要进行额外的策略改进。

3.3.2. 同策略与异策略

为了更加清晰地区分 SARSA 和 Q-learning，我们对这两种典型的 TD 算法中提到的目标策略和行为策略再次明确定义如下：

  • 行为策略：用于和环境交互产生样本的策略；
  • 目标策略：基于价值函数一直保持更新直至最优的策略。

当行为策略和目标策略相同时，称其为 同策略（on-policy）时序差分方法，不论是和环境交互还是被持续改进，都是同一个策略。当行为策略和目标策略不同时，就称其为 异策略（off-policy）时序差分方法。

按照上述定义，我们可以看出，SARSA 是一种同策略（on-policy）时序差分方法，因为其采样和更新的均为同一个策略（都是 $\varepsilon$-greedy 策略），而 Q-Learning 是一种异策略（off-policy）时序差分方法，因为其行为策略是 $\varepsilon$-greedy 策略，但更新的策略是 greedy（贪婪）策略，二者不同。

使用 off-policy 的好处在于，我们可以使用与目标策略不同的更加激进更加具备探索性的行为策略来与环境交互获得经验。行为策略越激进，那么能够探索到的状态动作对就越多，相应价值函数更新的频次就更高，探索效率就自然更高。注意，在 off-policy中，只要求行为策略与目标策略不同。行为策略本身可以随意选取，比如当目标策略是贪婪策略时，行为策略可以是 $\varepsilon$-greedy 策略，也可以是均匀随机策略（探索性更强），甚至是人在回路决策策略。

最后给出两个延伸问题供大家思考：

  • 思考1：MC 方法是同策略还是异策略？（同策略）
  • 思考2：怎么把 Q-Learning 改造成 on-policy 方法？（第一次动作采样使用$\varepsilon$-greedy，第二次动作选取使用greedy，目标策略使用 $\varepsilon$-greedy）

3.3.3. 不同行为策略的探索性

下面给出两种不同行为策略下 Q-Learning 探索 Grid World 的示例，场景设置与前述介绍 SARSA 时相同，唯一区别在于此处我们想找到所有状态下的最优策略，而不是某个初始状态的最优轨迹。

首先给出最优策略和其对应的状态价值函数作为参考，如下图所示

q-learning-result-optimal

  • 行为策略是均匀随机策略

设置行为策略是均匀随机策略，每个状态的五个动作 选取概率为 25%，采用异策略的 Q-Learning 方法迭代 100 万步，得到的结果如下图所示

q-learning-result-2

可以看出，均匀随机策略的探索性比较强，100 万步迭代后每个状态动作对都被多次采样到了。最终得到的最优策略估计（贪婪策略）如下图所示，下图右侧给出了状态价值函数与最优状态价值函数的差随迭代次数变化的曲线

q-learning-result-random

可以看出，最终得到的最优策略估计与真实的最优策略非常接近。

  • 行为策略是有倾向的随机策略

接着，我们采用另外一个行为策略，设置所有状态下 向右走的概率提高至 50%，剩下 50% 概率由其他动作平分。很明显，这个策略的探索性不如上一个全部动作都均匀随机选择的策略，因为他多了一个向右的倾向性。得到的结果如下图所示

q-learning-result-special

可以看出，经过 100 万步迭代，仍然有很多状态动作对从没有被探索到，得到的状态价值函数估计与真实的最优值相差较大。继续提高向右走的概率，探索性会变得更弱，Q-Learning 方法的收敛速度更慢。

3.4. 总结

3.4.1. 表述形式总结

所有的 TD 算法可以表述为一个统一的形式

\[q_{t+1}(s_t,a_t) = q_t(s_t,a_t) - \alpha [q_t(s_t,a_t) - \textcolor{red}{\bar{q}_t}]\]

不同 TD 算法的差异都可以体现在对 TD Target（$\bar{q}_t$）的不同选择上

\[\begin{aligned} \text{SARSA:}\quad\bar{q}_t &= r_{t+1}+\gamma q_t(s_{t+1},a_{t+1})\\ n\text{-step SARSA:}\quad \bar{q}_t &= r_{t+1} + r_{t+2}+\cdots +\gamma^n q_t(s_{t+n},a_{t+n})\\ \text{Expected SARSA:}\quad\bar{q}_t &= r_{t+1}+\gamma \sum_a \pi(a\vert s_{t+1})q(s_{t+1},a)\\ \text{Q-Learning:}\quad\bar{q}_t &= r_{t+1}+\gamma \max_a q(s_{t+1},a)\\ \text{MC:}\quad\bar{q}_t &= r_{t+1} + \gamma r_{t+2} + \cdots + \gamma^{T-t-1} r_T,\text{ where }\alpha = 1 \end{aligned}\]

3.4.2. 求解方程总结

从求解贝尔曼方程的角度也可总结如下

\[\begin{aligned} \text{SARSA:}\quad \text{BE:} \quad&q_\pi(s,a) = \mathbb{E}[R_{t+1}+\gamma q_\pi(S_{t+1},A_{t+1})\vert St+s, A_t=a]\\ n\text{-step SARSA:}\quad \text{BE:} \quad&q_\pi(s,a) = \mathbb{E}[R_{t+1}+\gamma^2R_{t+2}+\cdots+\gamma^n q_\pi(S_{t+n},A_{t+n})\vert St+s, A_t=a]\\ \text{Expected SARSA:}\quad \text{BE:} \quad&q_\pi(s,a) = \mathbb{E}[R_{t+1}+\gamma \mathbb{E}_{A_{t+1}}[q_\pi(S_{t+1},A_{t+1})]\vert St=s, A_t=a]\\ \text{Q-Learning:}\quad \textcolor{red}{\text{BOE:}} \quad&q_\pi(s,a) = \mathbb{E}[R_{t+1}+\gamma \max_a q_\pi(S_{t+1},a)\vert St=s, A_t=a]\\ \text{MC:}\quad \text{BE:} \quad&q_\pi(s,a) = \mathbb{E}[R_{t+1}+\gamma R_{t+2}+\cdots+\gamma^{T-t-1} R_T\vert St=s, A_t=a] \end{aligned}\]

3.4.3. 行为表现总结

  • Q-Learning：包含 greedy 策略中取 max 操作，也就是不考虑可能走到很大负奖励的状态-动作，只考虑会不会最终获得最大奖励的状态-动作。如果某状态下某动作可以获得很大的奖励，那这条路就牛逼，所以 Q-Learning更勇猛，不害怕错，更激进;

  • SARSA：只要某状态周围有错（很大的负奖励），那么就有机会（$\varepsilon/\vert\mathcal{A}\vert$）获得这个不好的奖励，那么整条路反馈都会评分很差，之后会尽量避开。最终导致Sarsa会对犯错更敏感，会远离犯错的状态-动作，更保守。

4. 参考文献

[1] shuhuai008. bilibili【强化学习】(SARSA) 时序差分-同轨策略TD控制

[2] 莫烦. 什么是 Sarsa (强化学习)

Academic, Knowledge
python reinforcement learning
本文由作者按照 CC BY 4.0 进行授权
最近更新
文章内容

强化学习（蒙特卡洛法）

强化学习（值函数近似）