Related papers: Long-Horizon Language Model Reinforcement Learning via Progressive Point Matching

Long-Horizon Language Model Reinforcement Learning via Progressive Point Matching

URL: http://arxiv.org/abs/2609.07303v1
Date: Mon, 07 Sep 2026 10:21:41 GMT
Title: Long-Horizon Language Model Reinforcement Learning via Progressive Point Matching
Abstract summary: We show that a simple and unbiased dense reward formulation, which we term progressive point matching, scales exponentially more efficiently to long-horizon tasks.<n>On extremely hard math reasoning problems, sparse outcome rewards cannot make any progress, whereas segment-level rewards enable improvements at larger test-time token budgets.
Score: 70.73681123064533
License: http://creativecommons.org/licenses/by/4.0/
Abstract: Current paradigms for training language models via reinforcement learning rely heavily on sparse outcome rewards. However, as we pursue tasks that require longer and more complicated trajectories, such strategies result in slow learning. Prior work has attempted to address this problem by rewarding partial progress; however, naive formulations are often biased and converge to suboptimal policies. We show that a simple and unbiased dense reward formulation, which we term progressive point matching, scales exponentially more efficiently to long-horizon tasks by rewarding partial progress on a segment level, both theoretically and empirically via synthetic environments. We then show how progressive point matching can be practically instantiated using a single reference trajectory per task. On extremely hard math reasoning problems, sparse outcome rewards cannot make any progress, whereas segment-level rewards enable improvements at larger test-time token budgets when measured by success rate or pass@k.

Related papers

Training Multi-Turn Search Agent via Contrastive Dynamic Branch Sampling [29.182538022605627]
Branching Relative Policy Optimization (BranPO) is a value-free method that provides step-level contrastive supervision without dense rewards.<n>BranPO truncates trajectories near the tail and resamples alternative continuations to construct contrastive suffixes over shared prefixes.<n>To further boost efficiency and stabilize training, we introduce difficulty-aware branch sampling to adapt branching frequency across tasks, and redundant step masking to suppress uninformative actions.
arXiv Detail & Related papers (2026-02-03T16:43:09Z)
Provable Benefit of Curriculum in Transformer Tree-Reasoning Post-Training [76.12556589212666]
We show that curriculum post-training avoids the exponential complexity bottleneck.<n>Under outcome-only reward signals, reinforcement learning finetuning achieves high accuracy with sample complexity.<n>We establish guarantees for test-time scaling, where curriculum-aware querying reduces both reward oracle calls and sampling cost from exponential to order.
arXiv Detail & Related papers (2025-11-10T18:29:54Z)
Adaptive Reward Design for Reinforcement Learning [2.3031174164121127]
We propose a suite of reward functions that incentivize an RL agent to complete a task specified by a formula as much as possible.<n>We develop an adaptive reward shaping approach that dynamically updates reward functions during the learning process.
arXiv Detail & Related papers (2024-12-14T18:04:18Z)
DreamSmooth: Improving Model-based Reinforcement Learning via Reward Smoothing [60.21269454707625]
DreamSmooth learns to predict a temporally-smoothed reward, instead of the exact reward at the given timestep. We show that DreamSmooth achieves state-of-the-art performance on long-horizon sparse-reward tasks.
arXiv Detail & Related papers (2023-11-02T17:57:38Z)
Mixing between the Cross Entropy and the Expectation Loss Terms [89.30385901335323]
Cross entropy loss tends to focus on hard to classify samples during training. We show that adding to the optimization goal the expectation loss helps the network to achieve better accuracy. Our experiments show that the new training protocol improves performance across a diverse set of classification domains.
arXiv Detail & Related papers (2021-09-12T23:14:06Z)
Learning Guidance Rewards with Trajectory-space Smoothing [22.456737935789103]
Long-term temporal credit assignment is an important challenge in deep reinforcement learning. Existing policy-gradient and Q-learning algorithms rely on dense environmental rewards that provide rich short-term supervision. Recent works have proposed algorithms to learn dense "guidance" rewards that could be used in place of the sparse or delayed environmental rewards.
arXiv Detail & Related papers (2020-10-23T23:55:06Z)
Expert Training: Task Hardness Aware Meta-Learning for Few-Shot Classification [62.10696018098057]
We propose an easy-to-hard expert meta-training strategy to arrange the training tasks properly. A task hardness aware module is designed and integrated into the training procedure to estimate the hardness of a task. Experimental results on the miniImageNet and tieredImageNetSketch datasets show that the meta-learners can obtain better results with our expert training strategy.
arXiv Detail & Related papers (2020-07-13T08:49:00Z)
Wasserstein Distance guided Adversarial Imitation Learning with Reward Shape Exploration [21.870750931559915]
We propose a new algorithm named Wasserstein Distance guided Adrial Imitation Learning (WDAIL) for promoting the performance of imitation learning (IL) The experiment results show that the learning procedure remains remarkably stable, and achieves significant performance in the complex continuous control tasks of MuJoCo.
arXiv Detail & Related papers (2020-06-05T15:10:00Z)
Hierarchical Reinforcement Learning as a Model of Human Task Interleaving [60.95424607008241]
We develop a hierarchical model of supervisory control driven by reinforcement learning. The model reproduces known empirical effects of task interleaving. The results support hierarchical RL as a plausible model of task interleaving.
arXiv Detail & Related papers (2020-01-04T17:53:28Z)

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