摆脱时序差分学习的强化学习：一种分而治之的新范式

📢 转载信息

原文链接：http://bair.berkeley.edu/blog/2025/11/01/rl-without-td-learning/

原文作者：Seohong Park’s blog

在本文中，我将介绍一种基于“分而治之”范式的强化学习（RL）算法。与传统的、基于时序差分（TD）学习（存在可扩展性挑战）的方法不同，该算法能很好地扩展到长程任务。

我们可以基于分而治之，而不是时序差分（TD）学习来进行强化学习（RL）。

问题设定：离策略RL

我们的问题设定是离策略RL。让我们简要回顾一下这意味着什么。

RL中有两类算法：在策略RL和离策略RL。在策略RL意味着我们只能使用当前策略收集的新鲜数据。换句话说，每次更新策略，我们都必须丢弃旧数据。PPO和GRPO等算法（以及通常的策略梯度方法）都属于这一类。

离策略RL意味着我们没有这个限制：我们可以使用任何类型的数据，包括旧经验、人类演示、互联网数据等等。因此，离策略RL比在策略RL更通用、更灵活（当然也更难！）。Q学习是最著名的离策略RL算法。在数据收集成本高昂的领域（例如，机器人技术、对话系统、医疗保健等），我们通常别无选择，只能使用离策略RL。这就是它如此重要的原因。

截至2025年，我认为我们已经为扩展在策略RL（例如，PPO、GRPO及其变体）准备了相当不错的方案。然而，我们仍然没有找到一个能够很好地扩展到复杂、长程任务的“可扩展”离策略RL算法。我将简要解释一下原因。

价值学习的两种范式：时序差分（TD）和蒙特卡洛（MC）

在离策略RL中，我们通常使用时序差分（TD）学习（即，Q学习）来训练价值函数，其Bellman更新规则如下：

\begin{aligned} Q(s, a) \gets r + \gamma \max_{a'} Q(s', a'), \end{aligned}

问题在于：下一个价值 $Q(s’, a’)$ 的误差通过自举（bootstrapping）传播到当前价值 $Q(s, a)$，并且这些误差会在整个时间跨度上累积。这基本上是TD学习难以扩展到长程任务的原因（如果感兴趣，请参阅这篇文章了解更多细节）。

为了减轻这个问题，人们将TD学习与蒙特卡洛（MC）回报混合使用。例如，我们可以进行 $n$ 步TD学习（TD-$n$）：

\begin{aligned} Q(s_t, a_t) \gets \sum_{i=0}^{n-1} \gamma^i r_{t+i} + \gamma^n \max_{a'} Q(s_{t+n}, a'). \end{aligned}

在这里，我们使用数据集中实际的蒙特卡洛回报作为前 $n$ 步，然后使用自举价值来处理剩余的跨度。通过这种方式，我们可以将Bellman递归的次数减少 $n$ 倍，从而减少误差的累积。在 $n = \infty$ 的极端情况下，我们恢复了纯蒙特卡洛价值学习。

虽然这是一个合理的解决方案（并且通常效果不错），但它仍然不尽人意。首先，它没有从根本上解决误差累积问题；它只是将Bellman递归次数减少了一个常数因子（$n$）。其次，随着 $n$ 的增加，我们会受到高方差和次优性的影响。因此，我们不能简单地设置一个很大的 $n$ 值，而需要在每个任务中仔细调整它。

是否存在一种根本不同的方法来解决这个问题？

“第三种”范式：分而治之

我的观点是，价值学习中的第三种范式——分而治之——可以为离策略RL提供理想的解决方案，使其能够扩展到任意长的任务。

分而治之将Bellman递归次数减少了对数级别。

分而治之的关键思想是将一个轨迹划分为两个等长的片段，并将它们的价值组合起来以更新完整轨迹的价值。通过这种方式，我们（理论上）可以将Bellman递归的次数对数级地减少（而不是线性级！）。此外，它不需要选择像 $n$ 这样的超参数，并且不像 $n$ 步TD学习那样必然遭受高方差或次优性的困扰。

从概念上讲，分而治之确实具备我们对价值学习所期望的所有良好特性。因此，我一直对这个高级思想感到兴奋。问题在于，在实践中如何真正实现它……直到最近。

一个实用的算法

在与Aditya共同领导的最新工作中，我们向实现和扩展这一思想迈出了有意义的一步。具体来说，我们设法将分而治之的价值学习扩展到了高度复杂的任务（据我所知，这是第一个此类工作！），至少在目标条件RL（Goal-Conditioned RL）这一重要类别的RL问题中是如此。目标条件RL旨在学习一个能够从任何状态到达任何状态的策略。这提供了一个天然的分而治之结构。让我解释一下。

结构如下。我们首先假设动力学是确定的，并将两个状态 $s$ 和 $g$ 之间的最短路径距离（“时间距离”）表示为 $d^*(s, g)$。那么，它满足三角不等式：

\begin{aligned} d^*(s, g) \leq d^*(s, w) + d^*(w, g) \end{aligned}

对于所有 $s, g, w \in \mathcal{S}$。

在价值方面，我们可以将此三角不等式等效地转化为以下“传递性”Bellman更新规则：

\begin{aligned} V(s, g) \gets \begin{cases} \gamma^0 & \text{if } s = g, \\ \gamma^1 & \text{if } (s, g) \in \mathcal{E}, \\ \max_{w \in \mathcal{S}} V(s, w)V(w, g) & \text{otherwise} \end{cases} \end{aligned}

其中 $\mathcal{E}$ 是环境中转移图中的边集，$V$ 是与稀疏奖励 $r(s, g) = 1(s = g)$ 相关的价值函数。直观地说，这意味着我们可以使用两个“更小”的价值 $V(s, w)$ 和 $V(w, g)$ 来更新 $V(s, g)$ 的价值，前提是 $w$ 是最短路径上的最优“中途点”（子目标）。这正是我们一直在寻找的分而治之价值更新规则！

问题

然而，这里有一个问题。问题在于在实践中如何选择最优子目标 $w$ 并不明确。在表格设置中，我们可以简单地枚举所有状态来找到最优的 $w$（这基本上就是Floyd-Warshall最短路径算法）。但在具有大状态空间的连续环境中，我们无法做到这一点。基本上，这就是为什么以前的工作在扩展分而治之价值学习方面遇到困难的原因，尽管这个想法已经存在了几十年（事实上，它甚至可以追溯到Kaelbling (1993)的首次目标条件RL工作——有关相关工作的进一步讨论，请参阅我们的论文）。我们工作的主要贡献是为这个问题提供了一个实用的解决方案。

解决方案

这是我们的关键思想：我们将 $w$ 的搜索空间限制在数据集中出现的那些状态中，特别是那些在数据集轨迹中位于 $s$ 和 $g$ 之间的状态。此外，我们没有搜索最优的 $\text{argmax}_w$，而是使用期望回归（expectile regression）来计算一个“软” $\text{argmax}$。具体来说，我们最小化以下损失：

\begin{aligned} \mathbb{E}\left[\ell^2_\kappa (V(s_i, s_j) - \bar{V}(s_i, s_k) \bar{V}(s_k, s_j))\right], \end{aligned}

其中 $\bar{V}$ 是目标价值网络，$\ell^2_\kappa$ 是期望值为 $\kappa$ 的期望损失，期望是针对随机采样的整个数据集轨迹中所有 $(s_i, s_k, s_j)$ 元组计算的。

这有两个好处。第一，我们不需要搜索整个状态空间。第二，我们通过使用更“软的”期望回归来防止 $\max$ 运算符导致的价值高估。我们将此算法称为Transitive RL (TRL)。有关更多详细信息和进一步讨论，请查看我们的论文！

效果如何？

为了检验我们的方法在复杂任务上是否能很好地扩展，我们直接在OGBench上的一些最具挑战性的任务上对TRL进行了评估，OGBench是离线目标条件RL的一个基准测试。我们主要使用了具有大型、10亿（1B）规模数据集的人形迷宫（humanoidmaze）和拼图（puzzle）任务的最难版本。这些任务极具挑战性：它们需要在多达3000个环境步长内执行组合复杂的技能。

TRL在极具挑战性的长程任务上取得了最佳性能。

结果非常令人兴奋！与跨越不同类别的许多强大基线（TD、MC、准度量学习等）相比，TRL在大多数任务上都实现了最佳性能。

TRL的性能与单独调整的TD-$n$相匹配，而无需设置 $oldsymbol{n}$。

这是我最喜欢的一张图。我们将TRL与不同 $n$ 值的 $n$ 步TD学习进行了比较， $n$ 值从 $1$（纯TD）到 $\infty$（纯MC）。结果非常好。TRL在所有任务上都与最佳TD-$n$相匹配，而无需设置 $oldsymbol{n}$！这正是我们从分而治之范式中期望的。通过递归地分割轨迹，它可以自然地处理长程，而无需任意选择轨迹块的长度。

论文中有许多额外的实验、分析和消融研究。如果您有兴趣，请查看我们的论文！

下一步是什么？

在本文中，我分享了我们新的分而治之价值学习算法Transitive RL的一些有希望的结果。这只是旅程的开始。还有许多悬而未决的问题和令人兴奋的方向有待探索：

• 也许最重要的问题是如何将TRL扩展到除目标条件RL之外的常规、基于奖励的RL任务。常规RL是否具有我们可以利用的类似分而治之的结构？我对这一点相当乐观，因为理论上可以将任何基于奖励的RL任务转换为目标条件任务（请参阅这本书第40页）。

• 另一个重要挑战是处理随机环境。TRL的当前版本假设动力学是确定的，但许多现实世界的环境是随机的，主要是由于部分可观察性。为此，“随机”三角不等式可能提供一些线索。

• 在实践中，我认为TRL仍有很大的改进空间。例如，我们可以找到选择子目标候选（超出同一轨迹中的那些）的更好方法，进一步减少超参数，进一步稳定训练，并进一步简化算法。

总而言之，我对分而治之范式的潜力感到非常兴奋。我仍然认为RL（甚至在机器学习中）最重要的问题之一是找到一个可扩展的离策略RL算法。我不知道最终的解决方案会是什么样子，但我确实认为分而治之，或者通常的递归决策制定，是实现这一“圣杯”的最有力竞争者之一（顺便说一下，我认为其他强有力的竞争者是（1）基于模型的RL和（2）带有某种“魔术”技巧的TD学习）。事实上，最近其他领域的一些工作展示了递归和分而治之策略的潜力，例如Shortcut Models、Log-Linear Attention和递归语言模型（当然，还有Quicksort、Segment Trees、FFT等经典算法）。我希望在不久的将来看到可扩展的离策略RL方面取得更多令人兴奋的进展！

致谢

我要感谢Kevin和Sergey对本文提供的有益反馈。

本文最初发表于Seohong Park的博客。

🚀 想要体验更好更全面的AI调用？

欢迎使用青云聚合API，约为官网价格的十分之一，支持300+全球最新模型，以及全球各种生图生视频模型，无需翻墙高速稳定，文档丰富，小白也可以简单操作。