- 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
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 .
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.
Thank you for the review 1/2
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 α 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.
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). When all the weights are equal, this ratio is η=1, when the objective is the max@k, then there is only one j 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.
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.