# Accelerating RL for LLM Reasoning with Optimal Advantage Regression

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

## Key facts

- Cited by 24 papers in the map (data through 14 Oct 2026).
- Placed in Reinforcement learning for reasoning, one of 17 directions in LLM reasoning.
- Builds on 43 of its 65 references that are in the map.
- First posted on arXiv 27 May 2025.

## Placed in

- LLM reasoning / [Reinforcement learning for reasoning](https://mlsanity.com/lr/reinforcement-learning-for-reasoning/)

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

- [Proximal Policy Optimization Algorithms](https://mlsanity.com/paper/1707.06347/) (2017)
- [Llama 2: Open Foundation and Fine-Tuned Chat Models](https://mlsanity.com/paper/2307.09288/) (2023)
- [Chain-of-Thought Prompting Elicits Reasoning in Large Language Models](https://mlsanity.com/paper/2201.11903/) (2022)
- [Training Verifiers to Solve Math Word Problems](https://mlsanity.com/paper/2110.14168/) (2021)
- [DeepSeekMath: Pushing the Limits of Mathematical Reasoning in Open Language Models](https://mlsanity.com/paper/2402.03300/) (2024)
- [DeepSeek-R1: Incentivizing Reasoning Capability in LLMs via Reinforcement Learning](https://mlsanity.com/paper/2501.12948/) (2025)
- [Measuring Mathematical Problem Solving With the MATH Dataset](https://mlsanity.com/paper/2103.03874/) (2021)
- [Qwen2.5 Technical Report](https://mlsanity.com/paper/2412.15115/) (2024)
- [DAPO: An Open-Source LLM Reinforcement Learning System at Scale](https://mlsanity.com/paper/2503.14476/) (2025)
- [Decoupled Weight Decay Regularization](https://mlsanity.com/paper/1711.05101/) (2017)
- [Solving Quantitative Reasoning Problems with Language Models](https://mlsanity.com/paper/2206.14858/) (2022)
- [Understanding R1-Zero-Like Training: A Critical Perspective](https://mlsanity.com/paper/2503.20783/) (2025)
- [Kimi k1.5: Scaling Reinforcement Learning with LLMs](https://mlsanity.com/paper/2501.12599/) (2025)
- [OlympiadBench: A Challenging Benchmark for Promoting AGI with Olympiad-Level Bilingual Multimodal Scientific Problems](https://mlsanity.com/paper/2402.14008/) (2024)
- [Tulu 3: Pushing Frontiers in Open Language Model Post-Training](https://mlsanity.com/paper/2411.15124/) (2024)
- [Does Reinforcement Learning Really Incentivize Reasoning Capacity in LLMs Beyond the Base Model?](https://mlsanity.com/paper/2504.13837/) (2025)
- [SimpleRL-Zoo: Investigating and Taming Zero Reinforcement Learning for Open Base Models in the Wild](https://mlsanity.com/paper/2503.18892/) (2025)
- [SLiC-HF: Sequence Likelihood Calibration with Human Feedback](https://mlsanity.com/paper/2305.10425/) (2023)
- [Cognitive Behaviors that Enable Self-Improving Reasoners, or, Four Habits of Highly Effective STaRs](https://mlsanity.com/paper/2503.01307/) (2025)
- [Self-Play Preference Optimization for Language Model Alignment](https://mlsanity.com/paper/2405.00675/) (2024)
- [Direct Nash Optimization: Teaching Language Models to Self-Improve with General Preferences](https://mlsanity.com/paper/2404.03715/) (2024)
- [Hybrid RL: Using Both Offline and Online Data Can Make RL Efficient](https://mlsanity.com/paper/2210.06718/) (2022)
- [A Minimalist Approach to LLM Reasoning: from Rejection Sampling to Reinforce](https://mlsanity.com/paper/2504.11343/) (2025)
- [A Minimaximalist Approach to Reinforcement Learning from Human Feedback](https://mlsanity.com/paper/2401.04056/) (2024)
- [Echo Chamber: RL Post-training Amplifies Behaviors Learned in Pretraining](https://mlsanity.com/paper/2504.07912/) (2025)
- [Reinforcement and Imitation Learning via Interactive No-Regret Learning](https://mlsanity.com/paper/1406.5979/) (2014)
- [Exploratory Preference Optimization: Harnessing Implicit Q*-Approximation for Sample-Efficient RLHF](https://mlsanity.com/paper/2405.21046/) (2024)
- [Correcting the Mythos of KL-Regularization: Direct Alignment without Overoptimization via Chi-Squared Preference Optimization](https://mlsanity.com/paper/2407.13399/) (2024)
- [An Empirical Study on Eliciting and Improving R1-like Reasoning Models](https://mlsanity.com/paper/2503.04548/) (2025)
- [Value-Incentivized Preference Optimization: A Unified Approach to Online and Offline RLHF](https://mlsanity.com/paper/2405.19320/) (2024)

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

- [Prompt Curriculum Learning for Efficient LLM Post-Training](https://mlsanity.com/paper/2510.01135/) (2025)
- [Single-stream Policy Optimization](https://mlsanity.com/paper/2509.13232/) (2025)
- [Decomposing the Entropy-Performance Exchange: The Missing Keys to Unlocking Effective Reinforcement Learning](https://mlsanity.com/paper/2508.02260/) (2025)
- [SPEC-RL: Accelerating On-Policy Reinforcement Learning with Speculative Rollouts](https://mlsanity.com/paper/2509.23232/) (2025)
- [LLMs Can Learn to Reason Via Off-Policy RL](https://mlsanity.com/paper/2602.19362/) (2026)
- [Stable and Efficient Single-Rollout RL for Multimodal Reasoning](https://mlsanity.com/paper/2512.18215/) (2025)
- [Coverage Improvement and Fast Convergence of On-policy Preference Learning](https://mlsanity.com/paper/2601.08421/) (2026)
- [Learning from Synthetic Data Improves Multi-hop Reasoning](https://mlsanity.com/paper/2603.02091/) (2026)
- [On the optimization dynamics of RLVR: Gradient gap and step size thresholds](https://mlsanity.com/paper/2510.08539/) (2025)
- [textttSPECS: Faster Test-Time Scaling through Speculative Drafts](https://mlsanity.com/paper/2506.15733/) (2025)
- [Is RL fine-tuning harder than regression? A PDE learning approach for diffusion models](https://mlsanity.com/paper/2509.02528/) (2025)
- [Understanding Reinforcement Learning for Model Training, and future directions with GRAPE](https://mlsanity.com/paper/2509.04501/) (2025)
- [Future Policy Approximation for Offline Reinforcement Learning in LLM Reasoning](https://mlsanity.com/paper/2509.19893/) (2025)
- [Variance-Aware Baselines and Adaptive Learning Rates for Reinforcement Learning with Verifiable Rewards](https://mlsanity.com/paper/2511.23310/) (2025)
- [Skip-Connected Policy Optimization for Implicit Advantage](https://mlsanity.com/paper/2604.08690/) (2026)
- [Alignment Tuning for Large Language Models: A Data-Centric Lens on Alignment Data Pipelines](https://mlsanity.com/paper/2605.26442/) (2026)
- [BASIS: Batchwise Advantage Estimation from Single-Rollout Information Sharing for LLM Reasoning](https://mlsanity.com/paper/2605.27293/) (2026)
- [Off-Policy Learning to Reason Works Because It Is More Pessimistic Than You Think](https://mlsanity.com/paper/2605.28150/) (2026)
- [Stratified Consistency Distillation for Natural Language Formalization](https://mlsanity.com/paper/2608.30258/) (2026)
- [Back to Blackwell: Closing the Loop on Intransitivity in Multi-Objective Preference Fine-Tuning](https://mlsanity.com/paper/2602.19041/) (2026)
- [Partition Function Estimation under Bounded f-Divergence](https://mlsanity.com/paper/2602.23535/) (2026)
- [MInTRL: Off-policy Intervention can boost On-policy RL](https://mlsanity.com/paper/2609.12419/) (2026)
- [SAGE: Mitigating Long-Horizon Reasoning Biases via Topological Guidance](https://mlsanity.com/paper/2609.30192/) (2026)
- [Policy as Data: Replay-Based Policy Dual Averaging via Advantage Regression](https://mlsanity.com/paper/2610.04638/) (2026)

## Abstract (arXiv)

Reinforcement learning (RL) has emerged as a powerful tool for fine-tuning large language models (LLMs) to improve complex reasoning abilities. However, state-of-the-art policy optimization methods often suffer from high computational overhead and memory consumption, primarily due to the need for multiple generations per prompt and the reliance on critic networks or advantage estimates of the current policy. In this paper, we propose A*-PO, a novel two-stage policy optimization framework that directly approximates the optimal advantage function and enables efficient training of LLMs for reasoning tasks. In the first stage, we leverage offline sampling from a reference policy to estimate the optimal value function V*, eliminating the need for costly online value estimation. In the second stage, we perform on-policy updates using a simple least-squares regression loss with only a single generation per prompt. Theoretically, we establish performance guarantees and prove that the KL-regularized RL objective can be optimized without requiring complex exploration strategies. Empirically, A*-PO achieves competitive performance across a wide range of mathematical reasoning benchmarks, while reducing training time by up to 2× and peak memory usage by over 30% compared to PPO, GRPO, and REBEL. Implementation of A*-PO can be found at https://github.com/ZhaolinGao/A-PO.