Accelerating RL for LLM Reasoning with Optimal Advantage Regression

Kianté Brantley, Mingyu Chen, Zhaolin Gao, Jason D. Lee, Wen Sun, Wenhao Zhan, Xuezhou Zhang · 2025

Read Accelerating RL for LLM Reasoning with Optimal Advantage Regression by Kianté Brantley, Mingyu Chen, Zhaolin Gao, Jason D. Lee, Wen Sun, Wenhao Zhan, Xuezhou Zhang (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2505-20686.txt.

Introduction

Kianté Brantley and six co-authors propose in 2025 a faster way to train large language models with reinforcement learning so they reason better. Today's best methods are costly: they need many sample answers per prompt and often rely on extra critic networks that eat memory.

Their method, called A*-PO, works in two stages and directly estimates the optimal advantage function, the signal that tells the model which answers are better than average. By skipping much of the usual overhead, the approach aims to cut the cost of reasoning training. Cheaper training would let more teams improve model reasoning.

Catalog record

CREATORKianté Brantley, Mingyu Chen, Zhaolin Gao, Jason D. Lee, Wen Sun, Wenhao Zhan, Xuezhou Zhang
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE95 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2505-20686

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Accelerating RL for LLM Reasoning with Optimal Advantage Regression Kianté Brantley, Mingyu Chen, Zhaolin Gao, Jason D. Lee, Wen Sun, Wenhao Zhan, Xuezhou Zhang Abstract 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 ⋆ A^{\star} -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 ⋆ V^{\star} , 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 ⋆ A^{\star} -PO achieves competitive performance across a wide range of mathematical reasoning benchmarks, while reducing training time by up to 2 × \times and peak memory usage by over 30% compared to PPO, GRPO, and REBEL ( Gao et al., 2024a ) . Implementation of A ⋆ A^{\star} -PO can be found at https://github.com/ZhaolinGao/A-PO . 1 Introduction Recent advances in large language models (LLMs), including OpenAI-o1 ( OpenAI, 2024 ) , DeepSeek-R1 ( DeepSeek-AI, 2025 ) , and Kimi-1.5 ( Team, 2025 ) , have demonstrated remarkable reasoning capabilities. These models excel at producing long Chain-of-Thought (CoT) ( Wei et al., 2023 ; DeepSeek-AI, 2025 ; Zeng et al., 2025 ) responses when tackling complex tasks and exhibit advanced, reflection-like reasoning behaviors ( Gandhi et al., 2025 ) . A key factor driving these improvements is reinforcement learning (RL) with rule-based rewards derived from ground-truth answers ( Lambert et al., 2025 ; DeepSeek-AI, 2025 ; Team, 2025 ) , where models receive binary feedback indicating whether their final answers are correct. Substantial efforts have been devoted to refining RL algorithms, such as PPO ( Schulman et al., 2017 ) and GRPO ( Shao et al., 2024 ) , to further improve performance and training stability ( Richemond et al., 2024 ; Wang et al., 2024 ; Ji et al., 2024 ; Liu et al., 2024 ; Yu et al., 2025 ; Liu et al., 2025b ) . However, these methods either require explicit critic networks to estimate value functions or advantages, or rely on multiple generations per prompt, leading to substantial computational overhead and memory consumption. These limitations make it challenging to scale to long-context reasoning tasks and larger model sizes. This naturally raises the question: Can we develop simpler and more efficient RL algorithms for long context reasoning? Our answer is A^{\star} -PO, Policy Optimization via Optimal Advantage Regression, a policy optimization algorithm that uses only a single sample per prompt during online RL. Instead of relying on an explicit value network or multiple online generations to estimate the advantage of the current policy during training, our approach directly approximates the fixed optimal value function in an offline manner. We observe that the value function of the optimal policy of the KL-regularized RL can be expressed as an expectation under the reference policy. Based on this insight, the first stage of the algorithm performs offline sampling from the reference policy to estimate the optimal values for all prompts in the training set. This stage is highly parallelizable and can efficiently leverage fast inference libraries without requiring gradient computations. In the second stage, we perform on-policy updates via regressing optimal advantages via least square regression, where the advantages are constructed using the optimal values from the first stage. The on-policy updates only use a single generation per prompt, which drastically reduces both the computational and memory overhead associated with RL training. Thus, algorithmically, A^{\star} -PO eliminates heuristics such as clipping and response-wise reward normalization, resulting an extremely simple algorithm . Theoretically, we establish formal performance guarantees for A^{\star} -PO, showing that it achieves near-optimal performance. Notably, our theoretical analysis reveals that, without sophisticated exploration, A^{\star} -PO learns a near-optimal policy with polynomial sample complexity, as long as the base model’s probability of solving a math question is lower bounded above zero . Experimentally, we evaluate A^{\star} -PO extensively across a range of reasoning benchmarks, including GSM8K ( Cobbe et al., 2021 ) , MATH ( Hendrycks et al., 2021 ) , and competition-level datasets such as AMC, AIME, and HMMT. Across multiple model sizes, including Qwen2.5-1.5B, 3B, and 7B, our approach consistently achieves comparable or superior results to strong baselines such as PPO, GRPO, and REBEL ( Gao et al., 2024a ) , while achieving the lowest KL-divergence to the base model, and reducing training time by up to 2 \times and peak memory usage by over 30%. Figure 1 : We present A^{\star} -PO, an efficient, regression-based approach for LLM post-training. Prior methods such as GRPO and PPO incur high computational costs, either due to requiring multiple samples per prompt or maintaining an explicit value network. In contrast, A^{\star} -PO simplifies the training process by estimating the optimal value function using offline generations from \pi_{\mathsf{ref}} and requiring only a single response per prompt during online RL. As a result, A^{\star} -PO reduces training time by up to 2 \times compared to GRPO and PPO. 2 Preliminary In this work, we denote x as a prompt (e.g., a math question) and y as a generation (e.g., a reasoning chain plus a solution for a given math question). Consider the following KL-regularized RL objective: \displaystyle\max_{\pi}\mathbb{E}_{x,y\sim\pi(\cdot|x)}r(x,y)-\beta\mathsf{KL}(\pi(\cdot|x)|\pi_{\mathsf{ref}}(\cdot|x)). We mainly consider the setting where r is binary: r(x,y)=1 if the generation y contains the correct answer and 0 otherwise. It is well known that the optimal policy is \pi^{\star}(y|x)\propto\pi_{\mathsf{ref}}(y|x)\exp(r(x,y)/\beta) . We also denote V^{\star}(x) as the optimal value function of the KL-regularized RL objective above. It can be shown that V^{\star} has the following closed-form expression: \displaystyle\forall x:\;V^{\star}(x)=\beta\ln{\color[rgb]{0.8984,0.4531,0.2227}\boldsymbol{\mathbb{E}_{y\sim\pi_{\mathsf{ref}}(\cdot|x)}}}\left[\exp(r(x,y)/\beta)\right]. (1) Note that the expectation in V^{\star} is under \pi_{\mathsf{ref}} , which indicates a simple way of estimating V^{\star} : we can generate multiple i.i.d. responses from \pi_{\mathsf{ref}} and take the average to estimate V^{\star} . We will show that under realistic conditions, the bias and variance of such an estimator are well under control. We aim to learn a policy that can maximize the expected reward (e.g., maximize the average accuracy). Particularly, our theoretical results will model the performance gap between our learned policy and \pi^{\star} – the optimal policy of the KL-regularized RL objective, in terms of maximizing the expected reward. 3 Algorithm The algorithm consists of two stages. The first stage collects data from \pi_{\mathsf{ref}} and estimates V^{\star}(x) for all x in the training set. Particularly, for every x in the training set, we generate N i.i.d responses y_{1},\dots,y_{N} , and estimate V^{\star}(x) as: \widehat{V}^{\star}(x)=\beta\ln\left(\sum_{i=1}^{N}\exp(r(x,y_{i})/\beta)/N\right) . Note that in general \widehat{V}^{\star} is a biased estimate of V^{\star} due to the nonlinearity of the \ln function. However, we will show that as long as v_{\mathsf{ref}}(x) –the probability

Read the complete text