Monte-Carlo and Temporal Difference

蒙特卡洛与时序差分

动态规划算法建立在已知或习得的环境模型的基础上，而对于大部分强化学习环境来说其环境模型未知并且难以学习，也就无法通过动态规划求解，此时智能体只能通过环境交互数据来直接或间接学习到最优策略。

蒙特卡洛方法（Monte-Carlo）

蒙特卡洛算法是一大类随机算法的总称，在后续的强化学习算法中被广泛应用，例如：

近似期望

为了估计随机变量函数 $f(\boldsymbol{x}) : \Omega \mapsto \mathbb{r}$ 关于服从分布 $p(\boldsymbol{x})$ 的随机变量 $\boldsymbol{x}$ 的数学期望：

$\mathcal{E}_{\boldsymbol{x} \sim p(\boldsymbol{x})} \Big[ f(\boldsymbol{x}) \Big] = \int_{\Omega} f(\boldsymbol{x}) p(\boldsymbol{x}) d\boldsymbol{x}$

可以通过分布 $p(\boldsymbol{x})$ 进行独立非均匀采样得到 $\mathcal{X}_{n} = \{ \boldsymbol{x}_{1},\ \boldsymbol{x}_{2},\ \cdots,\ \boldsymbol{x}_{n} \}$，通过样本函数值的均值来近似期望：

$q_{n} = \frac{1}{n} \sum_{i = 1}^{n} f(\boldsymbol{x}_{i}) \approx \mathcal{E}_{\boldsymbol{x} \sim p(\boldsymbol{x})} \Big[ f(\boldsymbol{x}) \Big]$

在实际中通常使用增量更新的方式进行计算：

$q_{n} = \frac{1}{n} \sum_{i = 1}^{n} f(\boldsymbol{x}_{i}) = \frac{1}{n} \bigg[ (n - 1) q_{n - 1} + f(\boldsymbol{x}_{n}) \bigg] = q_{n - 1} + \frac{1}{n} \Big( f(\boldsymbol{x}_{n}) - q_{n - 1} \Big)$

进一步使用学习率 $\alpha_{n}$ 来替换式中的 $\dfrac{1}{n}$ 得到 $q_{n} = q_{n - 1} + \alpha_{n} \Big( f(\boldsymbol{x}_{n}) - q_{n - 1} \Big)$，其中 $\alpha$ 需要满足以下性质：

$\lim_{n \to \infty} \sum_{t = 1}^{n} \alpha_{t} = \infty \qquad \lim_{n \to \infty} \sum_{t = 1}^{n} \alpha_{t}^{2} < \infty$

随机梯度

当 $\boldsymbol{x}$ 服从分布 $p(\boldsymbol{x})$ 时，为了求解以下形式的优化问题（例如神经网络）：

$\min_{\theta} \mathcal{E}_{\boldsymbol{x} \sim p(\boldsymbol{x})} \Big[ \ell(\boldsymbol{x};\ \theta) \Big]$

在损失函数 $\ell$ 可微时，可以利用梯度下降对模型参数 $\theta$ 进行更新，其中对参数 $\theta$ 的梯度为：

$\boldsymbol{g} = \nabla_{\theta} \mathcal{E}_{\boldsymbol{x} \sim p(\boldsymbol{x})} \Big[ \ell(\boldsymbol{x};\ \theta) \Big] = \mathcal{E}_{\boldsymbol{x} \sim p(\boldsymbol{x})} \Big[ \nabla_{\theta} \ell(\boldsymbol{x};\ \theta) \Big]$

利用蒙特卡洛近似期望的方法，通过一个批次的样本集合 $\mathcal{X}_{b} = \{ \boldsymbol{x}_{1},\ \boldsymbol{x}_{2},\ \cdots,\ \boldsymbol{x}_{b} \}$ 即可对梯度进行估计

$\hat{\boldsymbol{g}} = \frac{1}{b} \sum_{i = 1}^{b} \nabla_{\theta} \ell(\boldsymbol{x}_{i};\ \theta)$

蒙特卡洛策略评估

为了评估一个策略 $\pi$ 的状态价值函数 $v_{\pi}(s)$，可以通过 $\pi$ 采样若干条序列：

$s_{0}^{(i)} \overset{a_{0}^{(i)}}{\longrightarrow} r_{1}^{(i)},\ s_{1}^{(i)} \overset{a_{1}^{(i)}}{\longrightarrow} r_{2}^{(i)},\ s_{2}^{(i)} \overset{a_{2}^{(i)}}{\longrightarrow} \cdots \overset{a_{\mathrm{T} - 1}^{(i)}}{\longrightarrow} r_{\mathrm{T}}^{(i)},\ s_{\mathrm{T}}^{(i)}$

通过采样的序列中以状态 $s_{t}$ 为初始状态的局部子序列获得的局部回报 $g_{t}$ 来估计回报的期望：

$n(s_{t}) \leftarrow n(s_{t}) + 1 \qquad v(s_{t}) \leftarrow v(s_{t}) + \frac{1}{n(s_{t})} \Big( g_{t} - v(s_{t}) \Big)$

同样地可以使用超参数 $\alpha$ 来代替 $\dfrac{1}{n}$，$\alpha$ 也可以取做常数，此时更新方式不再严格遵循蒙特卡洛估计方法：

$v(s_{t}) \leftarrow v(s_{t}) + \alpha \Big( g_{t} - v(s_{t}) \Big)$

时序差分方法（Temporal Difference）

单步时序差分

在使用蒙特卡洛方法估计某个策略 $\pi$ 的状态价值函数时需要等待序列采样完毕才能够进行计算，而通过时序差分方法可以在每次状态转移时通过转移四元组 $(s_{t},\ a_{t},\ r_{t + 1},\ s_{t + 1})$ 进行自举并在线更新：

$v(s_{t}) \leftarrow v(s_{t}) + \alpha \Big[ r_{t + 1} + \gamma v(s_{t + 1}) - v(s_{t}) \Big]$

式中的 $\delta_{t}^{(1)} = r_{t + 1} + \gamma v(s_{t + 1}) - v(s_{t})$ 为 TD 误差项，$g_{t}^{(1)} = r_{t + 1} + \gamma v(s_{t + 1})$ 被称为 TD 目标，由于：

$v_{\pi}(s_{t}) = \mathcal{E}_{a_{t} \sim \pi(\cdot \mid s_{t})} \mathcal{r}(s_{t},\ a_{t}) + \gamma \mathcal{E}_{a_{t} \sim \pi(\cdot \mid s_{t})} \mathcal{E}_{s_{t + 1} \sim p(\cdot \mid s_{t},\ a_{t})} v_{\pi}(s_{t + 1}) = \mathcal{E}_{a_{t} \sim \pi(\cdot \mid s_{t})} \mathcal{E}_{r_{t + 1} \sim r(\cdot \mid s_{t},\ a_{t})} \mathcal{E}_{s_{t + 1} \sim p(\cdot \mid s_{t},\ a_{t})} \Big[ r_{t + 1} + \gamma v_{\pi}(s_{t + 1}) \Big]$

因此可以使用自举的 $g_{t}^{(1)} = r_{t + 1} + \gamma v(s_{t + 1})$ 来近似 $g_{t} = r_{t + 1} + \gamma v_{\pi}(s_{t + 1})$，在未收敛到 $v_{\pi}$ 前这种自举估计是有偏的，但是相对于蒙特卡洛方法降低了估计的方差，进而降低了估计的偏差：

多步时序差分

类似地，通过多步信息可以得到多步的 TD 目标 $g^{(k)} = r_{t + 1} + \gamma r_{t + 2} + \cdots + \gamma^{k - 1} r_{t + k} + \gamma^{k} v(s_{t + k})$

$v_{\pi}(s_{t}) = \mathcal{E}_{a_{t}} \mathcal{E}_{r_{t + 1}} \mathcal{E}_{s_{t + 1}} \mathcal{E}_{a_{t + 1}} \mathcal{E}_{r_{t + 2}} \cdots \mathcal{E}_{s_{t + k}} \Big[ r_{t + 1} + \gamma r_{t + 2} + \cdots + \gamma^{k - 1} r_{t + k} + \gamma^{k} v_{\pi}(s_{t + k}) \Big]$

以及多步 TD 误差 $\delta_{t}^{(k)} = r_{t + 1} + \gamma r_{t + 2} + \cdots + \gamma^{k - 1} r_{t + k} + \gamma^{k} v(s_{t + 1}) - v(s_{t})$，基于此可以实现多步 TD 方法：

$v(s_{t}) \leftarrow v(s_{t}) + \alpha \delta_{t}^{(k)}$

相较于单步 TD 方法，降低了估计的偏差，而相较于蒙特卡洛方法（$\mathrm{T} - t$ 步 TD）又可以降低估计的方差。

TD(λ)

TD(λ) 方法对不同时间步的 TD 目标 $g_{t}^{(k)}$ 进行加权求和来综合低偏差的短期 TD 和低方差的长期 TD：

$\begin{aligned} g_{t}^{(\lambda)} &= (1 - \lambda) g_{t}^{(1)} + (1 - \lambda) \lambda g_{t}^{(2)} + \cdots + (1 - \lambda) \lambda^{\mathrm{T} - t - 2} g_{t}^{(\mathrm{T} - t - 1)} + \lambda^{\mathrm{T} - t - 1} g_{t}^{(\mathrm{T} - t)} \\[5mm] &= (1 - \lambda) \sum_{k = 1}^{\mathrm{T} - t - 1} \lambda^{k - 1} g_{t}^{(k)} + \lambda^{\mathrm{T} - t - 1} g_{t}^{(\mathrm{T} - t)} \overset{\mathrm{T} \to \infty}{\longrightarrow} (1 - \lambda) \sum_{k = 1}^{\infty} \lambda^{k - 1} g_{t}^{(k)} \end{aligned}$

其中 $(1 - \lambda)$ 用于系数的归一化，即保证：

$\mathcal{E}_{a_{t}} \mathcal{E}_{r_{t + 1}} \mathcal{E}_{s_{t + 1}} \mathcal{E}_{a_{t + 1}} \mathcal{E}_{r_{t + 2}} \cdots \mathcal{E}_{s_{t + k}} g_{t}^{(\lambda)} = (1 - \lambda) \Big[ 1 + \lambda + \cdots + \lambda^{\mathrm{T} - t - 2} \Big] v_{\pi}(s_{t}) + \lambda^{\mathrm{T} - t - 1} v_{\pi}(s_{t}) = v_{\pi}(s_{t})$

更新方式为 $v(s_{t}) \leftarrow v(s_{t}) + \alpha \Big[ g_{t}^{\lambda} - v(s_{t}) \Big] = v(s_{t}) + \alpha \delta_{t}^{(\lambda)}$，其中：

$\begin{aligned} \delta_{t}^{(\lambda)} &= (1 - \lambda) \delta_{t}^{(1)} + (1 - \lambda) \lambda \delta_{t}^{(2)} + \cdots + (1 - \lambda) \lambda^{\mathrm{T} - t - 2} \delta_{t}^{(\mathrm{T} - t - 1)} + \lambda^{\mathrm{T} - t - 1} \delta_{t}^{(\mathrm{T} - t)} \\[5mm] &= (1 - \lambda) \sum_{k = 1}^{\mathrm{T} - t - 1} \lambda^{k - 1} \delta_{t}^{(k)} + \lambda^{\mathrm{T} - t - 1} \delta_{t}^{(\mathrm{T} - t)} \overset{\mathrm{T} \to \infty}{\longrightarrow} (1 - \lambda) \sum_{k = 1}^{\infty} \lambda^{k - 1} \delta_{t}^{(k)} \end{aligned}$

从 $\delta_{t}^{(\lambda)}$ 的形式可以看出，当 $\lambda = 0$ 时 TD(λ) 退化为单步 TD 方法，当 $\lambda = 1$ 时 TD(λ) 退化为蒙特卡洛方法。考虑无限期或不确定期规划下，将 TD(λ) 误差 $\delta_{t}^{(\lambda)}$ 展开得到：

$\begin{aligned} \delta_{t}^{(\lambda)} = g_{t}^{(\lambda)} - v(s_{t}) = -v(s_{t}) &+ (1 - \lambda) \lambda^{0} \Big[ r_{t + 1} + \gamma v(s_{t + 1}) \Big] \\[5mm] &+ (1 - \lambda) \lambda^{1} \Big[ r_{t + 1} + \gamma r_{t + 2} + \gamma^{2} v(s_{t + 2}) \Big] \\[5mm] &+ (1 - \lambda) \lambda^{2} \Big[ r_{t + 1} + \gamma r_{t + 2} + \gamma^{2} r_{t + 3} + \gamma^{3} v(s_{t + 3}) \Big] \\[5mm] & \cdots \\[2mm] \overset{\mathrm{T} \to \infty}{\longrightarrow} -v(s_{t}) &+ (\gamma \lambda)^{0} \Big[ r_{t + 1} + \gamma v(s_{t + 1}) (1 - \lambda) \Big] \\[5mm] &+ (\gamma \lambda)^{1} \Big[ r_{t + 2} + \gamma v(s_{t + 2}) (1 - \lambda) \Big] \\[5mm] &+ (\gamma \lambda)^{2} \Big[ r_{t + 3} + \gamma v(s_{t + 3}) (1 - \lambda) \Big] \\[5mm] &\cdots \\[2mm] = (\gamma \lambda)^{0} \Big[ r_{t + 1} + \gamma v(s_{t + 1}&) - v(s_{t}) \Big] + (\gamma \lambda)^{1} \Big[ r_{t + 2} + \gamma v(s_{t + 2}) - v(s_{t + 1}) \Big] + \cdots = \sum_{k = 0}^{\infty} (\gamma \lambda)^{k} \delta_{t + k}^{(1)} \end{aligned}$

基于此可以实现 TD(λ) 的在线更新，与离线更新方式相比更加高效，但二者的更新结果具有一定的差异。在线算法的实现需要使用资格迹来计算信度的分配 $e(s)$，其初始值 $e_{0}(s) = \boldsymbol{0}$，每个时间步的更新方式如下：

$e_{t}(s) = \gamma \lambda e_{t - 1}(s) + \boldsymbol{1}(s_{t} = s)$

从而得到对状态价值函数的在每个时间步的更新 $v(s) \leftarrow v(s) + \alpha \delta_{t}^{(1)} e_{t}(s)$，资格迹实质上在收集每个状态的每次访问后的系数总和，同时每个分量可以看做在单独进行衰减，衰减因子为 $\gamma \lambda$。