# Long-Horizon Language Model Reinforcement Learning via Progressive Point Matching

arXiv: https://arxiv.org/abs/2609.07303 · HTML: https://mlsanity.com/paper/2609.07303/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 41 of its 55 references that are in the map.
- First posted on arXiv 7 Sep 2026.

## Builds on (most cited first, 30 of 41)

- [Proximal Policy Optimization Algorithms](https://mlsanity.com/paper/1707.06347/) (2017)
- [DeepSeekMath: Pushing the Limits of Mathematical Reasoning in Open Language Models](https://mlsanity.com/paper/2402.03300/) (2024)
- [Generative Adversarial Imitation Learning](https://mlsanity.com/paper/1606.03476/) (2016)
- [Hindsight Experience Replay](https://mlsanity.com/paper/1707.01495/) (2017)
- [STaR: Bootstrapping Reasoning With Reasoning](https://mlsanity.com/paper/2203.14465/) (2022)
- [On-Policy Distillation of Language Models: Learning from Self-Generated Mistakes](https://mlsanity.com/paper/2306.13649/) (2023)
- [Solving math word problems with process- and outcome-based feedback](https://mlsanity.com/paper/2211.14275/) (2022)
- [Process Reinforcement through Implicit Rewards](https://mlsanity.com/paper/2502.01456/) (2025)
- [Self-Distilled Reasoner: On-Policy Self-Distillation for Large Language Models](https://mlsanity.com/paper/2601.18734/) (2026)
- [Improve Mathematical Reasoning in Language Models by Automated Process Supervision](https://mlsanity.com/paper/2406.06592/) (2024)
- [The Lessons of Developing Process Reward Models in Mathematical Reasoning](https://mlsanity.com/paper/2501.07301/) (2025)
- [Reinforcement Learning via Self-Distillation](https://mlsanity.com/paper/2601.20802/) (2026)
- [ProcessBench: Identifying Process Errors in Mathematical Reasoning](https://mlsanity.com/paper/2412.06559/) (2024)
- [VAPO: Efficient and Reliable Reinforcement Learning for Advanced Reasoning Tasks](https://mlsanity.com/paper/2504.05118/) (2025)
- [Rewarding Progress: Scaling Automated Process Verifiers for LLM Reasoning](https://mlsanity.com/paper/2410.08146/) (2024)
- [DualDICE: Behavior-Agnostic Estimation of Discounted Stationary Distribution Corrections](https://mlsanity.com/paper/1906.04733/) (2019)
- [Self-Distillation Enables Continual Learning](https://mlsanity.com/paper/2601.19897/) (2026)
- [IQ-Learn: Inverse soft-Q Learning for Imitation](https://mlsanity.com/paper/2106.12142/) (2021)
- [Imitation Learning via Off-Policy Distribution Matching](https://mlsanity.com/paper/1912.05032/) (2019)
- [Exploration in Deep Reinforcement Learning: A Survey](https://mlsanity.com/paper/2205.00824/) (2022)
- [SelfCheck: Using LLMs to Zero-Shot Check Their Own Step-by-Step Reasoning](https://mlsanity.com/paper/2308.00436/) (2023)
- [Stream of Search (SoS): Learning to Search in Language](https://mlsanity.com/paper/2404.03683/) (2024)
- [Offline RL for Natural Language Generation with Implicit Language Q Learning](https://mlsanity.com/paper/2206.11871/) (2022)
- [REASONING GYM: Reasoning Environments for Reinforcement Learning with Verifiable Rewards](https://mlsanity.com/paper/2505.24760/) (2025)
- [Imitation Learning as f-Divergence Minimization](https://mlsanity.com/paper/1905.12888/) (2019)
- [Reinforcement and Imitation Learning via Interactive No-Regret Learning](https://mlsanity.com/paper/1406.5979/) (2014)
- [Process Reward Models That Think](https://mlsanity.com/paper/2504.16828/) (2025)
- [Deeply AggreVaTeD: Differentiable Imitation Learning for Sequential Prediction](https://mlsanity.com/paper/1703.01030/) (2017)
- [Provably Efficient Imitation Learning from Observation Alone](https://mlsanity.com/paper/1905.10948/) (2019)
- [Reinforcing General Reasoning without Verifiers](https://mlsanity.com/paper/2505.21493/) (2025)

## Abstract (arXiv)

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.