Long-Horizon Language Model Reinforcement Learning via Progressive Point Matching
Preston Fu, Kevin Frans, Oleh Rybkin and Sergey Levine at UC Berkeley with Aviral Kumar at CMU give an unbiased dense-reward formulation, progressive point matching, that rewards partial progress at the segment level and scales exponentially better than sparse outcome rewards on long trajectories.
Ask this paper
Why sparse rewards stall: As tasks require longer and more complicated trajectories, outcome-only rewards make learning slow, and the usual fix of rewarding partial progress introduces bias that converges to suboptimal policies.
Unbiased by construction: Progressive point matching rewards partial progress on a segment level while remaining unbiased, which is the property the naive partial-credit formulations lack.
An exponential separation: The authors show, theoretically and in synthetic environments, that the segment-level formulation scales exponentially more efficiently to long-horizon tasks than sparse outcome rewards.
One reference trajectory per task: The practical instantiation needs only a single reference trajectory per task, which is a far weaker requirement than a dense hand-designed reward function.
Where sparse rewards get nothing: On extremely hard math reasoning problems sparse outcome rewards make no progress at all, while segment-level rewards improve success rate and pass@k as the test-time token budget grows.
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.