Adaptive Rollout Allocation for Online Reinforcement Learning with Verifiable Rewards Hieu Trung Nguyen, Bao Nguyen, Wenao Ma, Yuzhi Zhao, Ruifeng She, Viet Anh Nguyen Abstract Sampling efficiency is a key bottleneck in reinforcement learning with verifiable rewards. Existing group-based policy optimization methods, such as GRPO, allocate a fixed number of rollouts for all training prompts. This uniform allocation implicitly treats all prompts as equally informative, and could lead to inefficient computational budget usage and impede training progress. We introduce VIP, a Variance-Informed Predictive allocation strategy that allocates a given rollout budget to the prompts in the incumbent batch to minimize the expected gradient variance of the policy update. At each iteration, VIP uses a lightweight Gaussian process model to predict per-prompt success probabilities based on recent rollouts. These probability predictions are translated into variance estimates, which are then fed into a convex optimization problem to determine the optimal rollout allocations under a hard compute budget constraint. Empirical results show that VIP consistently improves sampling efficiency and achieves higher performance than uniform or heuristic allocation strategies in multiple benchmarks. Our code will be available at https://github.com/HieuNT91/VIP 1 Introduction The advent of Language Models (LMs) has marked a new era in artificial intelligence, transforming models from static knowledge bases into dynamic, intelligent agents capable of complex reasoning, creative generation, and intricate problem-solving. This evolution has been largely driven by the advancement of post-training methodologies, which are crucial for aligning a base LM’s vast, general knowledge with specific human intentions, ethical guidelines, and desired task-oriented behaviors. These refinement processes bridge the gap between a model that understands language and one that can reliably and safely act as a collaborator, assistant, or autonomous agent. As LMs become more integrated into real-world applications, the effectiveness and efficiency of these post-training stages have become a primary focus of research and development. Two prominent paradigms are used for post-training LMs: Supervised Fine-Tuning (SFT) and Reinforcement Learning (RL). SFT is a computationally efficient approach that trains the model on a curated dataset of input-output pairs, effectively equipping it with domain-specific knowledge. However, its effectiveness is often hampered by the difficulty of curating high-quality and comprehensive datasets. In contrast, RL-based methods, which treat the model as an agent optimizing for a reward signal derived from human preferences (Reinforcement Learning from Human Feedback, RLHF) or external verification mechanisms (Reinforcement Learning from Verifiable Rewards, RLVR), can explore a broader action space and achieve superior performance on complex, open-ended tasks. RLVR, in particular, has gained wide popularity thanks to its low reliance on human input. However, the performance of RL methods comes at a significant computational cost. Algorithms like Proximal Policy Optimization (PPO, 17 ) require the simultaneous training of a separate value model to estimate the advantage of actions, which can be prohibitively memory-intensive in resource-constrained situations. To address this, a family of “critic-free” or group-based RL methods has emerged, estimating the advantage as a relative measure within a group of rollouts, essentially trading speed for memory efficiency. Such methods include GRPO, ( 18 ) , Dr. GRPO ( 14 ) , RLOO ( 1 ) , and other variants. A direct drawback of these methods is the additional computation time required to generate multiple rollouts for a training example. The number of generations often needs to be large enough (e.g., 16) to obtain a stable training process, which exacerbates the generation overhead and eventually leads to a memory-bound system. Such high computational demands consequently highlight the need for greater sampling efficiency in the RL training process. The high computational demands of RL algorithms have led to a body of work dedicated to optimizing this performance-cost trade-off. One line of research involves hybrid approaches that combine an initial SFT phase with a subsequent RL refinement stage ( 2 ) or merge the two stages into a single method ( 5 ) . These methods demonstrated improvement in smoothening or even accelerating the training process, but often fail to dynamically adapt to the training process based on the model’s evolving capabilities for solving the training problems. The observation that simply filtering out problems where the accuracy is close to either 0 or 1 can boost performance ( 27 ) hints at the potential for more adaptive control. To the best of our knowledge, there is a lack of crucial metrics for such capabilities and, consequently, a lack of an adaptive control mechanism for the GRPO process. To address such challenges, we introduce the Variance-Informed Predictive allocation strategy (VIP), a principled training framework for efficient and adaptive rollout allocation in group-based policy optimization. We first provide a theoretical analysis of the gradient variance for three prominent RL algorithms, establishing the relationship between the gradient variance contributed by a prompt and the probability that it is solved by the current model. Building on this insight, at the beginning of each training iteration, VIP predicts the expected gradient variance of each prompt in a mini-batch. Based on these predictions, VIP then solves a convex optimization problem followed by integer rounding heuristic to allocate rollouts across prompts to minimize the total expected gradient variance under the given computational budget. The core contributions of this paper are the following: • Gradient variance analysis. We provide a rigorous analysis of the effect of gradient variance on the RL training process. We derive the connection between gradient variance and success probability for prevailing group-based RL methods, including Dr. GRPO and RLOO. This establishes the theoretical foundation for adaptively controlling budget allocation during training. • Variance prediction. VIP employs a Gaussian process (GP) over prompt embeddings to model the probability of success for each prompt in any training step. This enables recursive Bayesian updates that leverage both past rollout outcomes and the similarity structure of the prompts. The GP prediction allows the framework to estimate the gradient variance for each prompt in the minibatch at every training step. • Variance-minimizing rollout allocation. Given the predicted variances, VIP formulates a convex optimization problem to determine the optimal allocation of rollouts on prompts. This allocation minimizes the gradient variance subject to a rollout budget constraint. We derive an efficient algorithm that provides the exact solution to the continuous relaxation and further develop a greedy incentive-based rounding heuristic to produce a feasible integer solution. This process enables fast resource allocation under computational budget constraints. Our paper unfolds as follows. Section 2 discusses related work on adaptive strategies over group-based RL frameworks for RLVR, while Section 3 lays the technical background on RLVR. Section 4 presents our analysis of the per-prompt gradient variance. Section 5 delineates our VIP framework for variance prediction via Gaussian process, and the optimization problem for rollout allocation. Section 6 presents empirical results on mathematical reasoning and information retrieval datasets. 2 Related Work Recent advancements in group-based RL for LMs have focused on adaptive strategies to enhance both training efficiency and performance. These methods move beyond static training pipelines by dynamically selecting and managing data used for policy updates. Initial research empirically demonstrated that filtering out “non-informative” problems to which the model’s accuracy is either 0 or 1 can improve training efficiency, as these problems lead to rollout batches with zero variance and consequently make no contribution to the gradient signal ( 27 ) . Along similar lines, ( 13 ) filtered out rollouts with low absolute advantage, while ( 25 ) proposed to retain examples with the highest variance. Lacking an a priori measure of training prompt informativeness, these methods require the pre-sampling of an large batch of rollouts before each update iteration, potentially negating efficiency gains from the significant sampling overhead. Several works adopted a pre-rollout estimation of the prompt informativeness. ( 29 ) proposed skipping each problem with a probability determined by the number of recent consecutive rollouts where the prompt is non-informative. ( 28 ) proposed a signal-to-noise ratio indicating a problem’s contribution to the gradient, and showed that training can be accelerated by generating a small trial batch of rollouts to identify and filter out non-informative problems, and then continue sampling on intermediate-difficulty ones. ( 22 ) designed a difficulty-targeted online selection algorithm with attention-based difficulty prediction and rollout replay. ( 12 ) ranked problems by difficulty, indicated by the average rewards from past rollouts, and allocated resources to sample larger batches for difficult prompts. ( 26 ) took a similar approach as ( 28 ) to estimate problem difficulty, and assigned a larger budget and higher gradient weights to difficult prompts. ( 9 ) estimates prompt difficulty by aggregating historical performance discrepancies of the problems, then adaptively selects the set of problems whose difficulty is in alignment with the current competence of the model. Other works also considered the entropy-reward trade-off to mitigate the risk of premature convergence. ( 12 ) combined difficulty-aware reallocation with entropy-stabilizing temperature scheduling to effectively balance efficiency and exploration. Another approach steers exploration by maximizing information gain throughout the training process ( 11 ) . 3 Background on RLVR We study the prominent family of methods for RL training that employs group-based advantage estimation to stabilize learning and better utilize reward signals. This family includes Group Relative Policy Optimization (GRPO) ( 18 ) and its variants, such as Dr. GRPO ( 14 ) and RLOO ( 1 ) . Given a dataset of Q prompts \mathcal{Q}=\{q_{1},q_{2},\dots,q_{Q}\} , the general objective function for group-based policy optimization methods is \displaystyle J(\theta) \displaystyle=\mathbb{E}_{q\sim\mathcal{Q}}\mathbb{E}_{\pi_{\mathrm{old}}^{\otimes n}}\Bigg[\frac{1}{n}\sum_{j=1}^{n}\frac{1}{|\tilde{o}_{j}|}\sum_{\tau=1}^{|\tilde{o}_{j}|}\Big(A^{\prime}_{j,\tau}-\beta\,D_{\mathrm{KL}}\big(\pi_{\theta}(\cdot\mid q,\tilde{o}_{j,<\tau})\,\big\|\,\pi_{\mathrm{ref}}(\cdot\mid q,\tilde{o}_{j,<\tau})\big)\Big)\Bigg], (1) where n is the number of rollouts for each prompt, \tilde{o}_{j} is the j -th rollout from policy \pi_{\mathrm{old}} , |\tilde{o}_{j}| is the number of tokens in \tilde{o}_{j} , and \pi_{\theta} is the current policy with its learnable parameters \theta . Here, D_{\mathrm{KL}}\left(\pi_{\theta}(\cdot\mid q,\tilde{o}_{j,<\tau})\,\|\,\pi_{\mathrm{ref}}(\cdot\mid q,\tilde{o}_{j,<\tau})\right) is the Kullback-Leibler divergence between the policy \pi_{\theta} and a reference policy \pi_{\mathrm{ref}} , both of which are conditioned on the prompt q and the tokens generated thus far \tilde{o}_{j,<\tau} . We use a tilde ( \sim ) to emphasize the stochastic nature of the quantities. For prompt q , the term A^{\prime}_{j,\tau} is the normalized or advantage-shaped reward at token \tau for output \tilde{o}_{j} : A^{\prime}_{j,\tau}=\min\left(r_{j,\tau}\tilde{A}_{j,\tau},\;\operatorname{clip}(r_{j,\tau},1-\epsilon,1+\epsilon)\,\tilde{A}_{j,\tau}\right),~~\text{with}\quad r_{j,\tau}(\theta)=\frac{\pi_{\theta}(\tilde{o}_{j,\tau}\mid q,\tilde{o}_{j,<\tau})}{\pi_{\mathrm{old}}(\tilde{o}_{j,\tau}\mid q,\tilde{o}_{j,<\tau})}. (2) Notice that we momentarily omit the index q to avoid clutter. Here, r_{j,\tau} is the relative ratio between current and data-generating policies; while \tilde{A}_{j,\tau} is the advantage estimator for token \tau in output \tilde{o}_{j} . Let R(\tilde{o}_{j}) be the reward for output \tilde{o}_{j} on prompt q , taking values of -1 (incorrect) or 1 (correct). Based on the whole set of n rollouts \{\tilde{o}_{j}\} , there are two popular advantage estimators: • In Dr. GRPO ( 14 ) , \tilde{A}_{j}=\tilde{A}_{j,\tau}=R(\tilde{o}_{j})-\frac{1}{n}\sum_{k}R(\tilde{o}_{k}) , which uses all rollouts to compute the mean. • In RLOO ( 1 ) , \tilde{A}_{j}=\tilde{A}_{j,\tau}=R(\tilde{o}_{j})-\frac{1}{n-1}\sum_{k\neq j}R(\tilde{o}_{k}) , which excludes the j -th output when computing the mean. Both advantage estimators are token-independent: all tokens in the j -th rollout admit the same advantage \tilde{A}_{j} . In this paper, we will focus on a particular training regime under the next assumption. Assumption 3.1 . We set the KL regularization term to zero, i.e., \beta=0 . Assumption 3.1 is both practical and non-restrictive for the following reasons. In RLHF, reward models are only reliable near the distribution of the reference policy ( 6 ; 3 ; 7 ; 16 ) , which makes KL regularization essential to prevent reward hacking ( 10 ; 21 ; 20 ) . In contrast, our work focuses on the RLVR setting, where rewards are computed by rule-based verifiers. These verifiable rewards eliminate concerns about reward miscalibration. Indeed, recent studies in RLVR have successfully removed the KL term while still achieving state-of-the-art performance ( 27 ; 14 ) . Assumption 3.1 simplifies the training objective by eliminating the KL term. The objective function reduces to: J(\theta)=\mathbb{E}_{q\in\mathcal{Q}}\mathbb{E}_{\pi_{\text{old}}^{\otimes n}}\Bigg[\frac{1}{n}\sum_{j=1}^{n}\frac{1}{|\tilde{o}_{j}|}\sum_{\tau=1}^{|\tilde{o}_{j}|}\min\left(r_{j,\tau}\tilde{A}_{j},\;\operatorname{clip}(r_{j,\tau},1-\epsilon,1+\epsilon)\,\tilde{A}_{j}.\right)\Bigg] Whenever r_{j,\tau} falls outside the clipping region in a direction that worsens the surrogate, \min\Big(r_{j,\tau}\tilde{A}_{j},\;\operatorname{clip}(r_{j,\tau},1-\epsilon,1+\epsilon)\,\tilde{A}_{j}\Big) collapses to the clipped term and contributes no gradient. To isolate precisely when the gradient is active, we introduce the indicator \mathbb{I}^{\text{unc}}_{j,\tau}=1-\Big(\mathbf{1}\{r_{j,\tau}>1+\varepsilon\}\,\mathbf{1}\{\tilde{A}_{j}\geq 0\}+\mathbf{1}\{r_{j,\tau}<1-\varepsilon\}\,\mathbf{1}\{\tilde{A}_{j}<0\}\Big). Using this indicator, we define \bar{r}_{j}=\frac{1}{|\tilde{o}_{j}|}\sum_{\tau=1}^{|\tilde{o}_{j}|}\mathbb{I}^{\text{unc}}_{j,\tau}\,r_{j,\tau} and rewrite the objective as: J(\theta)=\mathbb{E}_{q\in\mathcal{Q}}\mathbb{E}_{\pi_{\mathrm{old}}^{\otimes n}}\left[\frac{1}{n}\sum_{j=1}^{n}\tilde{A}_{j}\bar{r}_{j}\right]=\mathbb{E}_{q\in\mathcal{Q}}\mathbb{E}_{\pi_{\mathrm{old}}^{\otimes n}}\left[\frac{1}{n}\sum_{j=1}^{n}A_{j}(\{\tilde{o}_{k}\})\bar{r}_{j}\right]. (3) The next section studies the gradient variance of J . 4 Analysis for Gradient Variance In this section, we analyze the variance of the gradient estimator arising from sampling rollouts in RLVR algorithms such as GRPO and RLOO. Each update step combines two types of data: previously collected rollouts from past batches (off-policy) and newly generated rollouts for the current batch of prompts \mathcal{B} (on-policy). However, as discussed in the subsequent Section 5 , our research objective is to determine how many rollouts should be allocated to the prompts in \mathcal{B} . This allocation decision influences only the on-policy component of the gradient. The off-policy contributions, while present in the overall update, are determined entirely by past data and therefore remain unaffected by the number of new rollouts we choose to sample. Consequently, to understand how allocation impacts gradient variance, it is both natural and sufficient to isolate the variance arising from the on-policy rollouts generated by the current policy \pi_{\theta} . For these on-policy samples, the behavior and target policies coincide \pi_{\mathrm{old}}=\pi_{\theta} , hence \bar{r}_{j}=1 . The gradient contribution of these on-policy rollouts is: \displaystyle\nabla_{\theta}J^{\mathrm{on}}(\theta) \displaystyle=\mathbb{E}_{q\in\mathcal{B}}\mathbb{E}_{\pi_{\theta}^{\otimes n}}\Bigg[\frac{1}{n}\sum_{j=1}^{n}A_{j}(\{\tilde{o}_{k}\})\underbrace{\frac{1}{|\tilde{o}_{j}|}\sum_{\tau=1}^{|\tilde{o}_{j}|}\nabla_{\theta}\log\pi_{\theta}(\tilde{o}_{j,\tau}|q,\tilde{o}_{j,<\tau})}_{\triangleq H(\tilde{o}_{j})}\Bigg]. (4) Above, H(\tilde{o}_{j}) is the average log-likelihood gradient, where the average is taken over all tokens in the j -th rollout. Consider a specific prompt q and the n rollouts \{\tilde{o}_{k}\} , the contribution of q to the calculation of the sample gradient is \frac{1}{n}\sum_{j=1}^{n}A_{j}(\{\tilde{o}_{k}\})H(\tilde{o}_{j}) , and we omit the subscript q to avoid clutter. This quantity is a random vector because H(\tilde{o}_{j}) is a random vector. We will study the projected gradient, obtained by projecting H(\tilde{o}_{j}) onto the vector \mathbbm{1} of all ones. To this end, we are interested in the (univariate) random variable: \tilde{G}\triangleq\frac{1}{n}\sum\nolimits_{j=1}^{n}A_{j}(\{\tilde{o}_{k}\})\mathbbm{1}^{\top}H(\tilde{o}_{j}). To simplify the notation, we define the random variables \tilde{R}_{j}=R(\tilde{o}_{j}) and \tilde{Z}_{j}=\mathbbm{1}^{\top}H(\tilde{o}_{j}) for all j . We first consider the Dr. GRPO case. The gradient \tilde{G} has the specific form: \tilde{G}\triangleq\frac{1}{n}\sum\nolimits_{j=1}^{n}\big(\tilde{R}_{j}-\frac{1}{n}\sum\nolimits_{k=1}^{n}\tilde{R}_{k}\big)\tilde{Z}_{j}. To have a rigorous analysis of the variance of \tilde{G} , we make the following assumption explicitly. Assumption 4.1 . (i) \tilde{R}_{1},\ldots,\tilde{R}_{n} are independent and identically distributed (i.i.d.) copies of \tilde{R} , and \tilde{Z}_{1},\ldots,\tilde{Z}_{n} are also i.i.d. copies of \tilde{Z} , (ii) \{\tilde{Z}_{j}\} and \{\tilde{R}_{j}\} are uncorrelated up to second-order: \mathrm{Cov}(\tilde{R}_{k},\tilde{Z}_{j})=0 for any (k,j) and \mathrm{Cov}(\tilde{R}_{k}\tilde{R}_{k^{\prime}},\tilde{Z}_{j}\tilde{Z}_{j^{\prime}})=0 for any (k,j,k^{\prime},j^{\prime}) Assumption 4.1 is realistic in common settings: given the same prompt and fixed sampling procedure, different rollouts are independent samples from the same distribution \pi_{\theta} . Thus, it is reasonable to assume that \{\tilde{o}_{j}\} are i.i.d., which induces Assumption 4.1 (i). Assumption 4.1 (ii) needs further justification because for the j -th rollout, the reward \tilde{R}_{j} may be correlated with the average gradient \tilde{Z}_{j} . However, we have strong reasons to believe that it holds because \tilde{R} is a Bernoulli distribution, and \tilde{Z}_{j} has a doubly-averaging nature over the number of tokens (from the definition of H(\tilde{o}_{j}) ) and over the number of dimensions in the gradient vector (from \mathbbm{1}^{\top}H(\tilde{o}_{j}) ). Empirically, we include in Appendix B a statistical test to support our assumption. The next result establishes the variance for the Dr. GRPO case. Proposition 4.2 (Dr. GRPO gradient variance) . Consider a prompt with binary reward R(\tilde{o}_{j})\in\{1,-1\} with \mathbb{P}(R(\tilde{o}_{j})=1)=p . If Assumption 4.1 holds and the variance of the projected gradient \tilde{Z} is \sigma_{Z}^{2} , the variance of the per-prompt projected Dr. GRPO gradient estimator with n rollouts is \mathrm{Var}(\tilde{G})=\frac{(n-1)}{n^{2}}4\sigma_{Z}^{2}p(1-p). We now switch gears to the RLOO case. The RLOO gradient \tilde{G} has the specific form: \tilde{G}\triangleq\frac{1}{n}\sum\nolimits_{j=1}^{n}\big(\tilde{R}_{j}-\frac{1}{n}\sum\nolimits_{\begin{subarray}{c}k=1\\ k\neq j\end{subarray}}^{n}\tilde{R}_{k}\big)\tilde{Z}_{j}. Proposition 4.3 (RLOO gradient variance) . Consider a prompt with binary reward R(\tilde{o}_{j})\in\{1,-1\} with \mathbb{P}(R(\tilde{o}_{j})=1)=p . If Assumption 4.1 holds and the variance of the projected gradient \tilde{Z} is \sigma_{Z}^{2} , the variance of the per-prompt projected RLOO gradient estimator with n rollouts is \mathrm{Var}(\tilde{G})=\frac{1}{n-1}4\sigma_{Z}^{2}p(1-p). 5 Predictive rollout Allocation Strategy Consider a specific iteration t when we have drawn a mini-batch \mathcal{B}_{t} from the set of training prompts. Propositions 4.2 - 4.3 indicate that the gradient variance for a prompt depends on the number of rollouts. Consequently, a uniform allocation of n rollouts for every prompt could be inefficient. Section 4 reveals that the per-prompt gradient variance depends on the success probability p_{q} , which is the probability that model \theta_{t} answers prompt q correctly. However, this probability is not observable ex ante without performing rollouts, and we need to resort to an estimate \hat{p}_{q} to make allocation decisions. Building an estimator for the success probability is challenging for at least two reasons: First, the success probability is, unfortunately, not static: it depends on the model weights, which evolve after every training iteration. As the weights are updated, the distribution over the outputs changes, and consequently, the success probability drifts. Second, prompt embeddings may not contain sufficiently informative signal for parametric classifiers. To improve rollout efficiency, we propose VIP, the Variance-Informed Predictive allocation strategy, which minimizes the minibatch gradient variance by allocating a different number of rollouts \{n_{q}\} for each prompt in the minibatch. The complete workflow of VIP, from prediction to optimized rollout allocation, is illustrated in Figure 1 . VIP comprises two main components: (i) a nonparametric Gaussian process model for predicting the success probability of the current model on each training prompt (green boxes), and (ii) an optimization model for making optimal allocation decisions given the computing budget (blue box). At the beginning of iteration t , we first predict the success probability for all q\in\mathcal{B}_{t} , as described in Section 5.1 . The probability estimates serve as input to our optimization framework for allocating rollouts across prompts in Section 5.2 . Figure 1: The process starts with an initial belief over prompt success probabilities. At each step t , a mini-batch \mathcal{B}_{t} is selected, and the belief function m_{t}(\cdot) predicts the success probabilities of the prompts in \mathcal{B}_{t} . A budget allocation module assigns rollout budgets \{n_{q}\} , rollouts are generated, and the resulting data updates the model and beliefs. Repeated for T steps, this yields a fine-tuned model \pi_{\theta_{T+1}} with improved performance and efficient rollout usage. 5.1 GP Prior and Recursive Posterior Update Given the training prompts \mathcal{Q}=\{q_{1},q_{2},\dots,q_{Q}\} , we denote their embeddings as \mathcal{D}=\{x_{q}\}_{q=1}^{Q} . At every iteration t , the success probability of the current model on prompt q is modeled using a sigmoid link function on the latent value g_{t}(x_{q}) : p_{q,t}=\mathrm{sigmoid}(g_{t}(x_{q}))=1/[1+\exp(-g_{t}(x_{q}))]\in(0,1), where g_{t}:\mathbb{R}^{d}\to\mathbb{R} is a latent function over prompt embeddings. Because g_{t} is real-valued, it is simpler to place a Gaussian process on g_{t} . Toward this goal, we set g_{t}\sim\mathrm{GP}(m_{t}(\cdot),\mathcal{K}(\cdot,\cdot)) , where m_{t} is the mean function and \mathcal{K} is a radial basis function (RBF) kernel with bandwidth h>0 : \mathcal{K}(x,x^{\prime})=\exp(-\|x-x^{\prime}\|_{2}^{2}/(2h^{2})) . Initialization. At t=1 , we use a zero-mean prior g_{1}\sim\mathrm{GP}(0,\mathcal{K}) . Over the dataset \mathcal{D}=\{x_{q}\}_{q=1}^{Q} , this gives g_{1}(\mathcal{D})\sim\mathcal{N}(0,\Sigma) where \Sigma=\mathcal{K}(\mathcal{D},\mathcal{D}) is the kernel matrix over all prompts. Prediction. At iteration t , the prior m_{t} is used to predict \hat{p}_{q,t}=\mathrm{sigmoid}(m_{t}(x_{q})) for q\in\mathcal{B}_{t} . These predicted values will be sent to the optimization problem to compute the rollout allocation. Sequential updates. At iteration t\geq 1 , the latent values for all prompts are captured by a random vector [g_{t}(x_{1}),\dots,g_{t}(x_{Q})]^{\top}\sim\mathcal{N}(m_{t},\Sigma) . For q\in\mathcal{B}_{t} , we observe n_{q} rollouts and rewards \tilde{R}_{q,j}\in\{-1,1\} for j=1,\ldots,n_{q} . Then, we compute the clipped average: \bar{R}_{q}=\frac{1}{n_{q}}\sum\nolimits_{j=1}^{n_{q}}\tilde{R}_{q,j}\in[-1,1],\quad\hat{p}_{q,t}=\mathrm{clip}\!\big(\frac{\bar{R}_{q}+1}{2},\epsilon,1-\epsilon\big)\in(\epsilon,1-\epsilon), which induces an observation for the latent value \hat{g}_{q,t}=\mathrm{sigmoid}^{-1}(\hat{p}_{q,t})\in\mathbb{R} for q\in\mathcal{B}_{t} . Clipping is necessary here to avoid the situation when \bar{R}_{q,t}=-1 or 1 , which leads to infinite values for the latent variable. The collection of these latent values is denoted \hat{g}_{\mathcal{B}_{t}} . Let \mathcal{B}_{t}^{c} be the complement set containing all prompts that are not in the mini-batch \mathcal{B}_{t} . We can partition the mean vector and the covariance matrix into the block form: m_{t}=\begin{bmatrix}m_{t,\mathcal{B}_{t}}\\ m_{t,\mathcal{B}_{t}^{c}}\end{bmatrix},\qquad\Sigma=\begin{bmatrix}\Sigma_{\mathcal{B}_{t}\mathcal{B}_{t}}&\Sigma_{\mathcal{B}_{t}\mathcal{B}_{t}^{c}}\\ \Sigma_{\mathcal{B}_{t}^{c}\mathcal{B}_{t}}&\Sigma_{\mathcal{B}_{t}^{c}\mathcal{B}_{t}^{c}}\end{bmatrix}, the posterior over unqueried prompts at iteration t is g_{t,\mathcal{B}_{t}^{c}}\mid\hat{g}_{\mathcal{B}_{t}}\sim\mathcal{N}(m_{t}^{\star},\Sigma^{\star}) with m_{t,\mathcal{B}_{t}^{c}}^{\star}=m_{t,\mathcal{B}_{t}^{c}}+\Sigma_{\mathcal{B}_{t}^{c}\mathcal{B}_{t}}\,\Sigma_{\mathcal{B}_{t}\mathcal{B}_{t}}^{-1}\,(\hat{g}_{\mathcal{B}_{t}}-m_{t,\mathcal{B}_{t}}),\quad\Sigma^{\star}=\Sigma_{\mathcal{B}_{t}^{c}\mathcal{B}_{t}^{c}}-\Sigma_{\mathcal{B}_{t}^{c}\mathcal{B}_{t}}\,\Sigma_{\mathcal{B}_{t}\mathcal{B}_{t}}^{-1}\,\Sigma_{\mathcal{B}_{t}\mathcal{B}_{t}^{c}}. Next-step prior. The prior mean at iterate t is updated into the posterior mean as follows: we set m_{t+1}(x_{q})=\hat{g}_{q,t} if q\in\mathcal{B}_{t} and set m_{t+1}(x_{q})=m_{t,\mathcal{B}_{t}^{c}}^{\star}(x_{q}) if q\in\mathcal{B}_{t}^{c} . This posterior mean m_{t+1} will serve as the prior in iteration t+1 . 5.2 Adaptive Budget Allocation for Gradient Variance Minimization Consider a mini-batch \mathcal{B}_{t} of B prompts, and every prompt q\in\mathcal{B}_{t} has a predicted success probability \hat{p}_{q} under the GP model from Section 5.1 . We now focus on deciding the number of rollouts \{n_{q}\} assigned to each prompt in this batch \mathcal{B}_{t} under a hard constraint of a total budget of C rollouts. Additionally, we impose that the number of rollouts should be between a lower bound L and an upper bound U : if the number of rollouts is too small, it is unlikely to obtain discriminative reward signals, while a large number of rollouts may lead to overfitting. For a meaningful setting, we require L\geq 3 , and assume that BL\leq C\leq BU . Our objective is to minimize the sum of the gradient variance induced by prompts in the mini-batch \mathcal{B}_{t} . This problem can be formulated as an integer optimization problem: \min\left\{\sum\nolimits_{q\in\mathcal{B}_{t}}\mathrm{Var}(\tilde{G}_{q})~:~\sum\nolimits_{q\in\mathcal{B}_{t}}n_{q}=C,\quad n_{q}\in\{L,L+1,\ldots,U\}\quad\forall q\in\mathcal{B}_{t}\right\}. (5) The variance \mathrm{Var}(\tilde{G}_{q}) is likely a nonlinear function of the rollout allocation n_{q} , and ( 5 ) becomes a nonlinear integer optimization problem. To tackle this problem, we will first solve its continuous relaxation and then apply a heuristic rounding algorithm. Relaxed Solution for Budget Allocation. Proposition 4.2 provides the per-prompt gradient variance \mathrm{Var}(\tilde{G}_{q}) for Dr. GRPO. By defining a_{q}\triangleq 4\,\sigma_{Z_{q}}^{2}\hat{p}_{q}(1-\hat{p}_{q}) for every q\in\mathcal{B}_{t} , the continuous relaxation of problem ( 5 ) for Dr. GRPO is \min\left\{\sum\nolimits_{q\in\mathcal{B}_{t}}a_{q}\frac{n_{q}-1}{n_{q}^{2}}~:~\sum\nolimits_{q\in\mathcal{B}_{t}}n_{q}=C,\quad L\leq n_{q}\leq U,\quad n_{q}\in\mathbb{R}\ \forall q\in\mathcal{B}_{t}\right\}. (6) The next theorem asserts a computationally efficient method to solve ( 6 ). Theorem 5.1 (Continuous allocation, Dr. GRPO) . For each q\in\mathcal{B}_{t} , let n_{q}^{\star} be the function: n_{q}^{\star}(\lambda)=\begin{cases}U&\text{if }\lambda\leq a_{q}\frac{U-2}{U^{3}},\\[6.0pt] \text{the unique solution to }\lambda=a_{q}\frac{n_{q}-2}{n_{q}^{3}}&\text{if }a_{q}\frac{U-2}{U^{3}}<\lambdaBU or C0 , we have \frac{\partial V}{\partial n_{q}}\leq 0 for all q . Thus, V is decreasing with respect to each n_{q} on the feasible set. For the second derivatives: \frac{\partial^{2}V}{\partial n_{q}\partial n_{q^{\prime}}}=0\quad\forall q\neq q^{\prime},\qquad\frac{\partial^{2}V}{\partial n_{q}^{2}}=2a_{q}\frac{1}{(n_{q}-1)^{3}}>0\quad\forall q Therefore, V is convex and decreasing in each n_{q} on the feasible set \left\{n\in\mathbb{R}^{B}:\sum_{q\in\mathcal{B}_{t}}n_{q}=C,\quad L\leq n_{q}\leq U\right\}. Hence, the minimizer exists and is unique whenever the feasible set is nonempty ( BL\leq C\leq BU ). The Lagrangian function is \mathcal{L}=\sum_{q\in\mathcal{B}_{t}}a_{q}\frac{1}{n_{q}-1}+\lambda\left(\sum_{q\in\mathcal{B}_{t}}n_{q}-C\right)+\sum_{q\in\mathcal{B}_{t}}\mu_{q}(L-n_{q})+\sum_{q\in\mathcal{B}_{t}}\nu_{q}(n_{q}-U) where \lambda\in\mathbb{R} , \mu_{q},\nu_{q}\geq 0 . The KKT conditions are: \displaystyle-a_{q}\frac{1}{(n_{q}-1)^{2}}+\lambda-\mu_{q}+\nu_{q}=0 \displaystyle\forall q \displaystyle\mu_{q}\geq 0,\quad\nu_{q}\geq 0 \displaystyle\forall q \displaystyle\mu_{q}(n_{q}-L)=0,\quad\nu_{q}(n_{q}-U)=0 \displaystyle\forall q \displaystyle L\leq n_{q}\leq U \displaystyle\forall q \displaystyle\sum_{q\in\mathcal{B}_{t}}n_{q}=C. We consider three cases of n_{q} : • For each q with LBU or C and < tool_call > tags . \ The results of the function calls will be given back to you after execution , \ and you can continue to call functions until you get the final answer for the user ’ s question . \ Finally , if you have got the answer , enclose it within \\ boxed {{}} with latex format and do not continue to call functions , \ i . e ., < think > Based on the response from the function call , I get the weather information . The weather in Beijing on 2025-04-01 is \\[ \\ boxed {{20 C }} \\]. For each function call , return a json object with function name and arguments within < tool_call > XML tags : < tool_call > {{" name ": < function - name >, " arguments ": < args - json - object >}} Appendix D Algorithms The algorithm capturing the complete flow the posterior update for the Gaussian Process is provided in Algorithm 1 . Algorithm 1 Recursive GP Posterior Update 0: Mini-batch \mathcal{B}_{t} ; rollout allocation \{n_{q}\}_{q=1}^{\mathcal{B}_{t}} ; prior mean m_{t}(\mathcal{D})\in\mathbb{R}^{Q} , kernel matrix \Sigma\in\mathbb{R}^{Q\times Q} ; 1: for each q\in\mathcal{B}_{t} do 2: # Run n_{q} rollouts and observe outcomes \tilde{R}_{j}\in\{-1,1\} 3: \bar{R}_{q}\leftarrow\frac{1}{n_{q}}\sum_{j=1}^{n_{q}}\tilde{R}_{j} 4: \hat{g}_{q}\leftarrow\mathrm{sigmoid}^{-1}\Big(\mathrm{clip}\left(\frac{\bar{R}_{q}+1}{2},\epsilon,1-\epsilon\right)\Big) 5: end for 6: g_{t}^{\text{observe}}\leftarrow(\hat{g}_{q})_{q\in\mathcal{B}_{t}} 7: Partition m_{t} and \Sigma according to \mathcal{B}_{t} and \mathcal{B}_{t}^{c} 8: m_{t,\mathcal{B}_{t}^{c}}^{\star}\leftarrow m_{t,\mathcal{B}_{t}^{c}}+\Sigma_{\mathcal{B}_{t}^{c}\mathcal{B}_{t}}\Sigma_{\mathcal{B}_{t}\mathcal{B}_{t}}^{-1}(g_{t}^{\text{observe}}-m_{t,\mathcal{B}_{t}}) 9: \Sigma^{\star}\leftarrow\Sigma_{\mathcal{B}_{t}^{c}\mathcal{B}_{t}^{c}}-\Sigma_{\mathcal{B}_{t}^{c}\mathcal{B}_{t}}\Sigma_{\mathcal{B}_{t}\mathcal{B}_{t}}^{-1}\Sigma_{\mathcal{B}_{t}\mathcal{B}_{t}^{c}} 10: for q=1 to Q do 11: if q\in\mathcal{B}_{t} then m_{t+1}(x_{q})\leftarrow\hat{g}_{q} else m_{t+1}(x_{q})\leftarrow m_{t,\mathcal{B}_{t}^{c}}^{\star}(x_{q}) end if 12: end for 13: \hat{p}_{t+1}=\mathrm{sigmoid}(m_{t+1}(\mathcal{D})) 14: return \{\hat{p}_{t+1}\} , m_{t+1} Algorithm 2 presents our heuristic rounding procedure, which maps a continuous solution to a discrete one while ensuring that the budget constraints remain satisfied. Algorithm 2 Heuristic rounding for integer rollout allocation 0: Solution \{n_{q}^{\star}\} , total budget C , bounds \{L,U\} , objective functions f_{q}(\cdot) for each q 1: For each q , set \hat{n}_{q}\leftarrow\lfloor n_{q}^{\star}\rfloor 2: C_{\mathrm{rem}}\leftarrow C-\sum_{q\in\mathcal{B}_{t}}\hat{n}_{q} 3: for each q with \hat{n}_{q}0 do 7: Select q^{\star}=\arg\max_{q:\hat{n}_{q}