强化学习新范式：摆脱时间差分学习

在这篇文章中，我将介绍一种基于「另类」范式的强化学习（RL）算法：分治。与传统方法不同，这种算法不依赖存在可扩展性难题的时序差分（TD）学习，并且能够很好地扩展到长时程任务。

我们可以基于分治而非时序差分（TD）学习来实现强化学习（RL）。

问题设定：离策略 RL

我们的问题设定是离策略 RL。先简单回顾一下它的含义。

RL 算法可以分为两类：同策略 RL 和离策略 RL。同策略 RL 意味着，我们只能使用当前策略刚刚收集的新数据。换句话说，每次更新策略时，都必须丢弃旧数据。PPO、GRPO 等算法以及广义上的策略梯度方法都属于这一类。

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

截至 2025 年，我认为我们已经有了相当成熟的同策略 RL 扩展方案，例如 PPO、GRPO 及其各种变体。然而，我们仍然没有找到一种「可扩展」的离策略 RL 算法，能够有效扩展到复杂的长时程任务。下面我来简单解释一下原因。

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

在离策略 RL 中，我们通常使用时序差分（TD）学习，也就是 Q-learning，按照下面的 Bellman 更新规则训练价值函数：

问题在于：下一个价值 $Q(s’, a’)$ 中的误差会通过 bootstrapping 传播到当前价值 $Q(s, a)$，而且这些误差会在整个时程中不断累积。从根本上说，这正是 TD 学习难以扩展到长时程任务的原因。如果你想了解更多细节，可以参阅相关文章。

为了缓解这个问题，人们将 TD 学习与蒙特卡洛（MC）回报结合起来。例如，我们可以采用 $n$ 步 TD 学习（TD-$n$）：

这里，我们在前 $n$ 步使用数据集中的实际蒙特卡洛回报，然后在剩余时程中使用 bootstrapping 得到的价值。这样一来，Bellman 递归的次数可以减少到原来的 $1/n$，误差累积也会随之减轻。在 $n = \infty$ 这一极端情况下，它就变成了纯粹的蒙特卡洛价值学习。

尽管这是一个合理的解决方案，而且通常效果不错，但它远不能令人满意。首先，它没有从根本上解决误差累积问题，只是将 Bellman 递归的次数减少了一个常数倍，也就是 $n$ 倍。其次，随着 $n$ 增大，我们会受到高方差和次优性的影响。因此，我们不能直接把 $n$ 设成很大的值，而是需要针对每项任务仔细调优。

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

「第三种」范式：分治

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

分治能够以对数级的幅度减少 Bellman 递归次数。

分治的核心思想，是把一条轨迹划分为两个长度相等的片段，再将它们的价值组合起来，用于更新整条轨迹的价值。通过这种方式，我们在理论上可以以对数级而不是线性级减少 Bellman 递归次数。此外，它不需要选择 $n$ 这样的超参数，而且与 $n$ 步 TD 学习不同，它不一定会遭遇高方差或次优性问题。

从概念上看，分治确实具备我们希望价值学习拥有的所有优秀性质。因此，我很早就开始对这个高层思想感到兴奋。问题在于，我们一直不清楚如何在实践中真正实现它……直到最近。

一种实用算法

在最近一项由我和 Aditya 共同领导的研究中，我们在实现和扩展这个想法方面取得了实质性进展。具体来说，至少在一类重要的 RL 问题——目标条件 RL——上，我们成功地将分治价值学习扩展到了高度复杂的任务。据我所知，这是第一项做到这一点的工作！目标条件 RL 的目标，是学习一个能够从任意状态到达其他任意状态的策略。这种问题天然具备分治结构。下面我来解释一下。

其结构如下。首先假设环境动态是确定性的，并将两个状态 $s$ 和 $g$ 之间的最短路径距离，即「时间距离」，记作 $d^*(s, g)$。那么，它满足三角不等式：

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

从价值的角度来看，我们可以等价地将这个三角不等式转换为下面这种「传递式」Bellman 更新规则：

其中，$\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}$。具体来说，我们最小化以下损失：

其中，$\bar{V}$ 是目标价值网络，$\ell^2_\kappa$ 是 expectile 为 $\kappa$ 的 expectile loss；期望是在随机采样的数据集轨迹中，对所有满足 $i \leq k \leq j$ 的 $(s_i, s_k, s_j)$ 三元组计算的。

这样做有两个好处。第一，我们不需要搜索整个状态空间。第二，通过采用更加「柔和」的 expectile regression，而不是 $\max$ 算子，可以避免价值高估。我们将这种算法称为 Transitive RL（TRL）。更多细节和进一步讨论，请参阅我们的论文！

为了检验这种方法能否有效扩展到复杂任务，我们直接在 OGBench 中一些最具挑战性的任务上评估了 TRL。OGBench 是一个面向离线目标条件 RL 的 benchmark。我们主要使用了 humanoidmaze 和 puzzle 任务中难度最高的版本，数据集规模高达 10 亿条。这些任务极具挑战性：Agent 必须在最多 3,000 个环境步中执行具有组合复杂性的技能。

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

结果非常令人振奋！与 TD、MC、quasimetric learning 等不同类别中的诸多强大 baseline 相比，TRL 在大多数任务上都取得了最佳性能。

TRL 无须设置 $\boldsymbol{n}$，就能达到针对各项任务单独调优的最佳 TD-$n$ 的水平。

这是我最喜欢的一张图。我们将 TRL 与采用不同 $n$ 值的 $n$ 步 TD 学习进行了比较，其中 $n$ 从 $1$（纯 TD）一直变化到 $\infty$（纯 MC）。结果非常漂亮：TRL 在所有任务上都达到了最佳 TD-$n$ 的水平，同时完全不需要设置 $\boldsymbol{n}$！这正是我们希望从分治范式中获得的能力。通过递归地把一条轨迹拆分为更小的轨迹，它可以自然地处理长时程问题，而不必武断地选择轨迹分块的长度。

论文中还有许多额外的实验、分析和消融研究。如果你感兴趣，可以阅读我们的论文！

在这篇文章中，我分享了我们新的分治价值学习算法 Transitive RL 所取得的一些令人鼓舞的结果。这段旅程才刚刚开始。仍有许多开放问题和值得探索的精彩方向：

也许最重要的问题，是如何把 TRL 扩展到目标条件 RL 之外的常规奖励型 RL 任务。常规 RL 是否也具有类似的分治结构，能够供我们利用？我对此相当乐观，因为至少从理论上讲，任何奖励型 RL 任务都可以转换为目标条件任务，相关内容可参阅这本书的第 40 页。

也许最重要的问题，是如何把 TRL 扩展到目标条件 RL 之外的常规奖励型 RL 任务。常规 RL 是否也具有类似的分治结构，能够供我们利用？我对此相当乐观，因为至少从理论上讲，任何奖励型 RL 任务都可以转换为目标条件任务，相关内容可参阅这本书的第 40 页。

另一个重要挑战是处理随机环境。目前版本的 TRL 假设环境动态是确定性的，但许多现实世界中的环境都是随机的，主要原因是部分可观测性。对此，「随机」三角不等式或许能够提供一些启发。

另一个重要挑战是处理随机环境。目前版本的 TRL 假设环境动态是确定性的，但许多现实世界中的环境都是随机的，主要原因是部分可观测性。对此，「随机」三角不等式或许能够提供一些启发。

从实践角度看，我认为 TRL 仍有很大的改进空间。例如，我们可以找到更好的子目标候选选择方式，不再局限于同一条轨迹中的状态；进一步减少超参数；进一步稳定训练；以及继续简化算法。

从实践角度看，我认为 TRL 仍有很大的改进空间。例如，我们可以找到更好的子目标候选选择方式，不再局限于同一条轨迹中的状态；进一步减少超参数；进一步稳定训练；以及继续简化算法。

总体而言，我对分治范式的潜力感到非常兴奋。我依然认为，RL 乃至整个机器学习领域最重要的问题之一，就是找到一种可扩展的离策略 RL 算法。我不知道最终的解决方案会是什么样子，但我确实认为，分治乃至更广义的递归决策，是通往这一圣杯最有力的候选方案之一。顺便说一句，我认为另外两个强有力的竞争者是：（1）基于模型的 RL；（2）加入某些「魔法」技巧的 TD 学习。事实上，近期其他领域的多项工作已经展示了递归和分治策略的潜力，例如 shortcut models、log-linear attention 和 recursive language models，当然也包括 quicksort、segment trees、FFT 等经典算法。我希望在不久的将来，能够看到可扩展离策略 RL 领域取得更多令人振奋的进展！

感谢 Kevin 和 Sergey 对本文提出的宝贵反馈。

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