acceptodds
Under review as a conference paper at ICLR 2027

Towards Optimal Policy Improvement

Abstract

Practical Reinforcement Learning (RL) algorithms learn to solve Markov Decision Processes (MDPs) through iterative policy improvement in the presence of approximate evaluation. We study policy improvement from first principles, defining optimal policy improvement as producing the best policy attainable in a single update under specified constraints. We show that optimal improvement restricted to a set of states is equivalent to solving an induced MDP, characterizing planning with an explicit or implicit model as a path towards optimal policy improvement. Because practical methods commonly solve such induced problems through iterative improvement in the form of greedification, we take steps towards optimal greedification under the central practical constraint of approximate evaluation. We formulate greedification under this constraint as probabilistic decision-making under uncertainty and derive a novel operator that is optimal with respect to the resulting objective. Empirically, the operator and its practical gradient-based approximations improve aggregate performance across GumbelAlphaZero, SAC, ReBRAC and Generalized Policy Iteration, in experiments spanning discrete and continuous actions, model-based and model-free, online and offline RL.

Primary area:
reinforcement learning
Keywords:
RL, policy improvement, search, model-based, model-free

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 3 reviews, above 27% of the others.
Reviewer_jP8dOpenReview ↗
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
  1. 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.
  2. 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
  1. 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 QQ-function does not by itself guarantee improvement in the true value function. This considerably limits the scope of the claimed framework.
  2. 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 β\beta 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
  1. 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?
  2. 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.
  3. 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 β\beta)?
3 comments

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.

The first part of the paper effectively characterizes model-based planning on an induced MDP, rather than providing a generally implementable optimal update.

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.

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.

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.

Moreover, greedification relative to an estimated Q-function does not by itself guarantee improvement in the true value function.

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 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 β\beta 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.

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.

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 λ\lambda. The approximation becomes exact as the posterior variances vanish and has an error of order O(λ2)O(\lambda^2) as λ→0\lambda\to0. The difference between the exact marginalized and CE policy updates is bounded by the posterior advantage uncertainty and the ratio λ/β\lambda/\beta. In particular, the bound vanishes as the posterior variances approach zero or as λ/β→0\lambda/\beta\to0.

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 β\beta)?

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 + IoptI_{opt}. 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 IoptI_{opt} 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.

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

The paper studies greedification operators in RL algorithms. First, it shows that optimal policy improvement restricted to a subset of states is equivalent to solving an induced MDP. Second, it models the Q-function estimation error using a Gaussian distribution. Under this assumption, the authors derive a new policy improvement operator and establish convergence guarantees. Finally, the authors demonstrate that the proposed operator performs well across a range of practical RL problems.

Critical strengths

The paper addresses the important problem of designing optimal policy improvement operators. It proposes an operator that is theoretically justified under certain assumptions and demonstrates its practical applicability across several RL algorithms.

Critical weaknesses

While I find the problem studied in this work interesting, I cannot recommend accepting the paper in its current form. Overall, the paper lacks a clear logical connection between its different contributions, the presentation is unnecessarily complicated, and the experimental results are not reported clearly enough. In particular:

  1. I might be missing something, but the first claimed result of the paper seems rather trivial. The arginf condition in Definition 3 already implies that the MDP is solved. What, then, is the main contribution of Theorem 1? Moreover, related ideas have already appeared in the literature; see, for example, Kearns and Singh (1998). It is also unclear how these results connect to the remainder of the paper.

  2. The choice to model Q-function estimation errors using a Gaussian distribution should be explicitly stated as an assumption. Theorem 4 could then be reformulated with a clear reference to this assumption.

  3. The writing in this section is often unnecessarily complicated. For example, the sentence:

"We compare Policy Iteration algorithms with different policy improvement operators I (Algorithm 1 with k → ∞) with evaluation error which coincides with the assumptions under which IoptI_{opt} is designed."

uses "with" three times and "which" twice, making it unnecessarily difficult to understand.

Questions for authors

I have several questions for the authors:

  1. In Theorems 1 and 2, do the induced MDPs constructed on subsets of states have all actions available at these states, or only those actions observed in the dataset?

  2. How are Theorems 1 and 2 connected to the remainder of the paper, particularly to the derivation of the proposed policy improvement operator?

  3. Theorems 3 and 4 establish greedification and convergence properties of the proposed operator, but the paper does not discuss whether this operator is theoretically better or worse than the classical regularized policy improvement operator. Do the authors have any theoretical arguments explaining why, under the proposed Gaussian error assumptions, the new operator should outperform the standard regularized update?

4 comments

We thank the reviewer for their time reviewing our work.

We address the reviewers questions and comments below.

I might be missing something, but the first claimed result of the paper seems rather trivial. The arginf condition in Definition 3 already implies that the MDP is solved. What, then, is the main contribution of Theorem 1? Moreover, related ideas have already appeared in the literature; see, for example, Kearns and Singh (1998). It is also unclear how these results connect to the remainder of the paper.

Theorem 1 demonstrates the connection between optimal improvement and planning, and provides an answer to a major question - what is the fundamental advantage of model based over model free RL? This result is significant, and to our knowledge this is the first time it is presented, making it an important contribution to publish.

Kearns and Singh published two papers in 1998; we assume the reviewer refers to "Near-Optimal Reinforcement Learning in Polynomial Time". While the ideas are related, the objectives and theoretical results differ. Kearns and Singh use planning in an induced MDP to address the exploration-exploitation trade-off, establishing conditions under which the agent can either achieve near-optimal returns or explore unknown states. In contrast, we establish that planning in an induced semi-MDP is exactly equivalent to optimal policy improvement constrained to a subset of states, with respect to the original RL objective. Their induced MDP terminates trajectories upon leaving the subset of known states, whereas ours preserves the discounted returns and possible re-entry into the subset, which is essential for establishing this exact equivalence.

It is also unclear how these results connect to the remainder of the paper.

In this paper, we investigate optimal policy improvement from first principles. These results establish the connection between optimal policy improvement and planning. Planning relies on the same dynamic-programming principles on which model-free RL relies, in the model instead of in the environment: greedification. We therefor proceed to derive a greedification operator which is optimal under the central practical constraint of uncertain evaluation (with respect to a specific modeling of the problem, as there are many ways to model optimization under uncertainty.)

We then evaluate this contribution in planning-based, planning-free, online and offline RL, and Dynamic Programming, demonstrating that the same operator can provide performance gains across all three.

The choice to model Q-function estimation errors using a Gaussian distribution should be explicitly stated as an assumption. Theorem 4 could then be reformulated with a clear reference to this assumption.

It is explicitly states as a modeling choice. It is not exactly an assumption: the error must be modeled in some way, and this is a classical modeling choice [1] that is supported by the data, including our own experiments (Figure 6). The corresponding theorem is analyzed under the same error.

The writing in this section is often unnecessarily complicated. For example, the sentence: "We compare Policy Iteration algorithms with different policy improvement operators I (Algorithm 1 with k → ∞) with evaluation error which coincides with the assumptions under which is designed." uses "with" three times and "which" twice, making it unnecessarily difficult to understand.

We thank the reviewer for the comment, and have improved the writing of this sentence.

[1] Hui et al. (2023). "Double Gumbel Q-Learning." NeurIPS 2023.

Questions:

In Theorems 1 and 2, do the induced MDPs constructed on subsets of states have all actions available at these states, or only those actions observed in the dataset?

All actions.

How are Theorems 1 and 2 connected to the remainder of the paper, particularly to the derivation of the proposed policy improvement operator?

Theorems 1 and 2 establish that optimal improvement corresponds to planning with a model. Planning algorithms however also need to solve the MDP, this time in the model, and use the same set of methods to solve the MDP in the model: iterative policy improvement, with greedification. This motivates us to find an optimal greedification operator, IoptI_{opt}, and then use it in planning-based algorithms (AlphaZero) as well as planning-free algorithms (Policy Iteration, SAC, ReBRAC), where it is able to consistently improve performance.

Theorems 3 and 4 establish greedification and convergence properties of the proposed operator, but the paper does not discuss whether this operator is theoretically better or worse than the classical regularized policy improvement operator. Do the authors have any theoretical arguments explaining why, under the proposed Gaussian error assumptions, the new operator should outperform the standard regularized update?

The new operator should outperform the standard regularized update because it is optimal with respect to the generalized-Bayesian-inference decision objective, which explicitly accounts for evaluation uncertainty. In contrast, the classical regularized policy improvement operator is a heuristic with respect to evaluation uncertainty. IoptI_{opt} also provides insight as to what exactly the regularized policy improvement operator corresponds to, with respect to evaluation uncertainty. The regularized policy improvement operator coincides with IoptI_{opt} when the uncertainty is uniform across all states and actions. In other words, regularized policy improvement is the optimal operator (with respect to the decision objective) in the setting where we have no estimate for the uncertainty. Whenever we do have a sufficiently accurate estimate of the uncertainty, IoptI_{opt} should be expected to perform better. As indeed it does in our experiments, both in the controlled DP experiments as well as in the fully real-RL, DNN-based, AlphaZero experiments.

One of the main contributions of our work is showing that by choosing relevant decision objective and finding operators that are optimal with respect to them results in better performance in practice.

I thank the authors for their responses, which have partially addressed my concerns. However, my main criticism remains unchanged.

Perhaps my expectations for theoretical papers differ from those of the authors, but I still do not see the main mathematical contribution of Theorem 1. I understand its interpretation and motivation, but the mathematical result itself still appears rather trivial to me. In their response, the authors emphasize the conceptual significance of the theorem and its role in the overall narrative of the paper, but they do not sufficiently explain its contribution from a formal mathematical perspective.

The same concern applies to the connection between Theorems 1 and 2 and the subsequent results, particularly Theorems 3 and 4. I understand how these results are connected conceptually, but I do not see a direct mathematical connection between them. In particular, Theorems 1 and 2 are not needed to establish Theorems 3 and 4. Consequently, the paper appears to contain two largely independent sets of theoretical results, connected primarily by the authors' interpretation rather than by mathematical necessity.

My final concern is that Theorems 3 and 4 do not establish whether the proposed greedification operator is theoretically better or worse than existing classical operators. In their response, the authors argue that the proposed operator should outperform the standard regularized operator because it optimally solves the formulated Bayesian decision problem. However, optimality with respect to this particular objective does not necessarily imply superior performance in terms of actual policy improvement or convergence. The authors do not provide a formal theoretical comparison establishing such an advantage.

Overall, while I acknowledge the work that has been done and appreciate the authors' efforts to address my concerns, I remain unconvinced of the significance of the theoretical contributions. Therefore, I maintain my original score of Weak Reject.

For future work, I would strongly encourage the authors to investigate theoretically under which conditions and in what sense the proposed operator outperforms classical policy improvement operators. I believe that establishing such results would substantially strengthen the paper.

We thank the reviewer for acknowledging our rebuttal.

This is not a theoretical paper, and should not be evaluated as such.

This is a practical machine learning contribution with practical significance: a practical policy improvement operator, the first to our knowledge to directly address learning under uncertainty while applicable across different algorithms, successful in practice and derived from first principles. The practical contribution is further supported by theoretical motivation and analysis, beyond empirical success.

A direct mathematical connection between the different theoretical contributions of the paper is not a requirement for a contribution to be novel, sound and significant (i.e. suited for publication).

Theorems 3 and 4 are indeed soundness results. The practical benefits of the operator are motivated by: (I) significant practical empirical success as well (II) the principled optimization framework of Generalized Bayesian Inference under which the operator is derived.

The theoretical foundation of our method goes beyond what is common in this area, see for example, among many others, the following classical, seminal as well as recent works in this field, which all have significantly less theoretical motivation, support or analysis [1-6]:

[1] Abdolmaleki et al. (2018). "Maximum a Posteriori Policy Optimisation." ICLR 2018.

[2] Macfarlane et al. (2024). "SPO: Sequential Monte Carlo Policy Optimisation." NeurIPS 2024.

[3] Oren et al. (2025). "Value Improved Actor Critic Algorithms." NeurIPS 2025.

[4] Haarnoja et al. (2018). "Soft Actor-Critic: Off-Policy Maximum Entropy Deep Reinforcement Learning with a Stochastic Actor." ICML 2018.

[5] Grill et al. (2020). "Monte-Carlo Tree Search as Regularized Policy Optimization." ICML 2020.

[6] Danihelka et al. (2022). "Policy Improvement by Planning with Gumbel." ICLR 2022.

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

This work introduces a policy update rule that weights each estimated advantage by τ2/(τ2+σ^A2(s,a))\tau^2/(\tau^2+\hat{\sigma}_A^2(s,a)), reducing the impact of less certain advantages on the policy. The authors derive this rule from an approximate Bayesian objective and analyze repeated updates under evaluation error. The update is tested in policy iteration and GumbelAlphaZero, while modified actor gradients are evaluated in SAC and ReBRAC. The paper also characterizes policy updates restricted to a subset of states through an induced decision process.

Critical strengths
  • The proposed update accounts for uncertainty in both positive and negative advantages. Remark 1 provides a clear motivation for using advantages: applying different weights directly to Q-values need not improve the policy. Theorem 3 verifies greedification with respect to the supplied Q estimates.

  • The direct tests in policy iteration and GumbelAlphaZero are promising. The Go training comparisons report a 107.8 Elo improvement without the added Q output. In the fixed-network comparisons, the proposed update with the added Q output has the highest mean performance at every tested search budget in both Go and chess. These comparisons include baselines with the same added output.

Critical weaknesses
  • The theoretical contribution is limited. Theorems 1 and 2 are straightforward reformulations. Theorem 3 follows from an elementary sign argument that holds for any positive advantage weights, so it does not establish a special benefit of the proposed weighting. Theorem 4 assumes exact underlying Bellman updates and fresh, conditionally independent Gaussian evaluation errors with known, vanishing variances in a finite-horizon tabular setting. These assumptions poorly represent practical evaluation errors. Without a finite-time bound or finite-noise comparison, the analysis does not explain when uncertainty weighting improves learning.

  • The optimality claim concerns the chosen approximate objective. The independent Gaussian advantage prior ignores the exact constraint ∑aπ(a∣s)Aπ(s,a)=0\sum_a\pi(a\mid s)A^\pi(s,a)=0. The derivation then approximates the joint posterior by a product and replaces expected exponential utility by the exponential of its mean. The Gaussian expectation itself is available in closed form, but its variance term is dropped to obtain a tractable optimizer. These choices are acknowledged, but their effects on the update or policy performance are not analyzed.

  • SAC and ReBRAC use modified actor gradients rather than the derived policy update. They stop gradients through the uncertainty weights, omitting the derivative of the weight. The authors explain this choice but do not directly test its effect. UWAC already weights its actor’s Q objective by inverse estimated variance and stops gradients through uncertainty. The paper acknowledges this work, but a matched comparison within the same algorithms is needed to establish the benefit of the proposed weight and advantage-based uncertainty.

  • The ReBRAC comparison changes both the uncertainty weighting and the balance between Q maximization and behavior cloning, doubling the relative weight of the Q term. A baseline with the same balance but without uncertainty weighting is needed to determine which change accounts for the gains.

Questions for authors
  • How does the update change when the advantage model enforces ∑aπ(a∣s)Aπ(s,a)=0\sum_a\pi(a\mid s)A^\pi(s,a)=0? How sensitive are the results to correlated evaluation errors or inaccurate variance estimates?

  • How do SAC and ReBRAC compare with matched UWAC-style weighting using Q uncertainty? For ReBRAC, how much improvement remains with constant weighting at the same relative Q coefficient? What is the additional training time?

4 comments

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.

The theoretical contribution is limited. Theorems 1 and 2 are straightforward reformulations. Theorem 3 follows from an elementary sign argument that holds for any positive advantage weights, so it does not establish a special benefit of the proposed weighting. Theorem 4 assumes exact underlying Bellman updates and fresh, conditionally independent Gaussian evaluation errors with known, vanishing variances in a finite-horizon tabular setting. These assumptions poorly represent practical evaluation errors. Without a finite-time bound or finite-noise comparison, the analysis does not explain when uncertainty weighting improves learning.

Theorem 1 demonstrates the connection between optimal improvement and planning, and provides an answer to a major question - what is the fundamental advantage of model based over model free RL? This result is significant, and to our knowledge this is the first time it is presented, making it an important contribution to publish.

Theorem 2 establishes the same result under more realistic conditions, which better fit a model that is learned from data.

Theorem 3 establishes that IoptI_{opt} is a policy improvement operator in the same manner as existing operators [1, 2]. It is an important soundness result, which is not preserved by other operators, such as UWAC's uncertainty-weighted hueristic objective. This has real consequences on learning - we include two additional UWAC-inspired agents in Figure 2. These agents are unable to learn in this experiment, as opposed to IoptI_{opt}, which is the best performer. This provides further empirical support to the importance of this theoretical result.

Theorem 4 establishes that IoptI_{opt} is not just an improvement operator, but also a sufficient-improvement operator for convergence to the optimal policy of the dynamic programming process underlying policy-based RL algorithms. Is is also an important soundness result, which is established under more relaxed assumptions than recent prior work establishing convergence for large families of operators [1].

We demonstrate that these assumptions in fact represent practical evaluation errors rather well, see Figure 6 in Appendix F.3. In this figure, we see that in the entirely real-RL setting of AlphaZero, the bulk of the error distribution is Gaussian. This assumption is also popular in literature [3], which further strengthens it as a natural choice for the first paper which models policy improvement explicitly as a decision making under uncertainty problem and derives a novel, well performing operator from this formulation.

The optimality claim concerns the chosen approximate objective. The independent Gaussian advantage prior ignores the exact constraint. The derivation then approximates the joint posterior by a product and replaces expected exponential utility by the exponential of its mean. The Gaussian expectation itself is available in closed form, but its variance term is dropped to obtain a tractable optimizer. These choices are acknowledged, but their effects on the update or policy performance are not analyzed.

Indeed, to derive a novel, well performing and practical operator we have followed the standard approach in ML, of simplifying the optimization objective to the point where it becomes usable. This is not a weakness, but a strength: it shows that even under these simplifications the principled uncertainty awareness of the operator achieves better performance than that of existing popular operators which do not explicitly account for the uncertainty. This is shown empirically both in the controlled DP experiment, as well as in a fully real settings, such as AlphaZero in boardgames.

We add a new theoretical result in Appendix B.6, in the updated version of the draft. This result quantifies the certainty-equivalent approximation error and its effect, analytically.

Our work opens up a wide area of research for the design of different operators: with different decision objectives, different approximation choices, different divergences etc. Naturally, we cannot develop and evaluate every single possible novel operator in one paper. A major contribution of our work is demonstrating how promising this direction is through the success of Iopt.I_{opt}.

[1] Oren et al. (2025). "Value Improved Actor Critic Algorithms." NeurIPS 2025.

[2] Danihelka et al. (2022). "Policy Improvement by Planning with Gumbel." ICLR 2022.

[3] Hui et al. (2023). "Double Gumbel Q-Learning." NeurIPS 2023.

Part 2:

SAC and ReBRAC use modified actor gradients rather than the derived policy update. They stop gradients through the uncertainty weights, omitting the derivative of the weight. The authors explain this choice but do not directly test its effect.

This is a popular choice in literature [4, 5], and is again a strength rather than a weakness. It demonstrates the facility of the operator under a wide range of approximations. In DP, we evaluate the operator under fully controlled conditions, where it outperforms all operators compared to. In MCTS, we evaluate the exact operator under the fully real conditions of AlphaZero, where paired with a Q network it is consistently the strongest performer. In SAC, we take the same approximation choices that SAC itself makes: instead of optimizing for $softmax(Q^\pi), $ SAC tracks the optimum using SGD. In the same set of practical constraints, we do not generally have access to a reliable uncertainty estimator gradient can be taken through. For that reason, we evaluate the operator under the real and practical constraints which induce similar approximation choices in the classical algorithm SAC, and show that even under these approximations it can provide at least competitive performance. We follow the same process with ReBRAC, where we follow the design constraints of the algorithm to keep the comparison between it and IoptI_{opt} as fair as and meaningful as possible, and evaluate how well the operator performs under very strong approximations.

UWAC already weights its actor’s Q objective by inverse estimated variance and stops gradients through uncertainty. The paper acknowledges this work, but a matched comparison within the same algorithms is needed to establish the benefit of the proposed weight and advantage-based uncertainty.

Per the reviewer's request, we include two additional results comparing the UWAC heuristic to Iopt,I_{opt}, to demonstrate the benefit of IoptI_{opt}'s uncertainty weighting, in Figure 2 in Appendix F.1 and in Figure F.5.

In the Policy Iteration experiments, we include two more agents (Figure 2). These agents optimize for the same objective as UWAC's Equation 5: $ argmax_a Q^\pi(s,a) / \sigma^2_Q(s,a). $ One of the agents uses this update directly, and the other uses a softmax similar to IoptI_{opt}, of the form: $\pi_{i+1}(s) = softmax(\log \pi_i(a|s) + Q(s,a)/ \sigma^2_Q(s,a)). $

UWAC's objective does not preserve policy improvement and greedification: consider an example when all action values are positive and the worst action has a much smaller uncertainty σQ2(s,a),\sigma^2_Q(s,a), this operator will worsen the policy by choosing the worst action. The result presented with the new agents in Figure 2 demonstrates the consequences of such a heuristic empirically: these agents are unable to learn.

However, since optimizing $argmax_a Q^\pi(s,a) / \sigma^2_Q(s,a) $ directly in continuous spaces is hard, UWAC further approximates this objective by reweighting different states in the same batch with σQ2(s,a),\sigma^2_Q(s,a), rather than weighting different actions in the same state. We follow the same choice of approximation in these domains, as another example of a way to implement IoptI_{opt}. As a result, the UWAC and IoptI_{opt} uncertainty-weights essentially coincide: both weigh the $Q^\pi(s,a) $ at different states in the same batch relative to each other, rather than those of different actions at the same state relative to each other. For this reason, their effects are also similar, which we show in Table 2 in Appendix F.5., where the 95% confidence intervals overlap in all environments.

[4] Wu et al. (2021). "Uncertainty Weighted Actor-Critic for Offline Reinforcement Learning." ICML 2021.

[5] Haarnoja et al. (2018). "Soft Actor-Critic: Off-Policy Maximum Entropy Deep Reinforcement Learning with a Stochastic Actor." ICML 2018.

Questions:

How does the update change when the advantage model enforces sum to zero?

There are many other versions of the operator that can be derived: with different divergences, with and without the certainty equivalent approximation, and with different advantage priors. In this work we have focused on deriving one operator which is practical, performs very well both in a controlled setting (Figure 1 left) as well as real RL settings (for example, AlphaZero in Chess and Go, as shown in Figures 1 second from left and Figure 5). Our work opens up this wide front for new research deriving new and better operators based on more complex design choices, and we leave the derivation of such operators to future work.

How sensitive are the results to correlated evaluation errors or inaccurate variance estimates?

Sufficiently robust to result in significant performance improvement in Chess and Go with AlphaZero, despite the correlated DNN errors.

How do SAC and ReBRAC compare with matched UWAC-style weighting using Q uncertainty?

We include two UWAC-based comparisons: one that uses UWAC's exact optimization objective, in Policy Iteration experiments in Figure 2, and one that uses the approximate gradient objective, in ReBRAC (Table 2). As discussed in previous points, UWAC's heuristic objective does not preserve policy improvement through greedification, which has real consequences, and it is unable to learn in the Policy Iteration experiment. In contrast, $I_{opt} $ is not a heuristic, preserves greedification, and is the best performer. In the gradient-based approximations of ReBRAC, the similar approximation choices strip away most of the difference between the operators, and indeed, the 95% confidence intervals overlap in all environments, see Table 2 in Appendix F.5. This suggests that IoptI_{opt} can be thought of as a theoretically motivated approach for UWAC's heuristic.

For ReBRAC, how much improvement remains with constant weighting at the same relative Q coefficient?

We include this new experiment in Table 1 in Appendix F.5. The same amount of improvement remains, constant weighting at the same relative Q coefficient performs similar to the baseline.

What is the additional training time?

The runtime cost of IoptI_{opt} is different per agent. We include the information in Table 3 in Appendix F.6.

I thank the authors for their clarifications and additional results, which strengthen the paper. However, my main concerns about the theoretical contribution remain. The analysis establishes soundness under restrictive assumptions but does not sufficiently explain the advantage of the proposed weighting. The consequences of modeling advantages without enforcing their exact constraint also remain insufficiently justified. While I acknowledge the promising empirical results, I find the overall contribution marginally below the acceptance threshold for ICLR and therefore maintain my score.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.