Accelerating RL for LLM Reasoning with Optimal Advantage Regression
Authors: Kianté Brantley
Mingyu Chen
Zhaolin Gao
Jason D. Lee
Wen Sun
Wenhao Zhan
Xuezhou Zhang
Venue: NeurIPS 2025 poster ()
Keywords: reinforcement learning
large language models
reasoning
Primary area: reinforcement_learning

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^\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^\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^\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. Implementation of $A^\star$-PO can be found at https://github.com/ZhaolinGao/A-PO.

Accelerating RL for LLM Reasoning with Optimal Advantage Regression
Kianté Brantley', Mingyu Chen', Zhaolin Gao Jason D. Lee", Wen Sun', Wenhao Zhan', Xuezhou Zhang Harvard University, Boston University, *Comeell University, "Princeton University
Abstract
Reinforcement learning (RL) has emerged as 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 over- head 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 A0-PO, 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, 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, and prove that the KL-regularized RL objective can be optimized without requiring complex exploration strategies. Empirically, AO achieves competitive perfor- mance across wide range of mathematical reasoning benchmarks, while reducing training time by up 2x and peak memory usage by over 30% compared PPO, GRPO, and REBEL[Gao et al., 2024a]. Implementation of -*-PO can be found at https: / titu.b..... cow com/ZhaolinGae AAO.
establish performance guarantees
Introduction
Recent advances in large language models (LLMs), including OpenAI-ol [OpenAI, 2024], DeepSeek- RI [De,pSeek-AI, 2025], and Kimi-1.5 [Team, 2025]. have demonstrated remarkable reasoning capabilities. These models excel producing long Chain-of-Thought (Wei et al., 2023, DeepSeek-AI, 2025, Zeng et al., 2025] responses when tackling complex tasks and exhibit advanced, reflection-like reasoning behaviorsGGandhi al., 2025]. A key factor driving these improvements is reinforcement learning (RL) with rule-based rewards derived from ground-truth answers [Lambert al., 2025, DeepSeek-AI. 2025, Team, 2025], where models receive binary feedback indicating whether their final answers are correct.
Substantial efforts have been devoted refining RL algorithms, such as PPO [Schulman 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 multiple generations per prompt, leading substantial computational overhead and memory consumption. These limitations make challenging to scale to long-context reasoning tasks and larger model sizes. This naturally raises the question: Can develop simpler and more efficient RL algorithms for long context reasoning?
Authhrrs listed in alphabetical order of their last names. Correspondence to mingyucdbu. edu, 2g2928cornell. edu, wenhao. zhan@princetoo..co
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

PPO
GRPO
PO
Trainino Time (hrs)
C.( (x)
CeC (x)
y
10
Vxx,y)
A (x)
online
online
offline
online
GSMBK
MATH
Figure 1: We present A -O, an efficient, regression- approach for LLM post-training Prior methods such GRPO and PPO incur high computational costs, either due requiring multiple samples per prompt or maintaining an explicit value network. In contrast, A*-PO simplifies the training process by estimating the optimal value function using offline generations from ref and requiring only a single response per prompt during online RL. As a result, -*-PO reduces training time by up 2x compared to GRPO and PPO.
Our answer is A POO 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 training, our approach directly approximates the fixed optimal value function in an offline manner. We observe that the value funetion of the optimal policy of the KL.rregllarized RI. can expressed as 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. regressing optimal advantages with least square regression, where the advantages are constructed using the optimal values from the first stage. The on 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, PPO eliminates heuristics such as clipping and response-wise reward normalization, resulting extremely simple algorithm.
estimate the advantage of the current policy during
the second stage, we perform on-policy updates via
Theoretically, we establish formal performance guarantees for A'-PO, showing that it achieves near-optimal performance. Notably, our theoretical analysis reveals that, without sophisticated exploration, -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 PO extensively across a range reasoning benchmarks, including GSM8K [Cobbe et al., 20211, 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, approach consistently achieves comparable 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 2x and peak memory usage by over 30%.
2 Preliminary
In this work, we denote x as a prompt (c.g., math question) and y as a generation (c.g., a reasoning chain plus solution for given math question). Consider the following KL-regularized RL objective:
max (a) y) (KKL(T(-12)) (-1z)) m.
We mainly consider the setting where r is binary: r(x, y) = 1 the generation y contains the correct answer and 0 otherwise. It is well known that the optimal policy is x² (v(l)> x (y(z)) exp(r(z, B). We also denote V V*(x) as the optimal value function of the KL-regularized RL objective above. It can be shown that V* has the following closed-form expression:
Vx: V*(x)= = -1 Bynmae()la) [exp(r(z, v)/
Note that the expectation V is under Tref, which indicates a simple way of estimating V*: we can generate multiple i.i.d. responses from Tref and take the average to estimate V*, We will show that under realistic conditions, the bias and variance of such an estimator are well under control. We aim to learn 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 x., the optimal policy of the KL-regularized RL objective, in terms of maximizing the expected reward.

---

Algorithm A*-P:: Policy Optimization via Optimal Advantage Regression
Require: Training prompts set X, reference policy Traf, temperature B, sample size N, iterations T Ensure: Learned policy ør
1: ### Stage 1: Estimating V*(x)) for all training prompts x in
2: for all x E X' do
3: Draw N i...d. samples {uel ~ xt(((11 2))
4: Compute (z)) 3 in N E exp(r(z, w)/)))
5: end for
6: (Optional: eliminate all training prompts whose N solutions are all wrong)
7: ### Stage 2: On-policy Update with one rollout per prompt
8: for to T do
9: Collect a batch of training samples D = {az, y)} with X and y <e(-(x)
10: Update policy ne to 1 by performing SGD on the following least square loss (T)
(((T) = Σ
(8
<(vl)) (x]())
(r(z. V* (=()))
(x.N)ED
11: end for
3 Algorithm
The algorithm consists of two stages. The first stage collects data from ref and estimates (*(x) for all in the training set. Particularly, for every in the training set, we generate N i.i.d responses
y1,-.. UN. and estimate (xx as: (*(x)= = 31 E>> exp(r(æ, 3:)/3)/N) Note that in general
V+ is a biased estimate of V* due to the nonlinearity of the In function. However, we will show that as long as Uret (r), the probability of Tref generating a correct solution at is lower bounded above zero, then the bias (z) (x)] can be well controlled and shrinks quickly N increases. We emphasize that while this stage requires generating N responses per prompt æ from Tref can be done completely offline, the data can be collected efficiently in parallel without any gradient computation, and any off-shelf faster inference library can be used for this stage.
The second stage performs the on-policy update. Specifically, at iteration i, given the current policy Te, we optimize the following loss:
(vlx)) Traf (y)oz)
(r(x,,) V -Vn))))
(T) ;= (ugyome(()l)) Bl
where the expectation is taken under the current policy n; and r(æ; y) V* approximates the optimal advantage A Ar v) = r(ar y) (11)-V' V=(x) in the bandit setting as Q1x y) = r(x, he)h the name -POP To estimate the least-squares loss (T). we collect a batch of online samples {(x, v)} with y Tt (-12)) and perform small number of stochastic gradient descent steps, starting from ne- to obtain the updated policy T as outlined in Algorithm 1. Notably, during this online stage, we generate only single sample y per prompt x, significantly accelerating the training.
The motivation behind the above loss is that when V KL-regularized RI. objective is the global minimizer of the least-squares regression loss, regardless of the distribution under which the expectation is defined (i.c., MSE is always zero under **). Unlike popular RL algorithms such as PPO [Schulman et al., 2017] and GRPO [Shao et al., 2024], we do not apply clipping mechanism to constrain π++1 from deviating too far from ,,. Instead, we introduce a single regularization term based on the KL divergence to the fixed reference policy Teef. Furthermore, while PPO and GRPO rely on the advantage of the current policy, defined as A := r(z, y) - (I), we instead use the optimal advantage A". A key benefit of using V is that it can pre-computed efficiently using large number of samples from nuef (Eq. (1)), whereas t must be estimated on the fly, requiring either multiple generations during training (e.g., GRPO or RLOO [Kool al., 2019]) or maintaining an explicit critic network (e.g., PPO). Since A only generates one response per prompt. it also climinates the heuristic of response-wist reward
V (xr). the optimal policy x' for the
3

---

Test Accuracy
90
90
90
85
85
85
RITHE:
A
80
80
1:59
75
75
10
15
20
40
60
80
100
0.2
0.3
0.4
Training Time (bours)
Peak Memory Usage (%)
KI[(1] (Rad))
[
Figure 2: Test accuracy versus training time, peak memory usage, and KL divergence across four baselines and three model sizes GSM8K. Our approach (orange) can achieve comparable performance (accuracy) to baselines GRPO and PPO, while being 2x faster, more memory efficient, and achieving smaller KL divergence. Note that for A A*-PO, the training time includes the time from both stages (i.e., offline data collection from ref and online RL training).
normalization. Finally, most existing policy optimization algorithms- PG [Williams, 1992], TRPO [Schulman al., 2015], GRPO, PPO, and REBEL [Gao et al., follow the idea of approximate policy ileration [Bertsekas and Tsitsiklis, 1996, Kakade and Langford, 2002] where T--1 1 designed approximately optimize the advantage function of the current policy AA subject to an implicit or explicit constraint that prevents it from deviating too far from Te. The consequence of relying on such an approximate policy iteration style update that it requires additional strong structural condition such as policy completeness [Bhandari and Russo, 2024]. In contrast, -P-PO does not follow the approximate policy iteration paradigm. It places no explicit constraints on keeping Te-1 close to Te. Instead, it directly aims to learn x² by regressing on the optimal advantages.
Experiments
Our implementation of A*-PO closely follows the pseudocode in Algorithm 1, with the only mod- ification of using two different Kl-rregularization coefficients, 81 and (3, during stages and respectively. In stage 1, we employ a relatively large 31 to ensure smoother estimation of (*)x). In contrast, a smaller 32 is used in stage 2 to relax the KL constraint to Tref, encouraging the learned policy to better optimize the reward. Although this introduces additional hyperparameter, find that the same set of 31 and 32 works well across different datasets and model sizes, and therefore, we keep them fixed throughout all experiments. In stage 1, sample N 8 responses per prompt to estimate the optimal value function with 81 = 1/2. At stage 2, we collect a dataset = (æ, y) with x E X' and y Tx(- æ)), and optimize the least-squares regression objective using gradient descent with AdamW W [Loshchilov and Hutter, 2017] and B2 = le 3. We empirically evaluate the performance of -POO across various reasoning datasets, model sizes, and evaluation benchmarks. Additional details are provided in Appendix A, and qualitative analysis is shown in Appendix B.
4.1 Basic Reasoning GSM8K
Training Details. We conduct experiments the GSM8K dataset [Cobbe al., 2021], which consists of grade school-level math problems. We compare A against several baseline RL algorithms, including PPO [Schulman al., 2017], GRPO [Shao et al., 2024], and REBEL [Gao et al., 2024a]. Simpler policy gradient methods such as REINFORCE with Leave-One-Out (RLOO) [Kool et al., 2019] are not included, as prior work has shown that REBEL consistently outperforms RLOO in performance with similar computational efficiency [Gao et al., 2024a]. We sample two generations per prompt for GRPO and use a model of the same size the policy for the critic PPO. Following the DeepSeek-RR R1 training recipe [DeepSeek-AA, 2025], we perform RL directly on the base model without any prior supervised fine-tuning (SFT). We report results using three different model 1.5B, 3B, and 7B 7B-based on the pre-trained Qwen2.5 models [Qwen, 2025] with a maximum context length of 1,024. A rule-based reward function used, assigning for correct answers and for incorrect ones. All experiments are implemented using the VERL framework [Sheng et al., 2025].

---

Model Size
Time (hrs)
Memory (%)
KL. (nt[[Frett
Minerva Math
Olympiad Bench
AMC: 23
Method
MATH500
Avg@32
base
/
45.8
16.91
17.66
20.55
PPO
10.84
42.64
0.151
57.0
21.69
20.92
29.84
1,58
GRPO
15.01
42.19
0.091
58.0
22.79
21.07
32.19
REBEL
10.33
63.34
0.098
57.8
20.22
23.15
31.67
A*-PO
6.92
41.59
0.069
57.8
22.43
22.26
31.88
base
/
50.8
23.16
23.74
29.77
PPO
13.59
54.95
0.111
65.8
23.90
26.71
34.68
3B
GRPO
18.26
49.75
0.102
66.0
25.00
28.93
34.61
REBEL
12.88
74,32
0.099
67.0
27.57
28. 19
36.33
A'-PO
8.78
49.28
0.082
66.2
25.74
28.04
35.47
base
/
62.8
22.43
30.56
39.61
PPO
20.53
92.81
0.133
74.4
30.88
33.98
55.47
7B
GRPO
20.15
77.82
0.172
73.2
33.46
33.98
55.86
REBEL
14.67
98.77
0.124
74.6
34.56
34.72
56.88
AP
11.01
76.57
0.078
76.2
34.56
34.27
56.25
Table 1: Results on MATH. For each metric, the best-performing method is highlighted in bold, and the second-best is underlined.
Evaluation. We evaluate each method based on its trade-off between accuracy and KL-divergence on the validation set, assessing the effectiveness of each algorithm in optimizing the KL-regularized RL objective. Additionally, we report the peak GPU memory usage (as percentage of total available memory) during backpropagation, as well as the total training time (in hours) for each method. Both runtime and memory usage are measured using 4 H100 GPUs under the same hyperparameter settings detailed in Appendix A.5. The training time for AO also includes the offline generation time in stage 1. Peak memory usage is averaged over 100 batches.
PO is faster, more memory-efficient, and better optimizes the KL-constrained RL objective. Figure 2 presents the training time, peak memory usage, and KL divergence ree across four methods and three model sizes. While all methods achieve similar test accuracy, they exhibit substantial differences in the other three metrics. Although REBEL achieves comparable training time as AT-PO, requires significantly more memory due to processing two generations simultaneously during each update. GRPO shows similar peak memory usage requires two generations per prompt and performs twice as many updates as A -PO, leading to approximately 2 longer training time. PPO incurs both higher computational cost and memory usage due its reliance on an explicit critic. By consistently updating with respect to Tref. -OO maintains the smallest KL divergence to reference policy, Overall, PPO achieves the fastest training time, lowest peak memory usage, and smallest KL. divergence compared to all baselines with similar test accuracy.
4.2 Advanced Reasoning on MATH
Training Details. In this section, we evaluate on the more advanced MATH dataset [Hendrycks et al., 2021], which consists of challenging problems from high school math competitions. Following the original experimental setup, we use 7,500 questions for training and randomly select 1,000 questions for validation. We adopt the same model and hyperparameter settings the previous section.
Evaluation. Following prior work [Zeng et al., 2025], we evaluate model performance on stan- dard mathematical reasoning benchmarks, including MATH500 [Hendrycks et al., 2021]. Minerva Math [Lewkowyez et al., 2022], and OlympiadBench [He et al., 2024]. as well as the competition- level AMC 2023 benchmark. For AMC 2023, due to the small size of the benchmark (40 questions), we report average accuracy over 32 generations to reduce variance.
A*-PO achieves higher accuracy, is the fastest and generalizes effectively across benchmarks. Table 1 presents the results, where the best persorerfonnnn method is highlighted in bold and the second- best is underlined. As shown, -O-PO consistently ranks as either the best or second-bes, method across various benchmarks and model sizes, while being faster than baselines, especially PPO and GRPO, when model size is large (e.g., 2x faster than PPO and GRPO for 7B model size). AP-PO also the most memory efficient and achieves the smallest KI. divergence to the base mdoel meet- For in-distribution test set MATH500, A PPO achieves similar performance to baselines smaller
5

---

Method
AIME 24
AIME 25
HMMT Feb 24
HMMT Feb 25
Average
Avg@:32 32
Pass 32
Avg
Pass 32
Av
Pass 32
Avg
Pass
Pass 62
21.25
21.15
43.33
9,48
36.67
8.85
15.21
42.50
PPO
30.94
80.00
25.12
46.67
15.94
43.33
14,06
50.00
21.52
55.00
GRPO
30.00
73.33
25.00
43.33
15.63
40.00
13.23
40.00
20.97
49.17
AO-P
29.17
46.67
16.77
43.33
13.65
43.33
21.57
50.83
Table 2:
Long-context reasoning results using the DeepSeek Distilled 1.5B Model. For each
metric, the best-performing method is highlighted in bold.
N
N N-
N
N
N N1-15
16
N - 32
0.72
0.75
67.0
Squared Regression Loss
66.6
0.71
Training Reward
66.5
66.6
0.70
MATH500
66.0
0.70
65.5
65.2
0.69
0.68
64.5
0.67
0.60
61.0
16
32
Step
Step
Figure 3: Ablation results with different number of N for estimating V*. Solid lines indicate the moving average with window size 100. (Left) Squared regression loss per step of A*-PO. (Middle) Training reward per step. (Right) Model performance MATH500 with varying values of N.
model sizes (1.5B and 3B), but outperforms on the larger model size (7B). One may wonder explicitly pre-computing V* for all training prompts would result overfitting to the training set. When evaluating on the out-of-domain benchmarks, PPOPO also demonstrates strong generalization capabilities.
4.3 Long-context Reasoning with DeepSeek--isttilld Qwen
Training Details. In this section, assess the ability of A train with long context lengths. We use the DeepSeek-RR RI distilled Qwen-1.55 model [DeepSeek-AI, 2025] with a context length of 16,384, training on a randomly selected subset of 5,000 problems from the VGS-AI/OpenRI ICClenne dataset [Wang et al., 2025]. We limit training to a subset of the dataset due to the large scale of the original corpus and the significant computational cost of data generation and training on academic hardware. We exclude results for REBEL, as it runs out of memory under this long-context setting. The same hyperparameter configurations from the previous section are used.
Evaluation. We evaluate on competition-level AIME and HMMT benchmarks from 2024 and 2025, reporting both Avg @ 32 and Pass@33 metries.
A' outperforms baselines and effectively scales long-context reasoning. The results are presented in Table 2, with the best-performing method highlighted in bold. -P-PO achieves the highest performance on AIME 2025 and HMMT February 2024, and performs comparably to GRPO and PPO on AIME 2024 and HMMT February 2025. Averaged over these 4 math competition benchmarks, -PO achieves the best performance (measured under the metric of Avg@32), 32). These results demonstrate that estimating V using 8 generations remains effective reasoning scenarios, and that A*PPO can be successfully applied to such settings. Unsurprisingly, POO remains the most efficient method, requiring only 49 hours of training time, compared to 88 hours for PPO and 90 hours for GRPO.
in long-context
4.4 Ablations
Number of Generations. We conduct ablation on the number of generations N used during stage I to estimate V* on the MATH dataset with the model, varying N from to 32. The results are shown in Figure 3, We observe that the squared regression loss consistently decreases N increases,

---

indicating that larger values of N lead to more accurate estimations of V*. The accuracy of this estimation significantly affects both the training reward and downstream evaluation metries, such as performance on MATH500. Notably, the training reward increases almost monotonically with larger N, and a similar trend observed for performance on MATH500, which begins to plateau at N We provide discussion of the plateau behavior in Appendix C.
Filtering Out Hard Problems. For fair comparison the baselines, our main result did not filter out hard ques- tions where pass@1 N is zero. In this section, we explore whether training efficiency can be further improved by filtering out problems whose pass@1 N is zero. Note that pass @ N can be easily estimated using the N samples generated from phase of PPO The intuition is that problems the reference policy Tef is unable to solve (i.e.,
Stage 2 Training Time
Filtered
Not Filtered
Not Filtered Stage 2 Traaining
MATH500
with near-zero success probability) are unlikely to be solved through RL post-training. Our method naturally supports this filtering mechanism, as we already estimate V* during the offline stage. We conduct an ablation study varying N from to 32, filtering out problems where all N sampled responses are incorrect. The results are shown in Figure 4. Filtering significantly reduces training time by reducing the effective size of the training set, illus- trated by the green bars compared to the dashed baseline. When N is small, filtering removes more problems since it is more likely that none of the responses are correct, further accelerating training. In terms of performance, the MATH500 evaluations for filtered and unfiltered runs remain closely aligned. Notably, the filtered run with N 8 achieves the highest accuracy, even surpassing the unfiltered baseline while reducing training time by 28%.
32
N
Figure 4: Ablation Results on Filtering Hard Prompts. (Green) Training time of Stage 2 for different values of N. The dashed line indicates the training time without filtering. (Purple) Performance on MATH500 with and without filtering.
31 for Estimating V*. The parameter 31 controls the level of smoothness when estimating V*. As 3 + O, the estimated V<'s value approaches Pass@N (computed using the collected N responses), while 31 oc, it estimates V" Proofs of these limiting cases are provided in Appendix D. We ablate 31 from oo to 1/8, and the results are shown in Figure 5. From the squared regression loss, observe that smaller values of 31 lead to higher initial training loss. But the final training loss decreases monotonically as 31 decreases, until reaching 31 = 1/8. A similar trend is observed for both the training reward and MATH500 performance, which improve monotonically with smaller 3, values up to 31 1/8. Further decreasing 3, may produce an overly optimistic estimate of V*, which the model cannot realistically achieve, ultimately hindering performance.
5 Theory
In this section, present a theoretical analysis of more general variant of Algorithm I and demonstrate that the output policy achieves near-optimal expected performance against π², the optimal policy of the KL-regularized RL objective, with polynomial complexity. Surprisingly, we will see that under reasonable conditions of Teef, we can achieve the above goal withour explicit exploration. Denote p(x) as the probability of ret returning correct solution and assume min, p(x) 2 Uref > 0, the key message of this section is that:
KL-regularized RL with 3 > 0 and Usef > can be solved without any sophisticated exploration (e.g., optimism in the face of uncertainty).
We demonstrate the above key message via reduction to no-regret online learning. Specifically, we assume access to a possibly stochastic no-regret oracle NR. In each iteration, the oracle invoked with the historical estimated losses 1 and policy class II to compute a distribution qe E A(TT) over policies for the next iteration: qe NR(fi.--11 1, II). We then sample a policy n. qr and use it to generate a prompt-response pair where x, ~ p and 3/+ ~ ne(-(x.). Here p is the distribution
For simplicity, we just assume each iteration our on-policy batch only contains one (æz, yr) pair.
7

---

P1
===2
=1=1
8.
1/2
01 1/4
8, = 1/8
0.70
0.73
67.0
Squared Regresion Loss
Training Reward
0.72
66.5
06.4
06.4
0.69
MATH500
66.0
65.3
63.5
0.68
65.0
64.5
0.67
0.69
200
400
600
400
450
500
550
600
2
1/2
1/4
178
Step
Stop
A3
Figure 5: Ablation results with different 31 for estimating V*. Solid lines indicate the moving average with window size 100. (Left) Squared regression loss per step of A*-PO. (Middle) Training reward per step. (Right) Model performance on MATH500 with varying values of 31.
of the prompts in the dataset. Given the pair (Ir,, vt), we construct the following least square loss Ey:
(T)
( @1
(v)
(n(Ze, B))
Tof (ye [.,))
Algorithm 1 indeed is a specific instance of the above algorithm that leverages online gradient descent (OGD) [Hazan al., 2016] as the oracle NR. We Reg(T) to denote the cumulative regret of NR over 7 iterations:
T
T
Reg(T)
= Σ
Exwa
E
[(((T)
min
Σ (TT). KEll
1=1
Remark. When the policy class and loss functions are convex, deterministic no-regret oracles such as OGD and mirror descent [Hazan al., 2016] can guarantee a regret bound of Reg(T) = O(VT). In more general settings, stochastic oracles like Netrapalli, 2020] are also capable of achieving vT regret.
perturbed--eedee (FTPL. [Suggala and
Due to the possible randomness of NR, will utilize the decoupling coefficient (DC), standard complexity measure in contextual bandits [Zhang, 2022, 2023, Li et al., 2024], to characterize the difficulty of learning over the policy class
Definition 1. The decoupling coefficient DC(II) is defined as the smallest d O such that for all distribution q on II:
E (1 [In (y] - x (ulx)) S Bo
(y) - In n (y ()]=:)
DC is perhaps the most general structural condition known in the contextual bandit and RL theory literature, and known to be much more general than other popular measures such as Eluder dimension [Zhang, 2023] which cannot casily capture non-linear structures in the problems.
Our analysis relies on some standard assumptions. We first assume that the policy class is realizable. Assumption 1. Suppose that n² TT.
Next, we assume the loss function is bounded.
Assumption 2. Suppose that ||xx| S Ci where (x, v) = B In =(1lz)
for all π E II.
x [x]])
The above assumption mainly ensures that our predictor π Kref has bounded outputs, a standard ussumption that is used in least squares regression analysis. These assumptions are commonly adopted in the policy optimization literature as well [Rosset al., 2024, Xie al., 2024, Gao et al., b024a,b, Huang et al., 2024].
Recall that our loss uses V to approximate V*, We introduce simple and reasonable condition which can ensure the bias V V*I is small.

---

Assumption 3. Suppose that we have By-ma((1) (m 3)] 2 uref > for all z.
Assumption 3 is practically reasonable, which intuitively says that hope ref has non-zero @ass@k value at z. For example, consider Vr = 0.03. One can show that with probability greater than 90%, Teer's 's Pass@50 on a is one. In practice, we typically do not expect RL post-traun post-training can solve problems whose Pass @ 50 under Tyef is zero anyway.
Now are ready to present bound on the performance gap between the output policies and x² Theorem 1. Suppose that Assumptions 1 to 3 hold true. With probability at least - 6, we have
T
(C
DC(II)C Ln(1/6)
1
Ex (z, v)
Exagge Ex (I,, U)1 2
+
T
T
T
((min exp (0)
1, Uref })
DC(IT)
In( (n((2118))
(2)
N
Theorem I shows that the performance gap decays with rates O (RT and O (N-+) +).
implying that a near-optimal policy can be learned with polynomial sample complexity as long as RTg(T) sublinear. Based on this theoretical guarantee, our algorithm exhibits two notable advantages over existing provable online policy optimization methods:
Only realizability. Our approach optimizes sequence of loss functions constructed from on-policy samples. Unlike other on on-policy policy optimization approaches (e.g., PG [Bhandari and Russo, 2024] and its variants PPO [Schulman et al., 2017], REBEL [Gao et al., 2024a]) which often relies on a stronger condition called policy completeness, our approach relies on much weaker realizability condition.
No exploration. Our method does not incorporate any explicit exploration mechanism such as optimism in the face of uncertainty or reset to some exploratory distribution. As result, it is conceptually simpler and more computationally efficient. For instance, the loss function & is just a least square regression loss. Treating In as predictor, then the loss lg is convex functional with respect in π as whole. In contrast, prior work that relies on explicit exploration (c.g.. optimism in the face of uncertainty) requires bi-level optimization which often leads to non-convex loss functionals [Cen et al., 2024, Xie et al., 2024].
Case study: log-linear policies. We present the learning guarantee for log- lin-linear policies as special case where we show that our simple regression loss indeed can be optimized via simple SGD, Consider the following log-linear policy class:
11
To To(y/æ) Ey exp (0, y'))
exp (10, o(s, v)))
0 0 e 0
where O C Rdd is the parameter space and Φ: X' y Rd represents predefined feature vectors. First, instantiating the learning oracle NR as FTPL [Suggala and Netrapalli, 2020], we can achieve sublinear regret when learning -og-linear policies:
Corollary 1 (log-linear policies with FTPL, Informal). Consider the log-lineer policy class II defined in Eq. (3), Suppose Assumptions to hold true and use FTPL as the NR oracle. Then we have the following regret with probability at least 1 5:
Enyyar rxx, v)
1
Σ
T
Exagee (I,
d3
+
(dC3In(1/8))
T
T
T32
d 1
((min) exp
-1, - Uref
1 1
1
})
exp
N
Alternatively, we can select OGD as NR, following the practical implementation in Algorithm 1. In this case, our analysis requires an additional assumption, which states that the Fisher information matrix remains full-rank throughout the algorithm's 's runtime.

---

Assumption 4. Suppose there exists À > 0 such that we have A(o,) = AI for all where A(0) is the Fisher information matrix:
A(0) = (o ())( - [0 wttp://weee....ooooooooooooo.
Under Assumption 4, show that OGD is able to learn x² with O convergence rate:
Theorem 2 (log-linear policies with OGD, Informal). Consider the log-lineet ag-linear policy class II defined in Eq. (3). Suppose Assumptions I, 2 and 4 hold true and use OGD as the NR oracle. Then we have with probability at least 1 - ó that:
B T
9In(T/1) BXT
CiBIn(1/0) BXT
Eu y) Ee v)] <
This theorem suggests that Algorithm 1 has three key strengths over existing policy optimization methods [Gao al., 2024a, Cen et al., 2024, Xie et al., 2024] for log-linear policies:
Last-iterate convergence. Unlike existing methods that output a mixture of all the online policies, Algorithm 1 ensures that the final policy #T+1 is close to π², which is more favorable in practice.
Dimension-free learning rate. The learning rate of Algorithm is independent of the parameter space dimension d, making it scalable for nigh-dimensional function classes. Computational efficiency. OGD is computationally efficient and trackable in practice.
More details are presented in Appendices E to G.
6 Related Work
RL for LLM Reasoning. Reinforcement learning (RL) has become a standard for post-training
LLMs, including Reinforcement Learning from Human Feedback (RLHF) [Christiano et al., 2017, Touvron et al., 2023] and Reinforcement Learning with Verifiable Rewards (RLVR) [DeepSeek- AI, 2025]. Notable examples include GRPO [Shao et al., 2024], DR-GRPO [Liu al., 2025a], DAPO [Liu et al., 2024], OREO [Wang et al., 2024], DQO [Ji et al., 2024], and RAFT++ [Xiong al., 2025]. Similar OREO, DAPO, DQO, and DRO, - operates efficiently by requiring only a single response per prompt and regressing the log ratio of æ and Tee to the advantage. However, unlike these methods, PO eliminates the need to train an explicit critie for value estimation, further improving its computational efficiency.
Exploration in RL. To combat the slow convergence and suboptimal policies yielded by classic entropy-based methods [Schulman et al., 2017, Shao et al., 2024], recent work has studied active exploration [Xiong al., 2024, Ye et al., 2024, Xie et al., 2024], which offers stronger theoretical guarantees but often suffers from practical instability, In contrast, motivated by recent findings [Zhao al., 2025, Yue et al., 2025] that exploring beyond the base model's knowledge is frequently waste- ful-and that existing RL methods struggle to outperform the base model's s pass @ K performance POOPO is designed for more realistic setting, where Fref has non-zero pass K (for some reasonably large K) on the target prompts. We show that in this setting, active exploration is unnecessary: A provably converges to n² with polynomial sample complexity, achieving both efficiency and meaningful optimality. Additional discussions of the related works are provided in Appendix H.
7 Conclusion
We introduced AOOPO, a simple and efficient policy optimization algorithm that directly regresses the estimated optimal advantage function, removing the need for critics and multiple generations per prompt. also completely removes heuristies such as clipping and trajectory reward normalization. A'-PO enables faster and more memory-efficient training, achieves smaller KI.-divergences to the base model, and consistently achieves competitive or superior performance on reasoning benchmarks, with strong theoretical guarantees.
10

---

Acknowledgements
KB acknowledge: This work has been made possible in part by a gift from the Chan Zuckerberg Initiative Foundation to establish the Kempner Institute for the Study of Natural and Artificial Intelligence. ZG supported by Linkedln under the Linkedln- Cornell Grant. WS acknowledges fundings from NSF IIS-215471,, NSF CAREER 2339395, DARPA LANCER: LeArning Network CybERRgents, Infosys Cornell Collaboration, and Sloan Research Fellowship.
References
Mohammad Gheshlaghi Azar, Zhaohan Daniel Guo, Bilal Piot, Remi Munos, Mark Rowland, Michal Valko, and Daniele Calandriello. A general theoretical paradigm to understand learning from human preferences. In International Conference on Artificial Intelligence and Statistics, pages 4447-4455. PMLR, 2024.
Kazuoki Azuma. Weighted sums of certain dependent random variables. Tohoku Mathematical Journal, Second Series, 193))357-367, 1967.
Chenjia Bai, Yang Zhang, Shuang Qiu, Qiaosheng Zhang, Kang Xu, and Xuelong Li. Online prefer- ence alignment for language models via count-based exploration. arXiv preprint 123: 2025.
Dimitri Bertsekas and John Tsitsiklis. Neuro-dynamic programming. Athena Scientific, 1996.
Alina Beygelzimer, John Langford, Lihong Li, Lev Reyzin, and Robert Schapire. Contextual bandit algorithms with supervised learning guarantees. In Proceedings of the Fourleenth International Conference on Artificial Intelligence and Statistics, pages 19-26. JMLR Workshop and Conference Proceedings, 2011.
Jalaj Bhandari and Daniel Russo. Global optimality guarantees for policy gradient methods. Opera- lions Research, 72(5): 1906-1977, 2024.
Shicong Cen, Jincheng Mei, Katayoon Goshvadi, Hanjun Dai, Tong Yang, Sherry Yang, Dale Schuurmans, Yuejie Chi, and Bo Dai. Value-incentivizedd preference optimization: A unified approach online and offline rlhf. arXiv preprint arXiv:2405. 19320, 2024.
Mingyu Chen, Yiding Chen, Wen Sun, and Xuezhou Zhang. Avoiding exp(rmax) scaling in rlhf through preference-based exploration. arXiv preprint arXiv:2502.00666, 2025a.
Zhipeng Chen, Yingqian Min, Beichen Zhang, Jie Chen, Jinhao Jiang, Daixuan Cheng, Wayne Xin Zhao, Zheng Liu, Xu Miao, Yang Lu, Lei Fang, Zhongyuan Wang, and Ji-Rong Wen. An empirical study on eliciting and improving rl-like reasoning models, 2025b. URL https://arxix: org/ abs/2503. 04548.
Paul F Christiano, Jan Leike, Tom Brown, Miljan Martic, Shane Legg, and Dario Amodei. Deep reinforcement learning from human preferences. Advances in neural information processing systems, 30, 2017.
Karl Cobbe, Vineet Kosaraju, Mohammad Bavarian, Mark Chen, Heewoo Jun, Lukasz Kaiser, Matthias Plappert, Jemry Tworek, Jacob Hilton, Reïchhro Nakano, et al. Training verifiers to solve math word problems. arXiv preprint arXiv:2110. 10.166,, 2021.
Thomas M Cover. Elements of information theory. John Wiley & Sons, 1999.
DeepSeek-AL. Deepseek-rl: Incentivizing reasoning capability in llms via reinforcement learning,
2025. URL htt.https// ptttps://arxivv org/ abs/ 12948.
Vikranth Dwaracherla, Seyed Mohammad Asghari, Botao Hao, and Benjamin Van Roy. Efficient exploration for llms. arXiv preprint arXiv:2402.00336, 2024.
Kanishk Gandhi, Ayush Chakravarthy, Anikait Singh, Nathan Lile, and Noah D. Goodman. Cognitive behaviors that enable self-improving reasoners, or, four habits of highly effective stars, 2025. URL https:/ puttps://arxiz //txxv/a/vvv//////////eee//aaav/ org/abs//500 01300. 01307.
11

---

Zhaolin Gao, Jonathan Chang, Wenhao Zhan, Owen Oertell, Gokul Swamy, Kianté Brantley, Thorsten Joachims, Drew Bagnell, Jason D Lee, and Wen Sun. Rebel: Reinforcement learning via regressing relative rewards. Advances in Neural Information Processing Systems, 37:52354-52400 2024a.
Zhaolin Gao, Wenhao Zhan, Jonathan D Chang. Gokul Swamy, Kianté Brantley, Jason D Lee, and Wen Sun. Regressing the relative future: Efficient policy optimization for multi-turn rlhf. arXiv preprint arXiv:2410.046/2 2024b.
Elad Hazan et Introduction to online convex optimization. Foundations and Trends@ in Optimiza- lion, 2(3-4):157-325, 2016.
Chaoqun He, Renjie Luo, Yuzhuo Bai, Shengding Hu, Zhen Leng Thai, Junhao Shen, Jinyi Hu, Xu Han, Yujie Huang, Yuxiang Zhang, Jie Liu, Lei Qi, Zhiyuan Liu, and Maosong Sun. Olympiad- bench: A challenging benchmark for promoting agi with olympiad-level bilingual multimodal scientific problems, 2024. URL htttps:///axiii org/ abs/2402 14008.
Dan Hendrycks, Collin Burns, Saurav Kadavath, Akul Arora, Steven Basart, Eric Tang, Dawn Song, and Jacob Steinhardt. Measuring mathematical problem solving with the math dataset, 2021. URL
https: /ttrii/////ai//e/eeeeeeeeeeeaaaa htt://aaxxvv.roaaabbe bbtrg//b//// 220.. 03874.
Audrey Huang, Wenhao Zhan, Tengyang Xie, Jason Lee, Wen Sun, Akshay Krishnamurthy, and Dy- lan J Foster. Correcting the mythos of kl-regularization: Direct alignment without overoptimization via chi-squared preference optimization. arXiv preprint arXiv: 13399, 2024.
Kaixuan Ji, Guanlin Liu, Ning Dai, Qingping Yang, Renjie Zheng. Zheng Wu, Chen Dun, Quanquan Gu, and Lin Yan. Enhancing multi-step reasoning abilities of language models through direct q-function optimization. arXiv preprint arXiv:2410.09300 2024.
Sham Kakade and John Langford. Approximately optimal approximate reinforcement learning. In Proceedings of the nineteenth international conference on machine learning, pages 267-274, 2002.
Wouter Kool, Herke van Hoof, and Max Welling. Buy 4 reinforce samples, get a baseline for free! DeepRLStructreed@ICC 2019.
Nathan Lambert, Jacob Morrison, Valentina Pyatkin, Shengyi Huang, Hamish Ivison, Faeze Brahman, Lester James V. Miranda, Alisa Liu, Nouha Dziri, Shane Lyu, Yuling Gu, Saumya Malik, Victoria Graf, Jena D. Hwang, Jiangjiang Yang, Ronan Le Bras, Oyvind Tafjord, Chris Wilhelm, Luca Soldaini, Noah A. Smith, Yizhong Wang, Pradeep Dasigi, and Hannaneh Hajishirzi. Tulu 3: Pushing frontiers in open language model post- post-training. 2025. URL https: aattps://att //arxiv. org/ abs/ 2411. 15124.
Aitor Lewkowycz, Anders Andreassen, David Dohan, Ethan Dyer, Henryk Michalewski, Vinay Ramasesh, Ambrose Slone, Cem Anil, Imanol Schlag, Theo Gutman-Solo, Yuhuai Wu, Behnam Neyshabur, Guy Gur-Ari, and Vedant Misra. Solving quantitative reasoning problems with language models, 2022. URL httpt:/t//aaae http://aaxvvvv./ www.oos//////ooooooooooooeee 22tgg//bs/200..... 14858.
Xuheng Li, Heyang Zhao, and Quanquan Gu. Feel-good thompson sampling for contextual dueling bandits. arXiv preprint arXiv:2404.0600 06013, 2024.
Jiacai Liu, Chaojie Wang, Chris Yuhao Liu, Liang Zeng, Rui Yan, Yiwen Sun, Yang Liu, and Yahui Zhou. Improving multi-step reasoning abilities of large language models with direct advantage policy optimization. arXiv preprint ar 2rXiv:24/2.1882 18279, 2024.
Zichen Liu, Changyu Chen, Wenjun Li, Penghui Qi, Tianyu Pang, Chao Du, Wee Sun Lee, and Min Lin. Understanding -1-zero-like training: A critical perspective. arXiv preprint arXiv:2503.20883, 2025a.
Zichen Liu, Changyu Chen, Wenjun Li, Penghui Qi, Tianyu Pang, Chao Du, Wee Sun Lee, and Min Lin. Understanding r1-zero-like training: A critical perspective, 2025b. URL. https:
//arxiv. www..org/abbe hbs//bbs/2503 20783.
Iyya Loshchilov and Frank Hutter. Decoupled weight decay regularization. arXiv preprint arXiv:1711.01101, 2017.
12

---

OpenAl. Learning to reason with 1lms. OpenAl Blog Post, 2024.
Qwen. Qwen2.5 technical report, 2025. URL
Rafael Rafailov, Archit Sharma, Eric Mitchell, Christopher D) Manning, Stefano Ermon, and Chelsea Finn. Direct preference optimization: Your language model is secretly a reward model. Advances in Neural Information Processing Systems, 36, 2024.
Pierre Harvey Richemond, Yunhao Tang, Daniel Guo, Daniele Calandriello, Mohammad Gheshlaghi Azar, Rafael Rafailov, Bernardo Avila Pires, Eugene Tarassov, Lucas Spangher, Will Ellsworth, et al. Offline regularised reinforcement learning for large language models alignment. arXiv preprint ar arXiv:2405. 19107, 2024.
Stephane Ross and J Andrew Bagnell. Reinforcement and imitation learning via interactive no-regret learning. arXiv preprint 1rXiv:1406.5979, 2014.
Corby Rosset, Ching-An Cheng, Arindam Mitra, Michael Santacroce, Ahmed Awadallah, and Tengyang Xie. Direct nash optimization: Teaching language models to self- saff-impove with general preferences. arXiv preprint 1rXXi:22444.37115 2024.
John Schulman, Sergey Levine, Pieter Abbeel, Michael Jordan, and Philipp Moritz. Trust region policy optimization. In International conference on machine learning, pages 1889-1897. PMLR, 2015.
John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. Proximal policy optimization algorithms. arXiv preprint arXiv:1707.06347, 2017.
Zhihong Shao, Peiyi Wang, Qihao Zhu, Runxin Xu, Junxiao Song, Xiao Bi, Haowei Zhang, Mingchuan Zhang, YK Li, Y Wu, et al. Deepscckmath: Pushing the limits of mathematical reasoning in open language models. arXiv preprint arXiv:2402.03300 2024.
Guangming Sheng, Chi Zhang, Zilingfeng Ye, Xibin Wu, Wang Zhang, Ru Zhang, Yanghua Peng. Haibin Lin, and Chuan Wu. Hybridflow: A flexible and efficient rlhf framework. In Proceedings of the Twentieth European Conference on Computer Systems, EuroSys '25, page 1279-1297. ACM, March 2025. doi: 10.1 10.11457768903333666677. URL http: 3696075.
//stt::/dxxx /xx doi org/10.11/ 1145/3689031.
Yuda Song, Yifei Zhou, Ayush Sekhari, J Andrew Bagnell, Akshay Krishnamurthy, and Wen Sun. Hybrid rl: Using both offline and online data can make rl efficient. arXiv preprint arXiv:2210,06718, 2022.
Arun Sai Suggala and Praneeth Netrapalli. Online non-convex learning: Following the perturbed leader is optimal. In Aryeh Kontorovich and Gergely Neu, editors, Proceedings of the 31st International Conference on Algorithmic Leurning Theory, volume 117 of Proceedings of Machine Learning Research, pages 845-861. PMLR, 08 Feb-11 Feb 2020. httph:ts/://// //ppoceddioc....... html.
mlr.
Wen Sun, Arun Venkatraman, Geoffrey Gordon, Byron Boots, and J Andrew Bagnell. Deeply aggrevated: Differentiable imitation learning for sequential prediction. In International conference on machine learning. pages 3309-3311 PMLR, 2017.
Gokul Swamy, Christoph Dann, Rahul Kidambi, Zhiwei Steven Wu, and Alekh Agarwal. A minimaxi- malist approach reinforcement learning from human feedback. arXiv preprint 2400000 2024.
Kimi Team. Kimi kl.5: Scaling reinforcement learning with 1lms, 2025. URL https:////ax org/abs/2500 12599.
Hugo Touvron, Louis Martin, Kevin Stone, Peter Albert, Amjad Almahairi, Yasmine Babaei, Nikolay Bashlykov, Soumya Batra, Prajjwal Bhargava, Shruti Bhosale, et al. Llama 2: Open foundation and fine-tuned chat models. arXiv preprint arXiv:2307.09288. 2023.
Huaijie Wang, Shibo Hao, Hanze Dong, Shenao Zhang Yilin Bao, Ziran Yang, and Yi Wu. Offline reinforcement learning for Ilm multi-step reasoning, arXiv preprint 4 2024.
13

---

Kaiwen Wang, Jin Peng Zhou, Jonathan Chang, Zhaolin Gao, Nathan Kallus, Kianté Brantley, and Wen Sun. Value-guided search for efficient chain-of cilin-of-thhuge thought reasoning, 2025. URL https:
//arxiv.orz .orgg 2b5/ 17373.
Jason Wei, Xuezhi Wang, Dale Schuurmans, Maarten Bosma, Brian Ichter, Fei Xia, Ed Chi, Quoe Le, and Denny Zhou, ofaain-of-thought prompting elicits reasoning in large language models, 2023. URL https:://////ttt /aappii////x/i//////aeessaaas/a/ org /bt. 11903.
Ronald J Williams. Simple statistical madieentfolllwing algorithms for connectionist reinforcement learning. Machine learning, 8:229-256, 1992.
Yue Wu, Zhiqing Sun, Huizhuo Yuan, Kaixuan Ji, Yiming Yang, and Quanquan Gu. Self-play preference optimization for language model alignment. arXiv preprint arXiv:2405.00675, 2024.
Tengyang Xie, Dylan Foster, Akshay Krishnamurthy, Corby Rosset, Ahmed Awadallah, and Alexander Rakhlin. Exploratory preference optimization: Harnessing implicit q apprroxximtiionn for sample-effciiett rlhf. arXiv preprint arXiv:2405. 1046, 2024.
Wei Xiong, Hanze Dong, Chenlu Ye, Ziqi Wang, Han Zhong. Heng Ji, Nan Jiang, and Tong Zhang Iterative preference learning from human feedback: Bridging theory and practice for rlhf under kl-constraint. In Forty-first International Conference on Machine Learning, 2024.
Wei Xiong, Jiarui Yao, Yuhui Xu, Bo Pang. Lei Wang, Doyen Sahoo, Junnan Li, Nan Jiang, Tong Zhang, Caiming Xiong, et al. A minimalist approach to IIm reasoning: from rejection sampling to reinforce. arXiv preprint arXiv:2504. / 1343, 2025.
Chenlu Ye, Wei Xiong, Yuheng Zhang, Nan Jiang, and Tong Zhang. A theoretical analysis of nash learning from human feedback under general kl-regularized preference. arXiv preprint arXiv:2402.073144 2024.
Qiying Yu, Zheng Zhang, Ruofei Zhu, Yufeng Yuan, Xiaochen Zuo, Yu Yue, Tiantian Fan, Gaohong Liu, Lingjun Liu, Xin Liu, et al. Dapo: An open-source Ilm reinforcement learning system at scale. arXiv preprint arXiv:2503. 14476, 2025.
Yang Yue, Zhiqi Chen, Rui Lu, Andrew Zhao, Zhaokai Wang, Shiji Song, and Gao Huang. Does reinforcement learning really incentivize reasoning capacity in iims beyond the base model? arXiv preprint arXiv:2504. 13837, 2025.
Weihao Zeng, Yuzhen Huang. Qian Liu, Wei Liu, Keqing He, Zejun Ma, and Junxian He. Simplerl- zoo: Investigating and taming zero reinforcement learning for open base models in the wild, 2025. URL https: /aaxivv.///aaiva//aa/e/a . orw.oogg//aoo. hwgg/abs//503.... 18892.
Shenao Zhang, Donghan Yu, Hiteshi Sharma, Han Zhong, Zhihan Liu, Ziyi Yang. Shuohang Wang, Hany Hassan, and Zhaoran Wang. Self-exploring language models: Active preference elicitation for online alignment. arXiv preprint arXiv:2405. 2024.
Tong Zhang. Feel-good thompson sampling for contextual bandits and reinforcement learning. SIAM Journal on Mathematics of Data Science, ((2):834-857 2022.
Tong Zhang. Mathematical Analysis of Machine Learning Algorithms. Cambridge University Press, 2023. doi: 10. 1009093077.
Rosie Zhao, Alexandru Meterez, Sham Kakade, Cengiz Pehlevan, Samy Jelassi, and Eran Malach. Echo chamber: RI post-training amplifies behaviors learned in pretraining. arXiv preprint arXiv:2504.07912. 2025.
Yao Zhao, Rishabh Joshi, Tianqi Liu, Misha Khalman, Mohammad Saleh, and Peter J Liu. Slic-hf: Sequence likelihood calibration with human feedback. arXiv preprint arXiv:2305. 2023.
Jin Peng Zhou, Kaiwen Wang, Jonathan Chang, Zhaolin Gao, Nathan Kallus, Kilian Q Weinberger, Kianté Brantley, and Wen Sun. qf: Provably optimal distributional rl for Ilm post-training. arXiv preprint 5002225522220.., 2025.
14

---

A Experiment Details
A.1 Dataset Details
Table 3: Dataset split, maximum prompt length, and maximum generation length
Dataset
Huggingface Dataset Card
Train Val
Prompt Length
Generation Length
GSM8K MATH OpenR 1
openai/gsm8k ADAN2099fighhevalMMAH ppen-r//Openkk-MMah-222
7.47k 1.32k
256
1,024
7.5k 1k
256
1,024
5k
256
16,384
Table 4: Dataset prompt format
Dataset
Prompt Format
GSM8K
(prompt) Let's think step by step and output the final answer after "*uн"". {prompt) Let's think step by step and output the final answer within (boxed().
MATH
OpenRI-Math-22N0
<lbegin_oof of hraneeobbeeelettpppppppssssaaaad
A.2 Model Details
For GSM8K and MATH, we use Qwen2.5 model series with size 1.5B (model card: Qwen/Qwen2.55 1.5B), 3B (model card: Qwen/Qwen2.5-33) and 7B (model card: Owen/Qwen2.5-77B with full parameter training on 4 H100 GPUs. For OpenRI, we use DeepSeck-disee --iistilll-QUU Distill-Qwen-- 1.5B) with full parameter training 8 H100 GPUs. For PPO, we use the same model as the policy for the critic.
Qwen model (model
card:
A.3 Reward Details
We use rule-based reward function based solely the correctness of the response, assigning +1 for correct answers and for incorrect ones. Recent studies [Chen et al., 2025b] have proposed incorporating bormat-based rules into reward calculations to encourage models to follow specific output formats. However, our experiments, we observed no significant difference in performance with without such format-based rewards. Therefore, for simplicity, exclude them from implementation.
A.4 KL and Entropy penalty
For PPO, to ensure that the learned policy remains close to the reference policy wref, an additional KI. penalty is applied to the reward:
r(z, v) -KL (In i (y ()) - In Fvo [=))
where r(a, y) is the rule-based reward for prompt x and response y, and 7KL controls the strength of the KL penalty. For GRPO, we adopt the same KL penalty as in [Shao et al., 2024]. also parameterized by 7KL. To further encourage exploration in PPO and GRPO, we apply standard entropy regularization by subtracting the policy entropy, computed over the generated responses in the batch, from the loss. This term is weighted by coefficient "entropyy Note that PPO does not require these additional penalties, highlighting the simplicity of our algorithm.
15

---

A.5
Hyperparameter Details
Setting
Parameters
Generation (train)
temperature:
top p:
Generation (validation)
temperature: 0
PPO
batch size: 256
Tentropy: le-3
mini batch size: 128
TKL: 1e-4
micro batch size: 1
gae 7 1
policy learning rate: le-6
gae A: 1
critic learning rate: le-5
clip ratio: 0.2
train epochs: 25
GRPO
batch size: 256
Tentropy: 1c-3
mini batch size: 128
7KL: 1c-4
micro batch size:
num rollout: 2
policy learning rate: le-6
critic learning rate: le-5
train epochs: 25
REBEL
batch size: 256
V 0
mini batch size:
TKL
micro batch size: 2
num rollout: 2 yy: lc3
policy learning rate: le-6
critic learning rate: le-5
train epochs: 25
A"-PO
batch size: 256
B1 1/2
mini batch size: 128
82: lc-3
micro batch size:
policy learning rate: le-6
critic learning rate: le-5
train epochs: 25
A.6
Evaluation Details
We evaluate each method based on the trade-off between accuracy and KL divergence on the test set, assessing the effectiveness of each algorithm in optimizing the KL-regularized RL objective. Additionally, we report the peak GPU memory usage (as a percentage of total available memory) during backpropagation,
well as the total training time (in hours) for each method. Both runtime and memory usage are measured using H100 GPUs under the same hyperparameter settings detailed in Appendix A.5. The reported training time for A*-PO includes the offline generation time in stage Peak memory usage is averaged over 100 batches.
Following prior work [Zeng et al., 2025], evaluate model performance standard mathematical reasoning benchmarks, including MATH500 [Hendrycks et al., 2021], Minerva Math [Lewkowycz et al., 2022], and OlympiadBench [He et al., 2024], as well competition-level benchmarks such as AMC 2023 and AIME/HMMT from 2024 and 2025. For competition- benchmarks, due to their small size (30-40 questions), report average accuracy over 32 generations to reduce evaluation variance.
For benchmarks other than competition-leve benchmarks, we use greedy decoding with temperature set to 0. For competition-level benchmarks, we sample with temperature of 0.6 and top-p value of 0.95.
16

---

B Qualitative Analysis
In this section, we qualitatively demonstrate that, after training with PO-P the model exhibits cognitive behaviors that are essential for effective reasoning, including verification, subgoal setting and backtracking, as identified by Gandhi et [2025].
B.1 Verification
Prompt: 66 a S 2 and 3 S b S 5, what is the greatest possible value of a (++5)
(b (b-a)
Express your answer
as common fraction. Let's think step by step and output the final answer within \boxed().
Qwen2.5-7B Generation: find the greatest possible value of the expression (a a). start simplifying the expression. Notice that the expression is difference of squares:
c++ (x+t)( -9 = 6
Given the ranges a and b: -6 -2- - maximize 2 a², we need
f and minimize a²
1. The maximum value of & occurs when at its minimum value. which is So, # = 5
2. The minimum value of occurs when a is at its maximum value, which is -2, So, a² (-2) Therefore, greatest possihle
expression
36
36
35
9
So, the greatest possible value of the expression
Qwen2.5-7B after A'-PO Generation: To find the greatest possible value of the expression (a +) ($ a). .). we start by difference squares:
simplifying it. Notice expression is
aa 5 t
a
6 1
Given the ranges and
6555 -2 and 35 6.55
need maximize a².
1. The term d is maximized when b is minimized. Since S S minimum value of Therefore, the maximum value of / + = J.
2. The term -a² is maximized when a² is minimized. Since -6 S -2, the minimum value of o² is (-2)* = 4. Therefore, the maximum value -u² is -4.
Combining these, the greatest possible value of the expression
However, we need to check if this is indeed the maximum value by considering the boundary conditions. Let's verify by culculating the expression boundary values: 1. When -6 and b
[-+ 3
3 +
17
19
323
2. When -2 and & 3:
(-3)
35
+ 2
3 +2)
3
9
3. When and b
(6
5 (0+)
1
(-23
29
31
899
3)
25
4. When -2 and 5:
[22
1 +2)
9
99
25
From these calculations, that the greatest possible value indeed uchieved when and 3, giving
35
In this example, Qwen2.5-7B after POOPO exhibits verification behavior where it performs systematic error-checking after arriving at the answer.
17

---

B.2
Subgoal Setting
Prompt: positive numhers ab and output the final auswer within (boxed(): )-
a 8 Let's think step by step
Qwen2.5-7B Generation:
minimum value given that ab
5, we can method Lagrunge
multipliers substitution. Here, will substitution.
Given:
ab²
We want to minimize:
f(, b)
at +
First, express terms of b using the constraint:
Substitute this function (a, b):
f(b)
6
f(b)
625
6
y
Now, need find the critical points by taking the derivative of [(b) with respect and setting
fb)
5000
+ 867
Set derivative equal to zero:
5000
857
86 00
16
5000
6 8
V625
1//4
Now, substitute 51/6 back into the expression for a:
5
(51/4)2
5
51/2
51/2
a
Now, substitute 51/2 and & 51/1 into the function (u,
f0 s//4) (51/294 (54/9/a
f(5"/2, 5//4)) = 5
5(51/2 ./111) 25 25
715"/,,5*/ 50
Thus, the minimum value of a 1
50
18

---

Qwen2.5-7B after A' Generation: the minimum value + subject to constraint ald We can use the method substitution. From the constraint, express terms of
6
Now, substitute this expression for into the function a LP:
625
62
So, expression at 8 becomes:
625 8
6
denote 8" Then, the expression becomes:
625
We need find minimum value this expression. zero:
derivative with respect
d
625
625
+ x
dz
x2
Setting derivative equal zem, we get:
625
25
(since x 6 0).
Now, we need to verify that this critical point is a minimum by checking the second derivative:
625
1250
d2
2
25, the derivative
1250
1250
100
27
25
15625
1250
25
25
25
which confirms that back into the expression, we get:
minimum. Therefore, the minimum value
23. Substituting 25
625
+ 25 25 + 25 50.
Finally, we need to express in terms of a. Since 1², we have 25, so b 25//0, And since 3. we have (2g1/=ja 251/4 51/2 3x v3. So, the minimum value of a" 6" is:
From this example, -P enables the model to perform more comprehensive subgoal setting, where decomposes problems into manageable steps, and verification to check intermediate results.
19

---

B.3 Backtracking
Prompt: Let b, d be distinct complex numbers such that |a| [6] maximum value of
1 and + b Find the
I(a + (a + o)(a + d)(6 + c)(b + d)(c + d]].
Let's think step by step and output the final answer within (boxed(].
Qwen2.5-7B Generation:
this problem numerically, but first, let's explore mathematical Given that |a] = [b] = |c] Id = 1, these complex numbers lie on the unit circle in the complex plane. Additionally, is a constraint their sum.
can utilize Python
properties and constraints.
a b-
Since a. b, c, are distinct complex numbers the unit circle, can represent them et e e* ea for some angles
0., G, Oc. 0g.
The constraint
b c+ implies that these complex numbers are arranged symmetrically around the origin on
unit circle.
We want to maximize the magnitude of the expression ( + () + e)(a + d)(b + () + d)(c d).
Given the symmetry and the unit circle constraint. possible configuration that meets the criteria is: -b=
e² e
This configuration ensures that |a| = |b]
[d] 1 and b Let's compute [[a - (a + c)(a + d)(B + c) + d) + d)] using Python for this configuration.
0.
We'll start by calculating values and then compute desired magnitude. Let's proceed with calculations. ""python
import numpy
Define the complex numbers on the unit circle a= Ij ap.pi/ /3) mp.exp((1 *2 np-pi/ = np-pi) up.pi/ 3)
1pjexp(1j
Calculate the products ab = (a b) ac (a ad d) be (b <) bd (b d) cd
Compute the magnitude of the product of these terms result = np.abe(ab ac ad be bd cd) printfresult)) " "uuupptt 4. .999999999999999 - After calculating
magnitude of the expression [[a + b) + c](a d)(b c)(b d)fc + d) using
the specific configuration the unit circle. we obtain approximately S. Therefore, the maximum value the given expression is
Qwen2.5-7k after A -PO Generation: Given that a, b, c, d are distinct complex numhers with |a| = and + b + e- First, we can use the fact that |a] = [b]
ld id
0, we need find the maximum value of the expression (a + b) + c](a d)(b c) d) d))-
|d] to express a, b, and in terms of their arguments. Let's denote the arguments of a, b, and d by o. B. 7, and 5 respectively. Then, we can write:
a=e", 5 et c=e", d=c
Given + b c d O. can use symmetry and properties complex numbers configuration. One useful configuration is when b, and d are the vertiees of square on the unit circle. Without loss of generulity, we can assume:
circle find suitable
=1 b= c=e't =11, d= d= =
This configuration ensures that + b+ c+ d= e c = + =i-i=0.
Now, let's compute the expression I(a + b)(a c +d
d]}
I. 2-4- b of 1+ a 1- -3dd- 15.
So, expression becomes:
I[a + 6)(a e) (a d)(b+ c)(b+ d) = [11+)) (-1
=
This configuration
not yield maximum value. Let's consider another configuration, such as when o, b, and the vertices of regular tetrahedron on the unit sphere. However, for simplicity, let's consider another symmetric configuration. such as when a, b, and d are the roots of polynomial with specific properties. Given symmetry
condition a + + o O, useful configuration when a, e, the polynomial 2 + = O. The roots of this polynomial are:
a=dt b= - c= d
Now, let's compute the expression ((a b)(a + c)(a df(b ((b+))(b+ +d)c d)} I. d= e 4 2. a= e e a + + 4. Autt==e= + e e. c d e¹ br +
Using the properties of complex numbers, cun simplify these expressions. For example, c (0+ o cc c'111+ + i).
After simplifying, we find that the maximum value of the expression achieved when the configuration is such that the terms not cancel each other out, The maximum value is found to be 16.
So, the final answer is:
Although the answers for both models are incorrect, the model after A -POO exhibits backtracking behavior where it abandons failing approaches and reconsiders another method.
20

---

C Pass@ K Evaluations
Figure 10 presents the Pass accuracies across all three model sizes and two datasets. The orange line indicates the Pass@) performance of the model after RL training. We hypothesize that this convergence behavior N is due to the relationship between N and the Pass@ K performance of the model. The final performance of the models after training falls between @ and Pass@8 of Tiee- This suggests that the optimal value function V should, at minimum, approximate Pass@4 performance. With N 8 samples, the estimated V* becomes sufficiently accurate, leading to convergence performance.
GSM8K
MATH
0.70
Qwen2 5-1..... 1.5B
0.70
0.60
0.50
0.50
0.50
0.30
0.80
0.85
Qwen2.5-333
0.66
Pass
Pats@
0.70
0.50
0.50
16
K
Qwen2. 5-BB
0.90
0.92
0.80
0.70
Pusek
Pass@/K
0.50
0.50
0.50
0.40
K
Figure 10: Pass@K K Evaluations for different models and datasets.
21

---

D Limiting Cases of B
Case 1: 3 - --eecovernng the Maximum.
We start from the expression:
N
r(z, yi)
(x) = 3lnn
Σ
N
exp
B
1=1
Let M max; y1), Then,
N
r(a, yi)
(
N
[r(z Mi) - M
Σ
Σ
exp
exx
exp
B
8
3
Taking the logarithm:
(*(x)= = =311 N
exp 3
M
Σ
N
exp
r((,
vi)
M -M)) )) - M
311
Σ exp
r((,, (1) -11) )
1
B
Since r(z, y1) M.
N
(rx, yi) M M) )) =
lim
3 In
Σ
exp
400
N
3
i=1
Therefore,
lim (x) = M = P for x.
8-0
Case 2: B - Recovering the Mean.
We start from the expression:
r(x, M1) ))
(x(x)) 3In
exp
B
We want
N
(xxx y1)
))
In
1 Em exp (r(2,, (1),,))))))))
lim (x)x)= lim
3 In
Σ
exp
lim
$-000
8-
3
8-5
3
Apply L'Hôpital's rule:
In ( E exp (r(x, v))8))
N ((), v.) exp (r(x,v:)))
lim 8-0
lim
Σ
rla, v.).
8-0
I exp ())))
N
N
1=1
Thus, 8 0o:
N
(x(x) +
ra, vi).
N
Summary:
max (1r,
if 3 + 0,
(x)
Σ r(x,):)
if
22

---

E Log-linear Policies With FTPL
In this section, we characterize the learning regret of log-linear policies with FTPL. We study bounded parameters and feature vectors:
|01l S B, 110(,, y)1l2 S 1, Vaz y-
We still assume II is realizable and let πt = TT. Note that we can indeed bound the DC of this log-linear policy class as follows.
Lemma 1. For the log- linear policy class II defined in Eq. (3), have DC(II) S d + 1.
FTPL. We instantiate NR to be FTPL [Suggala and Netrapalli, 2020]. That is, f-th iteration we generate i..d. random variables from an exponential distribution, ote EXP(n) for 1 S d. Let or denote the vector whose j-th entry o,j. then FTPL computes To, as follows:
0: = arg min BEB
Σ (mme) (0,,
From the literature, have the following guarantee of FTPL. Lemma 2 ([Suggala and Netrapalli, 2020, Theorem 1])- Let D denote the diameter of θ i.e, D suee, |10 6' ol. Suppose the loss functions L-Lipschitz w.r.t. fx-norm, i.e. (TT)) (((TT))) ) < L|10 0'l for all 0, 0' E O,t. Then we can bound the regret of FTPL as:
Reg(T) S nd DL dD
Given Lemmas and 2, we can bound the regret of learning log-linear policies with FTPL using Theorem 1:
Corollary 2 (log-linear policies with FTPL).. Consider the log-linear policy class IT defined in Eq. (3). Suppose Assumptions to 3 hold true and use FTPL as the NR oracle with 1/(3Cvv Then we have the following regret with probability least 1 d:
1
T
d dà
dC? [dc lm(1/8)
E Ex r (x. v)
Σ
E
Ex
E
E
(x,
+
T
T
T32
t=1
(miin exp )
1 Uref
))
d'ln((2215))
N
Proof. To utilize Theorem 1, we only need to bound the diameter D of the parameter space and Lipschitz constant L. First note that
sup ||A 8111 I sup 0
|| 81112 S 2B.
0
On the other hand, fix any f, 0 E O and we can compute the j-th entry of the loss gradient:
(Voli) 23 (
Tree (yel (f(21, ye) V (zx) (xx))
π T (Velare)
(Ó(z vc)), Ey exp ((0, d(r, // )/))) (o(2), v'),,
Ey exp (10, o (2, 8')))
From Assumption 2 and the fact that [| 8)112 < we have
Vola
< 4,3(C, + 1),
which implies that (via Holder's inequality)
L 4B(C + +1)
23

---

Now combine Theorem with Lemmas and 2, and we can obtain the final bound:
T
d8 dBBCi
dC? In(1/8) 4
Ez.gro F... ((.
T
Ex
T&B
+
T32
t=1
((min) exp
1
1
1)
2 dln(1221/6)
+
B
-
Uref
N
E.1 Proof of Lemma
Note that for any II, we can write In no as
In (y(a)) (0, Φ( u))
In Σ
exp
((0 ((,, 1/1)
y
((10 0. In Σ exp (10, 2(221111
[o(a, 10(a.
Let us use z(0,x) [Rd+1 and Φ(H, v) E gd+1 to denote the extended vectors:
f(0,x)) = 0, In Σ exp (10,
क(x, v) (0(2 v).
In addition, we define A(g, x)) to be the expected feature covariance matrix,
A(g,z) x) = Eang.vwno(H) (b(x; v) (x, w)
Let 8r denote the optimal parameter, i.e., x² :g. Then from Cauchy- Sauchy-Schwart. inequality, we have for all À >> 0 that
Egpp toa [In (yylo) In n [y)x)]
-Bxp. x))(0,)) - f(0", ,)), o(x,)))
Ss Exnup,nngg [f(0,z) f(0,,x))1 (00 Benpdrggy-oo( [|ī( x) (
For the first term, we have
Ex~a,0ng [1](0,,)- f(0", 100r
=Beapp w" (x) (ooll() - In (n + XB2 (1 + In (D)).
For the second term, we have
[1 v) ( Expp + A(q,xx)] S Sd+1.
Therefore, let + 0, we have DC(II) s dd+1.
24

---

F Log-linear Policies With OGD
In this section, we investigate the learning guarantee of OGD log- policies.
Quasi-quadratic Loss. Recall that the population loss in iteration is:
()) Eggyooo (+12) @I1n
To(y|æ)
V -
(y)
For log-linear policies, show that (()) is quasi-quadratic in terms of gradients, shown in the following lemma: Lemma 3. We have
Vol((0)) 2/2228822000 ((0.)(0, - 0*).
Recall that A(0) denote the Fisher information matrix:
A(0) = Ez, (e () y) E Bo y))
Online gradient descent. Inspired by Lemma 3, we instantiate NR to be online gradient descent [Hazan al., 2016] for log-linear policy learning. Specifically, in t-th iteration, we compute 0t+1 1 as follows:
8111 = Proje (6, - 7o (O))).
where ze is the stepsize in iteration i and Proje(-) is the projection onto θ w.r.t. l2 norm. Recall that online gradient descent is exactly what we utilize in our practical implementation of Algorithm 1.
Next we show that our algorithm enjoys a last-iterate convergence to 0 with a rate Õ(VI/T) given that the Fisher information matrix is full-rank Assumption 4.
Theorem 3 (log-linear policies with OGD). Suppose Assumptions 1, 2 and 4 hold true. Set any No n.x. Then with probability least 6, we have
B + +
E2 v) En [1, S
T
Proof. Let Oc+1 denote 0: - T)e V (0t). From the definition of nT" we know
BIn mo(ulæ)
(())) 2
(0) Ey. (11))
(z)22)
(0( |B1n
π (Ve (r2)
(v*)x) (V<
(ste (r.))
We use & to denote Vola - -V (f)) Then from Assumption 2, we know ||Ee|| s 83C; for all t.
From the update of online gradient descent, we have
θ 8" = 0, ne Vole(To.) m/E+ 0²
By Lemma 3, this implies that
O-1 0* = (1 - 2n, A(0r)) (0: -r) + mch..
With Assumption and the property of projection, we have
|10++1 0" 11 S |0:+1
0* < (1 2n, A)110, - 112 + 2n (zr, Ee) + 644
where 21 := -
2n. (1 ( (0, 8*). Let B7 = 41
Denote by C1 = 2110,32 and C2
32?, we have
|0 - 811 1
C1
110: - 0-112
2noo (Ze, Er)
+
t+
t ++1
(t 1)2
25

---

This implies that
t1|0: - (t + 1) - -0 - -
8-112 = (1 10)00 - 0-112 + 2no (2,, + t+1
By induction, have
||T+11 1- < |10 1- 02 + InT)
1 1-G C1 T+1 1
T
2170 T
Σ
10, - 0012 + T +
(Zt Et)
T+1
1=1
2B + 64m Cf (In C +1)
(1 (1)
Σ 21=1 10:
1-2 2 + 2770
Σ [-= (2), (t)
T T+1
++1
Let Fr denote the filtration generated by (z), U1, -t 11-1). Denote by = (Ee, Et), it can be observed that B[G, Fi] = and Kel S 83C, 0- a.s. conditioned on Ft. To proceed, we utilize the following form of Freedman's 's incquality from the literature [Beygelzimer et al., 2011]:
Lemma 4 (Freedman's s inequality [Beygelzimer et al., 2011]). Let (U1...., UT} be a martingale adapted to filtration {Fi}. Further, suppose that UU| S R for all t. Then, for any 8 > 0 and 7 [0, 2 we have with probability at least that,
In(2/0)
Up
E[U?
Fi]+
7
1=1
t=1
Applying Lemma with U, Se and 163BC, we have with probability least 1 that for any S 325BC
T
ln(2/8)
Σ 1=1
E ElS2
Fi] +
?
1=1
10 1-11 ln(2/8) S 647 64, C2
?
Therefore, we have
T
T
T
2npo In(2/5)
(1 (1-0) 11
10: 1-
+ 277o Σ
(2 E1) s (1 -1 + Cf Σ
110:
1-1
?
Choose 7 min
12807: 328BC; }. have
T
T 110 0-112 + 27oo Σ (z, 5(1 - 5(1-c1/2)
(1 c1
11 0-11
t=1
256C7 110 In(2/8) + 64,3Con
Choose 170 2 1/) we have with probability at least 1 5
5 that
(2r Ex) x 0n + BBC ln(28)).
(1-9) Σ 110 1-11 + 2nj Σ
This leads
10 10++1-0'1 B² + n C2 IT +
(5)
T
Now we start to bound the reward regret. Notice that
yxuxx your [r(x, y)1 En (r(x, < E. [[ITOT (11) n" (1x)
exp( (OT+1. 6(I 8)))
exp( Ó(I v)})
=E,
Σ
Σy exp((0 Φ(o, v')))
Ey exp((0' (0', ((1, v()))
26

---

For |00 - - 1/2, It suffices to note that
exp( o(x, v)))
exp((0' x(x,))))
exp(22l0r+1-1 - -0'1)] <oxp211011100111 Ey exp( o(x,
Ey exp((0r+1,0(z.x)))
exp( (0 p y)))
(1 41|00-1 0'11) Σy exp (0+ (x
and
exp((0r+1, ((z,
exp( ,xx; y)))
2 exp(-22|00 -8"11) En exp( 6(x f))
Ey exp v/))
exp((0' ,(2 y))
2 (1 41|0r+1-1100 - -0'11) Ey
(0 (x "0,,
Thus
Exgyna [r(x, w)] - Er E [r(x,y)]
exp( Φ(x, a)))
(pp((0",((x,) 8)))
SEz
Ey ys (op((Or+100 00 y')))
Ey exp((0r, ,(0, 8')))
expl (0 662, 60,, w)))
SEx
Σ 41l0T+1 - 0-11
Ey exp((00' (4r,,,'))
-Eg
4|10r41 - 8-1l Σ n" (vlx)
Ba + B2 In (7) + 3o
4110r+1 0-1 $
On the other hand, by (5), with probability at least 1- 5, know ||0T+1 0+ < 1/2 for T z B² + 3² T + (f)) In(1/)) + 7o,8C, B ln(1/5). For T < B² + 32 In - (nnC / A)) 1n(1/)) + 30 In (1118)). it suffices to note that
E Ex,y [r y)] Ez,g Tor [r v)l
Ba + n 32 C
+ (noC7 /A) (n(1/5) + m11(BB1(118)
$1
T
which completes the proof.
27

---

F1
Proof of Lemma 3
Recall
TT(3)2)
(T(z.)) - Ex..y,a,,
To(3|z) [3ln n (vlæ)
(V(x)- P (v
(2,
Tiae (y)z²
We have
Voli(0)) 2 To (1(x)
(y)2))
+V*(z)
(((..)) -V*)))-V'x)) m())
Ey exp(((e; (1x v/ 1) 1/1
n" (1/(2)
Ey expl (0,, (2 y'))
Te. (v/2z)
+ -M(5)) (((,.)) Σ To, [0
2/3TE, a.groot (11z)
B In
8In me, (vlz))
+ (z) v())) -x))) (p(z.v) v) - Byr-aaT (1))
2,3EE, 2, go (1/2)
2 Byy.yo (11z)
In
mu. (ular)
(0(x.)) R (13)
(y(aa)
Ey expl ol (d(s..) Byrnooo as ())(0)
2,3 yyyoo (111)
(0x 00, (,,, In Eg exp( 0(
2,3 Enayto (11))
[(0) 0*, olx v))) (d(z,)) v) Eny E (0 s/1)]]
2,32 (En.yroo (12) [0(2, v)d(,, w)
Ez Ex yxwnn (-1z) (o(a,, w)] gx (o(o,,)))) (0--07 07)
A(,3² 8*).
The fourth and sixth equalities are because
Bu, (11z) (Vv((x) v'())) (olr..) Bynns, (wo)
E. (v= (xx) Bynto (1a) (0(2,0) E -e
and
In exp( ((),))))))
exexp( exp((0* (00,,(((,))))) (Ó(z,)) v) By (, (100)6(222
Ex Egy (11z)
Ey y' exp((01e 0(., v/1)) Ey exp (0+ δ(I }/))) E (11)) (Ō(z,)) v) Ey (, (10)
Eg
In
28

---

G Proof of Theorem
Our proof consists of three steps. First, characterize the estimation error of V Second, with the learning guarantee of NR, we derive an upper bound on the average KI. divergence between the output policies and the optimal policy with DC. Finally, we apply Pinsker's inequality [Cover, 1999] to relate the KL divergence to the performance gap, completing the proof.
Step 1.
To begin with, can quantify the estimation error with Lemma 5: Lemma 5, With probability at least - 8/22, we have for all æ that
(V=)))-V(>0)) x 3 min
II (m(111/88)
exp
1,
B
Vrof
N
The proof is deferred to Appendix G.I.
Step 2. We first bound Et= le(TT) with Lemma 5. From the definition of 'T", we know
(<(T') = (V*(x;) - (V* V
Let F, denote the filtration induced by (a1, :/ 1. 1, ).. Note that we have
( )
E [x(x=))
Fi = Eupp
V v()))
[(D-(0)) - v(())) ]
EE
((((TT))
Fi Exuu
(v*(x) (v*(x) vz)) = [(((TT |
< Eppp
(6)
Next we utilize the following form of Freedman's 's inequality [Song et al., 2022] from the literature: Lemma 6 (Freedman's inequality [Song al., 2022]). Let (Zi...., Zr be sequence of non- negative random variables where 2, is sampled from a distribution depending on 21:1-1, i.e. ~
(1( Further, suppose that [7,) S R for all I. Then, for any > 0 and [0, 2R). we have with probability at least 5 that,
(2RE Ze P. + B[Z P.]) + In(2/5)
Σ Z E[ P..
Therefore, applying Freedman's 's inequality with Eq. (6), we have with probability at least 1 - 8/4 that
Σ v()))) S 2T
(V-(s)- v(r)) 27 In((1/).
From Lemma 5, this implies have with probability at least 1 - 5/4 that
Ea(T's (Amin
(
Urof })
2 T (
exp
-
N
On the other hand, from the definition of n², have
[ (v1(2x)) (vel
+ (V=)x) V v((ss)) 27
E Easag [[(mm]] = Eneaae
Note that we have
(s {(ylx) (v]l)) + - -v))))))(())))))))))))))))))())) -v()))
E E E
Fi]
(e. Bang
[(((m))
(
[(ylz) (1] +
E Eirrar
Fi
< ter (aa))laar
29

---

Note that from Assumption 2, we know
B ( x (u)2z)
+ ( s Sc+1
This implies that
E
E Ee
[)
Fr S (Cx (C++ Brng [(((TT Fz
Therefore, with Freedman's 's inequality, we have with probability 1 8/4 that [ T(ylx) (y)x) + (())))))(a))) 27
T 2
E
Eanq
P((TT)
+ c In(1/)).
(8)
Combining Eqs. (7) and (8) with the guarantee of no-regret oracle NR, we have with probability at least 1 that
T
Egp p, Me 10) (san
Ttyl)) (ulz)
+ (V^()) (v)))
Ea-a
T
t=1
{ exp (0)
1 1)
2 1n((x1/8)
Reg(T)
C7 lm(100)
min
Vref
N
T
T
Note that from AM-GM inequality, we have for all that
(
x(2122)) xx (v(zz)
+ (V=))) 21
E Egcep u p.o.p................... ug. (-12)
(
(In <(y(z)
) + 2.g "t
(In=((l)))) ) -
= 8 Exxx ao
(()))) )
+ Hamp
2 82 Ex Ex
[(m
क [w/|x)) - (y/ (r)
27
Ezup ((=())-v(<<))
2
Therefore have with probability at least 1 5 that
( BIn (3)(2:) 27
E or..
x (w](z)
(8min
{ exp
(1)
In(1X1/8)
Reg( (T)
C7 In(1/0)
1,
(9)
Uref
N
T
T
From the definition of decoupling coefficient (Definition 1), we know that
T
E qu Exup ( " (+|x)) =
E
Benp.rgg.errt(e) (y)l)) - In " (y/xx)
( ((y(+t) (v] )
1
DC((T) F Ee B ge
T
Apply Cauchy- Cauchy-Schwarte Schwartz inequality and we have
T
DC(II)
T
(in (tll²) 27
E Enng. Ezup (KL(T()))) x (+xx)) =
Σ
E Ex-p.rnn
T
T
t (3/
(10)
30

---

Combine Eqs. (9) and (10) and we have with probability at least 6 that
Twa Bxxu [KL(T(-|xx) x" (-1x))]
T
})
V
(C N
DC(TT) (T))
DC (n(1/0))
X
min
exp
- 1,
B
Uref
T
TB²
(11)
Step 3.
Note that from Pinsker's inequality [Cover, 1999], we have
T
J(x')
E nu 4e [J(T]]
Bm- (ta))a U)1
1
Σ E m -
T
T
1=1
T
E En Bzup [-|x() x" (+1x))111 -
_
E Br Eeup (2)
T
T
Therefore from
inequality, we have
T Σ Bange [T()] S
J( T
E Exep (T),
(12)
Combine Eqs. (11) and (12) and we have with probability at least 1 - that
(9C(m)))1((110))) 1
1 J(TT) T
(C((T))eg(T))
)
E B Σ
x
TB2
T32
1=1
((min exp
1
1
DC(LI) 1n(1x1/0)
1,
3
Uref
N
This concludes our proof.
G.1 Proof of Lemma 5
Let p(x) denote the empirical average reward that Tee attains for prompt x in the offline estimation stage. Then we can observe that
(x) 81n ((1 p(x)) ((x)) exp(1/8))
We also use p" (x) to denote E (x (2 v)]. From Azuma- houma-Hoeffding's inequality [Azuma, 1967] and union bound over all æ E X, with probability at least 6/2, we have for all x E X that
In((x(1/5)
- px))) $
N
On the other hand, we know
(*)x== = 3m 1² (x)) (x) exp(1/3)), Vz.
From mean value theorem, have
1, 1 }) (0(x) (x)1, Vz.
(ー(x)- - (xx 8
min exp {
Urat
Therefore, we have for all E X
Bmin exp (2) 1, ))
In((211/8)
((-())
Uree
N
31

---

H Additional Related Works
RL for LLM Reasoning Reinforcement learning (RL) has become a standard approach for post- training large language models (LLMs). The most prominent example is Reinforcement Learning from Human Feedback (RLHF), popularized by Christiano et al. [2017] and Touvron et al. [2023], which has garnered significant attention from both industry and academia due to its remarkable success aligning LLM behavior with human preferences. While this two-stage framework has achieved impressive results, it remains computationally inefficient, requiring separate training of both a reward model and a policy model. To mitigate this overhead, recent work has focused on developing one-stage algorithms, including SLiC [Zhao et al., 2023], DPO [Rafailov et al., 2024], REBEL [Gao et al., 2024a], and its variants such as IPO [Azar et al., 2024], SPO [Swamy ct al., 2024]. SPPO [Wu et al., 2024], and DRO [Richemond et al., 2024]. Building on recent advances from OpenAI OI [OpenAI, 2024] and DeepSeek RI DeeepSeek-AL, 2025], Reinforcement Learning with Verifiable Rewards (RLVR) has gained traction as an effective approach for improving LLM reasoning capabilities, particularly in domains such as mathematics and programming. Notable examples include GRPO [Shao et al., 2024], DR-GRPO [Liu et al., 2025a]. DAPO [Liu et al., 2024], OREO [Wang et al., 2024], DQO [Ji et al., 2024], and RAFT++ [Xiong et al., 2025]. Similar to OREO, DAPO, DQO, and DRO, POO operates efficiently by requiring only single response per prompt and regressing the log ratio of π and The to the advantage. However, unlike these methods, AO eliminates the need to train an explicit critic for value estimation, further improving its computational efficiency.
Exploration in RL Exploration is a critical component of reinforcement learning, particularly in complex reasoning tasks where large language models must navigate vast response spaces to discover correct solutions and learn from them [Dwaracherla et al., 2024]. In classic online RL methods such as PPO [Schulman et al.. 2017] and GRPO [Shao et al., 2024], exploration is typically encouraged through entropy regularization. By maximizing policy entropy, these methods discourage overly deterministic behavior, promoting more diverse outputs. However, this heuristic approach often leads to suboptimal policies and slow convergence due to increased objective complexity. To address these limitations, recent works have explored active exploration strategies [Xiong et al., 2024, Ye et al., 2024, Xie et al., 2024, Cen et al., 2024, Zhang et al., 2024, Bai et al., 2025, Chen et al., 2025a], which estimate environment uncertainty from historical data and plan optimistically, While these methods provide theoretical guarantees on sample efficiency, they often rely on complex exploration mechanisms or strong assumptions such as reward Linearit-maainn them difficult to implement and resulting in unstable empirical performance.
In contrast, POO does not perform explicit exploration, resulting a much simpler algorithm. PP- designed for a more realistic setting, where we do not expect RL post-training can help solve problems of which pass @K K values are zero for some large K under Tef- Recent studies [Zhao et al., 2025, Yue et al., 2025] suggest that existing RL algorithms struggle to incentivize capabilities that go beyond the knowledge boundaries of the pretrained model--falingg for instance, to surpass the Pass @K performance achievable by the base model Traf. As shown in Section 5, we prove that as long as we do not wish RL post-training to solve problems where Tref has zero probability of solving, even without any explicit exploration mechanism, AOOPO provably converges to T" with polynomial sample complexity. In this regard, A achieves both training efficiency and optimality under realistic setting.
Prior work Q# [Zhou et al., 2025] also leverages such a condition to achieve a near optimal regret bound for the KL-regularized RL objective at token level without performing any exploration. The difference is that Q# operates at the token level and learns a critic Q function to guide the base model to perform controllable generation test time. PO is a direct policy optimization approach. Another subtle difference in theory is that by operating at the trajectory-level, A*-PO's sample complexity does not have polynomial dependence on the size of the vocabulary. This is because when we operate at the trajectory-level, we can query the ground truth reward model to get a perfect reward for given trajectory (c.g.. whether the response is correct). The idea of directly regressing optimal advantage A is motivated from the classic imitation learning algorithm Aggre VaTe(d) [Ross and Bagnell, 2014, Sun et al., 2017] where these algorithm aim to learn a policy that greedily selects actions by maximizing the expert policy's 's advantage function. The difference is that PPO operates in the pure RL setting where one does not have an expert to query for feedback.
32

---

I Rate of Convergence
PPO
GRPO
REBEL
A
GSMBK 1.58
GSMEK
GSMAK 765
1.0
1.0
0.8
0.3
0.5
Training Reward
0.2
0.2
200
200
MATH 1,5
MATH 3B
MATH 7B
0.7
0.7
0.6-
0.5
0.7
0.4
0.5
0.5
0.3
0.5
200
400
600
200
400
100
600
Step
Figure 11: Training reward vs. steps over two datasets and three models.
Fig. 11 shows the training reward of PPO, GRPO, REBEL, and A' over MATH and GSM8K datasets at each step. We can see that all four methods have similar convergence behavior. Based on the plots, we can now safely conclude that A is the fastest method as it requires the least amount of time to complete the same number of training steps, while reaching convergence at the same step count the other methods. To illustrate this more clearly, we also include a plot of training and generation time versus training reward below. Note that the A*-PO curves do not start at time zero, as they include the time required for data generation. Each line starts the corresponding generation time for its dataset and model. While REBEL converges at a comparable rate in terms of time, requires significantly more memory than A POO
GRPO
GSMRK
OSMAK 7B
1.0
1.0
0.4
Training Reward
0.2
0.0
2.5
7.5
10.0
10
15
20
MATI
MATH 3R
0.8
0.9
0.7
0.7
0.5
0.5
Training Generation Time (bours)
Figure 12: Training reward vs. training and generation time over two datasets and three models.
33

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
The abstract and introduction (Section 1) accurately present the primary claims of the paper, aligning well with the detailed contributions and scope described in the main body.
Justification:
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results be expected to generalize other settings.
is fine include aspirational goals as motivation long is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: Limitations are discussed in Section and the assumptions are presented in Section 5.
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification. asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect the scope of the claims made, e.g., if the approach was only tested on a few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and prool's
Question: For each theoretical result, does the paper provide the full of assumptions and complete (and correct) proof?
34

---

Answer: [Yes]
Justification: All of the proof are provided in Appendices E to G with the theorems, formulas, and proofs numbered and cross-referenced and assumptions stated and referenced in the statement the theorems.
Guidelines:
The answer NA means that the paper does not include theoretical results, All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided not)?
Question:
Answer: [Yes]
Justification: We detail the datasets, models, hyperparameters, and evaluation metrics in Section 4 and Appendix
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, No answer this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data provided or not.
the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how replicate the results, access a hosted model (e.g.. in the of large language model), releasing of a model checkpoint, or other means that are appropriate the research performed.
While NeurIPS does not require releasing code, the conference does require submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm. (b) If the contribution is primarily
model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should possible for other researchers to have some path to reproducing verifying the results.
35

---

5. Open access to data and code
Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Question:
Answer: [Yes]
Justification:
We provide anonymized version of data and code as supplemental materials.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.cm cc/
poplic/guides Coodeeumisssiinnn
for more details.
While we encourage the release of code and data, we understand that this might be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https: // /nips. maips.c/pput mubbic/guudes: wtt.dddeeeeeeeemmmiiiiicaca
for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible supplemental material (appended the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: We detail the datasets (splits), model pipelines, and complete sets of hyperpa- rameters in Section and Appendix A.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [No]
Justification: The experiments are reported datasets that are significantly large or the average performances over 32 responses are reported.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by emoo bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
36

---

The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not show in tables figures symmetric error bars that would yield results that are out range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [Yes]
Justification: Resources for experiments are discussed in Appendix A.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount compute required for each of the individual experimental runs as well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics https: //tee///neuueeeee /neuriius....// cc
Answer: [Yes]
Justification:
The research conducted in the paper conform with the NeurIPS Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurlPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consid- cration due to laws or regulations their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: The paper introduces an algorithm that could potentially be applied to any reinforcement learning task.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
37

---

If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), faimess considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
The paper poses no such risk.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards challenging, and many papers do not require this, but encourage authors to take this into account and make best. faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Justification: Datasets and models we used in experiments are cited in Section 4 and the model/dataset cards are detailed in Appendix A.
Guidelines:
existing assets. The answer NA means that the paper does
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset used and, possible, include a URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
38

---

If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information not available online, the authors are encouraged to reach out to the asset's s creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [Yes]
Justification:
The code used in the paper is well documented with instructions.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/moodl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification:
The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country institution) were obtained?
Answer: [NA]
Justification: The paper does not involve crowdsoureing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
39

---

We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors adhere the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Does the paper describe the usage of LLMs if it is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, formatting purposes and does not impact the core methodology, scientific rigorousness, or originality of the research, declaration is not required.
Question:
Answer: [NA]
Justification: The core method development in this research does not involve LLMs as an important, original, or non-standard components.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, non-standard components.
Please refer to our LLM policy (https pectps:/nneurppee 220p:/pp////ooooeeeeee////////// for what should or should not be described.
40


Reviews:
[{"review_id": "EVoWUIwNPH", "reviewer": "Reviewer_Wcpu", "summary": "This paper proposes a way to significantly reduce the cost of online RL by decoupling value estimation. Specifically, for a given RL prompt dataset, they collect offline rollouts using a reference model to serve as the value baseline. Then during online RL, they use only 1 rollout per prompt and simplify the policy objective to a plain regression on the advantage (using MSE loss). Experiments are done on Qwen models and math domain.", "questions": "See the weaknesses part point 1.", "limitations": "yes", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 3, "significance": 2, "originality": 3, "strengths_and_weaknesses": "### Strengths:\n- Easy to plug into existing pipelines. Compared to other methods that modify value or advantage estimators, regressing offline advantages is a fresh idea.\n- The writing is clear and easy to follow.\n- The theory section gives a solid in-principle analysis, which is nice to see.\n\n### Weaknesses:\n- The key novelty — using offline value estimation — needs more ablations. For example, I would really like to see how it performs if they just estimate value online with the same setup (i.e. just keep updating \\pi in the process how will the value baseline change).\n- Experiments are limited and focus only on short-context (non-thinking) models. I totally get the resource constraints (they do not even have complete baselines for thinking models), but it still undercuts the strength of the paper’s message.", "was_revised": true, "final_justification": "The paper presents a simple yet effective method to decouple value estimation from online RL via offline rollouts with a reference policy. The idea is easy to implement and supported by theoretical grounding. While the scope of experiments is somewhat limited, the authors’ rebuttal provided useful clarifications and additional results on long-context models, which strengthen the case. I continue to view this as a technically solid contribution with efficiency benefits, though with limited breadth of evaluation. My borderline-accept rating remains unchanged.", "rebuttal": "We sincerely thank the reviewer for the thoughtful and constructive feedback.\n\n> The key novelty — using offline value estimation — needs more ablations. For example, I would really like to see how it performs if they just estimate value online with the same setup (i.e. just keep updating \\pi in the process how will the value baseline change).\n\nOur key contribution is to decouple value estimation from online learning by estimating the optimal value function offline using samples from the reference policy. This avoids the need for explicit critics or multi-sample estimation of the current policy’s value, which are required by PPO and GRPO and substantially increase both algorithmic complexity and training cost. While we understand the curiosity about online estimation under our setup, such an approach would revert to GRPO or PPO, thereby obscuring the benefits and novelty of our method. Moreover, as discussed in Section 2, the optimal value function under the KL-regularized RL objective is defined with respect to the reference policy $\\pi_{\\text{ref}}$, not the learned policy $\\pi$. This provides a theoretical justification for our offline estimation approach and highlights the limitations of online estimation in this setting.\n\n> Experiments are limited and focus only on short-context (non-thinking) models. I totally get the resource constraints (they do not even have complete baselines for thinking models), but it still undercuts the strength of the paper’s message.\n\nWe fully agree that evaluating on more complex, long-context reasoning tasks is important. To address this, we included experiments in Section 4.3 using the DeepSeek-R1 distilled Qwen-1.5B model with a 16k context length which is a setting for long-form reasoning. As shown in Table 2, $A^\\star$-PO achieves the best performance on AIME 2025 and HMMT February 2024, and performs comparably to PPO and GRPO on AIME 2024 and HMMT February 2025. These results demonstrate that $A^\\star$-PO effectively scales to long-context reasoning while remaining significantly more efficient in terms of training time and memory."}, {"review_id": "JMVwX9dSrZ", "reviewer": "Reviewer_yXFw", "summary": "This work focuses on the topic of using reinforcement learning to enhance the LLMs' reasoning capability.  Previous RL methods either rely on training a critic network (e.g., PPO) or generating multiple samples per prompt (e.g., GRPO) during online finetuning. This work, based on the property of the optimal value function under the KL-regularized policy, proposes a two-stage method, where the first stage offline sampling is performed directly via the reference policy to estimate the optimal value function, and the second stage performs online training with on-policy updates using a simple least-square loss and one response per prompt. The effectiveness of the proposed method, i.e., A*PO is verified with experimental results, showing that it achieves comparable results with previous methods, while speeding up training and reducing memory usage. Furthermore, theoretical results are also provided, providing the theoretical soundness of a more general version of A*PO, without strong assumptions or using complex exploration strategies but achieving nice convergence results and yielding attractive properties.", "questions": "There are a few clarification questions that I have in mind to discuss with the authors:\n\n- At the beginning of Section 4, there is a discussion on using two different KL-regularization coefficient during two stages. I am wishing to understand more about the choices and the reason behind. In particular, if I understand it correctly, using different beta essentially lead to different optimal values, which then damages the usefulness of the offline value estimation for the online phase.\n\n- Regarding the theoretical innovation concern raised above, I am also looking forward to learning from the authors more about the underlying and probably hidden contributions there.", "limitations": "Yes", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "This work is a nice exploration of the more efficient methods in RL finetuning of LLM:\n\n- The proposed method is based on theoretical properties of the optimal value under the KL-regularized target, in particular, discovering that it can be estimated via sampling through the reference policy\n\n- The designed algorithm is clear, intuitive, and easy to implement. It tackles the problem that existing methods use extra resources (both computation and memory) to estimate the value function. The pre-computed value estimation from the offline sampling can save resource and time in online fine-tuning.\n\n- The experimental results are comprehensive in terms of metrics. It helps a lot to visualize the comparison of time and memory used by different methods.\n\n- The theoretical results are also solid. I really appreciate the nice connection between empirical designs and theoretical understandings. The results themselves can be valuable in understanding the KL-regularized RL/contextual bandits problem. \n\n- The overall presentation is clear and well-organized.\n\nIf I have to nit-picking, I would hope the authors provide more illustrations of the novelty or innovation behind the theoretical discussions. Currently, the results are well-illustrated, but the underlying proof technics are largely deferred to the appendix without many highlights on the challenges/novelties there.", "was_revised": true, "final_justification": "The authors have answered my questions and I would like to maintain my favorable consideration of this work due to its strong theoretical insights and empirical performances.", "rebuttal": "We sincerely thank the reviewer for the thoughtful and detailed feedback.\n\n> If I have to nit-picking, I would hope the authors provide more illustrations of the novelty or innovation behind the theoretical discussions. Currently, the results are well-illustrated, but the underlying proof technics are largely deferred to the appendix without many highlights on the challenges/novelties there.\n\nThank you for the suggestion. We will highlight the key theoretical innovations more explicitly in the main text in the camera-ready version. With the additional page for camera ready, we plan to expand on the technical challenges and proof introduced in the Appendix.\n\n> At the beginning of Section 4, there is a discussion on using two different KL-regularization coefficient during two stages. I am wishing to understand more about the choices and the reason behind. In particular, if I understand it correctly, using different beta essentially lead to different optimal values, which then damages the usefulness of the offline value estimation for the online phase.\n\nThis is a great observation. Indeed, using different values of $\\beta$ leads to different KL-regularized objectives and corresponding optimal value functions. Our design choice is driven by empirical findings.\n\nAs $\\beta \\to \\infty$, the KL-regularized objective becomes more conservative, and $V^\\star(x)$ converges to the expected reward under the reference policy. Conversely, as $\\beta \\to 0$, $V^\\star(x)$ approximates the $\\text{Pass@}N$ performance of $\\pi_{\\text{ref}}$. The proofs are shown in Appendix E.\n\nWe use a larger $\\beta_1$ in the offline stage to estimate $V^\\star(x)$ and a smaller $\\beta_2$ in the online stage. Our intuition is that using a larger $\\beta_1$ results in a more stable and realistic estimate of the achievable value after policy training, avoiding overly optimistic targets. During the online stage, we use a smaller $\\beta_2$ to loosen the KL constraint, allowing the policy to better optimize reward. Appendix D presents an ablation showing that both overly optimistic or pessimistic estimates of $V^\\star(x)$ can degrade final performance.\n\n> Regarding the theoretical innovation concern raised above, I am also looking forward to learning from the authors more about the underlying and probably hidden contributions there.\n\nWe are grateful for your interest and are happy to elaborate on the theoretical contributions. Our analysis introduces several novel techniques and findings:\n- **Getting rid of policy completeness assumption.** In our analysis we only need policy realizability. In contrast, other on-policy policy optimization approaches including PG, PPO and REBEL rely on a stronger condition called policy completeness. We avoid such a condition by designing novel loss functions, which directly regress to the optimal policy rather than next-step policies similar to policy iteration. \n- **Getting rid of exploration mechanisms.** Our method does not incorporate any explicit exploration mechanism such as optimism in the face of uncertainty or reset to some exploratory distribution as in existing works [1, 2, 3, 4, 5] This is a significant improvement because exploration is necessary in general RL settings. We achieve this by noticing that in the context of LLMs, there exists a close connection between the novel loss functions we proposed and the KL divergence between the learned policy and the optimal policy (illustrated in step 2 of the proof in Appendix H). Leveraging this observation, we managed to bound the suboptimality of the learned policy efficiently.\n- **New findings on nonconvex no-regret learning with OGD.** In the case study of log-linear policy classes, we find that OGD provably converges with the optimal rate. This is a new finding because OGD doesn’t work for nonconvex losses in general. We achieve such a result by establishing a connection between the gradient of the loss and the distance from the optimal parameter (Lemma 3 in Appendix G). This connection enables us to efficiently bound the distance between the learned policy and optimal policy. Notably, the techniques used in Appendix G are totally different from the ones we use in Appendix H (Theorem 1), which is the reason why we can obtain a faster convergence rate.\n\n[1] Xie, T., Foster, D. J., Krishnamurthy, A., Rosset, C., Awadallah, A., & Rakhlin, A. (2024). Exploratory preference optimization: Harnessing implicit q*-approximation for sample-efficient rlhf. arXiv preprint arXiv:2405.21046.\n\n[2] Cen, S., Mei, J., Goshvadi, K., Dai, H., Yang, T., Yang, S., ... & Dai, B. (2024). Value-incentivized preference optimization: A unified approach to online and offline rlhf. arXiv preprint arXiv:2405.19320.\n\n[3] Zhang, S., Yu, D., Sharma, H., Zhong, H., Liu, Z., Yang, Z., ... & Wang, Z. (2024). Self-exploring language models: Active preference elicitation for online alignment. arXiv preprint arXiv:2405.19332.\n\n[4] Bai, C., Zhang, Y., Qiu, S., Zhang, Q., Xu, K., & Li, X. (2025). Online preference alignment for language models via count-based exploration. arXiv preprint arXiv:2501.12735.\n\n[5] Chen, M., Chen, Y., Sun, W., & Zhang, X. (2025). Avoiding $\\mathbf {exp (R_ {max})} $ scaling in RLHF through Preference-based Exploration. arXiv preprint arXiv:2502.00666."}, {"review_id": "qNBoSyGNzd", "reviewer": "Reviewer_bvzh", "summary": "This work proposes $A^*$-PO, an RL technique to finetune reasoning capabilities with improved sample efficiency. It achieves this by first learning an optimal advantage function offline on generations produced by the base reference policy, then during online training, regressing the log ratio against it. The authors demonstrate the improved efficiency compared to PPO/GRPO with only one generation per prompt during online training.", "questions": "These are some specific questions I had in addition to the ones I listed above:\n- In Table 1, what is the significance of showing lower KL-divergence from the base policy? Also, would this not be also impacted by the choice of $\\beta$ in baseline methods?\n- Have the authors considered adaptively changing $N$ based on problem difficulty? For simpler problems, a larger $N$ might not be necessary to estimate the advantage function, whereas for harder problems, it could be more crucial.\n- How well does a model post-trained with $A^{*}$-PO retain its original abilities, i.e., does it exhibit more/less catastrophic forgetting?", "limitations": "Yes.", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 4, "significance": 3, "originality": 3, "strengths_and_weaknesses": "**Strength**\n- The proposed method is novel and theoretically grounded. The paper theoretically and empirically supports the improved sample complexity.\n- The experiments are well-designed and comprehensive, including evaluations on GSM8K, MATH, and long-context benchmarks, as well as showing generalization to other benchmarks after training.\n\n**Weaknesses**\nI am not an RL expert, and would defer constructive criticism to more experienced reviewers. I mainly have a few questions:\n- How would the estimation of $V^*$ perform with non-binary or denser reward signals (e.g., with process-supervision)?\n- The authors state that during online training, only one sample is required to regress on the estimated optimal advantage, what would be the impact if multiple samples were generated?\n- Clarifying question: In Fig 4, is filtering applied during the online stage, i.e., problems that did not find a correct solution (as measured in Stage 1) are not used for online training? Would this technique also apply to PPO/GRPO, or is this something specific to your method?\n- Have the authors ablated the effect of different values of $\\beta$ for the two stages?", "was_revised": true, "final_justification": "Here is a summary of my thoughts after the rebuttal:\n* The generalization of the method to arbitrary/dense rewards is clear and promising.\n* Filtering strategy: Given that filtering is enabled by offline sampling in the proposed method, I asked a tiny follow-up question: does this filtering lead to any bias in the 'online' training distribution, especially in domains where initial success rates are low?\n* I encouraged the authors to discuss any interactions between $N$ and $\\beta_1$, given that both impact the quality of value estimates.\n* The empirical and theoretical results in App D/E make sense.\n\nOverall, the responses address my initial questions well, and I would like to maintain my positive rating and increase my confidence.", "rebuttal": "We thank the reviewer for their constructive and thoughtful comments.\n\n> How would the estimation of $V^\\star$ perform with non-binary or denser reward signals (e.g., with process-supervision)?\n\nOur method is compatible with non-binary and dense rewards, as we make no assumptions about the reward values. While our experiments focus on the bandit setting with terminal rewards, the value estimation naturally extends to dense or process-level supervision. Consider a setting with a prompt $x$ and a response with $H$ steps $y_{1:H}$. Then the optimal value at step $h$ can be expressed as $V^\\star(x, y_{1:h}) = \\beta \\ln \\mathbb{E} {\\pi_{ref}} \\left[\\exp( \\sum_{t > h} r(x,y_{1:t}) / \\beta )\\right]$ where $r(x,y_{1:t})$ is the process reward for step $t$. Thus, our framework remains applicable under denser reward feedback. We leave the empirical exploration under these settings for future work.\n\n> The authors state that during online training, only one sample is required to regress on the estimated optimal advantage, what would be the impact if multiple samples were generated?\n\nTheoretically, using multiple samples per prompt has no effect on the expected loss as $ \\mathbb{E}{x \\sim \\rho, y \\sim \\pi(\\cdot|x)}[\\ell(x, y)] = \\mathbb{E}{x \\sim \\rho,(y_1, \\dots, y_K) \\sim \\pi(\\cdot|x)}\\left[\\frac{1}{K} \\sum_{k=1}^K \\ell(x, y_k)\\right] $ holds for any loss function $\\ell$ and any $K$. However, in practice, generating multiple samples per prompt—as in GRPO—increases training time and memory usage. Our method is more efficient because it achieves comparable performance with only a single generation per prompt.\n\n> Clarifying question: In Fig 4, is filtering applied during the online stage, i.e., problems that did not find a correct solution (as measured in Stage 1) are not used for online training? Would this technique also apply to PPO/GRPO, or is this something specific to your method?\n\nYes, the filtering is applied before the online stage: we discard prompts for which none of the $N$ offline samples from $\\pi_{\\text{ref}}$ yield a correct answer. While this strategy could be applied to PPO or GRPO, those methods do not have offline sampling and would need to perform additional inference solely for filtering, which adds further overhead to already more complex training pipelines. In contrast, our method naturally performs offline sampling for value estimation, so filtering introduces negligible extra cost and offers a natural efficiency bonus.\n\n> Have the authors ablated the effect of different values of $\\beta$ for the two stages?\n\nYes, this is addressed in Appendix D. As $\\beta_1 \\to \\infty$, the estimated $V^\\star(x)$ approaches the expected reward under $\\pi_{\\text{ref}}$; as $\\beta_1 \\to 0$, it converges to the $\\text{Pass@}N$ performance. These properties are theoretically proven in Appendix E.\n\nWe choose a larger $\\beta_1$ for the offline stage to provide a smooth and stable value estimate, and a smaller $\\beta_2$ during online training to relax the KL constraint and promote reward maximization. Our ablations show that overly optimistic or pessimistic estimates of $V^\\star(x)$ can both harm performance. For $\\beta_2$, we found that $10^{-3}$ consistently gives strong results; larger or smaller values would degrade the performance.\n\n> In Table 1, what is the significance of showing lower KL-divergence from the base policy? Also, would this not be also impacted by the choice of $\\beta$ in baseline methods?\n\nLower KL divergence indicates that the trained policy stays closer to the reference policy while still achieving strong performance. This is significant because the KL-regularized RL objective aims to optimize reward while staying minimally divergent from the base model. Our results show that $A^\\star$-PO induces significantly less change to the base model than PPO/GRPO for comparable or better performance—suggesting better stability and less catastrophic forgetting.\n\nIndeed, the KL divergence can be influenced by the choice of $\\beta$ in baseline methods. However, we tuned $\\beta$ for all methods to maximize the validation accuracy to ensure a fair comparison, and $A^\\star$-PO consistently achieves the smallest KL divergence across model sizes and datasets.\n\n> Have the authors considered adaptively changing $N$ based on problem difficulty? For simpler problems, a larger $N$ might not be necessary to estimate the advantage function, whereas for harder problems, it could be more crucial.\n\nThis is an excellent suggestion. Intuitively, prompts with intermediate success rates (e.g., around 50% accuracy under $\\pi_{\\text{ref}}$) have higher variance in their value estimates, and would benefit from more samples to improve estimation accuracy. In contrast, very easy or very hard prompts (i.e., near 0% or 100% success) require fewer samples, as their value estimates are more stable. While we have not explored adaptive selection of $N$ in this work, it is indeed a promising direction.\n\n> How well does a model post-trained with $A^\\star$-PO retain its original abilities, i.e., does it exhibit more/less catastrophic forgetting?\n\nWhile we did not explicitly test for catastrophic forgetting, the significantly lower KL divergence to the base model suggests that $A^\\star$-PO better preserves the original capabilities compared to PPO and GRPO. This is an important benefit for applications requiring general-purpose LLMs with minimal task-specific overfitting."}, {"review_id": "0Q0rsd7wR2", "reviewer": "Reviewer_q8X3", "summary": "The paper introduces A⋆-PO (Policy Optimisation via Optimal Advantage Regression), a two-stage RL procedure for post-training LLMs on reasoning tasks. The work offers a neat regression-based alternative to critic-heavy RL algorithms, with solid speed-ups and \"formal guarantees\", but those guarantees require many unrealistic assumptions that may not hold for frontier-scale LLMs.\n\nI would like to clarify a point before I move on to the questions. it is known that under sufficient assumptions, one can get vanishing regrets; however the active area of research is generalising those to problems that include non-linearities and non-convexity.", "questions": "Please see above", "limitations": "Briefly mentioned", "rating": 4, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 2, "significance": 2, "originality": 2, "strengths_and_weaknesses": "The paper has a nice flow to it and reads well, till the theoretical section which I felt was not very well presented. I feel for the authors due to the constraints of space, but more discussions on the assumptions and their impact are indeed needed. I would like to ask the authors some questions: \n\n1. When are policy classes not misspecified? Because if they are, then the realizability assumption would have issues. Please discuss the approximation error or clearly detail which architectures make the assumption plausible and why? \n\n2. In assumption 2, can the log-ratio explode? I thought it could, e.g, if we pair a small model with a larger reference one? Is this correct? Can the authors please help me understand? If so, I think the theory should handle how to renormalise? \n\n3. In assumption 3, v_ref can be very low, especially on some hard problems. This might make the bound vacuous, can the authors please characterise performance as v_ref tends to zero? Maybe an adaptive sampling procedure might help to remedy this issue? \n\n4. The Fisher assumption also doesn't really hold in many high-dimensional cases with deep networks - in fact, many times the Fisher matrix ends up ill-conditioned. Maybe the authors could add a regularisation (which will change the update rules) and study and quantify the value of such regularisers needed in practice. \n\n5. The Gap hides a massive constant. Can the authors please bound those constants or give ballpark numbers so that those aren't massive, like they are not > 1?  \n\nI don't mean to be annoying, but given that I come from a theoretical background, the value of the theoretical section in this paper is minimal from my point of view; those assumptions are standard and (almost always and this is a well known fact) do not apply to non-convex losses, deep networks, and transformers. In other words, it is like taking a theory that had been developed for some types of problems and adding it to a new type of problem, but making the relevant assumptions so that the new type of problem meets the first type. \n\n6. I would like to see more experiments related to coding benchmarks as well; they also require formal reasoning. Can the authors please report those if possible? \n\n7. Please publish wall-clock times per stage and GPU hours for all baselines.  \n\n8. There are no error bars, and the authors clearly say NO to the statistical significance question. I am not sure how to take that? Like are the results reported in the paper by luck? \n\nI am happy to improve my scores of the above questions have been answered.", "was_revised": true, "final_justification": "Rebuttal addressed my concerns!", "rebuttal": "We thank the reviewer for their detailed comments.\n\n> the active area of research is generalising those to problems that include non-linearities and non-convexity.\n\nWe acknowledge this point, and would like to clarify that our theoretical analysis is exactly on **nonconvex and nonlinear cases**. More specifically, **Theorem 1 addresses general policy classes**, which are nonconvex and nonlinear. Consequently, the loss function $\\widehat{l}_t$ is also **nonconvex and nonlinear with respect to $\\pi$**. To handle this, we introduce the decoupling coefficient (Definition 1), which is effective when dealing with nonconvexity and nonlinearity.\n\nWe also present a case study on log-linear policy classes to illustrate our theoretical results more clearly. We would like to clarify that **log-linear policy classes and the corresponding loss functions are still “nonconvex and nonlinear” with respect to the parameter $\\theta$**. We designed two specific algorithms (utilizing FTPL and OGD) for this case and they achieve sub-linear regret. We will further highlight our focus on nonconvexity in the paper.\n\n> Weaknesses 1\n\nWe assume policy class realizability to simplify presentation, as almost all the existing theoretical works do. That said, **our analysis can be generalized to misspecified policy classes easily**. Assume that the approximation error of the policy class is as follows:\n$$\\min_{\\pi\\in\\Pi, x, y} |\\ln\\pi(y|x)-\\ln\\pi^{\\star}(y|x)|\\leq C_{\\mathsf{approx}}.$$\nLet $\\widetilde{\\pi}$ denote the policy in $\\Pi$ that is closest to $\\pi^{\\star}$. Then we have \n$$\\widehat{l} ^t(\\widetilde{\\pi}) \\leq 2\\widehat{l} ^t(\\pi^{\\star}) + 2\\beta^2C^2_{\\mathsf{approx}}.$$\nSubstituting the above inequality to the proof in Appendix H, we know that working with misspecified policy classes is equivalent to adding $\\beta^2C^2_{\\mathsf{approx}}$ to the regret. All the results still hold, with just an additional approximation error.\n\n> Weaknesses 2\n\nWe would like to point out that in empirical works, with clipping techniques, such log ratios can be controlled and not blow up. That is also the reason why the existing theoretical works on DPO-type algorithms have similar assumptions.\n\n> Weaknesses 3\n\nFirst we would like to clarify that our bound depends on $min(\\exp(1/\\beta), v_{ref})$. Therefore, if $\\beta$ is fixed (which is typically the setting in practice), our result would not be worsened by small $v_{ref}$. On the other hand, a well known and widely applied technique in LLM training is filtration, i.e., filtering out the prompts that are too difficult or too easy. With this process, $v_{ref}$ will be reasonably large during RL training, preventing $1/v_{ref}$ from blowing up.\n\n> Weaknesses 4\n\nFirst, Fisher matrix assumption is not necessary in terms of achieving sublinear regret. Corollary 1 does not need any assumptions on Fisher matrix. The reason why we introduce Fisher matrix assumption is that we want to claim that our algorithm can enjoy a faster convergence when the problem is regular and well conditioned. That said, in our experiments, we used OGD and our algorithm works pretty well. This demonstrates that even if the Fisher matrix can be ill conditioned sometimes, the problem is often regular and OGD can work in practice.\n\n> Weaknesses 5\n\nThrough a rough calculation, the constants in Theorems 1 and 2 can essentially be bounded by 16 and 64, respectively. For Theorem 1, we omitted four constants of 2 in Lines 680, 681, 686, and 690. For Theorem 3, the constant on the right-hand side of the inequality in Line 651 can be bounded by 256, which implies that the constant in Line 655 is $4\\sqrt{256} = 64$. Notice that the actual constants will be much smaller than these theoretical values, especially considering that we relaxed these constant terms for analytical convenience in analysis. Even so, it suffices to say that these constants are not massive.\n\n> those assumptions are standard and do not apply to non-convex losses, deep networks, and transformers\n\nWe agree that these assumptions are standard, but we respectively disagree that they do not apply to these settings. First, **realizability does not depend on whether the function classes are convex. Instead, more complicated function classes like deep networks and transformers typically have a higher representation capacity and thus realizability is easier to satisfy (at least the approximation error would be smaller.)** Second, **other assumptions have their origins in practice.** The log ratio is bounded because of clipping, and $v_{ref}$ is not small because of filtration. In addition, these techniques work well in practice, which further support the validity of these assumptions. **Since these assumptions are standard in existing works, we do not assume unreasonable assumptions to simplify analysis or use other works’ results directly.**\n\n> it is like taking a theory that had been developed for some types of problems and adding it to a new type of problem, but making the relevant assumptions so that the new type of problem meets the first type\n\nWe respectfully disagree with this claim. As the reviewer has noted, our assumptions are standard in existing works, indicating that we do not introduce additional, unreasonable assumptions merely to reuse existing theory. On the contrary, **our analysis introduces several novel techniques and results.** We summarize them below for clarity:\n- **Getting rid of policy completeness assumption.** In our analysis we only need policy realizability. In contrast, other on-policy policy optimization approaches including PG, PPO and REBEL rely on a stronger condition called policy completeness. We avoid such a condition **by designing novel loss functions, which directly regress to the optimal policy rather than next-step policies similar to policy iteration.**\n- **Getting rid of exploration mechanisms.** Our method does not incorporate any explicit exploration mechanism such as optimism in the face of uncertainty or reset to some exploratory distribution as in existing works. **This is a significant improvement because exploration is necessary in general RL settings.** We achieve this by noticing that in the context of LLMs, **there exists a close connection between the novel loss functions we proposed and the KL divergence between the learned policy and the optimal policy** (illustrated in step 2 of the proof in Appendix H). **This is a new finding.** Leveraging this observation, we managed to bound the suboptimality of the learned policy efficiently.\n- **New findings on nonconvex no-regret  learning with OGD.** In the case study of log-linear policy classes, we find that OGD provably converges with the optimal rate. **This is a new finding because the loss functions are still nonconvex with log-linear policy classes and OGD does not work for nonconvex losses in general.** We achieve such a result not by making unreasonable assumptions, but by **establishing a connection between the gradient of the loss and the distance from the optimal parameter** (Lemma 3 in Appendix G), **which is a new finding in this area.** This connection enables us to efficiently bound the distance between the learned policy and optimal policy. Notably, the techniques used in Appendix G are totally different from the ones we use in Appendix H (Theorem 1), which is the reason why we can obtain a faster convergence rate.\n\n> Weaknesses 6\n\nWe agree that coding benchmarks are an important and challenging class of reasoning tasks. However, we did not include them in this work due to the significant computational overhead involved—specifically, reward computation typically requires running unit tests in isolated environments, which introduces substantial cost and engineering complexity. Despite this, we believe $A^\\star$-PO remains well-suited for coding tasks, as it only requires one sample per prompt during online training, and thus demands fewer reward queries than approaches like GRPO that rely on multiple generations. This efficiency advantage would likely persist in the coding domain, and we are excited to explore this direction in future work.\n\n> Weaknesses 7\n\nThank you for the suggestion. We include wall-clock training times for each method in Figure 2 and Tables 1 and 2. As described in Appendix A.2 and A.4, our experiments were run on machines with 4 H100 GPUs (for Sections 4.1 and 4.2) and 8 H100 GPUs (for Section 4.3). Therefore, GPU hours can be directly computed by multiplying the reported training times by the number of GPUs used. To further clarify the training efficiency of $A^\\star$-PO, we include a rate-of-convergence analysis in the supplemental material, showing training and generation time versus reward. We will move this analysis into the appendix in the camera-ready version to make this information more accessible.\n\n> Weaknesses 8\n\nWe appreciate the opportunity to clarify. While we did not include error bars in the current submission, all experiments were run with fixed seeds, making our results exactly reproducible. Furthermore, in large-scale RL for LLMs, empirical results tend to be stable across runs due to the high sample count per iteration—often involving hundreds of prompt-response pairs per update and training over thousands of steps. To further reduce variance, we report results on large-scale datasets and, for smaller benchmarks such as AMC 23, AIME 24/25, and HMMT Feb 24/25, we compute the average performance over 32 generations per prompt. This setup ensures statistical reliability even in the absence of formal error bars. We are confident that the observed performance improvements are robust and not due to chance, as they are consistent across models, datasets, and evaluation metrics."}]

Author rebuttal:

Meta-review: This paper introduces A*-PO, a clever two-stage framework for fine-tuning LLMs on reasoning tasks using reinforcement learning. The core idea is to make the process more efficient by decoupling the costly value estimation from online training. It achieves this by first estimating the optimal value function offline using a reference model, and then updating the policy online with a simple regression loss that only requires a single generation per prompt. The method's main strengths are its impressive efficiency—significantly cutting training time and memory usage—and its elegant simplicity. The approach is novel, easy to implement, and well-supported by both solid theoretical guarantees and strong empirical results across various math reasoning benchmarks. While there were some initial questions from reviewers about the experimental scope and certain theoretical assumptions, the authors provided a thorough and convincing rebuttal that clarified these points well. This is a well-executed paper that presents a valuable and practical contribution to the field, and I'm happy to recommend its acceptance.
Decision: Accept (poster)