mlsanityData to 14 Oct 2026

Post-Training with Policy Gradients: Optimality and the Base Model Barrier

arXiv 2603.06957 ↗First posted 7 Mar 2026stat.ML cs.AI cs.LGcited by 3

On the map: Deep reinforcement learning methods → RL theory and sample complexity

Abstract (arXiv)

We study post-training linear autoregressive models with outcome and process rewards. Given a context boldsymbolx, the model must predict the response boldsymboly ∈ YN, a sequence of length N that satisfies a γ margin condition, an extension of the standard separability to sequences. We prove that on test samples where the base model achieves a non-trivial likelihood α, a variant of policy gradient (PG) can achieve likelihood 1 - varepsilon with an essentially minimax optimal number of reward queries tildeO((α-1 + varepsilon-1)/γ2). However, a barrier arises for going beyond the support of the base model. We prove that the overall expected error after post-training with outcome rewards is governed by a property of the base model called the Likelihood Quantile (LQ), and that variants of PG, while minimax optimal, may require a number of reward queries exponential in N to go beyond this support, regardless of the pre-training algorithm. To overcome this barrier, we study post-training with a process reward model, and demonstrate how PG variants in this setting avoid the curse of dimensionality in N via dependence on a token-level LQ. Along the way, we prove that under the margin condition, SGD with adaptive learning rate (LR) achieves a near optimal test error for statistical learning, and PG with adaptive LR achieves a near optimal number of mistakes for online learning while being computationally efficient whenever possible, both of which may be of independent interest.

Key facts. Cited by 3 papers in the map (data through 14 Oct 2026). Placed in RL theory and sample complexity, one of 15 directions in Deep reinforcement learning methods. Builds on 28 of its 37 references that are in the map. First posted on arXiv 7 Mar 2026.

Builds on

28 of 37 references.

Closest ancestors · 1

Same direction, newest first

  1. 2025Outcome-Based Online Reinforcement Learning: Algorithms and Fundamental Limits26 May

Other references · 27

  1. 2017Proximal Policy Optimization Algorithmscited by 15,215
  2. 2024DeepSeekMath: Pushing the Limits of Mathematical Reasoning in Open Language Modelscited by 9,379
  3. 2023Let's Verify Step by Stepcited by 3,789
  4. 2025Kimi k1.5: Scaling Reinforcement Learning with LLMscited by 1,210
  5. 2025Does Reinforcement Learning Really Incentivize Reasoning Capacity in LLMs Beyond the Base Model?cited by 982
  6. 2017The Implicit Bias of Gradient Descent on Separable Datacited by 655
  7. 2025Process Reinforcement through Implicit Rewardscited by 504
  8. 2025Reinforcement Learning with Verifiable Rewards Implicitly Incentivizes Correct Reasoning in Base LLMscited by 289
  9. 2024Rewarding Progress: Scaling Automated Process Verifiers for LLM Reasoningcited by 279
  10. 2020On the Global Convergence Rates of Softmax Policy Gradient Methodscited by 264
  11. 2025Spurious Rewards: Rethinking Training Signals in RLVRcited by 209
  12. 2019Global Convergence of Policy Gradient Methods to (Almost) Locally Optimal Policiescited by 124
15 more
  1. 2025Reasoning with Sampling: Your Base Model is Smarter Than You Thinkcited by 89
  2. 2025Scaling Test-Time Compute Without Verification or RL is Suboptimalcited by 84
  3. 2021On the Convergence and Sample Efficiency of Variance-Reduced Policy Gradient Methodcited by 70
  4. 2022An Improved Analysis of (Variance-Reduced) Policy Gradient and Natural Policy Gradient Methodscited by 68
  5. 2025Is a Good Foundation Necessary for Efficient Reinforcement Learning? The Computational Role of the Base Model in Explorationcited by 36
  6. 2025The Coverage Principle: How Pre-Training Enables Post-Trainingcited by 30
  7. 2020Gradient Methods Never Overfit On Separable Datacited by 29
  8. 2025Metastable Dynamics of Chain-of-Thought Reasoning: Provable Benefits of Search, RL and Distillationcited by 25
  9. 2013The price of bandit information in multiclass online classificationcited by 24
  10. 2025Do We Need to Verify Step by Step? Rethinking Process Supervision from a Theoretical Perspectivecited by 17
  11. 2021Beyond Bandit Feedback in Online Multiclass Classificationcited by 14
  12. 2019Bandit Multiclass Linear Classification: Efficient Algorithms for the Separable Casecited by 11
  13. 2024The Implicit Bias of Gradient Descent on Separable Multiclass Datacited by 11
  14. 2025How Reinforcement Learning After Next-Token Prediction Facilitates Learningcited by 10
  15. 2025Multiclass Loss Geometry Matters for Generalization of Gradient Descent in Separable Classificationcited by 2

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2026: 3.

3 papers.

  1. 2026RubricEM: Meta-RL with Rubric-guided Policy Decomposition beyond Verifiable Rewardscited by 12
  2. 2026High-Dimensional Statistics: Reflections on Progress and Open Problemscited by 4
  3. 2026The Role of Generator Access in Autoregressive Post-Trainingcited by 0

Similar, not cited

Close in wording, no citation either way

  1. 2026Fine-Tuning on Self-Generated and Reward-Weighted Data: Learning Dynamics, Convergence Rates, and Benefits of Off-Policyness
  2. 2026MaD-RL: Matching Distributions for Calibrating LLMs with Reinforcement Learning
  3. 2025From Data to Rewards: a Bilevel Optimization Perspective on Maximum Likelihood Estimation
  4. 2025Reinforcement Learning with Verifiable Rewards: GRPO's Effective Loss, Dynamics, and Success Amplification
  5. 2026Demystifying Reinforcement Learning Post-Training of Language Models
  6. 2025Shrinking the Variance: Shrinkage Baselines for Reinforcement Learning with Verifiable Rewards
  7. 2026On Advantage Estimates for Max@K Policy Gradients
  8. 2026RL Post-Training Diffusion Language Models Along Their Own Generation Paths