Variance-Optimal State Resampling for Reinforcement Learning with Verifiable Rewards

Yibo Wang; Yuanxin Liu; Zhaoran Wang

cs.LGOct 11, 2026

Variance-Optimal State Resampling for Reinforcement Learning with Verifiable Rewards

Authors: Yibo Wang, Yuanxin Liu, Zhaoran Wang

Abstract

Reinforcement learning with verifiable rewards spends much of its rollout budget on states that yield no learning signal. We recast this as a question about the sampling distribution itself: under a fixed rollout budget, which distribution over states minimizes the variance of the policy-gradient estimator? The answer admits a closed-form Neyman allocation, $μ_{\mathrm{var}}^π(s) \propto d^π(s)\,σ_π(s)$ , which connects naturally to GRPO's group-relative advantage and induces an emergent reverse curriculum as the policy improves, with no externally imposed schedule. Building on this principle, we propose VSR (Variance-driven State Resampling), a plug-in modification to GRPO using a prefix replay buffer and a zero-cost variance proxy. On mathematical reasoning benchmarks and long-horizon agentic tasks (Sokoban, BabyAI), VSR outperforms GRPO and GiGPO on most benchmarks with fewer generated tokens per update.

Figures & tables

Figure 1: Continuations from early prefixes mostly fail and from late prefixes mostly succeed; both yield low signal. VSR samples states in proportion to

d^{\pi}(s)\,\sigma_{\pi}(s)

to capture the highest signal.

Figure 2: An emergent curriculum from the variance-optimal proposal. $\mu_{\mathrm{var}}^{\pi}$ is concentrated near $G$ early in training, and gradually walks backward through the maze toward $S$ as cells closer to the goal are mastered one after another. This is the reverse curriculum: the training signal visits the state space in reverse without any externally imposed schedule. It is a built-in property of variance-optimal sampling: the variance-minimizing distribution by construction concentrates wherever the policy is reachable but still uncertain, and that frontier moves backward as the policy improves.

\hat{\sigma}_{t+1}(s_{i})=\sqrt{\hat{p}_{i}(1-\hat{p}_{i})},\quad\hat{p}_{i}=(1-\alpha_{i})\,p_{0}(x_{j})+\alpha_{i}\,R(\tau),\quad\alpha_{i}=i/|\tau|

Algorithm 1 VSR (Variance-driven State Resampling)

Figure 3: Illustration of intermediate states used by VSR. Left: a BabyAI agent after picking up the red key. Right: a math problem with a partial reasoning trace appended.

Model	Method	AIME24	AIME25	AMC23	Olympiad	MATH500	Minerva	Avg
Qwen2.5-7B -Instruct	Base model	$10.0$	$7.9$	$53.2$	$\mathbf{39.2}$	$\mathbf{75.6}$	$37.3$	$37.2$
	GRPO	$8.8$	$4.8$	$53.4$	$38.3$	$72.5$	$38.6$	$36.1$
	VSR+GRPO	$\mathbf{11.4}$	$\mathbf{10.4}$	$\mathbf{57.7}$	$33.5$	$73.7$	$\mathbf{38.7}$	$\mathbf{37.6}$
Llama-3.2 -3B-Instruct	Base model	$5.3$	$0.6$	$21.8$	$12.6$	$40.0$	$13.8$	$15.7$
	SFT	$0.3$	$0.4$	$7.2$	$5.0$	$23.1$	$5.4$	$6.9$
	GRPO	$4.4$	$\mathbf{1.0}$	$18.7$	$12.6$	$39.2$	$16.5$	$15.4$

Table 1: Mathematical reasoning results (%) on AIME24, AIME25, AMC23, OlympiadBench, MATH500, and Minerva. Reinforce-Ada-Est and static uniform expert-prefix resets are additional single-run controls on Llama-3.2-3B-Instruct. Best result in each column is in bold .

Figure 4: Training dynamics on the 1K hard subset of OpenR1-Math-220k for Qwen2.5-7B-Instruct (top) and Llama-3.2-3B-Instruct (bottom). Columns show training reward, validation accuracy, and response length over training steps. VSR+GRPO sustains higher training reward and validation accuracy than GRPO with shorter responses.

		Sokoban	BabyAI
Model	Method	Sokoban	SynthLoc	OneRoom	MiniBoss	Avg
Qwen2.5-1.5B-Instruct	Base model	$9.4$	$11.6$	$9.3$	$21.4$	$14.1$
	GiGPO	$12.7$	$32.3$	$27.9$	$30.9$	$30.4$
	VSR+GiGPO	$\mathbf{18.8}$	$\mathbf{51.2}$	$\mathbf{54.6}$	$\mathbf{36.9}$	$\mathbf{47.6}$
Qwen2.5-3B-Instruct	Base model	$17.2$	$9.3$	$18.6$	$16.7$	$14.9$
	GiGPO	$21.5$	$51.2$	$46.5$	$30.9$	$42.9$

Table 2: Agentic-task success rates (%) on Sokoban and BabyAI. Best result is in bold .

Figure 5: Training dynamics on BabyAI and Sokoban for Qwen2.5-1.5B-Instruct (top two rows) and Qwen2.5-3B-Instruct (bottom two rows). Columns show training reward, validation success rate, and newly generated continuation length after the selected reset state over training steps. The shorter continuation length partly follows mechanically from starting a fraction of rollouts at intermediate states and should not be read as shorter complete trajectories from the original task state.

Appendix figures & tables6 assets

Supplementary material from the paper’s appendix.

Appendix

\widetilde{\mu}_{h}^{t}(s)\propto d_{h}^{\pi_{t}}(s)\sigma_{h}^{\pi_{t}}(s),\qquad\mu_{h}^{t}(s):=(1-\varepsilon)\widetilde{\mu}_{h}^{t}(s)+\varepsilon\,d_{h}^{\pi_{t}}(s),

Appendix

Algorithm 2 State-Visitation Policy Mirror Descent (SVMD)

Figure 7: Empirical continuation success rate as a function of hint ratio. For each of the 1K hard prompts in the training subset, we truncate the corresponding successful DeepSeek-R1 trajectory to a fraction $\alpha\in\{0\%,25\%,50\%,75\%,100\%\}$ of its length and sample 8 continuations under Qwen2.5-7B-Instruct. The blue curve shows the mean per-prompt success rate across the 1K prompts; the shaded band shows the 25–75 percentile across prompts. The mean is approximately linear in $\alpha$ , supporting the linear interpolation used in $\hat{p}_{t}(s_{i}\mid\tau)=(1-\alpha_{i})\,p_{0}(x)+\alpha_{i}\,R(\tau)$ .

Hyperparameter	Qwen2.5-7B-Instruct	Llama-3.2-3B-Instruct
Replay ratio $\rho$	0.5	0.5
Training steps	360	360
Max Prompt Length	2048	2048
Max Response Length	4096	4096
Rollout Group Size	8	8
Training batch size	128	128

Appendix

Table 4: Hyperparameters for mathematical reasoning experiments.

Hyperparameter	Qwen2.5-1.5B-Instruct	Qwen2.5-3B-Instruct
Replay ratio	0.3	0.3
Recency window	5	5
Max prompt length	2048	2048
Max response length	256	256
Rollout group size	8	8
Training batch size	32	32

Appendix

Table 5: Hyperparameters for agentic-task experiments.

Method	AIME24	AIME25	AMC23	Olympiad	MATH500	Minerva	Avg.
GRPO	4.4	1.0	18.7	12.6	39.2	16.5	15.4
Reinforce-Ada-Est	4.2	0.1	18.0	12.4	39.9	15.4	15.0
Static uniform expert-prefix resets	5.6	0.5	22.7	14.1	43.7	15.8	17.1
VSR	6.2	0.6	20.4	15.3	54.0	17.8	19.1

Appendix

Table 6: Additional mathematical-reasoning controls on Llama-3.2-3B-Instruct. These are single training runs; the original benchmark evaluation protocol is otherwise unchanged.

Method	Run 1	Run 2	Run 3	Mean $\pm$ SD
Uniform replay	46.1	39.1	46.9	$44.0\pm 4.3$
VSR	47.6	50.8	46.1	$48.2\pm 2.4$

Appendix

Table 7: Independent-run BabyAI scoring ablation on Qwen2.5-1.5B. Values are average success rates (%).

Reinforcement Learning with Verifiable Rewards

Reinforcement learning with verifiable rewards trains models using outcomes checked by code, proofs, simulators, or structured criteria.

See all 663 papers

ABC: Advantage-Based Control Variates for Reinforcement Learning with Verifiable Rewards
Sep 28, 2026Hsiao-Ru Pan, Florent Draye, Bernhard SchölkopfReinforcement Learning Actor-Critic Methods
MPI-IS · ELLIS Institute Tübingen
Early Verdicts, Better Budgets: Sequential Adaptive Rollout Allocation for Compute-Efficient RLVR
Jul 28, 2026Pixel Nomand, Elena Voss, Marcus Hale +1Reinforcement Learning RL for Language Model Reasoning
University of Wisconsin–Madison · University of Washington
Learning as Reasoning Unfolds: Progressive Rollout Allocation for Efficient Reinforcement Learning
Jul 24, 2026Heyang Jiang, Henry Liu, Baharan MirzasoleimanRL for Code Generation RL for Language Model Reasoning
University of California, Los Angeles

Sep 28, 2026J/K move · Enter open · S save

ABC: Advantage-Based Control Variates for Reinforcement Learning with Verifiable Rewards

Hsiao-Ru Pan, Florent Draye, Bernhard Schölkopf

MPI-IS · ELLIS Institute Tübingen

Reinforcement Learning Actor-Critic Methods Reinforcement Learning with Verifiable Rewards

Open paper AskPDF arXiv

Recent progress in reinforcement learning with verifiable rewards (RLVR) has highlighted the effectiveness of simple critic-free policy-gradient methods such as Group Relative Policy Optimization (GRPO). In contrast, actor-critic methods rely on learned value functions whose approximation error can introduce bias through commonly used advantage estimators such as temporal-difference error. Motivated by this observation, we revisit trajectory-level control variates through an advantage-value formulation, which we call Advantage-Based Control Variates (ABC). This formulation reveals that the covariance structure is closely related to the return decomposition used in Direct Advantage Estimation (DAE). Finally, we combine ABC with DAE into a single actor-critic algorithm and evaluate it in an offline-to-online RLVR setting, where the critic is first trained on previously collected trajectories and adapted during online learning. On mathematical reasoning tasks, ABC achieves performance competitive with GRPO using substantially fewer online optimization steps.

Abstract

Reinforcement Learning with Verifiable Rewards

Explore similar work

ABC: Advantage-Based Control Variates for Reinforcement Learning with Verifiable Rewards

Early Verdicts, Better Budgets: Sequential Adaptive Rollout Allocation for Compute-Efficient RLVR

Learning as Reasoning Unfolds: Progressive Rollout Allocation for Efficient Reinforcement Learning