- Rating
- 2
- Confidence
- 3
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 2
Read review
Paper summary
The paper studies policy improvement under state restrictions and uncertain value estimates. First, it characterizes optimal improvement when policy updates are limited to selected states through an induced semi-MDP, and discusses a simpler bootstrapped sub-MDP. Second, it models evaluation errors using heteroscedastic Gaussians, combines them with Gaussian advantage priors, and derives a KL-regularized, certainty-equivalent objective for greedification. The resulting operator down-weights estimated advantages according to action-dependent uncertainty. The paper proves greedification with respect to the supplied value estimates and convergence under a finite-horizon setup with vanishing evaluation errors. Experiments cover noisy tabular policy iteration, search in Go and chess, and gradient-based modifications of SAC and ReBRAC.
Critical strengths
- The action-dependent adjustment of advantage estimates is a useful idea. Under the stated assumptions, the authors derive the exact optimizer of their surrogate objective and establish greedification and convergence properties. I did not identify major mathematical problems with these results.
- The experiments span discrete and continuous actions, model-based search, and online and offline learning. In particular, the comparisons in search-based learning provide evidence that the proposed weighting can be practically useful in some settings.
Critical weaknesses
- Achieving an optimal policy update in general model-free RL is difficult without sufficiently accurate dynamics or value information. The first part of the paper effectively characterizes model-based planning on an induced MDP, rather than providing a generally implementable optimal update. The more concrete contribution relies on Gaussian assumptions about evaluation errors and advantages, together with a certainty-equivalent approximation. The derived operator is optimal for this particular surrogate objective, not for general RL problems. Moreover, greedification relative to an estimated -function does not by itself guarantee improvement in the true value function. This considerably limits the scope of the claimed framework.
- The theory relies on known or consistently diminishing evaluation uncertainty, while the continuous-control experiments use estimated uncertainty and approximate gradient updates. In SAC, detaching the uncertainty weights does not generally optimize the displayed weighted objective. In ReBRAC, changing can also alter the effective balance between the value term and behavior regularization. These experiments suggest potential benefits, but do not yet isolate the impact of the derived optimality principle.
Questions for authors
- How robust is the operator to departures from the assumed unbiased Gaussian evaluation errors with independence across actions? In particular, could the authors examine biased or correlated errors, and clarify which theoretical conclusions continue to hold?
- Can the authors quantify the effect of replacing the original uncertainty-marginalized objective with the certainty-equivalent surrogate? A small finite-action comparison would help establish the practical significance of this approximation.
- For SAC and ReBRAC, can the authors provide matched controls that distinguish the proposed uncertainty weighting from simpler gradient rescaling or changes in regularization strength (for example, constant weights with the same )?
3 comments
Questions:
How robust is the operator to departures from the assumed unbiased Gaussian evaluation errors with independence across actions? In particular, could the authors examine biased or correlated errors, and clarify which theoretical conclusions continue to hold?
We evaluate this empirically with the AlphZero experiments, where the errors are real errors coming from DNN evaluations, and are not entirely independent or Gaussian. As we can see, the operator performs very well, outperforming the previous popular canonical variants of MCTS.
Can the authors quantify the effect of replacing the original uncertainty-marginalized objective with the certainty-equivalent surrogate? A small finite-action comparison would help establish the practical significance of this approximation.
We include additional theoretical analysis which quantifies the certainty-equivalent approximation error and its effect in Appendix B.6. The certainty-equivalent approximation underestimates the uncertainty-marginalized utility factor, with an error controlled by the posterior advantage variances and . The approximation becomes exact as the posterior variances vanish and has an error of order as . The difference between the exact marginalized and CE policy updates is bounded by the posterior advantage uncertainty and the ratio . In particular, the bound vanishes as the posterior variances approach zero or as .
For SAC and ReBRAC, can the authors provide matched controls that distinguish the proposed uncertainty weighting from simpler gradient rescaling or changes in regularization strength (for example, constant weights with the same )?
We have added a control for ReBRAC in Table 1. The control performs similarly to the ReBRAC baselines, and thus is similarly outperformed by ReBRAC + . In SAC the performance difference is already not statistically significant so we have not added an additional control. The purpose of the SAC experiments are to show that can be applied directly to different algorithms, where it performs as well or better than their existing choice for policy improvement.
Thank you for the detailed responses and additional analyses. I appreciate the authors' efforts to address my concerns.
I agree that the proposed operator can be applied beyond settings with Gaussian evaluation errors, and that the greedification property itself does not require the errors to follow a Gaussian distribution. My concern is more specifically about the scope of the optimality interpretation, which remains tied to the chosen probabilistic formulation and its approximations.
The new approximation-error analysis is a useful addition. However, I would be interested in whether the resulting bounds are informative under non-negligible evaluation uncertainty, rather than primarily in the limiting regime where posterior variances vanish.
I also appreciate the additional ReBRAC control, which appears to address an important experimental concern. The AlphaZero and Policy Iteration results provide meaningful evidence of the operator's usefulness.
Nevertheless, my main reservation concerns the overall significance and generality of the contribution. While the proposed operator is interesting and mathematically well motivated under its assumptions, I remain unconvinced that the work establishes a sufficiently general or substantial advance in policy improvement to warrant acceptance. I therefore maintain my recommendation of weak rejection.
We thank the reviewer for their time reviewing our work.
We address the reviewers questions and comments below, and uploaded an updated version of the draft with additional results requested by the reviewer.
Indeed, this is an important, foundational theoretical results demonstrating the connection between planning with a model and optimal improvement. We then follow on it by providing an implementable optimal greedification update, which can be used to improve the planning based update, as shown in the AlphaZero experiments with improved MCTS, as well as planning-free algorithms, such as Policy Iteration, SAC and ReBRAC.
This surrogate objective is a novel formulation of the single-step greedification objective of general RL problems, under uncertainty. It is directly applicable for general RL (as we show in our experiments), whenever there is evaluation uncertainty (essentially every practical setting, especially those that involve DNNs). Thus, it is more general than most other operators, as they do not explicitly account for the central constraint of inaccurate evaluation.
And yet it remains the main motivator for the design of foundational, classical and modern algorithms and operators, for examples [1, 2, 3]. We follow the same design motivation and direction.
In addition, we add to Figure 2 two new agents that account for uncertainty based in the heuristic proposed by [4]. This heuristic does not preserve greedification. And indeed, these agents are entirely unable to learn when optimizing for the true objective set by [UWAC], $argmax_a Q(s,a) / \sigma^2_Q(s,a) $ (Equation 5 in their work).
The impact of the derived optimality principle is isolated in the experiments in Policy Iteration and AlphaZero. The experiments in SAC and ReBRAC compliment these results by showing that even under approximations that may be necessary in specific practical settings, the operator can still provide performance gains.
[1] Danihelka et al. (2022). "Policy Improvement by Planning with Gumbel." ICLR 2022.
[2] Oren et al. (2026). "Twice Sequential Monte Carlo for Tree Search." ICML 2026.
[3] Oren et al. (2025). "Value Improved Actor Critic Algorithms." NeurIPS 2025.
[4] Wu et al. (2021). "Uncertainty Weighted Actor-Critic for Offline Reinforcement Learning." ICML 2021.