Research map / Reinforcement learning / RL from feedback

Variance-Optimal State Resampling for Reinforcement Learning with Verifiable Rewards

NeurIPS 2026 · Reinforcement learning › RL from feedback · approach: RL fine-tuning of generative models

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Proposes VSR, a plug-in to GRPO/GiGPO that resamples reset prefixes from a recency-windowed buffer with variance-driven weights, motivated by a closed-form Neyman allocation over states.

Problem

RL with verifiable rewards wastes rollout budget on states/prompts whose groups yield uniform rewards and thus no learning signal; the state sampling distribution is usually fixed to on-policy visitation.

Approach

Derives a variance-optimal state proposal mu proportional to d^pi * sigma_pi (Neyman allocation) under gradient uniformity, and approximates it practically by sampling prefixes from a recent successful-prefix buffer with a zero-cost score sqrt(p(1-p)) from group success rate and prefix position.

Key results

• On Qwen2.5-7B-Instruct math, VSR+GRPO averages 37.6 vs 36.1 for GRPO (AIME25 10.4 vs 4.8).
• On Sokoban/BabyAI with Qwen2.5-1.5B, VSR+GiGPO averages 47.6% vs 30.4% for GiGPO.
• Token accounting: VSR+GiGPO generates 39.27M vs 81.30M tokens for Qwen2.5-1.5B at matched updates.

Surprising findings

• GRPO's final benchmark accuracy falls below the base model on the hard math subset despite rising training reward.
• Static uniform expert-prefix resets explain part of the gain, but prompt-level adaptive allocation (Reinforce-Ada-Est) does not reproduce it.

Limitations

• Practical VSR does not estimate the exact density ratio; the score sqrt(p(1-p)) is a heuristic proxy, not a calibrated estimator of sigma_pi.
• Most agentic results and the no-recency ablation are single-run; math uses expert-prefix cold start from DeepSeek-R1.
• Theory relies on gradient-uniformity assumptions and an idealized SVMD algorithm not identical to the practical method.

Experimental setup

Datasets: OpenR1-Math-220k Sokoban BabyAI DeepSeek-R1 successful trajectories

Benchmarks: AIME24 AIME25 AMC23 OlympiadBench MATH500 Minerva Sokoban BabyAI SynthLoc BabyAI OneRoom BabyAI MiniBoss

Metrics: accuracy success rate generated tokens

Baselines: GRPO GiGPO SFT Reinforce-Ada-Est Uniform expert-prefix Base model

Builds on: GRPO GiGPO ReST Reinforce-Ada

Closest papers by meaning

• Reinforcement Learning with Verifiable Rewards: GRPO's Loss, Dynamics, and Success Amplification (ICML 2026 · similarity 0.91)
• Discounted Beta–Bernoulli Reward Estimation for Sample-Efficient Reinforcement Learning with Verifiable Rewards (ICML 2026 · similarity 0.90)
• Shrinking the Variance: Shrinkage Baselines for Reinforcement Learning with Verifiable Rewards (ICML 2026 · similarity 0.89)
• Multi-Step Likelihood-Ratio Correction for Reinforcement Learning with Verifiable Rewards (NeurIPS 2026 · similarity 0.88)
• Your Language Model is Its Own Critic: Reinforcement Learning with Value Estimation from Actor’s Internal States (NeurIPS 2026 · similarity 0.88)
• TIC-GRPO: Provable and Efficient Optimization for Reinforcement Learning from Human Feedback (NeurIPS 2026 · similarity 0.87)