Transitive RL: Value Learning via Divide and Conquer
This addresses the problem of efficient value learning in offline GCRL for robotics or planning applications, but it appears incremental as it builds on existing paradigms with specific improvements.
The paper tackles offline goal-conditioned reinforcement learning by introducing Transitive RL, a divide-and-conquer value learning algorithm that reduces bias accumulation and variance, achieving the best performance in long-horizon benchmark tasks.
In this work, we present Transitive Reinforcement Learning (TRL), a new value learning algorithm based on a divide-and-conquer paradigm. TRL is designed for offline goal-conditioned reinforcement learning (GCRL) problems, where the aim is to find a policy that can reach any state from any other state in the smallest number of steps. TRL converts a triangle inequality structure present in GCRL into a practical divide-and-conquer value update rule. This has several advantages compared to alternative value learning paradigms. Compared to temporal difference (TD) methods, TRL suffers less from bias accumulation, as in principle it only requires $O(\log T)$ recursions (as opposed to $O(T)$ in TD learning) to handle a length-$T$ trajectory. Unlike Monte Carlo methods, TRL suffers less from high variance as it performs dynamic programming. Experimentally, we show that TRL achieves the best performance in highly challenging, long-horizon benchmark tasks compared to previous offline GCRL algorithms.