Transitive RL: Value Learning via Divide and Conquer¶

会议: ICLR 2026
arXiv: 2510.22512
代码: 无
领域: 强化学习 / 目标条件RL
关键词: 分治算法, 值函数学习, 离线RL, 目标条件强化学习, 三角不等式

一句话总结¶

本文提出 Transitive Reinforcement Learning（TRL），一种基于分治范式的新型值函数学习算法，利用目标条件RL中固有的三角不等式结构，将值函数更新递归分解为子问题，在长时间跨度任务上实现了优于TD学习和蒙特卡洛方法的性能。

研究背景与动机¶

目标条件强化学习（Goal-Conditioned RL, GCRL）关注一个基本问题：学习一个策略，能够从任意状态以最少步数到达任意目标状态。这一问题在机器人导航、操控规划等领域有广泛应用。

GCRL中学习值函数（描述从一个状态到目标状态所需的最小步数）主要有两种经典范式：

时序差分（TD）学习：通过逐步的单步自举（bootstrapping）传播值信息。优点是方差低（动态规划），但缺点是偏差累积——对于长度为 \(T\) 的轨迹，需要 \(O(T)\) 次递归更新才能传播完整信息，每次更新都可能引入近似误差，误差会逐步累积。

蒙特卡洛（MC）方法：直接使用完整轨迹的回报来估计值函数。优点是无偏倚，但缺点是高方差——长轨迹的总回报方差随轨迹长度增长。

这两种方法各有致命弱点，特别是在长时间跨度（long-horizon）任务中：

TD方法的偏差累积使得估计越来越不准确
MC方法的高方差使得学习极其缓慢

本文的核心洞察是：GCRL问题中存在一个三角不等式结构——从A到C的最短距离不超过从A到B再从B到C的距离之和。这一结构可以被利用来设计比TD和MC都更好的值函数学习算法。

方法详解¶

整体框架¶

TRL的核心思想是分治（Divide and Conquer）：将从状态 \(s\) 到目标状态 \(g\) 的值函数估计问题分解为两个子问题——先估计从 \(s\) 到某个中间状态 \(m\) 的值，再估计从 \(m\) 到 \(g\) 的值，然后组合这两个估计。

这个分治递归的深度为 \(O(\log T)\)（将长度为 \(T\) 的轨迹不断二分），远小于TD学习的 \(O(T)\) 递归深度。同时，每一层的估计都利用了动态规划，避免了MC方法的高方差问题。

关键设计¶

1. 三角不等式结构¶

在GCRL中，最优值函数 \(V^*(s, g)\) 满足三角不等式：

\[V^*(s, g) \leq V^*(s, m) + V^*(m, g), \quad \forall m\]

这意味着通过中间点 \(m\) 的路径是一个上界。TRL利用这一性质，通过取所有中间点的最小值来逼近真实值：

\[V^*(s, g) = \min_m [V^*(s, m) + V^*(m, g)]\]

当 \(m\) 恰好在最优路径上时，等号成立。

设计动机：这一更新规则类似于图论中的Floyd-Warshall算法思想，但被巧妙地迁移到了连续状态空间的RL问题中。

2. 分治值函数更新规则¶

TRL的值函数更新可以递归描述：

基本情况：对于相邻状态对 \((s_{t}, s_{t+1})\)，值函数为1步（直接从数据获得）
递归步骤：对于较远的状态对 \((s_i, s_j)\)，选取中间点 \(m = s_{(i+j)/2}\)，计算：

\[V(s_i, s_j) = V(s_i, m) + V(m, s_j)\]

通过这种二分递归，原来需要 \(O(T)\) 步传播的信息现在只需 \(O(\log T)\) 层递归即可完成。

3. 实际实现中的改进¶

中间点采样：不仅使用轨迹中点，还从数据集中采样多个候选中间点，取最小值
函数逼近：使用神经网络参数化值函数 \(V_\theta(s, g)\)
离线设定：所有更新基于预收集的离线数据集，不需要在线环境交互

损失函数 / 训练策略¶

TRL的训练损失可以表示为：

\[\mathcal{L}(\theta) = \mathbb{E}_{(s, m, g) \sim \mathcal{D}} \left[ \left( V_\theta(s, g) - \min\{V_\theta(s, g), V_{\bar{\theta}}(s, m) + V_{\bar{\theta}}(m, g)\} \right)^2 \right]\]

其中 \(\bar{\theta}\) 是目标网络参数（用于稳定训练），\(m\) 是从数据集采样的中间点。

这个损失函数的直觉是：如果通过中间点 \(m\) 的路径更短（\(V(s,m) + V(m,g) < V(s,g)\)），则更新 \(V(s,g)\) 使其更小；否则保持不变。这保证了值函数逐步收紧到最优值。

实验关键数据¶

主实验¶

在高难度、长时间跨度的离线GCRL基准上与现有算法比较：

基准任务	指标	TRL	TD-based最佳	MC-based最佳	其他GCRL
长距离导航	成功率	最优	偏差累积退化	高方差表现差	中等
复杂操控	成功率	最优	中等	差	中等
超长距离规划	成功率	最优	严重退化	几乎不可用	差

消融实验¶

配置	关键指标	说明
TRL (完整)	最优	基准配置
去除分治 (TD替代)	显著下降	验证分治的核心作用
去除动态规划 (MC替代)	明显下降	验证DP的方差控制作用
不同递归深度	\(\log T\) 最优	过深过浅均非最优
中间点采样数量	适度即可	多中间点略有帮助

关键发现¶

分治递归深度 \(O(\log T)\) 的优势显著：这是TRL的核心理论优势。对于长达数百步的轨迹，TD需要数百次递归传播值信息（每次都有近似误差），而TRL只需7-8层递归。
在长时间跨度任务上优势尤为明显：当轨迹长度增加时，TD和MC方法的性能快速退化，而TRL的性能退化缓慢，差距越来越大。
兼得TD和MC的优点：TRL既有TD的低方差特性（通过动态规划），又避免了TD的偏差累积问题（通过对数级递归），实现了两全其美。
对离线数据质量的鲁棒性：即使离线数据集中的轨迹不是最优的，TRL仍能通过三角不等式的最小化操作找到更短的路径。

亮点与洞察¶

巧妙利用问题结构：三角不等式是GCRL问题的固有几何性质。将其转化为算法设计原则（分治更新规则）是非常优雅的思路。与Floyd-Warshall的联系提供了良好的直觉。
理论保证优美：\(O(\log T)\) vs \(O(T)\) 的递归深度差异直接转化为偏差累积的阶数差异，理论分析清晰有力。
概念简单但效果显著：算法的核心思想一句话就能描述——"用中间点把长路径分成两段"——但这个简单思想在实验中带来了巨大的性能提升。
通用性：分治思想不局限于特定的环境或任务，适用于任何满足三角不等式的值函数学习问题。

局限与展望¶

仅适用于GCRL：TRL利用的是最短路径的三角不等式结构，不能直接推广到一般的RL问题（如含奖励折扣的累积奖励最大化）。
中间点的选择：在连续空间中，如何高效地找到好的中间点是一个实际挑战。如果数据集中缺少"桥梁"状态，分治效果会打折扣。
离线设定的局限：目前仅在离线设定下验证。在线版本（结合探索）可能需要额外的设计。
函数逼近误差：虽然递归深度减少了，但每一层的函数逼近误差仍然可能累积。\(O(\log T)\) 层的累积误差是否在实践中始终可控需要更多验证。
与分层RL的关系：分治策略与分层强化学习（Hierarchical RL）有天然联系，但本文未深入探讨。结合子目标发现方法可能进一步提升性能。
离线数据的覆盖度要求：TRL需要数据集中包含足够的"中间状态"来构建分治路径。对于稀疏数据集，这一要求可能成为瓶颈。

评分¶

新颖性: ⭐⭐⭐⭐⭐ （分治 + RL的创新结合，概念清晰优雅）
实验充分度: ⭐⭐⭐⭐ （长时间跨度基准上的优越表现）
写作质量: ⭐⭐⭐⭐ （算法动机和理论分析清晰易懂）
价值: ⭐⭐⭐⭐ （为GCRL值学习开辟了新范式）