不依赖时序差分学习的强化学习：分而治之

📢 转载信息

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

原文作者：Seohong Park’s blog

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

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

问题设置：离策略RL

我们的问题设置是离策略RL（off-policy RL）。让我们简要回顾一下这意味着什么。

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

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

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

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

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

\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$ 步，然后对剩余的视域使用引导价值。通过这种方式，我们可以将贝尔曼递归次数减少 $n$ 倍，从而减少误差累积。在 $n = \infty$ 的极端情况下，我们恢复为纯粹的蒙特卡洛价值学习。

虽然这是一个合理的解决方案（并且通常效果很好），但它并不能从根本上解决误差累积问题；它只是将贝尔曼递归次数减少了一个常数因子（$n$）。其次，随着 $n$ 的增大，我们会遭受高方差和次优性的影响。因此，我们不能简单地将 $n$ 设置为一个较大的值，并且需要为每个任务仔细调整它。

有没有一种从根本上解决这个问题的不同方法呢？

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

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

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

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

从概念上讲，分而治之确实在价值学习中拥有我们想要的所有良好特性。所以我一直对这个高层想法感到兴奋。问题在于如何真正地在实践中做到这一点……直到最近。

一个实用的算法

在与Aditya共同领导的最新工作中，我们朝着实现和扩展这一想法取得了有意义的进展。具体来说，我们能够将分而治之价值学习扩展到高度复杂的任务（据我所知，这是第一个此类工作！），至少在RL问题的一个重要类别中，即目标条件RL（Goal-conditioned 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}$。

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

\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的基准测试，其中包含一些最具挑战性的任务。我们主要使用了 $\text{humanoidmaze}$ 和 $\text{puzzle}$ 任务的最难版本，使用了大型的10亿（1B）数据集。这些任务极具挑战性：它们需要在长达3,000个环境步的序列中执行组合复杂的技能。

TRL在高度挑战性的、长视域任务上取得了最佳性能。

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

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

这是我最喜欢的一张图。我们将TRL与 $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学习）。事实上，其他领域的一些最新工作已经展示了递归和分而治之策略的潜力，例如捷径模型、对数线性注意力和递归语言模型（当然，还有快速排序、线段树、FFT等经典算法）。我希望在不久的将来看到可扩展的离策略RL方面取得更多令人兴奋的进展！

致谢

我要感谢Kevin和Sergey对本帖提供的宝贵反馈。

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

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

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