# Benefits and Pitfalls of Reinforcement Learning for Language Model Planning: A Theoretical Perspective

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 35 of its 41 references that are in the map.
- First posted on arXiv 26 Sep 2025.

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

- [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)
- [Playing Atari with Deep Reinforcement Learning](https://mlsanity.com/paper/1312.5602/) (2013)
- [A Survey on Large Language Model based Autonomous Agents](https://mlsanity.com/paper/2308.11432/) (2023)
- [Voyager: An Open-Ended Embodied Agent with Large Language Models](https://mlsanity.com/paper/2305.16291/) (2023)
- [HybridFlow: A Flexible and Efficient RLHF Framework](https://mlsanity.com/paper/2409.19256/) (2024)
- [Does Reinforcement Learning Really Incentivize Reasoning Capacity in LLMs Beyond the Base Model?](https://mlsanity.com/paper/2504.13837/) (2025)
- [Progress measures for grokking via mechanistic interpretability](https://mlsanity.com/paper/2301.05217/) (2023)
- [SFT Memorizes, RL Generalizes: A Comparative Study of Foundation Model Post-training](https://mlsanity.com/paper/2501.17161/) (2025)
- [The Entropy Mechanism of Reinforcement Learning for Reasoning Language Models](https://mlsanity.com/paper/2505.22617/) (2025)
- [PlanBench: An Extensible Benchmark for Evaluating Large Language Models on Planning and Reasoning about Change](https://mlsanity.com/paper/2206.10498/) (2022)
- [On the Planning Abilities of Large Language Models : A Critical Investigation](https://mlsanity.com/paper/2305.15771/) (2023)
- [Can Language Models Solve Graph Problems in Natural Language?](https://mlsanity.com/paper/2305.10037/) (2023)
- [GPT4Graph: Can Large Language Models Understand Graph Structured Data ? An Empirical Evaluation and Benchmarking](https://mlsanity.com/paper/2305.15066/) (2023)
- [The Landscape of Agentic Reinforcement Learning for LLMs: A Survey](https://mlsanity.com/paper/2509.02547/) (2025)
- [LLaGA: Large Language and Graph Assistant](https://mlsanity.com/paper/2402.08170/) (2024)
- [A Survey of Reinforcement Learning for Large Reasoning Models](https://mlsanity.com/paper/2509.08827/) (2025)
- [Let Your Graph Do the Talking: Encoding Structured Data for LLMs](https://mlsanity.com/paper/2402.05862/) (2024)
- [Agent Lightning: Train ANY AI Agents with Reinforcement Learning](https://mlsanity.com/paper/2508.03680/) (2025)
- [GraphLLM: Boosting Graph Reasoning Ability of Large Language Model](https://mlsanity.com/paper/2310.05845/) (2023)
- [Scaling Test-Time Compute Without Verification or RL is Suboptimal](https://mlsanity.com/paper/2502.12118/) (2025)
- [Evaluating Cognitive Maps and Planning in Large Language Models with CogEval](https://mlsanity.com/paper/2309.15129/) (2023)
- [Octopus: Embodied Vision-Language Programmer from Environmental Feedback](https://mlsanity.com/paper/2310.08588/) (2023)
- [Understanding Transformer Reasoning Capabilities via Graph Algorithms](https://mlsanity.com/paper/2405.18512/) (2024)
- [GraphInstruct: Empowering Large Language Models with Graph Understanding and Reasoning Capability](https://mlsanity.com/paper/2403.04483/) (2024)
- [Plan-Seq-Learn: Language Model Guided RL for Solving Long Horizon Robotics Tasks](https://mlsanity.com/paper/2405.01534/) (2024)
- [Can Graph Learning Improve Planning in LLM-based Agents?](https://mlsanity.com/paper/2405.19119/) (2024)
- [Simulation of Graph Algorithms with Looped Transformers](https://mlsanity.com/paper/2402.01107/) (2024)
- [How Do Large Language Models Understand Graph Patterns? A Benchmark for Graph Pattern Comprehension](https://mlsanity.com/paper/2410.05298/) (2024)
- [ToolPlanner: A Tool Augmented LLM for Multi Granularity Instructions with Path Planning and Feedback](https://mlsanity.com/paper/2409.14826/) (2024)

## Built on by (most cited first, 4 of 4)

- [Efficient Estimation of Kernel Surrogate Models for Task Attribution](https://mlsanity.com/paper/2602.03783/) (2026)
- [Peer-Predictive Self-Training for Language Model Reasoning](https://mlsanity.com/paper/2604.13356/) (2026)
- [Ground-Truth Neighborhood Regularization for Reinforcement Learning Post-Training of Time Series Foundation Models](https://mlsanity.com/paper/2608.08010/) (2026)
- [When Do Hallucinations Arise? A Graph Perspective on the Evolution of Path Reuse and Path Compression](https://mlsanity.com/paper/2604.03557/) (2026)

## Abstract (arXiv)

Recent reinforcement learning (RL) methods have substantially enhanced the planning capabilities of Large Language Models (LLMs), yet the theoretical basis for their effectiveness remains elusive. In this work, we investigate RL's benefits and limitations through a tractable graph-based abstraction, focusing on policy gradient (PG) and Q-learning methods. Our theoretical analyses reveal that supervised fine-tuning (SFT) may introduce co-occurrence-based spurious solutions, whereas RL achieves correct planning primarily through exploration, underscoring exploration's role in enabling better generalization. However, we also show that PG suffers from diversity collapse, where output diversity decreases during training and persists even after perfect accuracy is attained. By contrast, Q-learning provides two key advantages: off-policy learning and diversity preservation at convergence. We further demonstrate that careful reward design is necessary to prevent Q-value bias in Q-learning. Finally, applying our framework to the real-world planning benchmark Blocksworld, we confirm that these behaviors manifest in practice.