Discounted Beta-Bernoulli Reward Estimation for Sample-Efficient Reinforcement Learning with Verifiable Rewards

Haechan Kim; Soohyun Ryu; Gyouk Chu; Doohyuk Jang; Eunho Yang

cs.LGMar 19, 2026

Discounted Beta-Bernoulli Reward Estimation for Sample-Efficient Reinforcement Learning with Verifiable Rewards

Authors: Haechan Kim, Soohyun Ryu, Gyouk Chu, Doohyuk Jang, Eunho Yang

Organizations: Kim Jaechul Graduate School of AI, KAIST, Daejeon, South Korea · KRAFTON, Seoul, South Korea · AITRICS, Seoul, South Korea

Abstract

Reinforcement learning with verifiable rewards (RLVR) has emerged as an effective post-training paradigm for improving the reasoning capabilities of large language models. However, existing group-based RLVR methods often suffer from severe sample inefficiency. This inefficiency stems from reliance on point estimation of rewards from a small number of rollouts, leading to high estimation variance, variance collapse, and ineffective utilization of generated responses. In this work, we reformulate RLVR from a statistical estimation perspective by modeling rewards as samples drawn from a policy-induced distribution and casting advantage computation as the problem of estimating the reward distribution from finite data. Building on this view, we propose Discounted Beta-Bernoulli (DBB) reward estimation, which leverages historical reward statistics for the non-stationary distribution. Although biased, the resulting estimator exhibits reduced and stable variance, theoretically avoids estimated variance collapse, and achieves lower mean squared error than standard point estimation. Extensive experiments across six in-distribution and three out-of-distribution reasoning benchmarks demonstrate that GRPO with DBB consistently outperforms naive GRPO, achieving average Acc@8 improvements of 3.22/2.42 points in-distribution and 12.49/6.92 points out-of-distribution on the 1.7B and 8B models, respectively, without additional computational cost or memory usage.

Figures & tables

Figure 1: Comparison between point estimation and DBB estimation. By trading a small bias for substantial variance reduction via shrinkage, DBB estimation achieves lower mean squared error. Compared to naive GRPO using point estimation, GRPO with DBB estimation consistently demonstrates superior performance across all benchmarks and both model scales.

	In-Distribution							Out-of-Distribution
Method	MATH500	Minerva	AIME24	AIME25	AMC24	Olympiad	Avg.	MMLU-Pro	GPQA-D	BBH	Avg.
Qwen3-8B-Base trained with DAPO-Math-17k
GRPO	87.87 $\pm$ 0.36	39.34 $\pm$ 0.29	29.17 $\pm$ 0.68	25.31 $\pm$ 2.16	57.71 $\pm$ 1.44	54.54 $\pm$ 0.19	48.99 $\pm$ 0.46	50.16 $\pm$ 0.33	45.27 $\pm$ 1.69	59.18 $\pm$ 0.33	51.54 $\pm$ 0.55
RePO	86.22 $\pm$ 0.31	35.02 $\pm$ 0.47	27.29 $\pm$ 0.80	23.44 $\pm$ 1.04	56.25 $\pm$ 0.70	52.70 $\pm$ 0.44	46.82 $\pm$ 0.07	53.29 $\pm$ 0.55	46.34 $\pm$ 1.74	42.44 $\pm$ 0.30	47.35 $\pm$ 0.80
GRESO	87.01 $\pm$ 0.20	33.88 $\pm$ 0.60	27.36 $\pm$ 0.79	22.78 $\pm$ 1.09	57.31 $\pm$ 0.57	52.81 $\pm$ 0.17	46.86 $\pm$ 0.12	62.81 $\pm$ 0.39	48.53 $\pm$ 0.43	65.17 $\pm$ 0.63	58.83 $\pm$ 0.40
DAPO	86.00 $\pm$ 0.07	37.08 $\pm$ 0.30	31.06 $\pm$ 1.19	21.02 $\pm$ 1.14	52.67 $\pm$ 0.92	51.64 $\pm$ 0.14	46.58 $\pm$ 0.16	59.28 $\pm$ 0.67	45.05 $\pm$ 1.79	63.41 $\pm$ 0.29	55.91 $\pm$ 0.46

Table 1: In-distribution (ID) and out-of-distribution (OOD) evaluation results trained on DAPO-Math-17k. For a fair comparison, all methods are trained with the same total number of rollouts. Evaluation is conducted over four independent runs with Acc@8 per run (i.e., 32 responses per prompt in total); each cell reports mean

\pm

standard deviation across the four runs.

\Delta

rows report the absolute Acc@8 improvement of GRPO-DBB over each baseline together with a one-sided paired

t

-test

p

-value (

H_{1}

: GRPO-DBB

>

baseline).

Qwen3-8B-Base trained with DAPO-Math-17k
Method	MATH500	Minerva	AIME24	AIME25	AMC24	Olympiad	Avg.
$\lambda=1.0$	89.08	37.91	33.33	26.25	59.44	55.19	50.20
$\lambda=0.75$	88.71	39.46	33.60	29.02	60.54	56.53	51.31
$\lambda=0.5$	89.35	38.56	33.33	27.08	59.17	56.19	50.61
$\lambda=0.25$	88.82	39.98	30.83	25.83	60.83	56.34	50.44
GRPO	87.87	39.34	29.17	25.31	57.71	54.54	48.99

Table 2: Effect of the discount factor

\lambda

of GRPO-DBB on in-distribution Acc@8 performance. Qwen3-8B-Base achieves the best performance at

\lambda=0.75

, while Qwen3-1.7B-Base performs best at

\lambda=0.5

Figure 2: Training dynamics of naive GRPO and GRPO with the DBB estimator (GRPO-DBB) on Qwen3-1.7B-Base (top) and Qwen3-8B-Base (bottom). GRPO-DBB achieves higher validation Acc@8 and training rewards, while maintaining longer responses with controlled entropy compared to GRPO, indicating more stable exploration during training.

Figure 3: MSE as a function of the discount factor

\lambda

and the number of rollouts

N

. The DBB estimator yields lower MSE than the point estimator across a wide range of

\lambda

, and it achieves lower MSE for rollout budgets up to

N=16

when

\lambda=0.4

Qwen3-1.7B-Base trained with DAPO-Math-17k
Method	MATH500	Minerva	AIME24	AIME25	AMC24	Olympiad	Avg.
Dr.GRPO	69.00	25.14	9.17	7.92	23.89	32.78	27.98
Dr.GRPO-DBB	70.60	26.15	12.08	9.17	28.06	33.59	29.94
$\Delta$ w.r.t. Dr.GRPO	+1.60	+1.01	+2.92	+1.25	+4.17	+0.81	+1.96

Table 3: In-distribution evaluation results on Qwen3-1.7B-Base trained with DAPO-Math-17k. We apply the proposed discounted Beta–Bernoulli reward distribution estimation to the advantage term of Dr.GRPO and observe consistent performance improvements.

\Delta

denotes the absolute Acc@8 improvement over naive Dr.GRPO.

Appendix figures & tables8 assets

Supplementary material from the paper’s appendix.

Appendix

	Point Estimation	DBB Estimation
$X_{\tau,i}$	$X_{\tau,i}\sim\mathrm{Bern}(p_{\tau})$	$X_{\tau,i}\sim\mathrm{Bern}(p_{\tau})$
$p_{\tau}$	fixed but unknown	$p_{\tau}\sim\mathrm{Beta}(\alpha_{\tau},\beta_{\tau})$
$\hat{p}_{\tau}$	$\displaystyle\hat{p}_{\tau}^{\mathrm{pt}}=\frac{1}{N}\sum_{i=1}^{N}X_{\tau,i}$	$\displaystyle\hat{p}_{\tau}^{\mathrm{dbb}}=\frac{\alpha_{\tau}}{\alpha_{\tau}+\beta_{\tau}}$
$\widehat{\mathrm{Var}}(X_{\tau})$	$\displaystyle\frac{N}{N-1}\,\hat{p}_{\tau}^{\mathrm{pt}}\!\left(1-\hat{p}_{\tau}^{\mathrm{pt}}\right)$	$\displaystyle\hat{p}_{\tau}^{\mathrm{dbb}}\!\left(1-\hat{p}_{\tau}^{\mathrm{dbb}}\right)$
$\mathbb{E}[\hat{p}_{\tau}]$	$p_{\tau}$	$w\mu_{\tau-1}+(1-w)p_{\tau}$
$\mathrm{Bias}(\hat{p}_{\tau})$	$0$	$w(\mu_{\tau-1}-p_{\tau})$

Appendix

Table 4: Comparison between point estimation and DBB estimation for reward distribution modeling. We denote the Bernoulli distribution by

\mathrm{Bern}(\cdot)

Training Configuration
Hyperparameter	Qwen3-1.7B-Base	Qwen3-8B-Base
Training batch size	128	128
Mini-batch size	64	64
Number of epochs	4	4
Total gradient steps	1080	1080
Samples per prompt	8	8

Appendix

Table 5: Common training hyperparameter settings for all experiments.

Figure 4: Training dynamics of Qwen3-1.7B-Base with GRPO and GRPO-DBB under clipping ranges $(0.2,0.28)$ and $(0.98,0.98)$ . From left to right: (a) validation Acc@8, (b) policy-gradient clip fraction, (c) gradient norm, and (d) policy-gradient loss. GRPO-DBB suffers excessive clipping under the standard range; once the range is widened, it recovers strong performance. GRPO under the wider range shows no improvement, confirming that the gains of GRPO-DBB are due to the DBB estimator rather than the clip range.

Figure 5: (a) Heatmap of $\min_{\lambda}\mathrm{MSE}$ of the DBB estimator over $(\alpha_{0},\beta_{0})$ . (b) MSE versus $\lambda$ for selected priors. The default symmetric prior $(\alpha_{0},\beta_{0})=(1,1)$ is competitive with the best prior and robust over a wide range of $\lambda$ .

Figure 6: Validation performance of Qwen3-1.7B-Base (top) and Qwen3-8B-Base (bottom) trained with GRPO and GRPO-DBB. The left column shows Mean@8 (= Acc@8) and the right column shows Best@8 on the validation set. Despite producing lower entropy during training, GRPO-DBB matches or exceeds GRPO in Best@8 across both model scales.

Qwen3-0.6B-Base trained with DAPO-Math-17k
Method	MATH500	Minerva	AIME24	AIME25	AMC24	Avg.
$\lambda=1.0$	47.12	14.25	2.92	0.00	10.83	15.02
$\lambda=0.75$	48.05	14.52	2.08	0.42	10.28	15.07
$\lambda=0.5$	47.95	14.11	2.08	1.25	11.94	15.47
$\lambda=0.25$	49.98	14.15	3.33	1.67	8.61	15.55

Appendix

Table 6: Effect of the discount factor

\lambda

of GRPO-DBB on in-distribution Acc@8 performance for Qwen3-0.6B-Base trained on DAPO-Math-17k. The best average performance is attained at

\lambda=0.25

Figure 7: MSE versus $\lambda$ for per-prompt exponential moving average (EMA), Laplace smoothing (Laplace), point estimator (GRPO), and DBB estimator (GRPO-DBB). The DBB estimator attains the lowest minimum MSE at $\lambda=0.4$ and improves on the point estimator over a broader range of $\lambda$ than EMA or Laplace.

Figure 8: MSE versus $\lambda$ for the Empirical Bayes estimator with online method-of-moments (EB), point estimator (GRPO), and DBB estimator (GRPO-DBB). EB improves over the point estimator without per-prompt tuning, but DBB attains a lower minimum MSE.

Reinforcement Learning

Reinforcement learning studies how agents learn sequential decisions from rewards and interaction, balancing exploration, performance, safety, and adaptation.

See all 1,661 papers

Non-vacuous Generalization Bounds for Reinforcement Learning with Verifiable Rewards
Jul 16, 2026Yuxuan Zhu, Rohan Alur, Daniel KangPAC-Bayesian Generalization Bounds Reinforcement Learning with Verifiable Rewards
UIUC · MIT · Bridgewater AIA Labs
Double-Rollout Reinforcement Learning with Sampling-based Reward Estimation
Oct 12, 2026Haifeng Qian, David Mosallanezhad, Christian Munley +2Reinforcement Learning RL for Language Model Reasoning
NVIDIA, 2788 San Tomas Expressway, Santa Clara, CA 95051, USA
MaPP: A Unified Marginalized Posterior-Predictive Framework for Data-Efficient RLVR
Sep 28, 2026Yangyang Ren, Haodong Zhu, Sheng Xu +4Prompt Selection for RL Bayesian RL
Beihang University · Zhongguancun Academy · Communication University of China +4

Jul 16, 2026J/K move · Enter open · S save

Non-vacuous Generalization Bounds for Reinforcement Learning with Verifiable Rewards

Yuxuan Zhu, Rohan Alur, Daniel Kang

UIUC · MIT · Bridgewater AIA Labs

PAC-Bayesian Generalization Bounds Reinforcement Learning with Verifiable Rewards RL Fine-Tuning Generalization in RL Parameter-Efficient Fine-Tuning

Open paper AskPDF arXiv

While reinforcement learning with verifiable rewards (RLVR) is widely used to improve the reasoning capabilities of large language models (LLMs), the generalizability of the resulting models remains poorly understood. In this work, we establish the first non-vacuous generalization bounds for parameter-efficient RLVR fine-tuning at the billion-parameter scale. Our approach adapts PAC-Bayes compression bounds to this setting, and addresses the inherent stochasticity of token generation by applying the Gumbel-max reparameterization trick. To operationalize these bounds, we propose the Progressive RLVR framework, which integrates RLVR with on-policy distillation, TinyLoRA, and model quantization. Progressive RLVR empirically retains 84-97% performance of standard LoRA fine-tuning while producing models that are 14,796x more compressible. We show that this framework yields non-vacuous generalization bounds in four domains: mathematical problem-solving, programming, general-knowledge reasoning, and Text-to-SQL. Our bounds exceed the accuracy of the base model by 9-51% and lie within 6-11% of the accuracy of the fine-tuned models.

Abstract

Reinforcement Learning

Explore similar work

Non-vacuous Generalization Bounds for Reinforcement Learning with Verifiable Rewards

Double-Rollout Reinforcement Learning with Sampling-based Reward Estimation

MaPP: A Unified Marginalized Posterior-Predictive Framework for Data-Efficient RLVR