Transitive RL: Value Learning via Divide and Conquer

• URL: http://arxiv.org/abs/2510.22512v1
• Date: Sun, 26 Oct 2025 03:32:31 GMT
• Title: Transitive RL: Value Learning via Divide and Conquer
• Authors: Seohong Park, Aditya Oberai, Pranav Atreya, Sergey Levine,
• Abstract summary: Transitive Reinforcement Learning (TRL) is a new value learning algorithm based on a divide-and-conquer paradigm.<n>Unlike Monte Carlo methods, TRL suffers less from high variance as it performs dynamic programming.
• Score: 54.190627631246166
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: 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.

Related papers

• RAPID: An Efficient Reinforcement Learning Algorithm for Small Language Models [27.643632808936403]
  Reinforcement learning (RL) has emerged as a promising strategy for finetuning small language models (SLMs) to solve targeted tasks such as math and coding.<n>RL algorithms tend to be resource-intensive, taking a significant amount of time to train.<n>We propose a novel RL algorithm that can substantially reduce the running time of RL.
  arXiv  Detail & Related papers  (2025-10-03T20:58:49Z)
• RoiRL: Efficient, Self-Supervised Reasoning with Offline Iterative Reinforcement Learning [4.311472216447055]
  Reinforcement learning is central to improving reasoning in large language models (LLMs)<n>We propose RoiRL: Reasoning with offline iterative Reinforcement Learning.<n>We show that RoiRL trains to 2.5x faster and consistently outperforms TTRL on reasoning benchmarks.
  arXiv  Detail & Related papers  (2025-10-03T10:59:26Z)
• $Q\sharp$: Provably Optimal Distributional RL for LLM Post-Training [63.602824642605775]
  $Qsharp$ is a value-based algorithm for KL-regularized RL that guides the reference policy using the optimal regularized $Q$ function.<n>Our results highlight $Qsharp$ as an effective approach for post-training LLMs, offering both improved performance and theoretical guarantees.
  arXiv  Detail & Related papers  (2025-02-27T21:43:00Z)
• Is Value Learning Really the Main Bottleneck in Offline RL? [70.54708989409409]
  We show that the choice of a policy extraction algorithm significantly affects the performance and scalability of offline RL. We propose two simple test-time policy improvement methods and show that these methods lead to better performance.
  arXiv  Detail & Related papers  (2024-06-13T17:07:49Z)
• Hybrid Inverse Reinforcement Learning [34.793570631021005]
  inverse reinforcement learning approach to imitation learning is a double-edged sword. We propose using hybrid RL -- training on a mixture of online and expert data -- to curtail unnecessary exploration. We derive both model-free and model-based hybrid inverse RL algorithms with strong policy performance guarantees.
  arXiv  Detail & Related papers  (2024-02-13T23:29:09Z)
• RL$^3$: Boosting Meta Reinforcement Learning via RL inside RL$^2$ [12.111848705677142]
  We propose RL$3$, a hybrid approach that incorporates action-values, learned per task via traditional RL, in the inputs to Meta-RL.<n>We show that RL$3$ earns a greater cumulative reward in the long term compared to RL$2$ while drastically reducing meta-training time and generalizes better to out-of-distribution tasks.
  arXiv  Detail & Related papers  (2023-06-28T04:16:16Z)
• Train Hard, Fight Easy: Robust Meta Reinforcement Learning [78.16589993684698]
  A major challenge of reinforcement learning (RL) in real-world applications is the variation between environments, tasks or clients. Standard MRL methods optimize the average return over tasks, but often suffer from poor results in tasks of high risk or difficulty. In this work, we define a robust MRL objective with a controlled level. The data inefficiency is addressed via the novel Robust Meta RL algorithm (RoML)
  arXiv  Detail & Related papers  (2023-01-26T14:54:39Z)
• A Tutorial on Meta-Reinforcement Learning [69.76165430793571]
  We cast the development of better RL algorithms as a machine learning problem itself in a process called meta-RL.<n>We discuss how, at a high level, meta-RL research can be clustered based on the presence of a task distribution and the learning budget available for each individual task.<n>We conclude by presenting the open problems on the path to making meta-RL part of the standard toolbox for a deep RL practitioner.
  arXiv  Detail & Related papers  (2023-01-19T12:01:41Z)
• RL-DARTS: Differentiable Architecture Search for Reinforcement Learning [62.95469460505922]
  We introduce RL-DARTS, one of the first applications of Differentiable Architecture Search (DARTS) in reinforcement learning (RL) By replacing the image encoder with a DARTS supernet, our search method is sample-efficient, requires minimal extra compute resources, and is also compatible with off-policy and on-policy RL algorithms, needing only minor changes in preexisting code. We show that the supernet gradually learns better cells, leading to alternative architectures which can be highly competitive against manually designed policies, but also verify previous design choices for RL policies.
  arXiv  Detail & Related papers  (2021-06-04T03:08:43Z)
• FOCAL: Efficient Fully-Offline Meta-Reinforcement Learning via Distance Metric Learning and Behavior Regularization [10.243908145832394]
  We study the offline meta-reinforcement learning (OMRL) problem, a paradigm which enables reinforcement learning (RL) algorithms to quickly adapt to unseen tasks. This problem is still not fully understood, for which two major challenges need to be addressed. We provide analysis and insight showing that some simple design choices can yield substantial improvements over recent approaches.
  arXiv  Detail & Related papers  (2020-10-02T17:13:39Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.