Streaming-DRL

原文：Streaming Deep Reinforcement Learning Finally Works

摘要：流式学习(streaming learning)，使用最新样本，不做存储。适用于资源有限，通信受限，隐私敏感的场景。深度学习采用批量学习和经验回放，样本利用率高。相比之下，流式学习有一个更致命的问题——流式障碍(stream barrier)，即学习不稳定，甚至难以有效学习。这篇文章提出stream-x算法，克服流式障碍并且具备批量学习的样本效率。

引言

从连续不断地经验流中学习是一项重要的挑战，这是一种对自然学习过程的镜像，并且和许多涉及设备上学习的应用相关。例如，从最新的经验中学习可以帮助系统快速适应变化（例如磨损）。在流式强化学习中（例如Q-learning，TD），在每个时间步，智能体接收一个观测和奖励，采取行动并进行策略更新，过程不涉及存储样本。这种场景是切合现实的，因为有些时候保存原始样本是不可行的，例如计算资源有限，缺乏沟通渠道，或者担心数据隐私问题。

尽管经典的RL算法（例如Q-learning，SARSA，AC，TD）都是流式学习，最近的进展主要转向了批量学习。事实上，DRL的最新进展很大程度上依赖于计算代价高昂的批量学习。批量强化学习将样本存储在经验回放池中，并从中批量抽取样本进行学习。

批量强化学习的成功通常归因于它的样本效率和现代硬件。对一批样本进行平均可能产生更可靠的更新，并且多次重用样本可能能够从样本中提取更多信息。此外，批量学习可以有效利用并行环境以及使用GPU等现代硬件加速计算。反过来，昂贵的计算资源也使得批量学习方法不适合资源受限的系统（边缘设备，火星探测器）。流式学习在DRL中仍然未被广泛采用，目前，实践中明显缺乏流式强化学习应用，使得资源受限下的DRL无法实现。

流式DRL发展困境

流式DRL被认为是样本效率低下的，因为样本不能重复使用。另一个原因是，基于单步方法（如Q-learning），每次更新仅考虑当前奖励和下一步的预测，信用分配通常传播缓慢，而多步方法（如n-step TD）则利用了多个时间步的奖励，将未来多个奖励的信息融入到当前的更新中，可以更快的传播奖励信号，提高信用分配的传播速度。但代价就是，多步方法无法做到实时更新，并且需要存储多步信息。资格迹试图平衡使用多步回报和一步更新的优势，然而，DRL中很少使用资格迹。

尽管流式DRL的缺失是由于其样本效率低下，更关键的原因是，现有的深度学习方法在流式学习环境中会遇到学习不稳定甚至失败的情况，称为流式障碍(stream barrier)。DRL方法在在线更新方面已经遇到了许多困难，例如可塑性丧失(loss of plasticity)、学习动态不佳(poor learning dynamics)、无法实现进一步改进(failure to achieve further improvement)、性能逐渐退化(gradual performance degradation)。此外，流式DRL有其独特的挑战，由于用于更新的观测和奖励分布会随着时间的推移而迅速变化，从而加剧了问题。DRL中很少使用资格迹的原因也可以归于不稳定问题。结果，流式DRL面临流式障碍并且很大程度上被忽视了。然而，有一小部分研究已经用流式学习展现出初步成果，表明这一领域具有进一步探索和发展的潜力。

本文贡献

这篇文章通过引入流式DRL方法——stream TD($\lambda$)，stream Q($\lambda$)，stream AC($\lambda$)来解决流式障碍，这些算法统称为stream-x算法，并且利用了资格迹技术。这篇文章的方法，可以从最近的经验中学习，而不需要经验回放池，批量更新，目标网络。展现了流式DRL方法可以稳定学习，可以和批量DRL具有一样的样本效率。这篇文章方法的有效性取决于一组关键技术，这些技术在所有stream-x算法中一致，包括(1)新的优化器；(2)适当的数据缩放；(3)新的初始化方案；(4)a standard normal distribution of pre-activations。

预备知识

符号定义

MC & TD

对于价值函数的估计方法，有蒙特卡洛(MC)和时序差分(TD)两种方案。前者使用完整的回报$G_{t}$，后者采用自举(bootstrapping)的思想，使用$R_{t+1}+\gamma v(S_{t+1})$替代$G_{t}$。因此MC方法需要一幕结束才能进行参数更新，而TD方法可以在看到下一步状态$S_{t+1}$和回报后$R_{t+1}$就进行更新。

策略梯度定理

对于参数化策略的方法，如何调整策略参数保证性能改善是一件很有挑战的事情，策略梯度定理提供了很好的理论解答——$\nabla J(\theta) \propto \sum_{s} u(s) \sum_{a} \nabla \pi_{\theta}(a|s) q(s,a)$

资格迹

定义式：$z_{t} \doteq \gamma\lambda z_{t-1} + \nabla_{\boldsymbol w} \hat{v}(S_{t}, \boldsymbol w), \space z_{-1} = \boldsymbol 0$。资格迹是一个”短时记忆“向量（相较于值函数这个”长时记忆“），本质上是在存储过去时间步，衰减后的价值函数的梯度信息。每个时刻根据资格迹和TD误差对价值函数进行参数更新时，过去的梯度信息会对当下的参数更新产生影响。反过来看，就好像每个时刻把TD误差（携带reward信息）向后传播，如果将资格迹的求和拆开看，可以想象每个时刻的梯度更新都是”不充分“的（相较于蒙特卡洛这种看到全部奖励信息的情况），每向前执行一个时间步的更新，都是过去”不充分“的梯度更新的完善，最终（一幕游戏结束）逼近蒙特卡洛的效果。

核心方法

这篇文章罗列了DRL训练的一些困难点：

1. 由于偶尔的大幅度的参数更新，可能训练过程不稳定；
2. 由于神经网络中激活值的分布在训练过程中不断变化，可能导致训练过程不稳定；
3. 数据缩放不恰当。

改进样本效率

这篇文章提出两种技术改进流式学习的样本效率：稀疏初始化和资格迹。

稀疏表示通过在更新网络时将影响局部化，减少了不同输入之间的权重更新干扰。这篇文章使用一种简单的技术在初始化时引入稀疏性——将大多数权重随机初始化为0。具体而言，在每一个网络层施加一个稀疏度$s$，表示零初始化权重的比例。这个稀疏初始化方案可以用于全连接层和卷积层，伪代码如下图：

这篇文章针对价值函数和策略函数都使用资格迹。引入资格迹后，必须使用谨慎的更新规则，以防止训练过程不稳定。

保持更新稳定

这篇文章开发了一个更适合流式DRL的稳定的优化器。

在优化领域，一个避免大更新和选择适当步长的著名策略是——回溯线搜索(backtracking line search)。该方法通常为每轮迭代选择最大化期望或基于批次的目标的步长。回溯线搜索已经被证明能够有效地稳定同轨的批量强化学习。在流式学习场景下，还不清楚选择一个减少当前样本误差的步长是否是最佳策略。一个更切题的目标是，淡化那些过大的更新。更具体讲，给定一个标量误差$\delta(S)$，更新后的误差记为$\delta_{+}(S)$，如果$\delta(S) \delta_{+}(S) < 0$，表明更新过度。Kearney在2023年定义了一个相关的量——有效步长(effective step size)，它量化了更新所取得的进步，定义如下:
$$
\xi \doteq \frac{\delta(S) - \delta_{+}(S)}{\delta(S)} \tag{1}
$$
当$\xi>1$时，意味着更新过度；当$\xi<1$时，意味着部分纠正；当$\xi=0$时，意味着没有纠正。我们可以使用一个初始步长$\alpha = \alpha_{Init} \in(0,1]$，通过反事实更新来计算有效步长。如果计算的有效步长大于最大有效步长，即$\xi > \xi_{max}, \xi_{max} \in (0,1])$，那么我们使用系数$\beta, \beta \in (0,1)$来减少步长$\alpha = \beta \alpha$。这个回溯线搜索持续到$\xi \le \xi_{max}$条件被满足。这篇文章将这个过程命名为——回溯限制有效步长(bounding effective step size with backtracking)，伪代码如下图：

这种回溯方法的缺点也很明显，每个时间步可能需要多轮迭代去找出合适的步长，每轮迭代需要额外前向传播计算误差$\delta$，这可能代价很大。一种不需要额外前向传播，成本更低的替代方案将更可取。

这篇文章对上述思路做出一些近似。首先，使用一阶泰勒近似并假设局部线性（权重更新幅度足够小），函数更新参数后预测可以写为：
$$
\begin{align*}
f(\boldsymbol x;\boldsymbol w_{+}) &= f(\boldsymbol x;\boldsymbol w - \boldsymbol u(\boldsymbol x;\boldsymbol w)) \
&= f(\boldsymbol x;\boldsymbol w) - \nabla_{\boldsymbol w}f(\boldsymbol x;\boldsymbol w)^{T} \boldsymbol u(\boldsymbol x;\boldsymbol w);
\tag{2}
\end{align*}
$$
基于上述近似，可以推导TD($\lambda$)算法对应的有效步长如下：
$$
\begin{align*}
\xi &= \frac{\delta - \delta_{+}}{\delta} \
&= \frac{(r + \gamma v(\boldsymbol s^{\prime};\boldsymbol w) - v(\boldsymbol s;\boldsymbol w)) -
(r + \gamma v(\boldsymbol s^{\prime};\boldsymbol w_{+}) - v(\boldsymbol s;\boldsymbol w_{+}))}{\delta} \
&= \frac{(r-r) +
\gamma[v(\boldsymbol s^{\prime};\boldsymbol w) - v(\boldsymbol s^{\prime};\boldsymbol w_{+})] -
[v(\boldsymbol s;\boldsymbol w) - v(\boldsymbol s;\boldsymbol w_{+})]}{\delta} \
&= \frac{\gamma \alpha \delta \boldsymbol z^{T} \nabla_{\boldsymbol w}v(\boldsymbol s^{\prime};\boldsymbol w) -
\alpha \delta \boldsymbol z^{T} \nabla_{\boldsymbol w}v(\boldsymbol s;\boldsymbol w)}{\delta} \
&= \alpha \boldsymbol z^{T} (\gamma \nabla_{\boldsymbol w}v(\boldsymbol s^{\prime};\boldsymbol w) - \nabla_{\boldsymbol w}v(\boldsymbol s;\boldsymbol w))
\end{align*}
$$
从结果上看，每次计算$\xi$需要额外计算一个状态$s^{\prime}$对应的价值函数的梯度值，这就产生了一个额外的反向传播的计算量。为了移除这个计算，作者又做出了一步近似：
$$
\begin{align*}
\xi &= \alpha \boldsymbol z^{T} (\gamma \nabla_{\boldsymbol w}v(\boldsymbol s^{\prime};\boldsymbol w) -
\nabla_{\boldsymbol w}v(\boldsymbol s;\boldsymbol w)) \
&\le \alpha |\boldsymbol z|^{T} |\gamma \nabla_{\boldsymbol w}v(\boldsymbol s^{\prime};\boldsymbol w) -
\nabla_{\boldsymbol w}v(\boldsymbol s;\boldsymbol w)| \
&\le \alpha |\boldsymbol z|^{T} \textbf{1} \
&= \alpha \Vert \boldsymbol z \Vert_{1} \
&\le \kappa \alpha \Vert \boldsymbol z \Vert_{1}, \ where \ \kappa > 1 \
&\le \kappa \alpha \bar{\delta} \Vert \boldsymbol z \Vert_{1}, \ where \ \bar{\delta}=\max(|\delta|,1)
\tag{3}
\end{align*}
$$
对上述符号做出一些解释。$|\cdot|$是对向量所有分量取模构成的新向量，文章假设$|\gamma \nabla_{\boldsymbol w}v(\boldsymbol s^{\prime};\boldsymbol w) -\nabla_{\boldsymbol w}v(\boldsymbol s;\boldsymbol w)|$所有分量小于等于1。

关于$|\gamma \nabla_{\boldsymbol w}v(\boldsymbol s^{\prime};\boldsymbol w) -\nabla_{\boldsymbol w}v(\boldsymbol s;\boldsymbol w)|$所有分量小于等于1假设，文章使用Lipschitz连续性的论证来支持这一假设。如果价值函数的梯度$\nabla_{\boldsymbol w} v(\boldsymbol s;\boldsymbol w)$满足k-Lipschitz连续，那么可以得到$\Vert \nabla_{\boldsymbol w}v(\boldsymbol s^{\prime};\boldsymbol w) -\nabla_{\boldsymbol w}v(\boldsymbol s;\boldsymbol w) \Vert_{1} \le k \Vert \boldsymbol s^{\prime} - \boldsymbol s \Vert_{1}$。因此在$\gamma \approx 1$（例如0.99），$k \Vert \boldsymbol s^{\prime} - \boldsymbol s \Vert_{1} \le 1$（即$s^{\prime}$和$s$足够接近）的条件下，$\Vert \gamma \nabla_{\boldsymbol w}v(\boldsymbol s^{\prime};\boldsymbol w) -\nabla_{\boldsymbol w}v(\boldsymbol s;\boldsymbol w) \Vert_{i} \le 1$对于任意$i$都成立。

文章提出了一个新的优化器，使用上述结论，控制更新步长。伪代码如下：

附录

信用分配问题

在强化学习中，智能体会根据动作获得奖励，但奖励可能不会立即显现，而是延迟的，信用分配问题就是如何正确地将这些奖励归因于之前的动作，从而帮助智能体改进策略。

神经网络与资格迹结合有什么问题

资格迹是一种结合了TD和MC的技巧，可以加速学习，改进信用分配。当神经网络和资格迹结合时，会产生不稳定性。

(1)梯度传播问题：资格迹累积了多个时间步的信息，相当于把多个时间步的更新叠加在一起，这可能导致梯度的剧烈波动或方法，使网络的训练过程变得不稳定，甚至导致参数更新过大；

(2)相关性问题：神经网络的输出是参数的复杂非线性组合，而资格迹试图将多个时间步的奖励信息整合，这使得神经网络输入的相关性增强，可能引入相关性问题，使得资格迹的累积更新效果被放大或削弱，从而加剧了网络的不稳定性；

(3)反馈循环问题：在强化学习中，神经网络的输出用于指导智能体的行为，而这些行为又会影响接下来的样本分布，如果资格迹传播的信息在网络中不稳定，这种反馈循环可能导致错误更新被反复放大，进而导致发散。

回溯线搜索

Lipschitz连续性

定义：

一个函数$f(x)$是Lipschitz连续的，如果存在一个常数$L\ge0$，使得对于所有的$x_{1},x_{2} \in \mathbb{R}^n$，都有：
$$
\Vert f(x_{1}) - f(x_{2}) \Vert \le L \Vert x_{1} - x_{2} \Vert
$$
其中：

• $L$是Lipschitz常数，表示函数$f(x)$的最大变化速率

• $\Vert\cdot\Vert$通常是欧几里得范数（也可以是其他范数）

几何意义：

• 函数变化率有限，函数不会过于“陡峭”

在深度学习中的应用：

• 如果网络每一层都是Lipschitz连续的，那网络输出对输入的变化会有界