RLVR landscapes for iterated multiplications can be benign: Insights from spin-glass theory
cs.LG, cond-mat.dis-nn, stat.ML
Submitted: 2026-09-23
Updated: 2026-09-23
License: http://creativecommons.org/licenses/by/4.0/
The gist: Despite the importance of reinforcement learning with verifiable rewards (RLVR), the extent to which it can learn new reasoning capabilities remains debated.
Terminology
Abstract
Despite the importance of reinforcement learning with verifiable rewards (RLVR), the extent to which it can learn new reasoning capabilities remains debated. Here we study the optimization landscape of RLVR on algorithmic tasks, such as iterated group and quasigroup multiplication. To this end, we map entropy-regularized RLVR over myopic tabular policies onto an energy-based (spin-glass) model over deterministic policies. This mapping upper-bounds what RLVR can achieve, and lets us rigorously characterize the landscape in this tabular setting. We show, both theoretically and experimentally, that for a wide class of models and tasks with uncorrelated inputs, this landscape is benign, containing no local minima that could trap RLVR training. Rather, the practical difficulty of these tasks appears to stem, at least in part, from issues such as diffusive barriers and gradient-estimation error in traversing the landscape. These are genuine obstacles that can prevent a solution from being found, but they are distinct from the landscape itself being rugged. We show that these obstacles can often be mitigated through the choice of entropy regulator. Consistent with this theory, we find that a transformer trained from scratch, using only last-token rewards, successfully learns an algorithmic chain of thought for iterated non-Abelian group multiplications.
Sources
- On the Theory of Policy Gradient Methods: Optimality, Approximation, and Distribution Shift
- Global Optimality Guarantees For Policy Gradient Methods
- The Entropy Mechanism of Reinforcement Learning for Reasoning Language Models
- DeepSeek-R1: Incentivizing Reasoning Capability in LLMs via Reinforcement Learning
- Revisiting Policy Gradients for Restricted Policy Classes: Escaping Myopic Local Optima with $k$-step Policy Gradients
- Non-Uniform Noise-to-Signal Ratio in the REINFORCE Policy-Gradient Estimator
- VCRL: Variance-based Curriculum Reinforcement Learning for Large Language Models
- Revisiting Entropy in Reinforcement Learning for Large Reasoning Models
- Reinforcement Learning and Control as Probabilistic Inference: Tutorial and Review
- Sequential Group Composition: A Window into the Mechanics of Deep Learning
- The Quantization Model of Neural Scaling
- The Primacy Bias in Deep Reinforcement Learning
- Hybrid Reinforcement: When Reward Is Sparse, It's Better to Be Dense
- Beyond the 80/20 Rule: High-Entropy Minority Tokens Drive Effective Reinforcement Learning for LLM Reasoning
- RAGEN: Understanding Self-Evolution in LLM Agents via Multi-Turn Reinforcement Learning
- PAEC: Position-Aware Entropy Calibration for LLM Reasoning in RLVR
- DAPO: An Open-Source LLM Reinforcement Learning System at Scale
- Does Reinforcement Learning Really Incentivize Reasoning Capacity in LLMs Beyond the Base Model?
Related papers
- Polynomial-Augmented Neural Networks (PANNs) with Weak Orthogonality Constraints for Enhanced Function and PDE Approximation
- AIRL-S: Unifying Reinforcement Learning and Search-Based Test-Time Scaling via Adversarial Inverse Reinforcement Learning
- Transformers as Bayesian In-Context Experimenters: Smoothness-Adaptive Efficient ATE Estimation
- Convergence issues in Relational Concept Analysis based on AOC-posets
- Beliefs Beyond Posteriors: The Predictive Cost of ELBO Binding
- Understanding Diffusion Models via Ratio-Based Function Approximation with SignReLU Networks