acceptodds
Under review as a conference paper at ICLR 2027

Fast Reward Evaluation in Reinforcement Learning via Simulation Optimization

Abstract

Reinforcement learning (RL) plays an increasingly critical role in modern artificial intelligence, including decision-making tasks and large language model (LLM) training. In RL, the reward function determines what behavior the policy is optimized to learn. In practice, different candidate rewards can lead to substantially different policy performance, making reward evaluation crucial for selecting rewards that effectively guide policy optimization. However, evaluating candidate rewards often requires training a separate policy for each candidate, resulting in substantial computational cost and making reward evaluation a major bottleneck. To address this challenge, we reframe reward evaluation as a simulation optimization problem in operations research, which studies efficient selection under limited budgets. Under this formulation, reward evaluation is cast as a sequential budget allocation problem. We then propose Fast Reward Evaluation by adapting Optimal Computing Budget Allocation (OCBA), a representative simulation optimization method, to guide the allocation of training budget across candidate reward functions. Empirical results on sparse-reward RL, automatic reward generation, and LLM reasoning tasks demonstrate that evaluation efficiency is significantly improved, and that high-quality reward functions are more reliably identified under the same computational budget.

Primary area:
reinforcement learning
Keywords:
Simulation Optimization, Reinforcement Learning

Reviews

Among:
Shape:
1234this paper, Top 49%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.33 over 3 reviews, above 51% of the others.
Reviewer_fCtROpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
1
Soundness
2
Read review
Paper summary

Reward evaluation often requires many complete training runs, creating a major bottleneck for large scale reward optimization. To address the question, this paper proposes Fast Reward Evaluation, which uses partially observed learning curves to assess the potential of candidate reward functions and guide training resource allocation. Therefore, Candidate reward functions with lower estimated performance and uncertainty receive less training budget. The method combines a Gaussian learning curve surrogate with Optimal Computing Budget Allocation (OCBA) to formalize this allocation process mathematically.

Critical strengths
  1. The paper addresses an important computational bottleneck in reward design. Furthermore, the method can be applied to other domains such as agentic rl.
  2. Applying OCBA in training resource allocation of reward evaluation is a reasonable and useful method.
  3. The experiments cover classical sparse-reward benchmarks, automatic reward generation tasks, and an LLM reasoning benchmark, supporting the method’s effectiveness across different domains.
Critical weaknesses
  1. Important implementation details are insufficiently explained. The paper mainly focuses on mathematical assumptions and theoretical results, but the practical estimation and updating of the surrogate statistics remain unclear. For example, the procedure for estimating the surrogate variances is not adequately specified, despite their central role in uncertainty quantification and budget allocation.
  2. The experiments are limited. Although the experiments cover several domains, they do not clearly establish whether the method remains effective on more challenging tasks that require long exploration before substantial performance improvements emerge. Such learning dynamics may violate the surrogate assumptions and cause promising reward candidates to receive insufficient training budget. Meanwhile, the advantage of Reward-Adaptive OCBA over standard OCBA is not clearly established.
Questions for authors
  1. How are the surrogate variances estimated and updated in practice?
  2. Can the method handle temporary plateaus followed by substantial improvements, which happen in lots of tasks?
3 comments

We thank the reviewer for their insightful feedback and helpful comments.

1. Important implementation details are insufficiently explained. How are the surrogate variances estimated and updated in practice?

Thank you for pointing out that the implementation details needed clarification. In the implementation, we summarize each training segment by averaging the final 10% of its logged task scores, using at least five observations. At each allocation round, we compute the arithmetic mean and empirical variance of all segment scores collected for each candidate since warm-up, with the number of segment scores as the variance divisor. When a candidate receives additional training, we append its new segment score and update both statistics. With only the warm-up segment available, the empirical variance is zero, so we apply a floor of 10−810^{-8}. The allocator uses this variance to quantify the observed variability across training segments. The Gaussian surrogate provides the local model used in the theoretical analysis.


2. The experiments are limited. Although the experiments cover several domains, they do not clearly establish whether the method remains effective on more challenging tasks that require long exploration before substantial performance improvements emerge. Can the method handle temporary plateaus followed by substantial improvements, which happen in lots of tasks?

Our experiments cover sparse-reward control, automated reward design, and LLM post-training. We agree that delayed improvements pose a distinct challenge. As discussed in Appendix J.2, the local approximation can break down when training dynamics change abruptly. If the observed return stays flat, a candidate may receive too little training to reach a later improvement within the available budget.

To further assess our method with a more complex set of reward candidates, we added a six-candidate GSM8K experiment in Appendix I.5. The candidates combine answer correctness with different forms of process feedback from two frozen reward models. Under the same training budget, Reward-Adaptive OCBA achieves higher mean held-out test accuracy than both standard OCBA and Uniform.

Standard OCBA assumes that repeated evaluations of a candidate come from a fixed performance distribution. In our setting, additional training updates the candidate's policy and can change its performance. Our analysis accounts for this evolution through a local learning-curve model. In the empirical comparison, both OCBA methods use the same updated score and variance estimates. Standard OCBA uses each candidate's estimated performance gap to the current leader. Reward-Adaptive OCBA uses the two leading candidates to define a shared selection boundary and weights each candidate by its variability and distance from that boundary. Across several experiments in the paper, Reward-Adaptive OCBA outperforms standard OCBA under the same training budget.

Thank you for the clarification. I will keep my original score because the theoretical analysis still oversimplifies learning dynamics in practical RL settings, limiting the method’s practical applicability.

Thank you for your follow-up. We appreciate your thoughtful concerns about the complexity of learning dynamics in practical RL settings.

We would like to clarify an important distinction between the assumptions used for theoretical analysis and the practical applicability of the allocation method. Our goal is not to predict the entire future learning curve, but to make more effective training-budget allocation decisions using the information available at each allocation round. The local learning-curve approximation provides a tractable framework for analyzing the allocation mechanism, rather than imposing a global assumption on how RL training must evolve.

In practice, Reward-Adaptive OCBA operates on observed training performance. At each allocation round, the performance estimates and empirical variances are updated using newly collected training segments, allowing subsequent allocation decisions to adapt to the observed learning progress. Therefore, the practical implementation does not require an accurate global model of the learning dynamics or an explicit prediction of each candidate's final performance.

Importantly, the effectiveness of this allocation strategy is also evaluated empirically across sparse-reward control, automated reward design, and LLM post-training. The additional six-candidate GSM8K experiment further demonstrates improvements over standard OCBA and uniform allocation under the same training budget. These results provide evidence that the proposed method can improve allocation efficiency in practical settings where policy performance evolves throughout training.

We acknowledge that abrupt changes following prolonged plateaus remain challenging, as discussed in Appendix J.2. Nevertheless, we believe that the simplified theoretical model and the demonstrated empirical utility should be evaluated as distinct aspects of the work.

We hope this clarification helps address your concern, and we thank you again for your valuable feedback.

Reviewer_qTzqOpenReview ↗
Rating
2
Confidence
3
Informativeness
1
Presentation
2
Soundness
2
Read review
Paper summary

This paper studies the cost of reward function evaluation in reinforcement learning: given multiple candidate reward functions, traditional methods typically require fully training a policy for each candidate, resulting in substantial computational overhead. The authors reformulate this problem as a ranking-and-selection problem in simulation optimization, i.e., under a fixed training budget, deciding how to allocate training resources among different candidate rewards so as to identify the optimal reward as accurately as possible.

The paper proposes the Fast Reward Evaluation framework and its core method, Reward-Adaptive OCBA. This method first allocates a portion of the warm-up training budget to each candidate reward, and then uses the learning curves evaluated under the true task reward to construct a lightweight Gaussian surrogate model for estimating the final performance, learning speed, and uncertainty of each candidate. In subsequent training, the method dynamically allocates more budget to reward functions that currently perform better, are close to the best candidate, or exhibit higher uncertainty, while reducing computational investment in clearly inferior candidates.

Critical strengths
  1. The problem setting is important, and the methodological perspective is novel. The paper focuses on the high training cost required to evaluate candidate reward functions and reframes it as a ranking-and-selection problem under a fixed computational budget. The authors further extend classical OCBA to non-stationary reinforcement learning training processes, dynamically allocating the budget based on the performance and uncertainty reflected in the learning curves. The overall idea is clear and practically valuable.

  2. The experimental scenarios are relatively diverse, and the results are reasonably convincing. The paper validates the method on three types of tasks: sparse-reward reinforcement learning, Eureka automatic reward generation, and LLM mathematical reasoning. Experimental results show that, under the same computational budget, the method generally identifies high-quality reward functions more effectively than uniform allocation and standard OCBA, demonstrating a certain degree of generality and advantages in computational efficiency.

Critical weaknesses
  1. The multi-reward ranking and selection in the GSM8K experiments has little practical significance. The paper only artificially constructs three reward functions with very obvious differences: one directly adopts the answer-correctness signal consistent with the final evaluation, one combines correctness with partial reasoning scores, and another even checks only the output format. The quality ranking of these candidate rewards can basically be determined in advance and does not require a complex budget allocation algorithm to identify. Therefore, this experiment does not demonstrate that the method can solve the problems in real LLM training where there are many candidate rewards, their qualities are close, and ranking them is difficult; nor can it support the paper’s broad conclusion that the method is suitable for LLM reward evaluation.

  2. The theoretical foundation of the method rests on assumptions that are overly idealized and lack sufficient validation. Reward-Adaptive OCBA requires the policy in the later stage of training to enter a stable local region and approximates the complex reinforcement learning process as a one-dimensional, shrinking Gaussian learning curve. However, actual RL training is usually markedly non-stationary and may exhibit performance jumps, training collapse, and reversals in candidate rankings. The paper does not sufficiently prove that these core assumptions hold in the tasks studied, nor does it systematically evaluate the algorithm’s behavior when the assumptions fail. Therefore, there is a clear disconnect between the theoretical guarantees in the paper and the actual effectiveness of the algorithm, and the so-called asymptotic optimality can hardly directly establish the reliability of the method in real training scenarios.

Questions for authors

see the above Weaknesses

2 comments

We sincerely appreciate the reviewer's careful evaluation and valuable suggestions.

1. The multi-reward ranking and selection in the GSM8K experiments has little practical significance.

Thank you for pointing out the limitations of the original reward candidates. To address this concern, we added a GSM8K experiment with six reward configurations in Appendix I.5 of the revised manuscript. All six candidates reward final-answer correctness and use feedback on intermediate reasoning steps to distinguish between solutions that receive the same binary correctness score.

We derive the process feedback from two frozen reward models, Qwen2.5-Math-PRM-7B and Skywork-o1-Open-PRM-Qwen-2.5-7B. For each model, we construct three configurations: the mean step score with a weight of 0.2, the mean step score with a weight of 0.5, and the minimum step score with a weight of 0.2. The two mean variants vary how strongly process feedback influences training. The minimum variant gives the lowest-scoring step more influence, so a reasoning error can lower the process score even when the other steps score well. These configurations reflect practical choices about the scorer, the aggregation rule, and the relative weight of process feedback. Their value is determined by the performance of the policies trained with them.

As is shown in Appendix I.5, Reward-Adaptive OCBA achieved 69.90% mean test accuracy across two post-warm-up seeds, compared with 68.12% for standard OCBA and 67.74% for Uniform. These results suggest that Reward-Adaptive OCBA can help select an effective reward configuration and obtain a better-performing LLM policy within a fixed training budget.


2. The theoretical foundation of the method rests on assumptions that are overly idealized and lack sufficient validation.

Thank you for highlighting the importance of connecting theoretical assumptions with practical RL training dynamics.

Our theoretical analysis establishes asymptotic selection consistency under the stated conditions. The Gaussian learning-curve surrogate provides a tractable local approximation for analyzing the allocation mechanism, while the practical algorithm makes allocation decisions based on observed training performance.

Importantly, Reward-Adaptive OCBA does not require an accurate prediction of the entire future learning curve. At each allocation round, the performance estimates and empirical variances are updated using newly collected training segments, allowing the allocation strategy to respond to observed changes in policy performance. The practical implementation therefore does not depend on fitting a single global model of the training trajectory or explicitly predicting each candidate's final performance.

We further provide empirical diagnostics of the Gaussian surrogate in Appendix H (Figs. 6–7). For a ShadowHand reward candidate, we fit the surrogate on the first 70% of a training window and evaluate its predictions on the remaining 30%. The nominal 90% prediction interval achieves 93% coverage on the held-out observations. The standardized innovations also closely follow the Gaussian reference across most of the distribution. These findings provide direct empirical support for the local approximation used in our analysis.

Beyond the surrogate diagnostics, the effectiveness of Reward-Adaptive OCBA is evaluated through matched-budget experiments across sparse-reward control, automated reward design, and LLM post-training. The consistent improvements over Uniform and standard OCBA across the evaluated settings provide empirical evidence that the allocation strategy remains effective when policy performance evolves during training.

We have also clarified the scope of the local approximation and discussed challenging learning dynamics, including prolonged plateaus and abrupt performance transitions, in Appendix J.2. This discussion makes explicit the conditions under which the approximation is most informative and identifies settings that warrant further investigation.

We hope these additional results and clarifications help address your concerns. We sincerely appreciate your constructive suggestions and consideration of the new evidence.

Thank you again for your time and thoughtful review. As the rebuttal period is coming to an end, we would greatly appreciate it if you could let us know whether our responses have adequately addressed your questions or if you have any further concerns.

Reviewer_UF7kOpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

The paper studies how to compare several candidate reward functions in RL under a fixed training budget, since each candidate otherwise needs its own full policy-training run. The authors treat this as a ranking-and-selection problem from simulation optimization and adapt Optimal Computing Budget Allocation (OCBA). Classical OCBA assumes static alternatives with independent samples, which RL training doesn’t provide. To bridge that gap, the authors model each candidate’s late-stage learning curve as a Gaussian process, whose mean and variance feed an OCBA-style allocation rule. They also prove that the probability of correct candidate selection goes to 1 as the budget grows. Experiments cover MountainCar-v0 with hand-designed shaping candidates, Eureka-generated rewards on four Isaac Gym tasks, and PPO post-training of Qwen2.5-1.5B-Instruct on GSM8K with three reward models.

Critical strengths

S1. Important, novel and well-motivated problem formulation. Evaluating many candidate rewards cheaply is a real bottleneck, both for automated reward design (Eureka-style generation) and for current RL-based LLM fine-tuning, where practitioners regularly choose between reward models or verifiers. Bringing OCBA over from Operations Research is a sensible fit: the goal is selecting the best candidate at the end of a fixed budget, not minimizing regret along the way, and the authors explain clearly why this differs from standard bandit settings. This framing is the main reason I lean toward acceptance.

S2. Thorough grounding in the literature and honest treatment of assumptions. The paper covers the reward-evaluation literature well, including the optimal reward problem, reward-distance metrics and LLM-based reward generation. I know most of the cited works and consider the coverage accurate. The authors also spell out why classical OCBA’s assumptions fail for RL. They then argue from Gaussian-process models of RL (Engel et al., 2005; Hennig, 2011) that OCBA can still be adapted in a principled way, rather than simply applying it.

Critical weaknesses

W1. No guidance on how the candidate set should be built or what it must contain. This is my biggest concern. The set F = {F_1, …, F_K} is defined without any conditions. Yet in this method the candidates directly affect each other’s allocation: the selection boundary is computed from the current best and second-best candidates, so every other candidate’s budget depends on that pair. The experiments don’t seem to test this either.

It’s unclear how the method behaves for different kinds of sets:

A. Must the set contain at least one optimal or near-optimal reward?

B. What happens if all candidates are poor?

C. What happens with many near-tied candidates, which is common when an LLM samples variations of one reward?

W2. The LLM post-training gains are small and not statistically supported. The GSM8K curves follow the same pattern as the classical RL benchmarks (Fig. 3), but the improvement over the baselines is much smaller.

The setup may also leave little room to improve: only K=3 candidates, a total budget of 2,100 steps of which 900 go to warm-up, and about three allocation rounds. Is the smaller gain due to this setup, or does the text space make efficiency gains harder to achieve than in the other benchmarks?

Questions for authors
  1. (W1) Does the method need at least one near-optimal candidate in the set to be useful? How does it behave when all candidates are poor, or when several are nearly tied? Could you add an experiment that varies the quality and spread of the candidate set?

  2. (W1) Can you give practical criteria or a recommended procedure for building the candidate set before running the method?

  3. (W2) Can you report means with confidence intervals over the 3 seeds for Fig. 4, plus a significance test against Uniform and OCBA?

  4. (W2) Do the GSM8K results change with more candidates (e.g., several LLM-generated rewards) or a larger post-warm-up budget? Is there something about LLM training dynamics that limits the gains?

3 comments

We thank the reviewer for their thoughtful comments and constructive feedback.

1.Does the method need at least one near-optimal candidate in the set to be useful? How does it behave when all candidates are poor, or several are nearly tied? Could you add an experiment that varies spread of the candidate set?

Thank you for this question. Our goal is to identify the best reward among the supplied candidates under a fixed training budget, so the set need not contain a globally near-optimal reward. If all candidates are poor, the selected policy may still have low absolute task performance. The method can help identify a relatively strong reward candidate within the set.

To examine how the method behaves when the candidate set has either a clear leader or two nearly tied candidates, we conducted an experiment on MountainCar using two sets of four candidates, as described in Section 4.5 of the revised manuscript. The second set replaces a weaker candidate with a close competitor while keeping the other three candidates fixed.

With a clear leader, Reward-Adaptive OCBA allocates 69.0% of the budget to candidate AA. Introducing a close competitor reduces AA's share to 42.4%, while the new competitor BB also receives 42.4%. Together, the two leaders receive 84.9% of the budget, compared with 50.0% under Uniform. Reward-Adaptive OCBA also achieves faster validation-return improvement in the clear-leader setting, while the methods approach similar return ranges at larger budgets.

These results show that Reward-Adaptive OCBA adapts its budget allocation to the competitive structure of the candidate set, concentrating resources on the strongest contenders.


2. Can you give a recommended procedure for building the candidate set before running the method?

In practice, the set can be built using a workflow inspired by Eureka, where an LLM generates several plausible reward functions for the same task. Before allocating the training budget, practitioners can run a few short rollouts to check that each reward function uses available environment signals, executes without errors, and returns finite values. The candidates that pass these checks can then be evaluated with our method under a common task metric.


3. Can you report means with confidence intervals over the 3 seeds for Fig. 4, plus a significance test against Uniform and OCBA?

Thank you for the suggestion. We report the mean final GSM8K accuracy and 95% tt-confidence intervals across three matched training seeds. The pp-values are from two-sided exact paired permutation tests comparing Reward-Adaptive OCBA with each baseline.

MethodMean Acc. (95% CI)Gainpp-value
Uniform69.0% [68.3, 69.7]+0.30.25
OCBA68.6% [67.7, 69.5]+0.70.25
Reward-Adaptive OCBA69.3% [68.6, 70.0]——

The gain column reports the mean accuracy difference in favor of Reward-Adaptive OCBA in percentage points. Reward-Adaptive OCBA achieved higher final accuracy than both baselines on each of the three matched seeds. These results suggest that adaptive allocation can modestly improve final GSM8K accuracy under the same training budget.


4. Do the GSM8K results change with more candidates or a larger post-warm-up budget? Is there something about LLM training dynamics that limits the gains?

Thank you for the suggestion. In response to the reviewers' feedback, we added a GSM8K experiment with six reward candidates to study allocation when several plausible rewards are available for LLM post-training (Appendix I.5 of the revised manuscript). We construct the candidates from two frozen process reward models, Qwen2.5-Math-PRM-7B and Skywork-o1-Open-PRM-Qwen-2.5-7B. All six candidates use the same final-answer correctness signal and supplement it with process feedback. For each model, we consider three configurations: the mean step score with a weight of 0.2 or 0.5, and the minimum step score with a weight of 0.2. These choices vary how strongly the training reward emphasizes process feedback and whether it rewards overall reasoning quality or emphasizes the weakest step.

Across two seeds, Reward-Adaptive OCBA achieved 69.90% mean test accuracy, compared with 67.74% for Uniform and 68.12% for standard OCBA. The gains suggest that Reward-Adaptive OCBA can help identify an effective reward configuration and deliver a better-performing LLM policy within a fixed training budget.

Our available compute limited the rollout batch size and the post-warm-up budgets we could explore. These constraints may partly explain the modest gains in the experiment.

Reviewer_UF7kOpenReview ↗

Response to rebuttal

Thanks for the responses and sufficiently addressing my requested clarifications and questions. I don't have any further questions and strongly recommend the authors to include these changes in the PDF too. I will be happy to raise my score afterwards.

Thank you for your positive feedback and valuable suggestions. We will incorporate all the changes into the revised manuscript. We sincerely appreciate your support and consideration.

Comments on the paper

1 comment

We sincerely thank the reviewers for their careful evaluation and constructive feedback. Below, we summarize the main concerns raised during the review process and our responses, highlighting the clarifications and additional empirical evidence provided in the revised manuscript.

1. Practical Relevance of the Theoretical Assumptions (Reviewers qTzq and fCtR)

The primary concern is whether the Gaussian learning-curve surrogate adequately captures practical RL training dynamics. We acknowledge that our selection-consistency guarantee is asymptotic and conditional on the stated assumptions. Our surrogate is intended as a tractable local approximation of late-stage learning dynamics, capturing performance trends and uncertainty to inform training-budget allocation.

The modeling approach is supported by established methodology and direct empirical diagnostics. Gaussian approximations have precedents in RL, including policy evaluation and approximate Bayesian analysis (Engel et al., 2005; Hennig, 2011). More importantly, we provide evidence specific to our surrogate in Appendix H. By fitting the model to an initial portion of a local ShadowHand training window and evaluating its predictions on held-out observations, we find that the prediction intervals achieve coverage close to the nominal level. The standardized innovations also align well with the Gaussian reference across most of the distribution, although some deviations remain in the upper tail. These results support the local plausibility of the modeling assumptions and the surrogate's ability to provide meaningful uncertainty estimates.

The practical value of the allocation strategy is further supported by experiments under finite training budgets. Across sparse-reward control, automated reward design, and LLM post-training, Reward-Adaptive OCBA achieves favorable results compared with Uniform and standard OCBA, demonstrating improved training efficiency and policy performance across multiple evaluated settings. These results are obtained from actual RL training trajectories rather than simulations generated from the surrogate assumptions.

These results help bridge the gap between our theoretical assumptions and practical RL training dynamics. We also discuss the limitations of the approximation in Appendix J.2.

2. Representativeness of Candidate Rewards and Strength of the LLM Evidence (Reviewers UF7k and qTzq)

Our objective is to identify the best reward within a given candidate set, rather than to assume that the set contains a globally optimal reward. We have clarified this distinction and added a candidate-composition experiment covering both a clear-leader setting and a setting with closely competing rewards. The results show that Reward-Adaptive OCBA adapts to the competitive structure of the candidate set, prioritizing promising candidates and improving performance under limited training budgets.

We further strengthen the LLM evaluation with an additional GSM8K experiment involving multiple plausible reward configurations. These candidates combine answer correctness with process feedback from different frozen reward models, varying both the aggregation rule and feedback weight. This setting reflects practical reward-design decisions in which candidate quality must ultimately be assessed through downstream policy performance.

Under the same training budget, Reward-Adaptive OCBA achieves higher mean test accuracy than both Uniform and standard OCBA. This additional evidence extends our evaluation beyond a simple reward comparison and demonstrates the method's applicability to more substantive reward-selection problems in LLM post-training.

We respectfully ask that these clarifications and additional results be considered in the overall assessment. We believe the theoretical analysis and empirical evidence support the paper's contribution to efficient reward evaluation and selection under limited training budgets.

Thank you for your consideration.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.