acceptodds
Under review as a conference paper at ICLR 2027

OrderGrad: Optimizing Beyond the Mean with Order-Statistic Policy Gradient Estimation

Abstract

Policy-gradient methods usually optimize expected return, but many real world applications care about distributional properties of returns: tail risk, outlier robustness, or best-of- discovery. We introduce OrderGrad, a family of likelihood-ratio and reparameterization gradient estimators for order-statistic objectives. OrderGrad optimizes finite-sample L-statistics, i.e., weighted averages of sorted rewards or costs, recovering objectives such as VaR, CVaR, trimmed means, medians, and top-/best-of- criteria by changing only the rank weights. For any fixed sample size and rank-weight vector, OrderGrad provides an unbiased gradient estimator for the corresponding order-statistic objective. The method is implemented as a simple reward transformation that can then be used in an otherwise standard policy-gradient or reparameterized update. We study the resulting estimator’s variance behavior and evaluate it on tasks where mean optimization is mismatched to the deployment objective, including LLM math post-training and other tasks. OrderGrad provides a unified, plug-and-play route to risk-averse, robust, and exploratory learning.

Primary area:
reinforcement learning
Keywords:
Policy Gradient, Reinforcement Learning, Order Statistics, Large Language Model

Reviews

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

The paper focuses on optimizing distributional properties of rewards beyond their mean and proposes OrderGrad for optimizing finite-sample L-statistics. The OrderGrad allows the method to target tail averages, medians, trimmed means, and best-of K performance. Theoretically, the authors establish the unbiasedness of the proposed gradient estimators for the specified finite-sample objective. The author further develop an efficient sorting-based implementation with an O(N log (N)) per-batch computational cost for fixed rank weights. Experiments examine gradient-estimation behavior and demonstrate improved performance over several baselines.

Critical strengths

The problem of optimizing distributional properties of rewards is novel and important. The main contribution of this paper is the gradient estimators that adapt likelihood-ratio and reparameterization techniques to general finite-sample L-statistic objectives. In particular, the likelihood-ratio estimator combines include-one conditional values with leave-one-out baselines to preserve unbiasedness. The authors also derive an efficient implementation with an O(N(log N)) per-batch cost. The quantile-weighted representation further help about understanding what the method optimizes and how finite-sample objectives relate to population distribution, which is a important theorical insight in my mind.

Critical weaknesses

My major concern is the lack of a theoretical guarantee for the approximation error between the finite-sample L-statistics and the population criterion. The unbiasedness result is established to the gradient of the finite-sample L-statistic, but not the exact population criterion. The authors acknowledge this distinction and explain the connection through Beta-kernel smoothing, which, intuitively, support the convergence under suitable conditions. While, does not itself establish convergence. Since author already aware it, if there is any difficulty proof it? Quantifying the approximation error through bound is important in my mind, particularly about k, which is the key value that could affect the estimation performance.

I am also concerned about the estimator’s uncertainty. Currently results is only about unbiasedness. However, if one target on extreme criteria, such as the 5th or 95th percentile, the observation size could be limited but value can be large. I am actually curious about how N, k, and rank weight affect the variance of the gradient estimator.

Furthermore, how sensitive is the approach to reward noise? Noisy observations could be ranked differently from their underlying true rewards. Something like quantile crossing issues in quantile regression.

Questions for authors

As I am more familiar with quantile regression, I wonder why don't I learn a policy through a quantile model. Particularly, the author build the connection to quantile-weighted objectives.

Similarly, could VaR or CVaR be optimized directly using zeroth-order policy-gradient methods?

That said, what is the advantages of OrderGrad over these alternatives?

2 comments
AuthorsOpenReview ↗

Thank you for the review 1/2

W1. My major concern is the lack of a theoretical guarantee for the approximation error between the finite-sample L-statistics and the population criterion. The unbiasedness result is established to the gradient of the finite-sample L-statistic, but not the exact population criterion. The authors acknowledge this distinction and explain the connection through Beta-kernel smoothing, which, intuitively, support the convergence under suitable conditions. While, does not itself establish convergence. Since author already aware it, if there is any difficulty proof it? Quantifying the approximation error through bound is important in my mind, particularly about k, which is the key value that could affect the estimation performance.

Thank you for the question. After looking into it, the Beta kernels coincide with the Bernstein polynomial basis up to a multiplicative factor. Regression with these polynomials has a long history with various convergence guarantees under different norms. The paper now mentions this literature for the proof on convergence to arbitrary population objectives. Additionally, we proposed a regularized fitting method that prevents the α\alpha weights from exploding when performing the fit. This is important to effectively trade off the estimation accuracy against gradient variance. We will also provide the code as a helper function, so the user can just specify their target population objective as a function, and our method will perform the optimal fit. The explanation is in the new appendix.

W2. I am also concerned about the estimator’s uncertainty. Currently results is only about unbiasedness. However, if one target on extreme criteria, such as the 5th or 95th percentile, the observation size could be limited but value can be large. I am actually curious about how N, k, and rank weight affect the variance of the gradient estimator.

This is an important point. To address it we derived upper and lower bounds on the ratio of signal-to-noise ratios between the mean reward gradient estimator and the OrderGrad gradient estimator (Added to the paper as Remark 2 and Appendix G). The upper bound is 1, and achieved for uniform weights, but the lower bound is based on an “effective sample size” given by η=1/(k∑jαj2)\eta = 1/(k\sum_j \alpha_j^2). When all the weights are equal, this ratio is η=1\eta = 1, when the objective is the max@k, then there is only one jj that is 1, and the rest are 0, so it becomes 1/k, whereas for Top-M@K, the ratio becomes M/K. This provides an intuitive and natural diagnostic regarding the reduction in estimation accuracy. In particular, when you consider extreme criteria, such as the 5th or 95th percentile, then the effective sample size will be small, and a large number of samples will be necessary to obtain accurate estimates. Our metric cleanly elucidates such phenomena. While the current estimation method has difficulties with extreme criteria, we nevertheless believe that the formulation points a way forward to estimate extreme criteria better as well. Namely, one could use the estimated order-statistics to construct a model and extrapolate to the extreme cases. This approach would use more of the samples, and essentially add a bias-variance tradeoff to achieve more efficient tail estimation. We believe this is a good direction for future work.

Regarding N, asymptotically it has the standard 1/N behavior for reducing variance.

W3. Furthermore, how sensitive is the approach to reward noise? Noisy observations could be ranked differently from their underlying true rewards. Something like quantile crossing issues in quantile regression.

This is an interesting point. There are different types of noise: while you ask about observation noise, we first want to clarify process noise. For process noise, it is actually part of the objective, we may for example want to avoid risky outcomes, so taking into account the process noise in the objective is exactly correct. However, for the observation noise, as you point out, if the noise is heteroscedastic (changes depending on what outputs are picked), then the objective may favor responses/actions that lead to different observation noise even though the expected noiseless objectives are the same. In the current work, we assume noiseless observations, but this is a limitation that should be noted and addressed (we added a note in the limitation section). We think the sensible approach to tackle this problem is to aim to denoise the rewards using some approach. This is an orthogonal problem, and a good topic for future research.

AuthorsOpenReview ↗

Thank you for the review 2/2

Q1. As I am more familiar with quantile regression, I wonder why don't I learn a policy through a quantile model. Particularly, the author build the connection to quantile-weighted objectives.

Learning a critic is difficult. In particularly, in the LLM scenarios that we consider, open LLM training is still predominantly done using sample-based GRPO type approaches. From this perspective, sufficiently accurate quantile models are just not available in our scenarios. Moreover, even RL approaches that do use critics, such as PPO, often still combine the critic with actual rollouts to reduce the bias from the critic. We believe combining critics together into our estimator is an interesting topic for future research.

Q2. Similarly, could VaR or CVaR be optimized directly using zeroth-order policy-gradient methods?

Q3. That said, what is the advantages of OrderGrad over these alternatives?

There do exist CVaR estimators in the literature (Tamar et al. 2015), and we added a comparison to figure 4 with a naive estimators as well as a version of it with a baseline. Our OrderGrad performs better. Moreover, OrderGrad allows for arbitrary population objectives, not just VaR or CVaR, and allows for controlling bias-variance by changing kk.

Thank you, we realize there is not much time left in the discussion phase, but do not hesitate to ask if there are any remaining concerns.

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

This paper proposes OrderGrad, a unified framework for constructing unbiased gradient estimators for finite-sample L-statistic objectives. By assigning different weights to order statistics, the framework accommodates a broad class of distributional objectives beyond expected reward. The authors develop likelihood-ratio (LR) and reparameterization (RP) estimators, provide efficient implementations, and demonstrate their applicability through numerical experiments, including LLM post-training.

Critical strengths
  1. Clear and compelling motivation. The paper addresses a meaningful problem: conventional expected-reward optimization may not align with distributional objectives arising in risk-sensitive learning, robust optimization, and best-of-K inference. The motivation is intuitive and well presented.

  2. Simple and general methodology. The construction of the LR and RP estimators is mathematically natural and easy to follow. Although the estimators build on established techniques, extending them to a unified class of L-statistic objectives is a useful contribution. The efficient computation of the corresponding advantages further strengthens the proposed framework.

  3. Solid theoretical and empirical support. The main unbiasedness results are supported by reasonable mathematical derivations. The experiments demonstrate computational efficiency, examine gradient estimation behavior, and illustrate the practical usefulness of different rank-weighted objectives.

Critical weaknesses
  1. Overly lengthy and scattered appendix. The appendix contains numerous auxiliary derivations, special cases, and illustrations that are not essential to the main contributions. Some material is repetitive and could be significantly condensed to improve readability.

  2. The main theoretical results are not sufficiently highlighted. Despite unbiased gradient estimation being the central contribution, the corresponding guarantees are scattered across several appendix sections. a clear main theorem could be better, which can make it easier to identify the key theoretical results.

  3. Limited direct comparison with existing gradient estimators. While the experiments demonstrate the computational efficiency and practical usefulness of OrderGrad, they do not directly compare its gradient estimation performance with alternative estimators applied to the same L-statistic objective. Consequently, it remains unclear whether the observed benefits arise primarily from the choice of distributional objectives or from improved gradient estimation.

Questions for authors
  1. Could the authors consolidate the main unbiasedness guarantees for the LR and RP estimators into a single theorem in the main text?

  2. Could the authors briefly clarify the main advantages of OrderGrad over directly applying multi-sample REINFORCE to the same L-statistic objective?

  3. Is there a simple guideline for choosing kk and α\alpha when targeting a specific distributional objective, such as CVaR or best-of-K performance?

4 comments
AuthorsOpenReview ↗

Thank you for the review 1/2

Thank you for the review.

W1. Overly lengthy and scattered appendix. The appendix contains numerous auxiliary derivations, special cases, and illustrations that are not essential to the main contributions. Some material is repetitive and could be significantly condensed to improve readability.

Thank you we rewrote parts of the appendix (see orange in the new manuscript). We will continue revising this to improve it further.

W2. The main theoretical results are not sufficiently highlighted. Despite unbiased gradient estimation being the central contribution, the corresponding guarantees are scattered across several appendix sections. a clear main theorem could be better, which can make it easier to identify the key theoretical results.

We restructured the main theoretical results in the main paper by adding theorem environments. We now have the main structure:

Theorem 1: Gives the likelihood ratio gradient equation based on the barred population quantities, i.e., exact expected conditional order-statistics.

Proposition 1: Gives the batch estimator for the order-statistic and proves that it is unbiased for the population quantity.

Theorem 2: Proves that the proposed LR and RP gradient estimators are unbiased for the L-statistic objective by applying the law of iterated expectations together with Proposition 1 to reduce the expected value of the estimator to that given in Theorem 1.

Theorem 3: Claims that the batch quantities can be computed efficiently in O(NlogN).

Theorem 4: Establishes that as kk increases, we can choose α\alpha to approximate arbitrary population objectives. This is done by noting that the beta kernels are the Bernstein polynomial basis up to a factor, so there is a rich literature on approximation guarantees.

Remark 1: GRPO and MaxRL are exact special cases of OrderGrad in the binary reward setting.

Remark 2: Proves a variance ratio bound of the OrderGrad estimator to the regular RLOO estimator. This bound is not a universal guarantee and requires some assumptions, but it provides an intuitive effective sample size ratio metric 1/(k∑jkαj2)1/(k\sum_j^k\alpha_j^2), that gives an indication of how much the variance may increase.

W3. Limited direct comparison with existing gradient estimators. While the experiments demonstrate the computational efficiency and practical usefulness of OrderGrad, they do not directly compare its gradient estimation performance with alternative estimators applied to the same L-statistic objective. Consequently, it remains unclear whether the observed benefits arise primarily from the choice of distributional objectives or from improved gradient estimation.

There are no prior existing gradient estimators for this objective. However, to address your concern, we tried adapting some existing estimators in the best way possible to the L-statistic case. In particular, we compared against Koyamada et al. (2022) and against Tang et al. (2025), by adapting their methods to our scenario. We performed experiments across numerous toy settings with different Softmax bandits and a linear reward with Gaussian noise, and our method consistently outperformed them in terms of accuracy, usually by around 2-7 times for Tang, and often by over 10 times for Koyamada. (Appendix J)

AuthorsOpenReview ↗

Thank you for the review 2/2

Q1. Could the authors consolidate the main unbiasedness guarantees for the LR and RP estimators into a single theorem in the main text?

Yes, we fixed this as explained in W2.

Q2. Could the authors briefly clarify the main advantages of OrderGrad over directly applying multi-sample REINFORCE to the same L-statistic objective?

First, it’s necessary to clarify what is meant by this. The basic multi-sample REINFORCE method for set objectives was provided by Koyamada et al. (2022), and later works are different ways to apply baselines and perform variance reduction. Our response above explained that our approach has lower variance than naive methods that could be derived (in W3).

Q3 Is there a simple guideline for choosing (k) and (\alpha) when targeting a specific distributional objective, such as CVaR or best-of-K performance?

Thank you for the question. In the updated paper, we explain that the beta kernels correspond to the Bernstein polynomial basis up to a constant factor offset. There is a rich literature on regression with this basis, so any of those techniques can be used to fit the α\alpha to get minimum error to your specified distributional objective. Another consideration is not only accurately fitting the objective, but also obtaining low gradient estimation variance. To address this we propose constrained optimization of α\alpha while keeping the “effective sample size” above a threshold (this amounts to setting a constraint on the squared norm of α\alpha). We believe this is an effective way to achieve objective approximation while trading off gradient estimation variance. kk is another parameter that controls this: Figure 4 shows how using lower kk has a lower variance, but by increasing kk, the bias can be reduced. Thus we can choose these parameters to achieve an effective bias-variance trade off.

Thank you, we realize there is not much time left in the discussion phase, but do not hesitate to ask if there are any remaining concerns.

I appreciate the authors for their response to my comments. I will maintain my positive score.

AuthorsOpenReview ↗

Thank you for the response

Thank you for the response and the support! We made several revisions to address your concerns (restructured the writing, added naive estimator comparisons, theoretical variance guarantees). If your concerns were addressed, we would appreciate it if you could consider increasing your score to 4. In particular, there are several objective indicators that our work is extremely strong:

  1. Previous strong works are special cases (MaxRL, ICML2026 oral; GRPO with binary rewards is itself also an exact special case) or related variants (PKPO, NeurIPS2025 spotlight, Tang et al. ICML2025) and are decisively experimentally outperformed.
  2. Our theory gives an exact characterization of the target objective as a weighting of the reward quantile function. Such a clean interpretation is rare.
  3. Our work is the first to give a sample-based and critic-free policy gradient algorithm for general distributional objectives.
  4. With increasing sample size, the weights α\alpha can be picked to approximate arbitrary quantile function weightings WW, with convergence guarantees, thus universally enabling to target different objectives like CVaR, Top-M, medians, trimmed means, etc.
  5. The necessary practical implementation is simple: it is a one line change after importing our library. Everything else about the user's code can remain the same. Methods that are easy to implement are what end up being useful in practice.

Thanks again for your comments; we think they improved the work.

Reviewer_cNymOpenReview ↗
Rating
3(+1)
Confidence
2
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

This paper introduces a method for optimizing weighted averages of sorted rewards (instead of picking a single reward) using policy gradient methods using both likelihood ratio estimation and reparameterization estimation. The authors demonstrate how to obtain efficient unbiased estimators for their target, and show that special choices of weights reduce to previous frameworks, e.g. choosing max/min reward among a number of rollouts. The authors apply their method to RL training of LLMs for math reasoning and show improvements compared to the MaxPO and GRPO baselines.

Critical strengths

The paper provides a nice general framework for taking the distribution of rewards into account and optimizing their L-statistics. The writing is clear, and authors have considered both the likelihood ratio and reparamterization formulations which is valuable.

Critical weaknesses
  • My main concern is with novelty. Specifically, Tang et al. (2025) considers optimizing a generic test-time objective which can be an L-statistic as well, so this paper might be better framed as a specialization of the general case to the case of L-statistics. The particular contribution seems to be introducing the batch calculations in Section 3.3.

  • The experimental results are also quite limited. Given that the theoretical contribution of the paper is more or less a straightforward derivation, one way to strengthen the paper is to test their proposal in environments beyond LLM math RLVR. Even in the math RLVR experiment, the only baselines considered are MaxPO and GRPO. I suppose there are many other baselines and it is not clear to me why they only compare with these two. Overall, I'm not sure if we are seeing a convincing gain for Top-M@K compared to Max@K, and my impression is that Top-M@K could already be somewhat derived from previous work.

Questions for authors
  • How would this method generalize to multi-turn settings where each rollout has multiple actions and rewards?

  • In Section 5.3 the authors mention that Top2@6 has a better pass@256 compared to Top2@4, but this can't be seen from the figure as the two curves are simply overlapping.

  • Building on the above, perhaps the authors could introduce some tables with numerical results in the paper instead of relying solely on figures, and also attempt to quantify uncertainties and error bars as much as it is feasible. These error bars could be important given the generally small margin between different methods.

4 comments
AuthorsOpenReview ↗

Thank you for the review 1/2

Thank you for the review.

W1. My main concern is with novelty. Specifically, Tang et al. (2025) considers optimizing a generic test-time objective which can be an L-statistic as well, so this paper might be better framed as a specialization of the general case to the case of L-statistics. The particular contribution seems to be introducing the batch calculations in Section 3.3.

Our work provides the first sampling-based critic-free policy gradient estimator for general distributional objectives. It generalizes and improves on several previous works, such as Walder et al. (NeurIPS2025 spotlight), MaxRL Tajwar et al. (ICML2026 Oral) and CVaR policy gradients. Moreover, it provides a clear unified explanation based on order-statistics, which allow interpreting the objective function as beta-kernel weighted averages of the reward quantile function. We believe this is highly novel.

The historical context explained in the paper introduction is the following: Koyamada et al. (2022) gave a general REINFORCE type estimator for set-based objectives (focusing on the max, but replacing it for other objectives is straight-forward). However, they used a rudimentary variance reduction baseline. -> Tang et al. (ICML2025) used the same base estimator in LLM tasks but gave an interesting variance reduction baseline from the k-1 other samples in a set of size k (e.g., using max@(k-1) as a baseline for max@k). -> Walder et al. (NeurIPS2025) gave an estimator that averages Tang’s method over subsets of size k with exact computations, where the batch size N>k. Our method similarly has N>k and performs the relevant computations for arbitrary L-statistics with a further improved baseline. In particular, the previous works did not connect their estimators to order-statistics or provide the theoretical interpretation. The realization that with a fixed weighting vector α\boldsymbol{\alpha} over the order-statistics, the whole computation over all statistics can be done efficiently is also non-trivial.

Regarding Tang et al. (2025), we note that our estimator is not an application of their method. To further highlight this, we did an experiment on a bandit task designed to show effects of baselines beyond variance reduction (Chung et al, 2021 https://proceedings.mlr.press/v139/chung21a.html), comparing against both Walder and Tang on the max@k special case that were implemented in these works. Their methods fail in around 20% of the cases getting stuck at the wrong arm, whereas OrderGrad fails 0/1000 times (Results in Appendix J.4.).

W2. The experimental results are also quite limited. Given that the theoretical contribution of the paper is more or less a straightforward derivation, one way to strengthen the paper is to test their proposal in environments beyond LLM math RLVR. Even in the math RLVR experiment, the only baselines considered are MaxPO and GRPO. I suppose there are many other baselines and it is not clear to me why they only compare with these two. Overall, I'm not sure if we are seeing a convincing gain for Top-M@K compared to Max@K, and my impression is that Top-M@K could already be somewhat derived from previous work.

We disagree with the point about it being a straightforward derivation. If an interpretation as clean as ours were straightforward it would already have been done by the great researchers behind the main prior works explained above. None of these works connected their methods to order-statistics or gave the general distributional policy gradient method that we derived.

Additionally, to address your concern regarding baselines, we added an entropy-based method and also MaxRL as baselines. We also increased the number of seeds from 1 to 3, and computed standard errors. The results with Qwen3-4B-Base averaged over math tasks are below. We see that OrderGrad consistently improves the performance.

Methodpass@1pass@2pass@4pass@16pass@64pass@256
GRPO40.6 ± 0.3546.0 ± 0.4050.7 ± 0.1758.6 ± 0.4065.8 ± 0.6972.7 ± 0.52
Entropy-adv40.7 ± 0.3545.7 ± 0.4050.4 ± 0.4659.1 ± 0.4666.6 ± 0.2372.8 ± 0.40
MaxRL40.7 ± 0.4646.5 ± 0.4051.6 ± 0.2360.5 ± 0.1768.0 ± 0.3574.8 ± 0.40
MaxPO K=436.9 ± 0.8745.9 ± 0.4652.7 ± 0.2362.8 ± 0.1271.9 ± 0.1279.4 ± 0.35
OrderGrad Top-2@439.8 ± 0.8747.8 ± 0.9253.9 ± 0.9864.1 ± 0.8173.3 ± 0.4680.6 ± 0.23
OrderGrad Top-2@638.9 ± 1.0447.8 ± 0.9854.6 ± 0.8165.3 ± 0.5274.2 ± 0.2981.1 ± 0.06
AuthorsOpenReview ↗

Thank you for the review 2/2

Q1. How would this method generalize to multi-turn settings where each rollout has multiple actions and rewards?

Because the method integrates straight-forwardly with sample-based GRPO-type training (the implementation is a reward transformation), it generalizes in the same way as GRPO. There are several works on this: https://swift.readthedocs.io/en/v4.6/Instruction/GRPO/DeveloperGuide/multi_turn.html https://arxiv.org/html/2505.11821v1

Q2. In Section 5.3 the authors mention that Top2@6 has a better pass@256 compared to Top2@4, but this can't be seen from the figure as the two curves are simply overlapping.

The pass@1 is clear, but the pass@256 are very close. The result is also available in Table 5 in the appendix. The main paper text now includes a pointer to the table. Thanks for mentioning this.

Q3. Building on the above, perhaps the authors could introduce some tables with numerical results in the paper instead of relying solely on figures, and also attempt to quantify uncertainties and error bars as much as it is feasible. These error bars could be important given the generally small margin between different methods.

The tables were in the appendix. The main paper text now adds pointers and links to the relevant tables in the appendix. Thank you for pointing this out.

Regarding uncertainties, we agree with you that this is a major pain point of LLM research. Unfortunately it is cost-wise not viable to get fully reliable results (e.g., the statistical precipice paper notes that we need ~50 seeds per RL algorithm for reliable results https://arxiv.org/pdf/2108.13264, see also https://arxiv.org/pdf/2504.07086 for an LLM specific reliability analysis). Therefore, the best we can do in terms of LLM experiments is give preliminary evidence on these tasks. To address your concern, we did increase the number of seeds to 3, and included standard error estimates as a rough estimate (see the table in our previous response to you).

For stronger justification, we instead argue for the validity of our method based on the following points:

  • Multiple existing works are special cases of our approach (e.g., MaxRL can be recovered with a specific choice of α\boldsymbol{\alpha}, so that the estimators are batch for batch numerically identical; the updated version explains that GRPO with binary rewards is also a special case). This means that our approach when tuned can be no worse than these existing strong works in the literature.
  • The Top-Bottom experiment with length rewards gives 60% reduction in the length. This is a strong result. We added some discussion of related work on reducing the response lengths for greater efficiency.
  • Some improvements are quite large, e.g., at pass@256 the improvement over GRPO is almost 10%.
  • The toy experiments do include errorbars and are run with a large number of seeds to obtain reliable results. The variance and signal-to-noise ratio metrics provide clear evidence of the mechanism by which it improves.
  • The appendix also had toy experiments showing the validity of the trimmed mean method for robustness in linear regression, and the toy trading task showed the validity of our CVaR method.

Thank you, we realize that there is not much time left in the discussion phase, but please do not hesitate to ask if there are any remaining concerns.

What I was specifically referring to in the novelty concern was the following: Tang et al. (2025) considers a leave-p-out estimator that when applied to weighted reward, precisely gives the α\alpha-weighted objective introduced in this paper. However, I agree that presenting and experimenting with the α\alpha-weighted objective and estimator more explicitly can be valuable. I have increased my score, but my confidence in my assessment remains low as I'm not an expert in this field.

AuthorsOpenReview ↗

Thank you for the response and increasing the score! Regarding Novelty: Tang's baseline does not give our alpha-weighted objective.

Thank you for increasing your score and for the follow-up!

Regarding Tang et al. (2025), while we found their baseline inspiring when we first saw it, we insist that it has little effect on the novelty assessment of our work. Specifically, applying their baseline does not lead to our objective. We would like to clarify with specific explanations.

Tang considers sets S=AiiKS = \\{A_i\\}_i^K of size KK, they construct an estimator (F(S)−b)∑i=1k∇θlog⁡π(Ai)(F(S)-b)\sum_{i=1}^k\nabla_\theta \log\pi(A_i), and specifically construct a baseline from the samples other than ii for sample ii giving ∑i=1k(F(S)−b−i)∇θlog⁡π(Ai)\sum_{i=1}^k(F(S)-b_{-i})\nabla_\theta \log\pi(A_i). Here, F(S)F(S) is a set objective for KK samples, such as max@K, and the value is shared for all log-derivatives in the set. The basic structure, but without their interesting baseline was given earlier by Koyamada et al. (2022).

Specifically, Tang et al. considered the objectives max@k and majority@k. Let’s focus on the max@k case, and see how their method relates to ours. What Tang et al. specifically suggested was to use the max@(k-1) from the other k-1 samples as a baseline for the max@k objective. This is already different from our approach, as their baseline has the expected value of max@(k-1), whereas in our approach, the expected value of the advantage and baseline are both max@k, not max@(k-1). Consider how their approach works out specifically for binary rewards with different numbers of correct responses in the batch:

0 correct responses: all advantages are 0.

1 correct response at index ii: The max is 1, so F(S)=1F(S)=1. b−i=0b_{-i} = 0 for ii and 11 for j≠ij \neq i, so sample ii has advantage 1, and all other samples have advantage 0.

2 or more correct responses: F(S)=1F(S)=1 and b−m=1b_{-m} = 1 always, so all advantages are 0.

So there is only one case when the advantages will not all be 0.

Our approach has considerably different behavior to this. We consider N>k samples, and estimating the values by enumerating subsets of size k. While in Tang’s approach, the advantages are always ≥0\ge 0, in our approach, the advantages for wrong responses will be negative. And the magnitudes of the advantages also change non-trivially when the number of correct responses changes. Tang et al. did not discuss such constructions using N>k.

Let’s consider more concretely the difficulties that one might get when trying to apply Tang et al.’s approach to the L-statistic objective in a batch of size kk. The L-statistic will weight the k samples, and then apply different weights αj\alpha_j to each rank. The first difficulty is how to decide on the weights for the set of size k−1k-1. The original weights are for a set of size kk, so we cannot just reuse the same weights. What we did in our new experiments comparing with Tang et al. was to redistribute the weights to the k-1 samples, and this can potentially lead to an estimator, but the baseline will not be estimating the same L-statistic objective.

Our OrderGrad approach is considerably more involved. I will go through the specific computations to make this clear. We consider all subsets of size kk sampled from the batch of size NN. For each order-statistic jj and each sample ii, we have two key quantities qiq_i and v−iv_{-i}. qiq_i is the include-i value when considering all subsets that include sample ii, and v−iv_{-i} is the average over all subsets that exclude sample ii. I will focus specifically only on computing all of the qiq_i values for now.

After sorting all rewards, qiq_i for one sample can be computed via a dot product ∑m=1NwmRm\sum_{m=1}^N w_m R_m, requiring NN computations. Note that the necessary weight vectors for computing two different values qiq_i and qnq_n for samples ii and nn are actually different. So if we want to naively compute all qiq_i, we could construct an NxN matrix WW, and perform a matrix-vector product WRWR, requiring N2N^2 computations. Moreover, the matrices WW are different for all kk order-statistics, so naively, we would perform k separate matrix-vector products, and require kN2kN^2 computation. This cannot be computed by simply using one multiplier for each reward, and deleting out some elements to create leave-one-out values. We further create an O(Nlog⁡N)O(N\log N) algorithm for computing this without using a matrix-vector product. This determines the qiq_i values, and by computing the v−iv_{-i} values in a similar manner, we can compute the advantages. We hope it is clear that the computation is significantly more complicated than the cases considered by Tang et al. The new experiment in Appendix J.4. considers the exact max@k estimator in Tang’s paper, and compares it against our OrderGrad for the same max@k, and the difference in performance and optimization behavior is also clear.

Thank you again, we hope this clarifies that our baseline computations are considerable more involved.

Comments on the paper

1 comment
AuthorsOpenReview ↗

General response and summary of rebuttal

We thank all reviewers for their constructive feedback. We made several changes to the paper indicated in orange in the newly uploaded manuscript.

In particular we:

  • Revised the writing in the appendix.
  • Added theorem statements to highlight the contribution cleanly.
  • Added pointers to the tables in the appendix.
  • Added experimental comparisons with existing CVaR estimators into Figure 4 (ours is more accurate and allows controlling bias-variance tradeoff).
  • While there is no previous existing gradient estimator for L-statistics, we created naive estimators by extending Koyamada et al. and Tang et al.’s methods, and added a comparison into appendix J. Ours is typically 2-7 times more accurate. Moreover, we replicated Chung et al’s (2021, https://proceedings.mlr.press/v139/chung21a.html) bandit example that showed that off-center baselines can cause optimization problems. Previous works, Tang (ICML2025) and Walder (NeurIPS2025) for max@k get stuck in the wrong arm ~20% of times, whereas ours gets stuck in 0% of cases (App J.4).
  • We added LLM experimental results with previous works MaxRL and also an entropy advantage method. Ours outperforms them convincingly.
  • We added extra seeds (up from 1 to 3) to show reproducibility, and the results remain consistent.
  • We added an explanation that Beta kernels are the Bernstein polynomial basis functions up to a factor. Therefore, there is a rich literature of approximation guarantees with these kernels. Any population objective can be approximated by appropriately choosing α\alpha with theoretical guarantees on the convergence as kk is increased. We also added helper code functions that do this fitting automatically, so that the user can specify their target population objective as a function, and the α\alpha weights are computed automatically. Several fitting methods are available.
  • We added theoretical guarantees about the gradient variance. Specifically, we introduce an “effective sample size” metric 1/(k∑jαj2)1/(k\sum_j \alpha_j^2) that gives an estimate of the variance relative to the mean objective gradient estimator. In the worst case, the effective sample-size is 1/k1/k, whereas when all α\alpha are equal, it is 1. This bound requires some assumptions; it is not a universal bound. However, we believe it is informative.
  • We added an explanation that the binary reward GRPO is also a special case of OrderGrad (this does not hold for continuous rewards). This is an insightful addition to the previous explanation that MaxRL (ICML2026 oral) is a special case.

We would also like to give a brief overview of our paper to highlight the significance:

Our paper presents the first sampling-based policy gradient estimator for general distributional objectives. This contrasts with previous distributional RL methods that require a critic for estimating the value distribution. Such critics are difficult to learn, which is why open LLM training is still predominantly GRPO-style sampling based training. Our work generalizes and improves on several existing strong works (Walder et al. NeurIPS2025 spotlight, MaxRL Tajwar et al. ICML2026 Oral). We provide a clean interpretation of the resulting objective in terms of a beta-kernel weighting of the reward quantile function ∫01Q(q)∑j=1kαjbj(q)\int_0^1 Q(q)\sum_{j=1}^k \alpha_j b_j(q) dq, where the user can pick the quantile region that they want to weight by choosing the weights α\boldsymbol{\alpha}. This allows optimizing for arbitrary distributional objectives, such as CVaR, medians, trimmed means, best of N/max@k and TopM criteria. We implemented both REINFORCE-type policy gradient estimators and reparameterization type gradient estimators for this objective. The method is implemented as a reward transformation aii=1N←rii=1N\\{a_i\\}_{i=1}^N \leftarrow \\{r_i\\}_{i=1}^N that can be inserted into one’s code with a one line change after importing our reward transform. Experimentally, we did GRPO-type post-training on LLM math experiments. But also showed toy experiments that compare gradient variance, signal-to-noise ratio, bias. We also demonstrated the effect on a toy regression task with poisoned data and trimmed mean objective for robustness, and demonstrated the effect of CVaR on a toy trading task. The gradient estimation accuracy outperforms naive approaches that one could try. The LLM experiments included an experiment with multiple reward axes: we applied a TopM objective on the task reward and BottomM objective on a length penalty and the response length was reduced by ~60% without greatly affecting the accuracy. Typical performance on LLM tasks showed significantly improved pass@k metrics, and the results were consistent across multiple seeds.

Overall, our work presents a paradigm shift in policy gradient reinforcement learning, where we are no longer constrained to optimizing for the expected reward objective, but can arbitrarily choose and weight the region in the reward distribution that is most related to our down-stream task.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.