Paper deep dive
Variance-Optimal State Resampling for Reinforcement Learning with Verifiable Rewards
Yibo Wang, Yuanxin Liu, Zhaoran Wang
Intelligence
Status: not_run | Model: - | Prompt: - | Confidence: 0%
Entities (0)
Relation Signals (0)
No relation signals yet.
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
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, $\mu_{\mathrm{var}}^\pi(s) \propto d^\pi(s)\,\sigma_\pi(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.
Tags
Links
- Source: https://arxiv.org/abs/2610.15888v1
- Canonical: https://arxiv.org/abs/2610.15888v1
Trouble viewing inline? Open PDF directly →
Full Text
103,163 characters extracted from source content.
Expand or collapse full text
Variance-Optimal State Resampling for Reinforcement Learning with Verifiable Rewards Yibo Wang Yuanxin Liu Zhaoran Wang Affiliation: Northwestern University Affiliation: yibowang2030, yuanxinliu2029@u.northwestern.edu Email: zhaoranwang@gmail.com 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, μvarπ(s)∝dπ(s)σπ(s) _var^π(s) 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. 1 Introduction Training large language models with reinforcement learning from verifiable rewards has become a standard recipe for improving reasoning and agentic capabilities. In practice, however, a non-trivial fraction of training steps contribute little signal: in GRPO-style training, rollout groups that return uniform rewards—all-fail or all-success—yield a collapsed group-relative advantage and a near-zero update. 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π(s)σπ(s)d^π(s)\, _π(s) to capture the highest signal. It can be helpful to look at this pathology at the level of state distribution, rather than prompt difficulty. Even on hard problems, not all intermediate states are equally uninformative. Consider a competition math problem that the current policy rarely solves from the prompt alone. Once the policy has produced a partial chain of thought that performs a key algebraic reduction, continuations from that prefix tend to succeed with noticeably higher probability, and different continuations produce genuinely mixed outcomes. A similar pattern shows up in long-horizon agentic tasks: from the initial query, a successful trajectory is uncommon, but once the agent has identified the relevant information source through a few tool calls, the remaining decisions can lead to meaningfully different outcomes. In both cases, the trajectory passes through intermediate states with rich gradient signals, although rollouts generated from the prompt alone rarely reach it. The challenge is that such states tend to be visited with low probability under the current policy’s state distribution dπd^π, so finite-sample training encounters them only occasionally. Therefore, a complementary question which seems to have received comparatively less direct attention is: Under a fixed rollout budget, which state distribution minimizes the variance of the policy-gradient estimator? In this paper we take up that question. Under a gradient uniformity assumption, we find that the answer takes a closed form with Neyman-allocation structure, μvarπ(s)∝dπ(s)σπ(s). _var^π(s) d^π(s) _π(s). (1) This proposal allocates training mass by the product of on-policy relevance and residual signal magnitude, and it evolves with the policy, giving rise to an emergent curriculum without a hand-designed difficulty schedule. Implementing μvarπ _var^π with exact proposal correction would involve an inverse-σπ _π factor. GRPO’s group-relative normalization provides a practical analogue of this factor by normalizing rewards with an empirical within-group standard deviation. We instantiate this idea as VSR (Variance-driven State Resampling), a practical plug-in modification to GRPO-style algorithms that approximates the variance-optimal proposal. As a tractable algorithmic realization of the allocation principle, VSR uses a recent prefix replay buffer as a density-free surrogate for the current state-visitation distribution and a cheap proxy for σπ _π to prioritize replayed prefixes. Experiments on math reasoning and long-horizon agentic tasks demonstrate the effectiveness of this approximation. Contributions. • We formulate the uniform-reward pathology in GRPO-style training as a variance-reduction problem over the state sampling distribution, and derive a closed-form μvarπ∝dπ(s)σπ(s) _var^π d^π(s)\, _π(s), which matches the form of GRPO’s group-relative advantage and induces an emergent reverse curriculum as the policy improves. • Building on this principle, we propose VSR (Variance-driven State Resampling), a plug-in practical modification to GRPO that approximates μvarπ∝dπ(s)σπ(s) _var^π d^π(s)\, _π(s) through a state replay buffer and a zero-cost variance proxy. • On hard mathematical reasoning benchmarks and long-horizon agentic tasks, VSR outperforms GRPO and GiGPO baselines with fewer generated tokens per update, and ablations isolate the contributions of variance-driven scoring and recency-based buffer updates. 2 The variance-driven state proposal 2.1 Setup A natural starting question for any policy-gradient method is: what distribution is training actually averaging over? For general RL the answer is the state visitation measure dπd^π, and the policy gradient takes the form ∇J(π)=s∼dπ,a∼π(⋅∣s)[∇logπ(a∣s)r~(s,a)],dπ(s)∝∑t=0T−1Pr(st=s|s0∼,π),∇ J(π)\;=\;E_s d^π,\,a π(· s)\! [∇ π(a s)\, r(s,a) ], d^π(s)\; \; _t=0^T-1 (s_t=s\, |\,s_0 ,\,π ), (2) where r~(s,a)=r(s,a)−b(s) r(s,a)=r(s,a)-b(s) for a state-dependent baseline b. The expectation is taken with respect to dπd^π, which is therefore the distribution under which gradient signal is sampled. LLM RL with verifiable rewards is most often presented as a contextual bandit under which the only input-side distribution is the prompt distribution D. This framing is coarse relative to how generation actually proceeds: a single rollout on a reasoning problem spans thousands of tokens and passes through qualitatively distinct regimes such as restatement, algebraic reduction, and reflection, while on long-horizon agentic tasks a trajectory decomposes into a sequence of consequential intermediate decisions. We therefore adopt the standard state-action view throughout, in which s0=x∼,st=(x,y<t),at=yt,τ=(s0,a0,s1,a1,…,sT).s_0=x , s_t=(x,y_<t), a_t=y_t, τ=(s_0,a_0,s_1,a_1,…,s_T). (3) This is the same structure realized by the triangular attention mask inside the transformer itself. Under this instantiation, dπd^π is a marginal over all intermediate contexts the policy passes through, not over prompts alone. 2.2 The sampling proposal as a variance-reduction lever Reducing the variance of policy-gradient estimators is a long-standing concern, and most of the work has gone into the gradient baseline b(s)b(s) (Greensmith et al., 2004). The proposal μ from which states are sampled has not, by comparison, been treated as something to be optimized: it is set to dπd^π and any deviation is handled as an off-policy correction problem rather than as a variance-reduction choice. This section asks whether μ can be optimized alongside the baseline to minimize the variance. The standard policy-gradient estimator with a state-dependent baseline takes the form ∇J^b(π)=(r(s,a)−b(s))∇logπ(a∣s),s∼dπ,a∼π(⋅∣s), ∇ J_b(π)\;=\; (r(s,a)-b(s) )\,∇ π(a s), s d^π,\ a π(· s), (4) which is unbiased for ∇J(π)∇ J(π) for every state-dependent b. For trace-covariance minimization, however, the optimal baseline generally depends on the action-gradient norm. Writing g(s,a):=∇logπ(a∣s)g(s,a):=∇ π(a s) and H(s,a):=‖g(s,a)‖2H(s,a):=\|g(s,a)\|^2, the statewise optimum is bw∗(s)=[r(s,a)H(s,a)∣s][H(s,a)∣s].b_w^*(s)= E[r(s,a)H(s,a) s]E[H(s,a) s]. (5) It reduces to the conditional mean r¯(s):=[r(s,a)∣s] r(s):=E[r(s,a) s] under the within-state conditional-moment condition stated below. Crucially, unbiasedness of (4) does not require sampling from dπd^π. For any proposal μ with supp(μ)⊇supp(dπ)supp(μ) (d^π), the importance sampling estimator ∇J^b,μ(π)=dπ(s)μ(s)(r(s,a)−b(s))∇logπ(a∣s),s∼μ,a∼π(⋅∣s), ∇ J_b,μ(π)\;=\; d^π(s)μ(s) (r(s,a)-b(s) )\,∇ π(a s), s μ,\ a π(· s), (6) is unbiased for every admissible pair (b,μ)(b,μ). The on-policy choice μ=dπμ=d^π is the operational default in policy-gradient methods, but it is not, in general, the variance-minimizing choice. The reason is that states contribute different amounts of gradient signal per sample: a state whose continuations almost always succeed or fail yields little reward variation after baseline subtraction. A state whose continuations produce mixed outcomes yields per-sample signal proportional to that variation. Sampling states by visitation frequency alone does not reflect this difference. We therefore treat μ, alongside b, as a variable to be optimized. Minimizing the trace covariance of (6) jointly over (b,μ)(b,μ) admits a closed-form solution. Theorem 2.1 (Joint-optimal baseline and proposal; informal). Let H(s,a)=‖∇logπ(a∣s)‖2H(s,a)=\|∇ π(a s)\|^2 and let bw∗(s)b_w^*(s) be given by (5). The general joint minimizer of the trace covariance of (6) is μ⋆(s)∝dπ(s)Mw∗(s),Mw∗(s):=[(r(s,a)−bw∗(s))2H(s,a)∣s].μ (s)\; \;d^π(s) M_w^*(s), M_w^*(s):=E\! [(r(s,a)-b_w^*(s))^2H(s,a) s ]. (7) If [H∣s,r]=G(s)E[H s,r]=G(s) is independent of the realized reward within each state, then bw∗(s)=r¯(s)b_w^*(s)= r(s) and μ⋆(s)∝dπ(s)σπ(s)G(s).μ (s) d^π(s) _π(s) G(s). (8) Under the additional across-state homogeneity condition G(s)≡G0G(s)≡ G_0, this reduces to μ⋆(s)∝dπ(s)σπ(s)=:μvarπ(s),μ (s)\; \;d^π(s)\, _π(s)\;=:\;μ^π_var(s), (9) where σπ(s):=Vara∼π(⋅∣s)(r(s,a)) _π(s):= Var_a π(· s)(r(s,a)). On its effective support, the corresponding proposal-corrected estimator takes the standardized-residual form ∇J^⋆(π)∝r(s,a)−r¯(s)σπ(s)∇logπ(a∣s),s∼μvarπ,a∼π(⋅∣s). ∇ J^\, (π)\; \; r(s,a)- r(s) _π(s)\,∇ π(a s), s μ^π_var,\ a π(· s). (10) Specialization to the GRPO form. Under the two conditions above, the exact proposal-corrected estimator (10) has the same standardized reward-residual form as GRPO’s group-relative advantage (Shao et al., 2024). This connection concerns the form of the normalization: standard GRPO does not sample states from μvarπμ^π_var or apply the exact state-density ratio dπ/μd^π/μ. A formal statement, with an explicit expression for the variance gap, is given in Theorem B.5. Beyond the regularity assumption. The two conditions that yield μvarπ∝dπσπμ^π_var d^π _π are idealizations. In practice, action-gradient norms can depend on the realized reward within a state and their conditional scale can vary across states, so μvarπμ^π_var need not coincide with the exact joint optimum. We make this precise in Appendix B.4 (Assumption B.6 and Theorem B.7). That result is a proposal comparison under the stated regularity condition, not an unrestricted joint-optimality result. Analysis of an idealized theoretical algorithm. Separately from practical VSR, Appendix C analyzes an idealized smoothed state-reweighting algorithm under oracle-score, coverage, critic-realizability, and exact-weighting assumptions. Consider sampling critic data from a smoothed version of dπσπd^π _π at every iteration and updating the policy by KL-regularized mirror ascent. For any comparator policy μ covered by every iterate, the resulting theoretical algorithm satisfies J(μ)−J(π¯T)≤O~(KL(μ∥π1)T+H2εN),J(μ)-J( π_T)\;≤\; O\! ( KL(μ\,\|\, _1)T\;+\; H^2 N ), combining a 1/T1/ T optimization rate with a critic-estimation term inflated only by the smoothing factor 1/ε1/ . The full statement, assumptions, and proof are deferred to Appendix C. 2.3 Structure of the variance-optimal proposal μvarπ _var^π reweights the effective support of dπd^π. The unsmoothed proposal assigns zero mass to states with σπ(s)=0 _π(s)=0, i.e., states with no centered reward-variance signal, and therefore need not preserve the full support of dπd^π. When full support is required, one may use the smoothed proposal με=(1−ε)μvar+εdπ _ =(1- ) _var+ d^π, which retains an on-policy component while preserving the same variance-driven preference on the remaining mass. μvarπ _var^π trades off on-policy relevance and residual signal. The two factors capture distinct and complementary quantities: dπ(s)d^π(s) measures how relevant a state is to the current policy’s behavior, penalizing distributional shift away from on-policy sampling, while σπ(s) _π(s) measures how much per-sample gradient signal a state carries, penalizing states whose outcomes are already deterministic. Their product is the Neyman allocation that minimizes estimator variance—what is upweighted is the intersection of states that are both reachable under π and informative about π’s residual errors. Figure 2: An emergent curriculum from the variance-optimal proposal. μvarπ _var^π 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. μvarπ _var^π shifts with the policy, producing an emergent curriculum. Both factors depend on π: states that were once unreachable acquire visitation mass as π improves, and states that once produced mixed-outcome rollouts become near-deterministic and lose residual signal. The frontier of high μvarπ _var^π therefore re-localizes itself as training proceeds, without any externally imposed schedule. The dynamics above can be hard to visualize in settings where dπd^π and σπ _π are intractable, so we examine μvarπ _var^π in a setting where both can be computed exactly. A small MLP policy navigates a 7×77× 7 gridworld with obstacles from start S to goal G under terminal reward R∈0,1R∈\0,1\; the state space is small enough that dπt(s)d _t(s) and σπt(s) _ _t(s) can be enumerated, and μvarπt∝dπtσπtμ _t_var d _t _ _t sampled from without approximation. Figure 2 shows the three quantities and a learning-curve comparison across training. Early on, dπtd _t concentrates near S while σπt _ _t peaks in a band of states near G that the policy can occasionally reach; their product picks out the intersection. As training progresses, the high-σ band recedes from G toward S as goal-adjacent states become near-deterministic successes, and μt _t tracks it—until both factors collapse onto a small residual hard region near the start. We note that this curriculum is not designed; it is what minimizing estimator variance looks like when made visible. 3 VSR: A Practical Algorithm The previous section characterized the variance-optimal proposal μvarπ∝dπσπ _var^π d^π _π as a structural object. However, both dπd^π and σπ _π are intractable to compute exactly under realistic LLM rollout budgets, requiring cheap surrogates for implementation. We present Variance-driven State Resampling (VSR) in Algorithm 1, a plug-in modification of GRPO that approximates μvarπ _var^π via a prefix replay buffer and a zero-cost variance proxy. The resulting algorithm should be understood as an approximation to the allocation principle of μvarπ _var^π rather than as an unbiased estimator of the exact proposal-corrected gradient it induces. In particular, practical VSR does not estimate the density ratio dπ/μd^π/μ: it changes the reset-state distribution from which rollout groups are launched and then applies the usual GRPO-style loss. Because the replay buffer and priorities evolve with the policy and replay history, practical VSR is a biased adaptive reset-state procedure motivated by the variance-allocation geometry, not optimization of one fixed reweighted objective. Algorithm 1 VSR (Variance-driven State Resampling) 1: Initial policy π0 _0, prompt distribution D, group size G, recency window W, replay ratio ρ∈[0,1]ρ∈[0,1] 2: Optional: expert successful trajectories E for cold-start bootstrapping 3: Initialize replay buffer ℬ0←∅B_0← (or seed with prefix states from E if cold-starting) 4: for t=0,1,…,T−1t=0,1,…,T-1 do 5: Draw fresh prompts xj∼\x_j\ (fraction 1−ρ1-ρ) and replay prefixes sk∼ℬt\s_k\ _t with probability ∝σ^t(s) σ_t(s) (fraction ρ) 6: Generate G rollouts under πt _t from each xjx_j and each sks_k 7: Compute GRPO-style loss function ℒPG(πt)L_PG( _t) over the rollouts 8: Update πt+1←πt−η∇ℒPG(πt) _t+1← _t-η\, _PG( _t) 9: For each successful fresh trajectory τ generated from prompt xjx_j, insert every prefix state si=(xj,y<i)s_i=(x_j,y_<i) into ℬt+1B_t+1 with score σ^t+1(si)=p^i(1−p^i),p^i=(1−αi)p0(xj)+αiR(τ),αi=i/|τ| σ_t+1(s_i)= p_i(1- p_i), p_i=(1- _i)\,p_0(x_j)+ _i\,R(τ), _i=i/|τ| where p0(xj)p_0(x_j) is the empirical success rate of xjx_j’s fresh rollout group 10: Evict from ℬt+1B_t+1 all entries older than W steps 11: end for 3.1 From μvarπμ^π_var to a tractable surrogate 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. The two factors in μvarπμ^π_var are intractable in different ways. (i) σπ _π need to be approximated at zero rollout cost. Estimating σπ(s) _π(s) from conditional rollouts would reintroduce precisely the cost that state-level resampling is designed to amortize, so any usable proxy must be built from quantities already available in each GRPO step—the group success rate p0p_0 and terminal rewards R(τ)R(τ). (i) dπd^π is not directly tractable. We sidestep explicit density modeling via a recency-windowed prefix replay buffer ℬtB_t that collects states from recent rollouts, so that uniform draws from ℬtB_t approximate samples from dπtd _t; recency-based eviction keeps the buffer aligned with the current policy. Combining the two, we sample prefixes from ℬtB_t with probability proportional to σ^t(s) σ_t(s) and launch fresh rollout groups from each (Algorithm 1). The design follows directly from μvarπμ^π_var: stay close to on-policy visitation through ℬtB_t, and concentrate the sampling budget on states that still carry signal through σ^t σ_t. Both surrogates are deliberately cheap rather than accurate. 3.2 Online prefix proposal construction Recent prefix buffer. VSR maintains a recency-windowed replay buffer ℬtB_t of token-level prefix states extracted from recent rollout groups. For a trajectory τ=(s0,a0,…,sH)τ=(s_0,a_0,…,s_H), a replayable state has the form si=(x,y<i)s_i=(x,y_<i), i.e., the original prompt together with the generated prefix up to position i. In agentic settings, the same state representation is applied to the serialized interaction history, including prior actions, tool outputs, and environment observations (Figure 3). Sampling from ℬtB_t gives a density-free empirical approximation to the current state-visitation measure dπtd _t, while recency eviction keeps the proposal aligned with the evolving policy. In our implementation, ℬtB_t stores prefixes from successful trajectories only. This is a deliberate departure from the exact empirical visitation distribution. This filtering is not theoretically required by the variance-optimal proposal. In the hard-problem regime studied here, longer failed prefixes are empirically more likely to yield another all-fail continuation group (Appendix D.5); we therefore use successful-prefix filtering as a practical budget-allocation choice that favors states known to lie on at least one completable trajectory. Zero-cost variance score. Each buffered prefix is assigned a score intended to rank residual continuation uncertainty without additional conditional rollouts. For a prompt x, let p0(x)p_0(x) denote the empirical success rate of the rollout group generated from the original prompt, and let R(τ)∈0,1R(τ)∈\0,1\ denote the terminal reward of trajectory τ. For sis_i being the i-th state along a trajectory with length |τ||τ|, we define its normalized position as αi=i/|τ| _i=i/|τ| . VSR then estimates the continuation success probability at sis_i by interpolating between the group-level success rate at the initial state and the realized terminal outcome: p^t(si∣τ)=(1−αi)p0(x)+αiR(τ),σ^t(si∣τ)=p^t(si∣τ)(1−p^t(si∣τ)). p_t(s_i τ)=(1- _i)p_0(x)+ _iR(τ), σ_t(s_i τ)= p_t(s_i τ) (1- p_t(s_i τ) ). Early prefixes are therefore scored mostly by the prompt-level rollout statistics, while late prefixes are scored mostly by the observed outcome of the trajectory they belong to. Because the buffer stores only successful trajectories, R(τ)=1R(τ)=1 for every stored prefix, so the implemented score is determined by the prompt-level success rate and normalized prefix position. We therefore use σ^t σ_t only as a zero-additional-rollout uncertainty-ranking proxy, not as a calibrated, unbiased, or consistent estimator of σπt(s) _ _t(s). Appendix D.5 reports a statewise validation showing moderate positive association with empirical continuation uncertainty, including within fixed prefix positions. Replay update. At each update, VSR forms a mixed batch of fresh prompts and replayed prefixes. A replay ratio ρ∈[0,1]ρ∈[0,1] determines the fraction of batch elements drawn from ℬtB_t, with ρ=0ρ=0 recovering the base GRPO procedure. Replayed prefixes are sampled with probability proportional to σ^t σ_t. For each selected prefix, the current policy generates a fresh group of continuations; the prefix itself is treated as fixed context and masked out of the policy-gradient loss. The GRPO-style objective and group-relative advantage computation are otherwise unchanged. Cold start. When the base policy almost never reaches successful trajectories, the replay buffer may be initialized with prefixes from a small set of expert successful trajectories. These prefixes are used only as reset states for fresh rollouts under πt _t; their tokens are masked from the loss exactly like ordinary replayed prefixes. Recency eviction then gradually replaces seeded prefixes with states produced by the current policy, so the proposal transitions from expert-supported states to on-policy states as training progresses. Overall, the recent prefix buffer supplies the dπd^π factor by keeping replay states close to the current policy’s visitation distribution, while variance-weighted sampling supplies the σπ _π factor by concentrating rollout budget on uncertain states. Successful-prefix filtering and cold-start seeding bias the construction toward states that lie on completable trajectories, and recency eviction lets the resulting proposal move with the policy. The individual components are not independent replay heuristics, but practical approximations to the same variance-driven state allocation rule. 4 Experiments Our experiments target the regime where a variance-driven proposal is predicted to matter most: tasks on which the base policy almost always fails from the initial state, but where some mid-trajectory states admit continuations with genuinely mixed outcomes. In this regime, σπ _π is concentrated on intermediate states that on-policy rollouts rarely reach. We accordingly evaluate VSR in two settings where signals are rare: mathematical reasoning on a hard subset of OpenR1-Math-220k (filtered to prompts with low base-policy pass rate), and long-horizon agentic decision making on Sokoban and difficult BabyAI levels, where successful trajectories remain sparse under the base policies. 4.1 Mathematical reasoning Setup. We train Qwen2.5-7B-Instruct (Yang et al., 2024) and Llama-3.2-3B-Instruct (Meta, 2024) on a 1K hard subset of OpenR1-Math-220k (Hugging Face, 2025). The subset is constructed by filtering for prompts with low base-policy pass rate; for Qwen2.5-7B-Instruct, we retain prompts with at most 1 success out of 32 samples. VSR is initialized with replay prefixes extracted from successful DeepSeek-R1 trajectories (DeepSeek-AI et al., 2025). These expert-seeded prefixes are used only as starting states for fresh rollouts, with prefix tokens masked from the policy-gradient loss, and are gradually replaced by recent on-policy prefixes through the replay buffer. We compare VSR+GRPO against standard GRPO under the same training setup, and against SFT on the same expert trajectories used for cold-start initialization. We evaluate on AIME24 (MAA Committees, 2024), AIME25 (MAA Committees, 2025), AMC23, OlympiadBench (He et al., 2024), MATH500 (Hendrycks et al., 2021), and Minerva (Lewkowycz et al., 2022). Final benchmark accuracy is reported in Table 1, and training dynamics, including reward, validation performance, and response length, are shown in Figure 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. Model Method AIME24 AIME25 AMC23 Olympiad MATH500 Minerva Avg Qwen2.5-7B -Instruct Base model 10.010.0 7.97.9 53.253.2 39.239.2 75.675.6 37.337.3 37.237.2 GRPO 8.88.8 4.84.8 53.453.4 38.338.3 72.572.5 38.638.6 36.136.1 VSR+GRPO 11.411.4 10.410.4 57.757.7 33.533.5 73.773.7 38.738.7 37.637.6 Llama-3.2 -3B-Instruct Base model 5.35.3 0.60.6 21.821.8 12.612.6 40.040.0 13.813.8 15.715.7 SFT 0.30.3 0.40.4 7.27.2 5.05.0 23.123.1 5.45.4 6.96.9 GRPO 4.44.4 1.01.0 18.718.7 12.612.6 39.239.2 16.516.5 15.415.4 Reinforce-Ada 4.24.2 0.10.1 18.018.0 12.412.4 39.939.9 15.415.4 15.015.0 Uniform expert-prefix 5.65.6 0.50.5 22.722.7 14.114.1 43.743.7 15.815.8 17.117.1 VSR+GRPO 6.26.2 0.60.6 20.420.4 15.315.3 54.054.0 17.817.8 19.119.1 Additional controls. We include two additional single-run controls for the Llama-3.2-3B math setting. Static uniform expert-prefix resets use the same successful expert-trajectory source as VSR but sample uniformly from a fixed expert-prefix pool, probing how much of the gain comes from privileged reset states alone. Reinforce-Ada-Est(Xiong et al., 2025) reallocates a matched response budget across the original prompts without intermediate-state resets, testing whether prompt-level adaptive allocation alone reproduces the VSR gain. As shown in Table 1, static expert-prefix resets improve the average score from 15.4 for GRPO to 17.1, while Reinforce-Ada-Est obtains 15.0 and VSR reaches 19.1. Thus privileged resets explain part of the improvement, whereas prompt-level allocation alone does not reproduce the full VSR result. Detailed setups and limitations are provided in Appendix D.5. 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. 4.2 Long-horizon agentic tasks Setup. We implement VSR on Sokoban(Schrader, 2018) and BabyAI(Chevalier-Boisvert et al., 2018) using Qwen2.5-1.5B-Instruct and Qwen2.5-3B-Instruct(Yang et al., 2024). For BabyAI, we use SynthLoc, OneRoom, and MiniBoss, which require multi-step planning and compositional decision making. We choose GiGPO (Feng et al., 2025a) as our base RL algorithm, and VSR is added as a plug-in state-resampling component. Unlike the math setting, the replay buffer is populated entirely from the model’s own trajectories, without expert cold-start initialization. We compare GiGPO+VSR against GiGPO under matched model, environment, and training settings. Final task success rates are reported in Table 2, and training dynamics, including reward, validation success, and newly generated continuation length after the selected reset state, are shown in Figure 5. The main training curves and most entries in Table 2 are from single training runs; evaluation success rates use 128 fixed map seeds per environment, while independent-training-run uncertainty is reported separately for the scoring ablation below. Table 2: Agentic-task success rates (%) on Sokoban and BabyAI. Best result is in bold. Sokoban BabyAI Model Method SynthLoc OneRoom MiniBoss Avg Qwen2.5-1.5B-Instruct Base model 9.49.4 11.611.6 9.39.3 21.421.4 14.114.1 GiGPO 12.712.7 32.332.3 27.927.9 30.930.9 30.430.4 VSR+GiGPO 18.818.8 51.251.2 54.654.6 36.936.9 47.647.6 Qwen2.5-3B-Instruct Base model 17.217.2 9.39.3 18.618.6 16.716.7 14.914.9 GiGPO 21.521.5 51.251.2 46.546.5 30.930.9 42.942.9 VSR+GiGPO 25.925.9 53.553.5 60.460.4 33.333.3 49.149.1 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. 4.3 Ablations We isolate the two engineering components of VSR through controlled variants, both built on top of GiGPO and evaluated on BabyAI under the same setup as Section 4.2. (i) Uniform vs. variance-weighted sampling over the replay buffer. VSR(w/o scoring) retains the recency-updated replay buffer but samples prefixes uniformly rather than in proportion to σ^t σ_t. This isolates the contribution of the variance-driven weighting from that of prefix replay itself. (i) Static vs. policy-tracking replay buffer. VSR(w/o recency) retains σ^t σ_t-weighted sampling but disables the recency-based buffer update, so the buffer is populated once at the start of training and held fixed thereafter. This isolates the contribution of tracking dπtd _t from that of variance-driven weighting. We additionally repeat the Qwen2.5-1.5B VSR-versus-uniform-replay scoring comparison across three independent training runs per variant. VSR reaches 48.2±2.448.2± 2.4 versus 44.0±4.344.0± 4.3 for uniform replay (mean ± SD), providing additional evidence for the benefit of variance-driven prioritization; full per-run results are reported in Appendix D.5. The original no-recency curve remains a single run. Figure 6: Ablation on BabyAI: validation success rate over training. Method Avg GiGPO 30.430.4 VSR(w/o scoring) 46.146.1 VSR(w/o recency) 36.736.7 VSR 47.647.6 Table 3: Ablation on BabyAI (avg success rate, %). Best in bold. 4.4 Discussion VSR yields stronger per-batch training signal. The training-reward curves in Figures 4 and 5 indicate that VSR yields a higher per-batch gradient signal: VSR consistently gains more training reward over the whole training. On the hard math subset, GRPO’s training reward continues to climb while its validation accuracy stays essentially flat, and final benchmark performance ends up below the base model on both models. The reason is that training signal is concentrated on a narrow handful of prompts that occasionally produce mixed-outcome groups, and on-policy sampling repeatedly draws gradient signal from that same small set. VSR addresses this at the level predicted by μvarπμ^π_var: even when the prompt-level support of σπ _π is narrow, its state-level support is much wider. VSR reduces the rollout cost of each policy update. Because a non-trivial fraction of rollouts are initiated from mid-trajectory prefixes rather than from the original prompt, the expected number of newly generated tokens per trajectory is reduced; this is reflected in the consistently shorter newly generated continuation lengths in the agentic experiments and the analogous reduction in completion length observed in the mathematical reasoning experiments. Direct token accounting further supports this effect: at matched update counts, VSR+GiGPO generates 39.27M versus 81.30M tokens for Qwen2.5-1.5B and 34.43M versus 36.26M for Qwen2.5-3B; full accounting is reported in Appendix D.5. Variance-driven scoring improves training efficiency over uniform replay. The comparison between VSR and VSR(w/o scoring) in Figure 6 indicates that weighting buffered prefixes by σ^t σ_t yields higher validation performance on average over uniform sampling from the same buffer, particularly in the later phase of training. Across three independent training runs, VSR achieves 48.2±2.448.2± 2.4 versus 44.0±4.344.0± 4.3 for uniform replay (mean ± SD), further supporting the benefit of variance-driven prioritization; see Appendix D.5 for the individual runs. This indicates that the variance-driven weighting is not redundant with the replay mechanism itself: prioritizing prefixes with larger residual outcome variance translates into a more efficient use of the resampling budget. Recency-based buffer updates are necessary to sustain learning. VSR(w/o recency) outperforms full VSR initially but plateaus thereafter. Without ongoing updates, the buffer’s empirical state distribution drifts away from dπtd _t as the policy evolves, and the policy is optimized against a proposal that no longer reflects its current visitation. The dπd^π factor in μvarπ _var^π is precisely what guards against this distributional shift, consistent with the prediction in Section 2.3 that the variance-optimal proposal re-localizes with π. 5 Conclusion We recast the signal-sparsity problem in RL with verifiable rewards as a variance-reduction problem over the state sampling distribution, and showed that the general trace-variance optimum depends on the action-gradient norm; under the stated within-state and across-state homogeneity conditions it reduces to the clean Neyman form μvarπ∝dπ(s)σπ(s)μ^π_var d^π(s) _π(s), whose proposal-corrected estimator has the same standardized-residual form as GRPO’s group-relative normalization. Building on this allocation principle, we proposed VSR, a practical prefix-replay method that improves over the compared GRPO/GiGPO baselines on most evaluated settings. A main limitation is the gap between the exact proposal-corrected estimator and practical VSR. VSR does not estimate the exact density ratio, stores only successful prefixes, uses expert-prefix cold start in the math experiments, and relies on a coarse zero-additional-rollout uncertainty score. The additional controls and validations in Appendix D.5 clarify these effects but do not completely isolate every practical component; most main agentic results and the no-recency ablation also remain single-run. Tighter low-cost state scores and broader multi-seed evaluation remain important directions. References Andrychowicz et al. [2017] Marcin Andrychowicz, Filip Wolski, Alex Ray, Jonas Schneider, Rachel Fong, Peter Welinder, Bob McGrew, Josh Tobin, OpenAI Pieter Abbeel, and Wojciech Zaremba. Hindsight experience replay. Advances in neural information processing systems, 30, 2017. Bengio et al. [2009] Yoshua Bengio, Jérôme Louradour, Ronan Collobert, and Jason Weston. Curriculum learning. In Proceedings of the 26th annual international conference on machine learning, pages 41–48, 2009. Chen et al. [2025] Lili Chen, Mihir Prabhudesai, Katerina Fragkiadaki, Hao Liu, and Deepak Pathak. Self-questioning language models. arXiv preprint arXiv:2508.03682, 2025. Chevalier-Boisvert et al. [2018] Maxime Chevalier-Boisvert, Dzmitry Bahdanau, Salem Lahlou, Lucas Willems, Chitwan Saharia, Thien Huu Nguyen, and Yoshua Bengio. Babyai: A platform to study the sample efficiency of grounded language learning. arXiv preprint arXiv:1810.08272, 2018. Cui et al. [2025] Ganqu Cui, Lifan Yuan, Zefan Wang, Hanbin Wang, Yuchen Zhang, Jiacheng Chen, Wendi Li, Bingxiang He, Yuchen Fan, Tianyu Yu, et al. Process reinforcement through implicit rewards. arXiv preprint arXiv:2502.01456, 2025. DeepSeek-AI et al. [2025] DeepSeek-AI, Daya Guo, Dejian Yang, Haowei Zhang, Junxiao Song, Ruoyu Zhang, Runxin Xu, Qihao Zhu, Shirong Ma, Peiyi Wang, Xiao Bi, Xiaokang Zhang, Xingkai Yu, Yu Wu, Z. F. Wu, Zhibin Gou, Zhihong Shao, Zhuoshu Li, Ziyi Gao, Aixin Liu, Bing Xue, Bingxuan Wang, Bochao Wu, Bei Feng, Chengda Lu, Chenggang Zhao, Chengqi Deng, Chenyu Zhang, Chong Ruan, Damai Dai, Deli Chen, Dongjie Ji, Erhang Li, Fangyun Lin, Fucong Dai, Fuli Luo, Guangbo Hao, Guanting Chen, Guowei Li, H. Zhang, Han Bao, Hanwei Xu, Haocheng Wang, Honghui Ding, Huajian Xin, Huazuo Gao, Hui Qu, Hui Li, Jianzhong Guo, Jiashi Li, Jiawei Wang, Jingchang Chen, Jingyang Yuan, Junjie Qiu, Junlong Li, J. L. Cai, Jiaqi Ni, Jian Liang, Jin Chen, Kai Dong, Kai Hu, Kaige Gao, Kang Guan, Kexin Huang, Kuai Yu, Lean Wang, Lecong Zhang, Liang Zhao, Litong Wang, Liyue Zhang, Lei Xu, Leyi Xia, Mingchuan Zhang, Minghua Zhang, Minghui Tang, Meng Li, Miaojun Wang, Mingming Li, Ning Tian, Panpan Huang, Peng Zhang, Qiancheng Wang, Qinyu Chen, Qiushi Du, Ruiqi Ge, Ruisong Zhang, Ruizhe Pan, Runji Wang, R. J. Chen, R. L. Jin, Ruyi Chen, Shanghao Lu, Shangyan Zhou, Shanhuang Chen, Shengfeng Ye, Shiyu Wang, Shuiping Yu, Shunfeng Zhou, Shuting Pan, S. S. Li, Shuang Zhou, Shaoqing Wu, Shengfeng Ye, Tao Yun, Tian Pei, Tianyu Sun, T. Wang, Wangding Zeng, Wanjia Zhao, Wen Liu, Wenfeng Liang, Wenjun Gao, Wenqin Yu, Wentao Zhang, W. L. Xiao, Wei An, Xiaodong Liu, Xiaohan Wang, Xiaokang Chen, Xiaotao Nie, Xin Cheng, Xin Liu, Xin Xie, Xingchao Liu, Xinyu Yang, Xinyuan Li, Xuecheng Su, Xuheng Lin, X. Q. Li, Xiangyue Jin, Xiaojin Shen, Xiaosha Chen, Xiaowen Sun, Xiaoxiang Wang, Xinnan Song, Xinyi Zhou, Xianzu Wang, Xinxia Shan, Y. K. Li, Y. Q. Wang, Y. X. Wei, Yang Zhang, Yanhong Xu, Yao Li, Yao Zhao, Yaofeng Sun, Yaohui Wang, Yi Yu, Yichao Zhang, Yifan Shi, Yiliang Xiong, Ying He, Yishi Piao, Yisong Wang, Yixuan Tan, Yiyang Ma, Yiyuan Liu, Yongqiang Guo, Yuan Ou, Yuduan Wang, Yue Gong, Yuheng Zou, Yujia He, Yunfan Xiong, Yuxiang Luo, Yuxiang You, Yuxuan Liu, Yuyang Zhou, Y. X. Zhu, Yanhong Xu, Yanping Huang, Yaohui Li, Yi Zheng, Yuchen Zhu, Yunxian Ma, Ying Tang, Yukun Zha, Yuting Yan, Z. Z. Ren, Zehui Ren, Zhangli Sha, Zhe Fu, Zhean Xu, Zhenda Xie, Zhengyan Zhang, Zhewen Hao, Zhicheng Ma, Zhigang Yan, Zhiyu Wu, Zihui Gu, Zijia Zhu, Zijun Liu, Zilin Li, Ziwei Xie, Ziyang Song, Zizheng Pan, Zhen Huang, Zhipeng Xu, Zhongyu Zhang, and Zhen Zhang. Deepseek-r1: Incentivizing reasoning capability in llms via reinforcement learning, 2025. URL https://arxiv.org/abs/2501.12948. Ecoffet et al. [2019] Adrien Ecoffet, Joost Huizinga, Joel Lehman, Kenneth O Stanley, and Jeff Clune. Go-explore: a new approach for hard-exploration problems. arXiv preprint arXiv:1901.10995, 2019. Feng et al. [2025a] Lang Feng, Zhenghai Xue, Tingcong Liu, and Bo An. Group-in-group policy optimization for llm agent training. arXiv preprint arXiv:2505.10978, 2025a. Feng et al. [2025b] Yunzhen Feng, Ariel Kwiatkowski, Kunhao Zheng, Julia Kempe, and Yaqi Duan. Pilaf: Optimal human preference sampling for reward modeling. arXiv preprint arXiv:2502.04270, 2025b. Florensa et al. [2017] Carlos Florensa, David Held, Markus Wulfmeier, Michael Zhang, and Pieter Abbeel. Reverse curriculum generation for reinforcement learning. In Conference on robot learning, pages 482–495. PMLR, 2017. Gao et al. [2025] Zhaolin Gao, Joongwon Kim, Wen Sun, Thorsten Joachims, Sid Wang, Richard Yuanzhe Pang, and Liang Tan. Prompt curriculum learning for efficient llm post-training. arXiv preprint arXiv:2510.01135, 2025. Greensmith et al. [2004] Evan Greensmith, Peter L Bartlett, and Jonathan Baxter. Variance reduction techniques for gradient estimates in reinforcement learning. Journal of Machine Learning Research, 5(Nov):1471–1530, 2004. Gulcehre et al. [2023] Caglar Gulcehre, Tom Le Paine, Srivatsan Srinivasan, Ksenia Konyushkova, Lotte Weerts, Abhishek Sharma, Aditya Siddhant, Alex Ahern, Miaosen Wang, Chenjie Gu, et al. Reinforced self-training (rest) for language modeling. arXiv preprint arXiv:2308.08998, 2023. Haluptzok et al. [2022] Patrick Haluptzok, Matthew Bowers, and Adam Tauman Kalai. Language models can teach themselves to program better. arXiv preprint arXiv:2207.14502, 2022. He et al. [2024] Chaoqun He, Renjie Luo, Yuzhuo Bai, Shengding Hu, Zhen Leng Thai, Junhao Shen, Jinyi Hu, Xu Han, Yujie Huang, Yuxiang Zhang, et al. Olympiadbench: A challenging benchmark for promoting agi with olympiad-level bilingual multimodal scientific problems. arXiv preprint arXiv:2402.14008, 2024. Hendrycks et al. [2021] 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. arXiv preprint arXiv:2103.03874, 2021. Huang et al. [2025] Chengsong Huang, Wenhao Yu, Xiaoyang Wang, Hongming Zhang, Zongxia Li, Ruosen Li, Jiaxin Huang, Haitao Mi, and Dong Yu. R-zero: Self-evolving reasoning llm from zero data. arXiv preprint arXiv:2508.05004, 2025. Hugging Face [2025] Hugging Face. Open r1: A fully open reproduction of deepseek-r1, January 2025. URL https://github.com/huggingface/open-r1. Lewkowycz et al. [2022] Aitor Lewkowycz, Anders Andreassen, David Dohan, Ethan Dyer, Henryk Michalewski, Vinay Ramasesh, Ambrose Slone, Cem Anil, Imanol Schlag, Theo Gutman-Solo, et al. Solving quantitative reasoning problems with language models. Advances in neural information processing systems, 35:3843–3857, 2022. Liao et al. [2026] Baohao Liao, Hanze Dong, Xinxing Xu, Christof Monz, and Jiang Bian. Self-hinting language models enhance reinforcement learning. arXiv preprint arXiv:2602.03143, 2026. Liu et al. [2025] Bo Liu, Leon Guertler, Simon Yu, Zichen Liu, Penghui Qi, Daniel Balcells, Mickel Liu, Cheston Tan, Weiyan Shi, Min Lin, et al. Spiral: Self-play on zero-sum games incentivizes reasoning via multi-agent multi-turn reinforcement learning. arXiv preprint arXiv:2506.24119, 2025. Lu et al. [2025] Hongliang Lu, Yuhang Wen, Pengyu Cheng, Ruijin Ding, Jiaqi Guo, Haotian Xu, Chutian Wang, Haonan Chen, Xiaoxi Jiang, and Guanjun Jiang. Search self-play: Pushing the frontier of agent capability without supervision. arXiv preprint arXiv:2510.18821, 2025. MAA Committees [2024] MAA Committees. AIME Problems and Solutions. https://artofproblemsolving.com/wiki/index.php/AIME_Problems_and_Solutions, 2024. MAA Committees [2025] MAA Committees. AIME Problems and Solutions. https://artofproblemsolving.com/wiki/index.php/AIME_Problems_and_Solutions, 2025. Meta [2024] AI Meta. Introducing meta llama 3: The most capable openly available llm to date. Meta AI, 2(5):6, 2024. Portelas et al. [2020] Rémy Portelas, Cédric Colas, Lilian Weng, Katja Hofmann, and Pierre-Yves Oudeyer. Automatic curriculum learning for deep rl: A short survey. arXiv preprint arXiv:2003.04664, 2020. Qu et al. [2026] Yuxiao Qu, Amrith Setlur, Virginia Smith, Ruslan Salakhutdinov, and Aviral Kumar. Pope: Learning to reason on hard problems via privileged on-policy exploration. arXiv preprint arXiv:2601.18779, 2026. Schrader [2018] Max-Philipp B. Schrader. gym-sokoban, January 2018. URL https://github.com/mpschrader/gym-sokoban. Setlur et al. [2025] Amrith Setlur, Matthew YR Yang, Charlie Snell, Jeremy Greer, Ian Wu, Virginia Smith, Max Simchowitz, and Aviral Kumar. e3: Learning to explore enables extrapolation of test-time compute for llms. arXiv preprint arXiv:2506.09026, 2025. Shao et al. [2024] Zhihong Shao, Peiyi Wang, Qihao Zhu, Runxin Xu, Junxiao Song, Mingchuan Zhang, YK Li, Y Wu, and Daya Guo. Deepseekmath: Pushing the limits of mathematical reasoning in open language models. arXiv preprint arXiv:2402.03300, 2024. Shi et al. [2024] Ruizhe Shi, Runlong Zhou, and Simon S Du. The crucial role of samplers in online direct preference optimization. arXiv preprint arXiv:2409.19605, 2024. Shi et al. [2025] Taiwei Shi, Yiyang Wu, Linxin Song, Tianyi Zhou, and Jieyu Zhao. Efficient reinforcement finetuning via adaptive curriculum learning. arXiv preprint arXiv:2504.05520, 2025. Simonds and Yoshiyama [2025] Toby Simonds and Akira Yoshiyama. Ladder: Self-improving llms through recursive problem decomposition. arXiv preprint arXiv:2503.00735, 2025. Team et al. [2025] Kimi Team, Angang Du, Bofei Gao, Bowei Xing, Changjiu Jiang, Cheng Chen, Cheng Li, Chenjun Xiao, Chenzhuang Du, Chonghua Liao, et al. Kimi k1. 5: Scaling reinforcement learning with llms. arXiv preprint arXiv:2501.12599, 2025. Wang et al. [2026] Yinjie Wang, Tianbao Xie, Ke Shen, Mengdi Wang, and Ling Yang. Rlanything: Forge environment, policy, and reward model in completely dynamic rl system. arXiv preprint arXiv:2602.02488, 2026. Wang et al. [2025] Zihan Wang, Kangrui Wang, Qineng Wang, Pingyue Zhang, Linjie Li, Zhengyuan Yang, Xing Jin, Kefan Yu, Minh Nhat Nguyen, Licheng Liu, et al. Ragen: Understanding self-evolution in llm agents via multi-turn reinforcement learning. arXiv preprint arXiv:2504.20073, 2025. Wilf et al. [2025] Alex Wilf, Pranjal Aggarwal, Bryan Parno, Daniel Fried, Louis-Philippe Morency, Paul Pu Liang, and Sean Welleck. Propose, solve, verify: Self-play through formal verification. arXiv preprint arXiv:2512.18160, 2025. Xi et al. [2024] Zhiheng Xi, Wenxiang Chen, Boyang Hong, Senjie Jin, Rui Zheng, Wei He, Yiwen Ding, Shichun Liu, Xin Guo, Junzhe Wang, et al. Training large language models for reasoning through reverse curriculum reinforcement learning. arXiv preprint arXiv:2402.05808, 2024. Xiong et al. [2025] Wei Xiong, Chenlu Ye, Baohao Liao, Hanze Dong, Xinxing Xu, Christof Monz, Jiang Bian, Nan Jiang, and Tong Zhang. Reinforce-ada: An adaptive sampling framework under non-linear rl objectives. arXiv preprint arXiv:2510.04996, 2025. Yang et al. [2024] An Yang, Baosong Yang, Beichen Zhang, Binyuan Hui, Bo Zheng, Bowen Yu, Chengyuan Li, Dayiheng Liu, Fei Huang, Haoran Wei, et al. Qwen2. 5 technical report. arXiv preprint arXiv:2412.15115, 2024. Yao et al. [2025] Jiarui Yao, Yifan Hao, Hanning Zhang, Hanze Dong, Wei Xiong, Nan Jiang, and Tong Zhang. Optimizing chain-of-thought reasoners via gradient variance minimization in rejection sampling and rl. arXiv preprint arXiv:2505.02391, 2025. Yi et al. [2026] Junkeun Yi, Damon Mosk-Aoyama, Baihe Huang, Ritu Gala, Charles Wang, Sugam Dipak Devare, Khushi Bhardwaj, Abhibha Gupta, Oleksii Kuchaiev, Jiantao Jiao, et al. Pivotrl: High accuracy agentic post-training at low compute cost. arXiv preprint arXiv:2603.21383, 2026. Yu et al. [2025] Qiying Yu, Zheng Zhang, Ruofei Zhu, Yufeng Yuan, Xiaochen Zuo, Yu Yue, Weinan Dai, Tiantian Fan, Gaohong Liu, Lingjun Liu, et al. Dapo: An open-source llm reinforcement learning system at scale. arXiv preprint arXiv:2503.14476, 2025. Zeng et al. [2025] Zhiyuan Zeng, Hamish Ivison, Yiping Wang, Lifan Yuan, Shuyue Stella Li, Zhuorui Ye, Siting Li, Jacqueline He, Runlong Zhou, Tong Chen, et al. Rlve: Scaling up reinforcement learning for language models with adaptive verifiable environments. arXiv preprint arXiv:2511.07317, 2025. Zhang et al. [2025] Xuechen Zhang, Zijian Huang, Yingcong Li, Chenshun Ni, Jiasi Chen, and Samet Oymak. Bread: Branched rollouts from expert anchors bridge sft & rl for reasoning. arXiv preprint arXiv:2506.17211, 2025. Zhao et al. [2025] Andrew Zhao, Yiran Wu, Yang Yue, Tong Wu, Quentin Xu, Matthieu Lin, Shenzhi Wang, Qingyun Wu, Zilong Zheng, and Gao Huang. Absolute zero: Reinforced self-play reasoning with zero data. arXiv preprint arXiv:2505.03335, 2025. Zhao et al. [2024] Zirui Zhao, Hanze Dong, Amrita Saha, Caiming Xiong, and Doyen Sahoo. Automatic curriculum expert iteration for reliable llm reasoning. arXiv preprint arXiv:2410.07627, 2024. Appendix A Related Work A broad line of recent work on sparse-reward RL for LLMs aims, at varying levels of explicitness, to address the same underlying difficulty: when terminal reward is binary and success is rare, naively sampling rollouts under the current policy yields many uninformative updates. We organize the discussion around what each line of work effectively reshapes—the prompt distribution, the within-trajectory state at which generation is conditioned, the task itself, or the per-prompt sampling budget. Selecting and scheduling existing prompts. A first family of methods operates at the prompt level. Filtering and dynamic sampling discard prompts whose rollout groups produce uniform reward, on the grounds that they contribute no group-relative signal [Yu et al., 2025, Cui et al., 2025, Wang et al., 2025, Gulcehre et al., 2023]. Curriculum-style schedulers go further and order prompts by difficulty or learnability, ranging from classical curriculum learning [Bengio et al., 2009, Portelas et al., 2020] to recent LLM-specific instantiations that adapt the prompt distribution online [Zhao et al., 2024, Shi et al., 2025, Gao et al., 2025, Team et al., 2025, Setlur et al., 2025]. RLVE [Zeng et al., 2025] makes the environment itself adaptive, generating verifiable problem instances calibrated to the current learner. A separate but related line studies the role of the sampler in preference-based post-training, where sampling distribution similarly affects gradient signal [Shi et al., 2024, Feng et al., 2025b]. The granularity of intervention in this family is the prompt: once a prompt is selected, the distribution of intermediate states encountered along its rollouts is left entirely to the current policy. Conditioning on intermediate states within a trajectory. A second family conditions generation on intermediate states rather than only on prompts. Prefix-conditioned RL methods inject partial trajectories—either expert-derived or drawn from earlier policy iterates—as starting points for fresh rollouts [Zhang et al., 2025, Qu et al., 2026, Yi et al., 2026], extending an older RL tradition of reverse curricula style state resets [Andrychowicz et al., 2017, Florensa et al., 2017, Ecoffet et al., 2019, Xi et al., 2024] . Hint injection during rollout [Liao et al., 2026] and recursive problem decomposition [Simonds and Yoshiyama, 2025] can be viewed as variants of the same idea, supplying privileged context that places the policy at a more learnable state before continuation. ReST [Gulcehre et al., 2023] is a closer precedent on the replay side, iteratively training on successful trajectories, though as an offline SFT-then-RL procedure rather than as an online state-resampling mechanism. The criterion by which intermediate states are selected varies across these methods—difficulty, expert provenance, or a hand-designed schedule. Generating new tasks: self-play schemes. A third family sidesteps the question of which existing state to train on by generating new tasks calibrated to the learner. Self-play and proposer–solver frameworks have the model—or a paired proposer model—propose problems that are subsequently solved and verified, with the proposal policy itself trained to produce informative tasks [Haluptzok et al., 2022, Zhao et al., 2025, Huang et al., 2025, Chen et al., 2025, Lu et al., 2025, Liu et al., 2025, Wilf et al., 2025, Wang et al., 2026] . The motivation of self-play schemes overlaps with curriculum learning and prefix conditioning, putting training mass on states from which learning signal is accessible Variance-driven sampling budget reallocation. Closest in motivation are methods that explicitly target estimator variance. While a classical thread on variance reduction in policy-gradient estimators more broadly [Greensmith et al., 2004] focuses on baseline design rather than proposal design, some recent researches focus on prompt sampling. Reinforce-Ada [Xiong et al., 2025] adaptively allocates rollouts across prompts under non-linear RL objectives, and Yao et al. [2025] minimizes gradient variance through rejection sampling and rollout reallocation in chain-of-thought RL. Both are concerned with the same underlying inefficiency—sampling budget spent on prompts that yield no usable signal—and both reallocate rollouts across prompts, holding the per-prompt distribution of intermediate states fixed. Appendix B Theoretical analysis of the variance-driven proposal This appendix collects the full theoretical analysis underlying the variance-driven proposal μvar∝dπ(s)σπ(s) _var d^π(s) _π(s) introduced in Section 2.2. Section B.1 establishes notation and the working form of the estimator variance. Section B.2 derives the exact variance-optimal proposal. Section B.3 specializes it to the standard gradient-uniformity convention, recovering μvar _var and the GRPO-style estimator. Section B.4 relaxes that convention and gives a quantitative condition—weaker than gradient uniformity—under which μvar _var still strictly reduces variance relative to on-policy sampling. B.1 Setup Throughout, we use the state-action view of LLM RL described in Section 2.1: st=(x,y<t)s_t=(x,y_<t), at=yta_t=y_t, s0=x∼s_0=x , with terminal verifiable reward R∈0,1R∈\0,1\. The state-visitation distribution is dπ(s)∝∑t=0T−1Pr[st=s|s0∼,π].d^π(s)\; \; _t=0^T-1 \! [s_t=s\, |\,s_0 ,\,π ]. For a state-dependent baseline b and a proposal μ with supp(μ)⊇supp(dπ)supp(μ) (d^π), the proposal-corrected policy-gradient estimator is ∇J^b,μ=dπ(s)μ(s)(r(s,a)−b(s))∇logπ(a∣s),s∼μ,a∼π(⋅∣s), ∇ J_b,μ\;=\; d^π(s)μ(s) (r(s,a)-b(s) )∇ π(a s), s μ,\ a π(· s), (11) which is unbiased for ∇J(π)∇ J(π) for every admissible pair (b,μ)(b,μ). We write g(s,a):=∇logπ(a∣s)g(s,a):=∇ π(a s), δ(s,a):=r(s,a)−b(s)δ(s,a):=r(s,a)-b(s), r¯(s):=a∼π(⋅∣s)[r(s,a)] r(s):=E_a π(· s)[r(s,a)], and use σπ(s) _π(s) for the within-state reward standard deviation, σπ(s)2:=Vara∼π(⋅∣s)(r(s,a)) _π(s)^2:=Var_a π(· s)\! (r(s,a) ). For a fixed baseline b, define the gradient-signal second moment Mb(s):=a∼π(⋅∣s)[(r(s,a)−b(s))2H(s,a)],H(s,a):=∥g(s,a)∥2.M_b(s)\;:=\;E_a π(· s)\! [(r(s,a)-b(s))^2\,H(s,a) ], H(s,a):=\|g(s,a)\|^2. (12) Lemma B.1 (Working form of the variance). For any admissible (b,μ)(b,μ), V(μ,b):=trCov(∇J^b,μ)=s∼dπ[dπ(s)μ(s)Mb(s)]−‖∇J(π)‖2.V(μ;b)\;:=\;tr\,Cov\! ( ∇ J_b,μ )\;=\;E_s d^π\! [ d^π(s)μ(s)\,M_b(s) ]\;-\;\|∇ J(π)\|^2. (13) Proof. By unbiasedness, trCov(∇J^b,μ)=‖∇J^b,μ‖2−‖∇J(π)‖2tr\,Cov( ∇ J_b,μ)=E\,\| ∇ J_b,μ\|^2-\|∇ J(π)\|^2. Expanding s∼μs μ gives ‖∇J^b,μ‖2=dπ[dπ(s)μ(s)Mb(s)].∎E\,\| ∇ J_b,μ\|^2=E_d^π\! [ d^π(s)μ(s)M_b(s) ]. B.2 The exact joint optimum Theorem B.2 (Exact joint-optimal baseline and proposal). For each state, the trace-variance-minimizing baseline is bw∗(s)=[r(s,a)H(s,a)∣s][H(s,a)∣s].b_w^*(s)= E[r(s,a)H(s,a) s]E[H(s,a) s]. (14) Defining Mw∗(s):=[(r(s,a)−bw∗(s))2H(s,a)∣s],M_w^*(s):=E[(r(s,a)-b_w^*(s))^2H(s,a) s], (15) the joint-optimal proposal on the effective support is μπ,⋆(s)∝dπ(s)Mw∗(s).μ^π, (s) d^π(s) M_w^*(s). (16) If full support is required, the proposal can be smoothed by mixing with dπd^π. Proof. For fixed μ, the statewise factor multiplying Mb(s)M_b(s) in (13) is positive, so minimizing over b(s)b(s) is equivalent to minimizing [(r−b)2H∣s]E[(r-b)^2H s]. Differentiating in b gives (14). Substituting bw∗b_w^* into (13), Cauchy–Schwarz yields the minimizing proposal μ(s)∝dπ(s)Mw∗(s)μ(s) d^π(s) M_w^*(s) exactly as in the standard Neyman-allocation argument. ∎ B.3 Clean case: conditions yielding dπσπd^π _π The exact joint optimum couples reward variability and action-gradient norms. The following two conditions separate these quantities. Assumption B.3 (Within-state conditional-moment condition). For each state s, there exists G(s)>0G(s)>0 such that [H(s,a)∣s,r]=G(s).E[H(s,a) s,r]=G(s). (17) That is, conditional on the state, the expected squared score-function norm does not depend on the realized reward. Under Assumption B.3, bw∗(s)=r¯(s)b_w^*(s)= r(s) and Mw∗(s)=G(s)σπ(s)2,μπ,⋆(s)∝dπ(s)σπ(s)G(s).M_w^*(s)=G(s) _π(s)^2, μ^π, (s) d^π(s) _π(s) G(s). (18) Assumption B.4 (Across-state gradient-scale homogeneity). G(s)≡G0G(s)≡ G_0 on the effective support. Theorem B.5 (Clean Neyman form). Under Assumptions B.3 and B.4, the joint-optimal proposal on the effective support reduces to μπ,⋆(s)∝dπ(s)σπ(s)=:μvar(s),μ^π, (s)\; \;d^π(s)\, _π(s)\;=:\; _var(s), (19) and the exact proposal-corrected estimator is proportional to r(s,a)−r¯(s)σπ(s)∇logπ(a∣s),s∼μvar,a∼π(⋅∣s). r(s,a)- r(s) _π(s)∇ π(a s), s _var,\ a π(· s). (20) Moreover, V(dπ,r¯)−V(μvar,r¯)=G0Vars∼dπ(σπ(s))≥0,V(d^π; r)-V( _var; r)=G_0\,Var_s d^π( _π(s))≥ 0, (21) with strict inequality whenever σπ _π is non-constant on the effective support. Proof. Assumption B.3 gives bw∗=r¯b_w^*= r and Mw∗=G(s)σπ2(s)M_w^*=G(s) _π^2(s). Assumption B.4 then gives Mw∗=G0σπ2M_w^*=G_0 _π^2, so (16) reduces to (19); substituting in the proposal-corrected estimator yields (20). The variance-gap expression follows from the same Jensen calculation as in the original clean-case derivation. ∎ B.4 Weak version: variance reduction beyond gradient uniformity The clean conditions above are idealizations that fail to varying degrees in practice: different states have different conditional gradient-norm scales, and these scales may co-vary with σπ _π across states. The natural question is whether μvar∝dπσπ _var d^π _π—which no longer coincides with the exact optimum (16) once Assumption B.4 is dropped—is still a strict improvement over on-policy sampling, and under what condition. To state this cleanly we factor M(s)M(s) through σπ(s) _π(s). On s:σπ(s)>0\s: _π(s)>0\, define K(s):=M(s)σπ(s)2.K(s)\;:=\; M(s) _π(s)^2. (22) Assumption B.4 is equivalent to K≡G0K≡ G_0 being a state-independent constant; relaxing it amounts to allowing K to vary across s. For notational simplicity, we assume throughout this subsection that σπ(s)>0 _π(s)>0 for dπd^π-almost every state. States with σπ(s)=0 _π(s)=0 carry no reward-variance signal under b=r¯b= r and can be removed by working on the effective support, with the corresponding normalization factors tracked explicitly. The relaxed assumption is a quantitative bound on the heterogeneity of K, measured by its coefficient of variation, relative to the spread of σπ _π: Assumption B.6 (Gradient regularity). On the set of states s:σπ(s)>0\s: _π(s)>0\, the function K(s)K(s) satisfies Vardπ(K)dπ[K]<23Vardπ(σπ), Var_d^π(K)E_d^π[K]\;<\; 23 Var_d^π( _π), (23) where the moments are taken with respect to s∼dπs d^π restricted to that set. Assumption B.6 is strictly weaker than Assumption B.4: gradient uniformity is the limit Var(K)=0Var(K)=0, in which the left-hand side is zero and (23) is vacuous (provided σπ _π is non-constant). It admits a transparent reading: μvar _var remains beneficial as long as the relative state-to-state variation of K is small compared to the absolute spread of σπ _π on the policy’s reachable set—i.e., as long as the policy’s reachable-but-uncertain frontier is wide enough to outweigh whatever heterogeneity K exhibits across states. Theorem B.7 (Variance reduction under gradient regularity). Suppose r∈0,1r∈\0,1\ and b=r¯b= r. Under Assumption B.6, V(μvar,b∗)<V(dπ,b∗).V( _var;b^*)\;<\;V(d^π;b^*). (24) The proof proceeds via an exact decomposition of the variance gap, isolating a non-positive Jensen-type term and a coupling correction that vanishes under Assumption B.4. Lemma B.8 (Variance gap decomposition). Let b=r¯b= r. Then, with all expectations, variances, and covariances taken with respect to s∼dπs d^π restricted to σπ>0\ _π>0\, V(μvar;b∗)−V(dπ;b∗)=−[K]⋅Var(σπ)+Δcoup,V( _var;b^*)-V(d^π;b^*)\;=\;-\,E[K]·Var( _π)\;+\; _coup, (25) where Δcoup:=[σπ]Cov(σπ,K)−Cov(σπ2,K) _coup:=E[ _π]\,Cov( _π,K)-Cov( _π^2,K). Proof. Let Z:=dπ[σπ]>0Z:=E_d^π[ _π]>0, so μvar=dπσπ/Z _var=d^π _π/Z. By Lemma B.1, the ‖∇J‖2\|∇ J\|^2 terms cancel and V(μvar,b∗)−V(dπ,b∗)=Zdπ[M(s)σπ(s)]−dπ[M(s)].V( _var;b^*)-V(d^π;b^*)=Z\,E_d^π\! [ M(s) _π(s) ]-E_d^π[M(s)]. Substituting M=σπ2KM= _π^2K, =[σπ][σπK]−[σπ2K].=E[ _π]\,E[ _πK]-E[ _π^2K]. Apply [XY]=[X][Y]+Cov(X,Y)E[XY]=E[X]E[Y]+Cov(X,Y) to both products: [σπ][σπK] [ _π]\,E[ _πK] =[σπ]2[K]+[σπ]Cov(σπ,K), =E[ _π]^2\,E[K]+E[ _π]\,Cov( _π,K), [σπ2K] [ _π^2K] =[σπ2][K]+Cov(σπ2,K). =E[ _π^2]\,E[K]+Cov( _π^2,K). Subtracting and using Var(σπ)=[σπ2]−[σπ]2Var( _π)=E[ _π^2]-E[ _π]^2 gives (25). ∎ Lemma B.9 (Variance-of-square bound). For any random variable X with values in [0,M][0,M], Var(X2)≤4M2Var(X)Var(X^2)≤ 4M^2\,Var(X). Proof. Let X′X be an independent copy of X. Then Var(X2)=12[(X2−X′2)2]=12[(X+X′)2(X−X′)2]≤2M2[(X−X′)2]=4M2Var(X),Var(X^2)= 12\,E[(X^2-X 2)^2]= 12\,E[(X+X )^2(X-X )^2]≤ 2M^2\,E[(X-X )^2]=4M^2\,Var(X), where the inequality uses 0≤X+X′≤2M0≤ X+X ≤ 2M almost surely. ∎ Proof of Theorem B.7. By Lemma B.8, it suffices to show [K]Var(σπ)>ΔcoupE[K]\,Var( _π)> _coup. We bound |Δcoup|| _coup| from above. By Cauchy–Schwarz, |Cov(σπ,K)|≤Var(σπ)Var(K),|Cov(σπ2,K)|≤Var(σπ2)Var(K).|Cov( _π,K)|≤ Var( _π)Var(K), |Cov( _π^2,K)|≤ Var( _π^2)Var(K). For binary rewards, σπ(s)≤1/2 _π(s)≤ 1/2 structurally, so Lemma B.9 with M=1/2M=1/2 gives Var(σπ2)≤Var(σπ)Var( _π^2) ( _π) and hence |Cov(σπ2,K)|≤Var(σπ)Var(K)|Cov( _π^2,K)|≤ Var( _π)Var(K). Combined with [σπ]≤1/2E[ _π]≤ 1/2, |Δcoup|≤12Var(σπ)Var(K)+Var(σπ)Var(K)=32Var(σπ)Var(K).| _coup|\;≤\; 12 Var( _π)Var(K)+ Var( _π)Var(K)\;=\; 32 Var( _π)Var(K). (26) Plugging (26) into (25), V(μvar,b∗)−V(dπ,b∗)≤−[K]Var(σπ)+32Var(σπ)Var(K).V( _var;b^*)-V(d^π;b^*)\;≤\;-\,E[K]\,Var( _π)+ 32 Var( _π)Var(K). The right-hand side is negative iff [K]Var(σπ)>32Var(K)E[K] Var( _π)> 32 Var(K), i.e. iff Var(K)/[K]<23Var(σπ) Var(K)/E[K]< 23 Var( _π), which is exactly Assumption B.6. ∎ Remark B.10 (Beyond binary rewards). For r∈[0,R]r∈[0,R], σπ(s)≤R/2 _π(s)≤ R/2 and Lemma B.9 gives Var(σπ2)≤R2Var(σπ)Var( _π^2)≤ R^2Var( _π). The proof of Theorem B.7 carries over with constants scaled accordingly: |Δcoup|≤3R2Var(σπ)Var(K)| _coup|≤ 3R2 Var( _π)Var(K), and Assumption B.6 becomes Var(K)/[K]<23RVar(σπ) Var(K)/E[K]< 23R Var( _π). Appendix C State-Visitation Policy Mirror Descent: Theory This appendix analyzes an idealized algorithm—State-Visitation Policy Mirror Descent (SVMD)—that samples states from a smoothed version of dπσd^πσ and uses an explicit critic fitted by importance-weighted regression. SVMD is not the GRPO-based algorithm of the main text: it assumes an oracle for σhπ(s) _h^π(s) and replaces GRPO’s group-relative advantage with a fitted Q. We include it as theoretical evidence that proposals of the form dπσd^πσ are well-behaved in a tractable PMD setting; a direct finite-sample analysis of the practical algorithm is left to future work. C.1 Setup We consider a finite-horizon episodic MDP with horizon H, state space S, action space A, transition kernels Ph(⋅∣s,a)P_h(· s,a), reward functions rh(s,a)∈[0,1]r_h(s,a)∈[0,1], and initial state distribution ρ. A (non-stationary) policy is π=(π1,…,πH)π=( _1,…, _H). Define Vhπ(s):=π[∑ℓ=hHrℓ(sℓ,aℓ)|sh=s],Qhπ(s,a):=rh(s,a)+s′∼Ph(⋅∣s,a)[Vh+1π(s′)],V_h^π(s):=E_π\! [ _ =h^Hr_ (s_ ,a_ )\, |\,s_h=s ], Q_h^π(s,a):=r_h(s,a)+E_s P_h(· s,a)[V_h+1^π(s )], Ahπ(s,a):=Qhπ(s,a)−Vhπ(s),J(π):=s1∼ρ[V1π(s1)].A_h^π(s,a):=Q_h^π(s,a)-V_h^π(s), J(π):=E_s_1 ρ[V_1^π(s_1)]. Let dhπd_h^π denote the stage-h state occupancy of π, and let νhπ(s,a):=dhπ(s)πh(a∣s) _h^π(s,a):=d_h^π(s) _h(a s) be the stage-h state-action occupancy. Throughout the appendix, σhπ:→ℝ≥0 _h^π:S _≥ 0 denotes a fixed nonnegative state-score function associated with policy π at stage h (e.g. σhπ(s)=Vara∼πh(⋅∣s)(Qhπ(s,a)) _h^π(s)= Var_a _h(· s)(Q_h^π(s,a))). Our analysis does not depend on the specific form of σ. C.2 Algorithm Algorithm 2 State-Visitation Policy Mirror Descent (SVMD) 1: Initial policy π1 _1, horizon H, iterations T, per-stage state budgets Nhh=1H\N_h\_h=1^H, step size η>0η>0, smoothing parameter ε∈(0,1] ∈(0,1], state-score oracle σhπ(⋅) _h^π(·), stagewise critic classes ℱhh=1H\F_h\_h=1^H. 2: for t=1,…,Tt=1,…,T do 3: for h=1,…,Hh=1,…,H do 4: Define the proposal μ~ht(s)∝dhπt(s)σhπt(s),μht(s):=(1−ε)μ~ht(s)+εdhπt(s), μ_h^t(s) d_h _t(s) _h _t(s), _h^t(s):=(1- ) μ_h^t(s)+ \,d_h _t(s), and importance weights wht(s):=dhπt(s)/μht(s)∈[0,1/ε]w_h^t(s):=d_h _t(s)/ _h^t(s)∈[0,1/ ]. 5: Sample i.i.d. data (sh,i,ah,i,Gh,i)i=1Nh\(s_h,i,a_h,i,G_h,i)\_i=1^N_h: sh,i∼μhts_h,i _h^t, ah,i∼πt,h(⋅∣sh,i)a_h,i _t,h(· s_h,i), and Gh,i:=∑ℓ=hHrℓ(sℓ,aℓ)G_h,i:= _ =h^Hr_ (s_ ,a_ ) is the Monte Carlo return-to-go obtained by rolling out πt _t from (sh,i,ah,i)(s_h,i,a_h,i). 6: Weighted critic fit: Q^ht∈argmin∑i=1Nhf∈ℱhwht(sh,i)(f(sh,i,ah,i)−Gh,i)2. Q_h^t∈ _f _h _i=1^N_hw_h^t(s_h,i) (f(s_h,i,a_h,i)-G_h,i )^2. 7: KL-regularized mirror ascent: for each s∈s , πt+1,h(⋅∣s)←argmaxp∈Δ()η⟨Q^ht(s,⋅),p⟩−KL(p∥πt,h(⋅∣s)). _t+1,h(· s)← _p∈ (A) \η\, Q_h^t(s,·),\,p -KL\! (p\, \|\, _t,h(· s) ) \. 8: end for 9: end for 10: return uniform mixture π¯T:=Unifπ1,…,πT π_T:=Unif\ _1,…, _T\. The mirror update has the closed form πt+1,h(a∣s)∝πt,h(a∣s)exp(ηQ^ht(s,a)) _t+1,h(a s) _t,h(a s) (η Q_h^t(s,a)), i.e. a softmax NPG step. C.3 Assumptions Assumption C.1 (Bounded rewards and bounded critic class). For all h,s,ah,s,a, rh(s,a)∈[0,1]r_h(s,a)∈[0,1], hence 0≤Qhπ(s,a)≤H0≤ Q_h^π(s,a)≤ H for all π,h,s,aπ,h,s,a. Moreover ℱh⊆f:×→[0,H]F_h \f:S×A→[0,H]\. Assumption C.2 (Stagewise realizability). For every iteration t∈[T]t∈[T] and stage h∈[H]h∈[H], Qhπt∈ℱhQ_h _t _h. Assumption C.3 (Comparator coverage). There exist κ≥1κ≥ 1 and a comparator policy μ such that for all t∈[T]t∈[T], h∈[H]h∈[H], (s,a)(s,a), νhμ(s,a)≤κνhπt(s,a). _h^μ(s,a)≤κ\, _h _t(s,a). Assumption C.4 (Proposal smoothing). For every t∈[T]t∈[T], h∈[H]h∈[H], s∈s , μht(s)≥εdhπt(s) _h^t(s)≥ \,d_h _t(s), equivalently dhπt(s)/μht(s)≤1/εd_h _t(s)/ _h^t(s)≤ 1/ . (This holds by construction of μht _h^t in Algorithm 2.) C.4 Main Theorem Theorem C.5 (Finite-sample guarantee for SVMD). Under Assumptions C.1–C.4, fix δ∈(0,1)δ∈(0,1). With probability at least 1−δ1-δ, the policy mixture π¯T π_T returned by Algorithm 2 satisfies J(μ)−J(π¯T)≤DμηT+ηH32+ 2κ∑h=1Hβh,J(μ)-J( π_T)\;≤\; D_μη T\;+\; η H^32\;+\;2κ _h=1^H _h, where Dμ:=∑h=1Hs∼dhμ[KL(μh(⋅∣s)∥π1,h(⋅∣s))],βh:=C⋅H2ε⋅log(HT|ℱh|/δ)Nh,D_μ:= _h=1^HE_s d_h^μ\! [KL\! ( _h(· s)\, \|\, _1,h(· s) ) ], _h:= \,C· H^2 · (HT|F_h|/δ)N_h\,, for a universal constant C>0C>0. In particular, choosing η=2Dμ/(H3T)η= 2D_μ/(H^3T) yields J(μ)−J(π¯T)≤2DμH3T+ 2κ∑h=1Hβh.J(μ)-J( π_T)\;≤\; 2D_μH^3T\;+\;2κ _h=1^H _h. C.5 Proof Outline The proof has three modular parts. 1. Per-step mirror descent inequality (Lemma C.7). The KL-regularized update yields, stagewise and per iteration, a bound on η⟨Q^ht,μh−πt,h⟩η Q_h^t, _h- _t,h in terms of the progress KL(μh∥πt,h)−KL(μh∥πt+1,h)KL( _h\| _t,h)-KL( _h\| _t+1,h) plus a quadratic drift term. 2. Telescoping and averaging. Summing the per-step inequality over t and h and dividing by T controls the average inner product between Q^ht Q_h^t and μh−πt,h _h- _t,h. 3. Critic error control (Lemma C.8). The performance difference lemma reduces J(μ)−J(πt)J(μ)-J( _t) to the same inner product plus a critic error ℰh,tE_h,t. Coverage (Assumption C.3) bounds |ℰh,t||E_h,t| by an on-policy L1L^1 critic error, which is in turn controlled by weighted ERM analysis under realizability and proposal smoothing. C.6 Lemmas Lemma C.6 (Performance difference). For any policies π,μπ,μ, J(μ)−J(π)=∑h=1Hs∼dhμ[⟨Qhπ(s,⋅),μh(⋅∣s)−πh(⋅∣s)⟩].J(μ)-J(π)= _h=1^HE_s d_h^μ\! [ Q_h^π(s,·),\, _h(· s)- _h(· s) ]. Proof. Standard finite-horizon performance difference lemma; see e.g. Kakade and Langford (2002). ∎ Lemma C.7 (Mirror descent per-step inequality). Fix t∈[T]t∈[T] and h∈[H]h∈[H], and any state s. Let πt+1,h(⋅∣s) _t+1,h(· s) be the mirror update in Algorithm 2. Then for any p∈Δ()p∈ (A), η⟨Q^ht(s,⋅),p−πt,h(⋅∣s)⟩≤KL(p∥πt,h(⋅∣s))−KL(p∥πt+1,h(⋅∣s))+η2H22.η\, Q_h^t(s,·),\,p- _t,h(· s) \;≤\;KL\! (p\, \|\, _t,h(· s) )-KL\! (p\, \|\, _t+1,h(· s) )+ η^2H^22. Proof. Fix s and write πt,πt+1 _t, _t+1 for πt,h(⋅∣s),πt+1,h(⋅∣s) _t,h(· s), _t+1,h(· s), Q Q for Q^ht(s,⋅) Q_h^t(s,·). Step 1: First-order optimality. Since πt+1 _t+1 maximizes η⟨Q^,p⟩−KL(p∥πt)η Q,p -KL(p\| _t) over p∈Δ()p∈ (A) in the relative interior, the closed-form solution is πt+1(a)∝πt(a)exp(ηQ^(a)) _t+1(a) _t(a) (η Q(a)), equivalently logπt+1(a)−logπt(a)=ηQ^(a)−Z, _t+1(a)- _t(a)=η Q(a)-Z, (27) where Z is the (state-dependent) log-normalizer. Step 2: Three-point identity. For any p∈Δ()p∈ (A), direct computation gives the well-known three-point identity for KL: KL(p∥πt)−KL(p∥πt+1)−KL(πt+1∥πt)=⟨p−πt+1,log(πt+1/πt)⟩.KL(p\| _t)-KL(p\| _t+1)-KL( _t+1\| _t)= p- _t+1,\, ( _t+1/ _t) . Substituting (27), the right-hand side equals η⟨p−πt+1,Q^⟩η p- _t+1, Q (the Z term vanishes since p and πt+1 _t+1 are both probabilities). Therefore η⟨Q^,p−πt+1⟩=KL(p∥πt)−KL(p∥πt+1)−KL(πt+1∥πt).η Q,\,p- _t+1 =KL(p\| _t)-KL(p\| _t+1)-KL( _t+1\| _t). (28) Step 3: Bound the drift ⟨Q^,πt+1−πt⟩ Q, _t+1- _t . By Hölder and Pinsker, η⟨Q^,πt+1−πt⟩≤η‖Q^‖∞‖πt+1−πt‖1≤ηH2KL(πt+1∥πt),η Q, _t+1- _t ≤η\| Q\|_∞\| _t+1- _t\|_1≤η H 2\,KL( _t+1\| _t), where ‖Q^‖∞≤H\| Q\|_∞≤ H uses Assumption C.1. By ab≤12a2+12b2ab≤ 12a^2+ 12b^2 with a=ηHa=η H, b=2KL(πt+1∥πt)b= 2\,KL( _t+1\| _t), η⟨Q^,πt+1−πt⟩≤η2H22+KL(πt+1∥πt).η Q, _t+1- _t ≤ η^2H^22+KL( _t+1\| _t). (29) Step 4: Combine. Adding (28) and (29), η⟨Q^,p−πt⟩≤KL(p∥πt)−KL(p∥πt+1)+η2H22,η Q,\,p- _t (p\| _t)-KL(p\| _t+1)+ η^2H^22, where the two KL(πt+1∥πt)KL( _t+1\| _t) terms cancel exactly. This is the claim. ∎ Lemma C.8 (Weighted critic error). Fix t∈[T]t∈[T] and h∈[H]h∈[H]. Under Assumptions C.1, C.2, C.4, and conditional on πt _t, with probability at least 1−δ′1-δ over the sampling of (sh,i,ah,i,Gh,i)i=1Nh\(s_h,i,a_h,i,G_h,i)\_i=1^N_h, (s,a)∼νhπt[(Q^ht(s,a)−Qhπt(s,a))2]≤C⋅H2ε⋅log(|ℱh|/δ′)Nh,E_(s,a) _h _t\! [( Q_h^t(s,a)-Q_h _t(s,a))^2 ]≤ C· H^2 · (|F_h|/δ )N_h, for a universal constant C>0C>0. Consequently, by Cauchy–Schwarz, (s,a)∼νhπt[|Q^ht(s,a)−Qhπt(s,a)|]≤C⋅H2ε⋅log(|ℱh|/δ′)Nh.E_(s,a) _h _t\! [| Q_h^t(s,a)-Q_h _t(s,a)| ]≤ C· H^2 · (|F_h|/δ )N_h. Proof. Step 1: Reweighting to on-policy loss. For any f∈ℱhf _h, the weighted population squared loss equals the on-policy loss to a constant offset: s∼μht,a∼πt,h,G[wht(s)(f(s,a)−G)2]=(s,a)∼νhπt,G[(f(s,a)−G)2],E_s _h^t,a _t,h,G\! [w_h^t(s)(f(s,a)-G)^2 ]=E_(s,a) _h _t,G\! [(f(s,a)-G)^2 ], because wht(s)=dhπt(s)/μht(s)w_h^t(s)=d_h _t(s)/ _h^t(s) exactly cancels the change of state measure, while a|s∼πt,ha s _t,h and the conditional distribution of G given (s,a)(s,a) are the same under both samplings. Step 2: Realizability and noise structure. By construction, Gh,iG_h,i is a return-to-go obtained by rolling out πt _t from (sh,i,ah,i)(s_h,i,a_h,i), so [Gh,i∣sh,i,ah,i]=Qhπt(sh,i,ah,i),Gh,i∈[0,H].E[G_h,i s_h,i,a_h,i]=Q_h _t(s_h,i,a_h,i), G_h,i∈[0,H]. By Assumption C.2, Qhπt∈ℱhQ_h _t _h, so QhπtQ_h _t minimizes the on-policy population squared loss over ℱhF_h. Step 3: Weighted ERM fast rate. The per-sample weighted squared loss is bounded: wht(s)(f(s,a)−G)2∈[0,H2/ε]w_h^t(s)(f(s,a)-G)^2∈[0,H^2/ ] by Assumption C.4 and Assumption C.1. Standard realizable-case ERM analysis (e.g. Bartlett–Mendelson local Rademacher, or the offset-Rademacher bound of Liang–Rakhlin–Sridharan 2015) for finite classes then gives (s,a)∼νhπt[(Q^ht(s,a)−Qhπt(s,a))2]≤C⋅Blog(|ℱh|/δ′)Nh,E_(s,a) _h _t\! [( Q_h^t(s,a)-Q_h _t(s,a))^2 ]≤ C· B (|F_h|/δ )N_h, with B=H2/εB=H^2/ the per-sample loss range. The Cauchy–Schwarz step |X|≤X2E|X|≤ EX^2 then converts L2L^2 to L1L^1. ∎ C.7 Proof of Theorem C.5 Step 1: Per-step bound, telescoping. Apply Lemma C.7 with p=μh(⋅∣s)p= _h(· s), take expectation over s∼dhμs d_h^μ, and sum over h∈[H]h∈[H] and t∈[T]t∈[T]. The KL terms telescope in t: η∑t=1T∑h=1Hs∼dhμ[⟨Q^ht(s,⋅),μh−πt,h⟩]≤Dμ+Tη2H32,η _t=1^T _h=1^HE_s d_h^μ\! [ Q_h^t(s,·), _h- _t,h ]≤ D_μ+ Tη^2H^32, since each per-step term contributes η2H2/2η^2H^2/2 and there are THTH of them. Dividing by ηTη T, 1T∑t=1T∑h=1Hs∼dhμ[⟨Q^ht(s,⋅),μh−πt,h⟩]≤DμηT+ηH32. 1T _t=1^T _h=1^HE_s d_h^μ\! [ Q_h^t(s,·), _h- _t,h ]≤ D_μη T+ η H^32. (30) Step 2: Performance difference and critic error. By Lemma C.6 and adding/subtracting Q^ht Q_h^t, J(μ)−J(πt)=∑h=1Hs∼dhμ[⟨Q^ht(s,⋅),μh−πt,h⟩]+∑h=1Hℰh,t,J(μ)-J( _t)= _h=1^HE_s d_h^μ\! [ Q_h^t(s,·), _h- _t,h ]+ _h=1^HE_h,t, where, with eh,t(s,a):=Q^ht(s,a)−Qhπt(s,a)e_h,t(s,a):= Q_h^t(s,a)-Q_h _t(s,a), ℰh,t:=s∼dhμ[⟨Qhπt(s,⋅)−Q^ht(s,⋅),μh−πt,h⟩].E_h,t:=E_s d_h^μ\! [ Q_h _t(s,·)- Q_h^t(s,·), _h- _t,h ]. Step 3: Coverage transfers ℰh,tE_h,t to on-policy L1L^1. By the triangle inequality, |ℰh,t|≤|s∼dhμ,a∼μh[eh,t(s,a)]|+|s∼dhμ,a∼πt,h[eh,t(s,a)]|.|E_h,t|≤ |E_s d_h^μ,a _h[e_h,t(s,a)] |+ |E_s d_h^μ,a _t,h[e_h,t(s,a)] |. Assumption C.3 gives νhμ≤κνhπt _h^μ≤κ _h _t, hence |s∼dhμ,a∼μh[eh,t]|≤κ(s,a)∼νhπt[|eh,t|]. |E_s d_h^μ,a _h[e_h,t] |≤κ\,E_(s,a) _h _t[|e_h,t|]. Summing νhμ(s,a)≤κνhπt(s,a) _h^μ(s,a)≤κ _h _t(s,a) over a also gives dhμ≤κdhπtd_h^μ≤κ d_h _t pointwise, so |s∼dhμ,a∼πt,h[eh,t]|≤κ(s,a)∼νhπt[|eh,t|]. |E_s d_h^μ,a _t,h[e_h,t] |≤κ\,E_(s,a) _h _t[|e_h,t|]. Therefore |ℰh,t|≤2κ(s,a)∼νhπt[|eh,t(s,a)|].|E_h,t|≤ 2κ\,E_(s,a) _h _t[|e_h,t(s,a)|]. (31) Step 4: Apply Lemma C.8 with a union bound. Apply Lemma C.8 with confidence δ/(HT)δ/(HT) for each (t,h)(t,h). A union bound over the HTHT such events implies that, with probability at least 1−δ1-δ, simultaneously for all t,ht,h, (s,a)∼νhπt[|eh,t(s,a)|]≤βh.E_(s,a) _h _t[|e_h,t(s,a)|]≤ _h. Combined with (31), |ℰh,t|≤2κβh|E_h,t|≤ 2κ _h on this event. Step 5: Assemble. On the high-probability event of Step 4, J(μ)−J(πt)≤∑h=1Hs∼dhμ[⟨Q^ht,μh−πt,h⟩]+2κ∑h=1Hβh.J(μ)-J( _t)≤ _h=1^HE_s d_h^μ\! [ Q_h^t, _h- _t,h ]+2κ _h=1^H _h. Averaging over t∈[T]t∈[T] and using J(π¯T)=1T∑t=1TJ(πt)J( π_T)= 1T _t=1^TJ( _t) (since π¯T π_T is the uniform mixture), then plugging in (30), J(μ)−J(π¯T)≤DμηT+ηH32+2κ∑h=1Hβh.J(μ)-J( π_T)≤ D_μη T+ η H^32+2κ _h=1^H _h. The choice η=2Dμ/(H3T)η= 2D_μ/(H^3T) minimizes the first two terms, giving the second form of the bound. □ Appendix D Experiments This appendix provides additional details for the experiments in Section 4. The purpose of these experiments is to test whether variance-driven state resampling is most useful in the regime predicted by our analysis: tasks in which rollouts from the initial state often produce uniform rewards, but intermediate states along successful or partially successful trajectories can still produce mixed continuation outcomes. Across all experiments, VSR changes only the state from which rollout groups are initialized; the underlying policy-gradient objective, reward function, and evaluation protocol are otherwise kept the same as the corresponding baseline. D.1 Toy gridworld We use the gridworld experiment in Section 2.3 as a controlled setting where both the on-policy state-visitation distribution dπtd _t and the within-state reward standard deviation σπt _ _t can be computed exactly. The environment is a 7×77× 7 gridworld with fixed obstacles, a start state S, and a goal state G. The agent receives a binary terminal reward R∈0,1R∈\0,1\ indicating whether it reaches the goal. The policy is a one-hidden-layer MLP with 32 hidden units and tanh activations, followed by a four-action output layer. At each training iteration, we enumerate the finite state space to compute the current occupancy distribution dπt(s)d _t(s) and the continuation success probability pt(s)p_t(s) from every reachable state. We then compute σπt(s)=pt(s)(1−pt(s)) _ _t(s)= p_t(s)(1-p_t(s)) and form the variance-driven proposal μt(s)∝dπt(s)σπt(s). _t(s) d _t(s) _ _t(s). We compare policy-gradient updates that sample states from the standard on-policy proposal dπtd _t against updates that sample from μt _t. This experiment is intended as a diagnostic visualization of the variance-optimal proposal rather than as a benchmark of practical replay heuristics: unlike the LLM and agent experiments, no approximation to either dπtd _t or σπt _ _t is used. D.2 Mathematical reasoning Training data. For mathematical reasoning, we train on a hard subset of OpenR1-Math-220k. The subset contains 1K prompts selected to have low pass rate under the base policy. We filter for prompts with pass@32 at most 1 using Qwen2.5-7B-Instruct. This filtering focuses training on problems for which prompt-level on-policy rollouts are usually uninformative, creating a setting where intermediate successful prefixes can provide useful continuation states. Models and baselines. We run experiments with Qwen2.5-7B-Instruct and Llama-3.2-3B-Instruct. For each model, we compare the base model, supervised fine-tuning on expert trajectories, standard GRPO, and VSR+GRPO. The SFT baseline uses the same successful expert trajectories that are used to initialize the VSR replay buffer, so that the comparison separates direct imitation of expert completions from using expert prefixes only as reset states for RL rollouts. All experiments are performed on 4 A100 GPUs. VSR initialization. In the math experiments, VSR uses cold-start initialization because successful trajectories are rare under the base policy. We seed the replay buffer with prefix states extracted from successful DeepSeek-R1 trajectories. A seeded prefix consists of the original prompt concatenated with a partial reasoning trace. During VSR training, the prefix tokens are treated as fixed context and are masked out of the policy-gradient loss; only newly generated continuation tokens contribute to the GRPO objective. As training proceeds, the replay buffer is updated with successful prefixes generated by the current policy, and recency-based eviction gradually replaces expert-seeded prefixes with on-policy states. For every prompt, we only keep the most recent single successful trajectory. Replay construction and scoring. For every successful fresh trajectory τ generated during training, we insert prefix states si=(x,y<i)s_i=(x,y_<i) into the replay buffer. Each inserted prefix receives the zero-cost variance score σ^(si)=p^i(1−p^i),p^i=(1−αi)p0(x)+αiR(τ),αi=i/|τ|. σ(s_i)= p_i(1- p_i), p_i=(1- _i)p_0(x)+ _iR(τ), _i=i/|τ|. Here p0(x)p_0(x) is the empirical success rate of the rollout group generated from the original prompt, and R(τ)R(τ) is the terminal reward of the trajectory from which the prefix was extracted. At each update, a fraction ρ of batch elements is drawn from the replay buffer with probability proportional to σ σ, while the remaining batch elements are fresh prompts from the training set. For replayed prefixes, we generate a fresh GRPO rollout group from the prefix using the current policy. 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 α∈0%,25%,50%,75%,100%α∈\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 α, supporting the linear interpolation used in p^t(si∣τ)=(1−αi)p0(x)+αiR(τ) p_t(s_i τ)=(1- _i)\,p_0(x)+ _i\,R(τ). Empirical justification of the linear interpolation. The score σ^t σ_t in Algorithm 1 estimates the continuation success probability at an intermediate prefix sis_i by linearly interpolating between the prompt-level rollout success rate p0(x)p_0(x) and the terminal reward R(τ)R(τ) of the trajectory the prefix is drawn from. We adopt the linear form because it is the simplest functional form consistent with the boundary conditions p^0=p0(x) p_0=p_0(x) and p^|τ|=R(τ) p_|τ|=R(τ), and we did not tune it. To check that this choice is not grossly mis-specified in our training setting, we measure the empirical continuation success rate as a function of the hint ratio α=i/|τ|α=i/|τ|. Concretely, for each of the 1K hard prompts in our training subset—on which the base policy’s pass rate is essentially zero—we take the corresponding successful DeepSeek-R1 trajectory used to seed the replay buffer, truncate it to α∈0%,25%,50%,75%,100%α∈\0\%,25\%,50\%,75\%,100\%\ of its length, and sample 8 continuations under Qwen2.5-7B-Instruct from each truncation. Figure 7 reports the mean and 25–75 percentile of the resulting per-prompt success rate across the 1K prompts. The mean success rate rises approximately linearly in α from ≈0≈ 0 at α=0α=0 to ≈1≈ 1 at α=100%α=100\%, with no strong concavity or saturation that would favor a sigmoid or quadratic interpolant. The interquartile spread is widest near the middle of the trajectory, which is exactly the regime where σπ(s) _π(s) is largest under the proxy and where VSR is designed to concentrate sampling mass. We therefore retain the linear form throughout; tighter low-cost surrogates remain a natural target for future work. Evaluation. We evaluate final models on AIME24, AIME25, AMC23, OlympiadBench, MATH500, and Minerva. For each benchmark, we report accuracy under the same decoding and evaluation protocol across all methods. We sample 16 rollouts over 2 different seeds for all the prompts under temperature=0.7 and report the mean results. In addition to final benchmark accuracy, we track training reward, validation accuracy, and response length over training. Response length is included because VSR can reduce the number of newly generated tokens per update by starting a fraction of rollouts from mid-trajectory prefixes. Table 4: Hyperparameters for mathematical reasoning experiments. Hyperparameter Qwen2.5-7B-Instruct Llama-3.2-3B-Instruct Replay ratio ρ 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 Mini batch size 64 64 Learning rate 1×10−61× 10^-6 1×10−61× 10^-6 KL coefficient 0 0 D.3 Long-horizon agentic tasks Environments. We evaluate VSR on both Sokoban and BabyAI. These environments require multi-step decision making and produce sparse terminal rewards, making them a natural testbed for state-level resampling. For BabyAI, we use the SynthLoc, OneRoom, and MiniBoss levels. The policy observes a serialized interaction history consisting of the task instruction, previous actions, environment feedback, and current observations. A replay state is therefore represented as a prefix of this serialized trajectory, analogous to a token prefix in the math experiments. Models and baselines. We use Qwen2.5-1.5B-Instruct and Qwen2.5-3B-Instruct. The base RL algorithm is GiGPO, and VSR is added as a plug-in state-resampling component. We compare the base model, GiGPO, and VSR+GiGPO under matched model, environment, reward, and training settings. Unlike the math experiments, we do not use expert successful trajectories for cold-start initialization. The replay buffer is populated entirely from trajectories generated by the current policy. All experiments are performed on a single H200 GPU. VSR in agentic environments. At each training iteration, the policy generates rollout groups either from the initial environment state or from replayed intermediate states. When a successful trajectory is observed, we insert its intermediate serialized states into the replay buffer. Each replayed state includes all information needed to resume interaction from that point, including prior actions and environment observations. As in the math setting, prefix tokens or history tokens preceding the replay point are treated as fixed context and are masked from the policy-gradient loss. The model is optimized only on newly generated actions after the replay state. Prefix scores are computed with the same zero-cost interpolation rule used in the math experiments. For a prefix at normalized position αi _i along a successful trajectory, the estimated continuation success probability interpolates between the rollout-group success rate from the initial state and the realized terminal reward of the trajectory. Replay prefixes are sampled in proportion to the resulting σ σ score. The recency window is used to keep the replay buffer aligned with the current policy, preventing the proposal from becoming dominated by states collected under earlier, weaker policies. Evaluation. For Sokoban and BabyAI, we report task success rate. For Sokoban, we sample 128 times over a fixed set of map seeds and report the average success rate. For each level of Baby AI, we sample 128 times over a fixed set of map seeds and report the average success rate. The environment hyperparameters remain the same as what we use in training. For training dynamics, we additionally track training reward, validation success rate, and episode length. Episode length is reported because state replay changes the average number of newly generated steps per rollout: when training starts from intermediate states, the model can receive useful gradient signal while generating fewer new actions. Table 5: Hyperparameters for agentic-task 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 Learning rate 1×10−61× 10^-6 1×10−61× 10^-6 KL coefficient 0 0 D.4 Ablation details We conduct ablations on BabyAI using the same training and evaluation setup as the main agentic-task experiments. All ablation variants are built on top of GiGPO and differ only in the replay component. Uniform replay. The variant VSR w/o scoring keeps the same replay buffer construction and recency-based updates as VSR, but samples prefixes uniformly from the buffer rather than in proportion to σ σ. This ablation tests whether the variance-driven score contributes beyond the benefit of simply restarting rollouts from previously visited successful prefixes. Static replay buffer. The variant VSR w/o recency keeps σ σ-weighted prefix sampling but disables recency-based buffer updates. The buffer is populated early in training and then held fixed. This ablation tests whether tracking the current policy’s state-visitation distribution is necessary for sustained learning. A static buffer can be useful early in training, but as the policy improves, its state distribution changes; without recency updates, replayed prefixes may no longer approximate the current dπtd _t factor in the variance-driven proposal. Full VSR. Full VSR combines both components: recent successful-prefix replay approximates the current state-visitation factor, while σ σ-weighted sampling prioritizes prefixes whose continuations are estimated to have high residual uncertainty. The ablations therefore isolate the two practical approximations to the proposal μvarπ∝dπσπ _var^π d^π _π. D.5 Discussion-period controls and validations 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 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 Static expert-prefix reset control. For Llama-3.2-3B-Instruct, we added a control using the same successful expert-trajectory source as VSR but sampling uniformly from a fixed expert-prefix pool and never adding prefixes generated by the current policy. The benchmark results (AIME24/AIME25/AMC23/OlympiadBench/MATH500/Minerva/Avg.) are 4.4/1.0/18.7/12.6/39.2/16.5/15.4 for GRPO, 5.6/0.5/22.7/14.1/43.7/15.8/17.1 for static uniform expert-prefix resets, and 6.2/0.6/20.4/15.3/54.0/17.8/19.1 for VSR. Thus privileged reset states themselves explain a material part of the gain. Because full VSR also adds online policy-generated replay, recency updates, and priority-weighted sampling, the remaining difference cannot be attributed specifically to the priority score. This is one training run per method. Prompt-level adaptive allocation. We also compare with Reinforce-Ada-Est on Llama-3.2-3B-Instruct. Each update uses 128 prompts and exactly 128×8=1024128× 8=1024 generated responses. Reinforce-Ada-Est reallocates these responses across prompts subject to Nx∈[4,32]N_x∈[4,32] and ∑xNx=1024 _xN_x=1024, so its average group size is 8, matching GRPO and VSR. It uses no expert trajectories, expert prefixes, or intermediate reset states; every rollout begins from the original problem prompt. The training subset, number of updates, optimization hyperparameters, and evaluation protocol are otherwise matched. Under this matched response budget, its benchmark results are 4.2/0.1/18.0/12.4/39.9/15.4 (Avg. 15.0), compared with GRPO at 15.4 and VSR at 19.1. This supports the narrower conclusion that prompt-level response reallocation alone does not reproduce the full VSR result in this hard-prompt setting; it does not isolate state-level allocation as the sole source of the difference, and it is a single run. Independent-run scoring ablation. On Qwen2.5-1.5B BabyAI, the three uniform-replay runs are 46.1, 39.1, and 46.9 (mean 44.0±4.344.0± 4.3 SD), while the three VSR runs are 47.6, 50.8, and 46.1 (mean 48.2±2.448.2± 2.4 SD). We report all runs and do not perform formal significance testing. Table 7: Independent-run BabyAI scoring ablation on Qwen2.5-1.5B. Values are average success rates (%). Method Run 1 Run 2 Run 3 Mean ± SD Uniform replay 46.1 39.1 46.9 44.0±4.344.0± 4.3 VSR 47.6 50.8 46.1 48.2±2.448.2± 2.4 Failed-prefix analysis and same-checkpoint continuations. For failed trajectories, the mean continuation success rate decreases as the prefix becomes longer (0.396, 0.260, and 0.130 at the three tested prefix positions), while the fraction of continuation groups with no successful rollout increases from 26% to 42% to 62%. For successful trajectories from the same problems, the corresponding all-fail rates are 0%, 2%, and 4%. At the latest tested failed-prefix position, 36% of groups still contain mixed outcomes, so this evidence does not imply that every failed prefix is unrecoverable; it supports successful-only filtering as a budget-allocation choice in the sparse-reward regime. Statewise validation of the priority score. We directly validate the implemented score on MATH-500. For each policy, we select 50 problems with mixed initial outcomes, retain one self-generated successful trajectory per problem, extract prefixes at 25%, 50%, and 75% of the response, and generate 16 new continuations from each prefix, yielding 150 prefix states per policy. For Qwen2.5-7B-Instruct, predicted versus empirical continuation standard deviation has pooled Pearson correlation 0.441 [95% CI: 0.277, 0.591] and Spearman correlation 0.433 [0.270, 0.585]; Pearson correlations at the three fixed prefix positions are 0.446/0.387/0.342 and Spearman correlations are 0.494/0.305/0.329. For an intermediate training checkpoint, pooled Pearson is 0.484 [0.291, 0.641] and pooled Spearman is 0.499 [0.314, 0.642], with within-position Pearson 0.587/0.432/0.307 and Spearman 0.620/0.424/0.315. These moderate positive associations, including within fixed prefix positions, show that the score contains state-dependent information beyond prefix position alone. The validation uses selected successful MATH-500 states rather than the full online replay-buffer distribution, and the score remains an uncalibrated heuristic rather than an unbiased or consistent variance estimator. Generated-token accounting. Across all model calls in the agentic experiments, Qwen2.5-1.5B VSR+GiGPO generates 39.27M tokens over 150 matched updates compared with 81.30M for GiGPO; Qwen2.5-3B generates 34.43M versus 36.26M over 100 matched updates. These totals establish lower generated-token usage at matched update counts. We do not claim lower wall-clock cost or performance superiority under an exactly matched total-token budget.