Transitive RL: Scaling Off-Policy RL via Divide and Conquer

BAIR has introduced Transitive RL (TRL), a new reinforcement learning algorithm that replaces traditional temporal difference (TD) learning with a "divide and conquer" paradigm. This approach allows off-policy RL to scale to complex, long-horizon tasks by reducing the number of Bellman recursions logarithmically rather than linearly, eliminating the need to tune n-step hyperparameters.

The Scalability Challenge of Off-Policy RL

Off-policy RL is critical for domains where data collection is expensive, such as robotics, healthcare, and dialogue systems, because it allows the use of any data, including old experiences and human demonstrations. However, scaling off-policy RL to long-horizon tasks has remained difficult due to the limitations of current value learning paradigms:

  • Temporal Difference (TD) Learning: Traditional Q-learning relies on bootstrapping, where errors in the next value $Q(s', a')$ propagate to the current value $Q(s, a)$. These errors accumulate over the entire horizon, hindering scalability.
  • Monte Carlo (MC) Returns: While n-step TD learning (TD-n) reduces Bellman recursions by a constant factor $n$, it does not fundamentally solve error accumulation. Increasing $n$ to reduce bias often leads to high variance and suboptimality, requiring careful per-task tuning.

The Divide and Conquer Paradigm

Transitive RL introduces a third paradigm that divides a trajectory into two equal-length segments and combines their values to update the value of the full trajectory. This method reduces the number of Bellman recursions logarithmically, avoiding the high variance of pure Monte Carlo methods and the tuning requirements of n-step TD.

Application to Goal-Conditioned RL

TRL is specifically implemented for goal-conditioned RL, where the objective is to learn a policy capable of reaching any state from any other state. This setting provides a natural structure based on the triangle inequality of shortest path distances $d^*(s, g)$:

$$d^(s, g) \le d^(s, w) + d^*(w, g)$$

In terms of value functions $V$ for sparse rewards, this translates to a "transitive" Bellman update rule:

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

This rule allows the value of $V(s, g)$ to be updated using two smaller values, $V(s, w)$ and $V(w, g)$, where $w$ is an optimal midpoint or subgoal.

Practical Implementation of TRL

To make divide-and-conquer value learning practical for continuous environments with large state spaces, TRL employs two key technical solutions to the problem of finding the optimal subgoal $w$:

  1. Restricted Search Space: Instead of searching the entire state space, TRL restricts the search for $w$ to states that appear in the dataset trajectory between $s$ and $g$.
  2. Expectile Regression: To prevent value overestimation typically caused by the $\max$ operator, TRL uses a "soft" argmax via expectile regression. The algorithm minimizes the following loss:

$$\mathbb{E}[\ell_{2\kappa}(V(s_i, s_j) - \bar{V}(s_i, s_k)\bar{V}(s_k, s_j))]$$

where $\bar{V}$ is the target value network and $\ell_{2\kappa}$ is the expectile loss with expectile $\kappa$, calculated over all tuples $(s_i, s_k, s_j)$ where $i \le k \le j$ in a sampled trajectory.

Performance and Benchmarks

TRL was evaluated on the OGBench benchmark for offline goal-conditioned RL, specifically focusing on the hardest versions of humanoidmaze and puzzle tasks involving 1B-sized datasets and horizons up to 3,000 environment steps.

  • Superiority over Baselines: TRL outperformed strong baselines across TD, MC, and quasimetric learning categories on most tasks.
  • Elimination of Hyperparameter Tuning: TRL matched the performance of the best individually tuned n-step TD learning (TD-n) across all tasks without requiring the user to specify a value for $n$.

Future Directions

While TRL currently assumes deterministic dynamics, BAIR identifies several paths for future development:

  • Generalization: Extending TRL to regular reward-based RL tasks beyond goal-conditioned settings.
  • Stochasticity: Adapting the algorithm to handle stochastic environments and partial observability, potentially using "stochastic" triangle inequalities.
  • Optimization: Improving subgoal candidate selection beyond the same trajectory and further stabilizing training.

Sources