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 660 papers

Sep 28, 2026

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

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.

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

MPI-IS · ELLIS Institute Tübingen

Reinforcement Learning Actor-Critic Methods Reinforcement Learning with Verifiable Rewards

Ask PDF

Jul 28, 2026

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

Reinforcement learning with verifiable rewards (RLVR) is bottlenecked by rollout generation, yet many sampled prompts produce saturated groups (all responses correct or all incorrect) whose zero reward variance yields no policy-gradient signal. Existing remedies either oversample a larger candidate pool and discard saturated prompts (dynamic sampling), paying heavy extra rollouts, or predict prompt difficulty before sampling, which is fragile under a shifting policy. We observe that a group's effectiveness is usually decided early, within the first few of its rollouts, so spending a full group on an already-decided prompt is wasteful. We cast per-step rollout collection as a budget-constrained sequential allocation (optimal stopping) problem and introduce SARA (Sequential Adaptive Rollout Allocation). SARA maintains a Beta posterior over each prompt's success rate, evaluates a closed-form predictor of group effectiveness, and applies a two-threshold, SPRT-style rule that commits effective groups, abandons saturated ones after a short probe, and reallocates the freed budget to fresh prompts, without any extra prediction rollouts. We prove abandonment reliability, expected rollout savings, fixed-budget yield dominance, and a link between effective-group yield and the GRPO gradient norm. On mathematical reasoning and planning with 1.5B/3B models on a single GPU, SARA matches DPS (both below the DS oracle) while using 22% fewer rollouts than DS; composing SARA with DPS yields the best accuracy, slightly above DS, at 67% fewer rollouts (near-uniform cost).

Pixel Nomand, Elena Voss, Marcus Hale +1

University of Wisconsin–Madison · University of Washington

Reinforcement Learning RL for Language Model Reasoning Reinforcement Learning with Verifiable Rewards Sample-Efficient RL

Ask PDF

Jul 24, 2026

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

Reinforcement learning with verifiable rewards (RLVR) has emerged as a highly effective framework for improving LLM reasoning, with methods such as GRPO among its most successful instantiations. However, GRPO relies on repeated generation of long chain-of-thought rollouts. Training time scales with the number of rollouts, a large fraction of which are uninformative. Thus, GRPO is computationally expensive and unstable. To mitigate this, existing approaches either generate a larger pool of rollouts and filter the most informative prompts, or leverage historical signals for filtering at later stages of training. These strategies offer modest performance gains, but slow down the overall process. To address this, we propose VarIance Guided Online Rollout allocation (VIGOR) which instead of allocating a fixed rollout budget per example, begins with a small number of rollouts for all examples in a batch and iteratively allocates additional rollouts to those with the highest group reward variance until a fixed total rollout budget is reached. Theoretically, we show that under RLVR, reward variance controls the gradient magnitude, and derive VIGOR's closed-form speedup ratio over GRPO, which grows with refinement rounds under Pareto-distributed reward variance. Experiments on mathematical reasoning and coding tasks show that VIGOR reaches target accuracy with up to 2.3

\times

fewer rollouts on math, reaches GRPO's final coding full pass rate with 1.49

\times

fewer rollouts, and improves the coding average test pass rate by 3.4 points.

Heyang Jiang, Henry Liu, Baharan Mirzasoleiman

University of California, Los Angeles

RL for Code Generation RL for Language Model Reasoning Reinforcement Learning with Verifiable Rewards Sample-Efficient RL

Ask PDF

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