[2509.22613] Benefits and Pitfalls of Reinforcement Learning for Language Model Planning: A Theoretical Perspective

Computer Science > Artificial Intelligence arXiv:2509.22613 (cs) [Submitted on 26 Sep 2025 (v1), last revised 3 Mar 2026 (this version, v2)] Title:Benefits and Pitfalls of Reinforcement Learning for Language Model Planning: A Theoretical Perspective Authors:Siwei Wang, Yifei Shen, Haoran Sun, Shi Feng, Shang-Hua Teng, Li Dong, Yaru Hao, Wei Chen View a PDF of the paper titled Benefits and Pitfalls of Reinforcement Learning for Language Model Planning: A Theoretical Perspective, by Siwei Wang and 7 other authors View PDF HTML (experimental) Abstract: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 desi...