- Rating
- 2
- Confidence
- 3
- Informativeness
- 2
- Presentation
- 1
- Soundness
- 3
Read review
Paper summary
This paper studies a tabular softmax model (the tabular size is ) learning from pair data with a biased reward annotator. They established a so-called "recovery threshold" result, showing that if the bias scale is somehow lower than the threshold, then convergence is guarenteed; and if larger than the threshold, they can construct an evaluator wrongly prefer a sub-optimal action to the optimal action, not converging to the optimal action in some settings; and if equal to the threshold, it still converges if , and they constructed counterexamples for . They also conducted some small synthetic experiments with tiny .
Critical strengths
- I think this paper's theoretical results are insteresting to me, such as the convergence analysis technique and the concept of recovery threshold. The proof technique using martingale might be of independent interest. And the studied setting is clean and related to some topics in preference learning and machine learning.
Critical weaknesses
- The paper-writing is terrible. I find it very hard to follow the paper. There are "too many theories" and the organization is not arranged very well. Sections 3–4 explain why the transition occurs at four actions, however, this should not be viewed as a major contribution which can take so many pages. The transition at four actions is only about the case when exactly equals to the threshold, which is a corner case, and the results can be viewed as: only cases are proved where is already a trivial case, and cannot be proved in this way (which is unnecessary to show in such a detailed way because we already have counterexamples in Theorem 2). The idea is not very new, as there are some analogous analysis in [1][2]. I feel that the paper develops an excessive amount of technical machinery without establishing sufficiently meaningful results.
- The results are too specific and limited. One may expect to see the application of this idea in preference learning. The current version is more like solving a mathematic problem in which the general audience of ICLR might not be very interested. For example, one can try to relate the method with some standard preference learning practice, such as [3], which studies a similar pairwise RL training objective, and [4], which studies the tabular softmax model in DPO. It's also unclear whether the proposed Balanced-query recovery is a major contribution as it is only covered in theorem 5 without further detailed discussions, such as how to deploy it in practice.
[1] Escaping the Gravitational Pull of Softmax. NeurIPS 2020.
[2] Delightful Gradients Accelerate Corner Escape. arXiv.
[3] REBEL: Reinforcement Learning via Regressing Relative Rewards. NeurIPS 2024.
[4] The Crucial Role of Samplers in Online Direct Preference Optimization. ICLR 2025.
Questions for authors
Please see my comments in "Weakness".
3 comments
Connections to Preference Learning
“The results are too specific and limited. One may expect to see the application of this idea in preference learning.”
The original analysis focused on real-valued contrasts and a particular evaluator family. To see whether the failure mechanism extends beyond this setting, we added Proposition 4 (Section 3.1), which gives a local failure criterion that also applies to Bradley–Terry binary feedback. For , the optimal action can beat every alternative with probability above at every interior policy, yet the sampled update can converge to a suboptimal vertex with high probability from a suitable open set of initializations. The actor remains a finite tabular softmax policy.
We also tested the mechanism with a less structured evaluator, using PRM800K mathematical reasoning steps and human ratings. The text-kernel evaluator is refitted under policy-dependent weights as the actor changes. We compare the sampled update (U), full-information update (FI), and balanced-query update (BQ). After 100,000 scalar evaluator calls, the mean optimal-action masses are:
| Problems | U | FI | BQ |
|---|---|---|---|
| All 37 eligible official-test problems | 0.028 | 0.919 | 0.657 |
| 16 initially correctly ranked problems | 0.063 | 1.000 | 0.688 |
The 16-problem group was fixed before the actor runs. Across all 128 U trajectories in this group, the evaluator ranks the optimum first at every visited policy. Yet on 15 of the 16 problems, none of eight U runs reaches . The median score margin falls from 0.0132 to 0.00060, while the probability of comparing the optimal action falls from 0.0198 to 0.00113. Since the evaluator is fitted using each task's offline human ratings, this is a controlled study on real reasoning text rather than live LLM retraining (Section 6; Appendix H.10).
“For example, one can try to relate the method with some standard preference learning practice, such as [3], which studies a similar pairwise RL training objective, and [4], which studies the tabular softmax model in DPO.”
Section 5.2 now makes this connection precise at the update level. For a sampled pair with real-valued contrast , the relative-reward regression loss can be written in tabular softmax logits as
At , a gradient step of size gives exactly , our update (U). If the conditional mean contrasts equal the evaluator score differences, exact minimization of the expected loss over a full-support pair distribution gives the noiseless full-information multiplicative update with step . A DPO step with its reference reset to the current policy gives the binary-feedback form of (U). These identities concern the specified updates, not the full REBEL algorithm or standard fixed-reference DPO. Reference [4] studies fixed-reference DPO with fixed Bradley–Terry rewards and a KL-regularized target, whereas our target is the optimal vertex under policy-dependent evaluation (Appendix G.7).
“It's also unclear whether the proposed Balanced-query recovery is a major contribution as it is only covered in theorem 5 without further detailed discussions, such as how to deploy it in practice.”
The purpose of balanced queries is to distinguish failure of the sampled update from loss of information in the evaluator. We have expanded Section 5.3 (now Theorem 7) to explain this distinction and the access that BQ requires. Instead of evaluating pair at the actor's current policy, BQ uses . The dispersion bound then gives , so the optimal action retains a positive pairwise margin whenever , without a sensitivity assumption. Theorem 7 proves recovery up to this evaluator-only identification limit.
BQ requires access to the evaluator at counterfactual policies, which a fixed judge API does not automatically provide. In the PRM800K experiment, we implement this access by reweighting and refitting the evaluator. We also compared the updates under matched evaluator-call budgets. On quadratic compression, BQ reaches in 59/64 runs versus 28/64 for U after 200,000 calls, although its global factor makes it slower in other settings (Section 6; Appendix H.8).
We would be glad to clarify any remaining points.
Thank you for your rebuttal. I appreciate the reorganization of the paper. The rate analysis is better than previous results. However, I still have concerns remained:
- As the authors admitted, "Since the evaluator is fitted using each task's offline human ratings, this is a controlled study on real reasoning text rather than live LLM retraining", the supplemental PRM800K experiments are still toy experiments with only four actions, while in the practice of REBEL and online DPO, the number of actions can be much larger than . For the same reason, the theorems showing a different between and , as a separate theoretical tabular result, are not very interesting to me.
- This paper points a theoretically-identified issue in preference training when , however, it's not identified in practical preference learning training beyond the 4-action toy experiments. What's more, the authors proposed BQ as a remedy, while the practical effect of BQ is still unclear. This further limits this paper's contribution.
Presentation and Theoretical Significance
Thank you for the detailed comments. We address your concerns below.
“I find it very hard to follow the paper. There are "too many theories" and the organization is not arranged very well.”
The original presentation introduced several technical ideas before explaining how they fit together. We have revised the exposition to make the main argument clearer. The Introduction now explains bias dispersion and pairwise bias contrasts when they first appear, and Section 2.2 motivates the recovery threshold through endpoint cancellation. We also revisited the original four-action example in Section 3 to explain the role of the auxiliary actions. Their comparisons continue to favor the designated suboptimal action, while the auxiliaries themselves become rare. Through the conserved-product structure, the optimal action's mass also decreases, and its shrinking score margin can make the total corrective drift finite despite infinitely many comparisons.
Section 4 has also been reorganized around the proof itself. We first use the evaluator assumptions to bound the optimal action's aggregate score advantage. After removing the convergent martingale term, we introduce reciprocal coordinates whose conserved product controls how rare the optimal action can become. These bounds lead to the integrability test, and we now explain where its exponent K−2 comes from. We also moved the bias-geometry figure and full sample-path rate theorem to Appendices A and E, so that the main text can focus on the central argument.
“Sections 3–4 explain why the transition occurs at four actions, however, this should not be viewed as a major contribution which can take so many pages.”
The original presentation focused on the exact threshold, which may have made the distinction seem specific to that case. We therefore investigated whether it persists strictly below the threshold. The new Theorem 2 shows that the same distinction governs near-critical recovery budgets.
Let κ=Δ−ΨL−1(ε)>0. A cumulative step-size budget of O(κ−(K−1)) suffices for high-probability first hitting. For every fixed K≥4, we construct a family of correctly ranked, strictly subcritical evaluators, one for each κ, with a matching Ω(κ−(K−1)) lower bound from an open set of initializations independent of κ. For K≤3 and fixed L>0, the required budget remains uniformly bounded up to the threshold (Section 2.3; Appendix D). The difference comes from the integral ∫0∞(1+τ)−(K−2),dτ, which diverges for K≤3 but converges for K≥4. The same argument therefore explains both recovery at the boundary and the slowdown approaching it.
“The idea is not very new, as there are some analogous analysis in [1][2].”
There is a connection to earlier work on escaping suboptimal softmax corners, and we have made it more explicit in the Introduction and Appendix G.7. Escaping the Gravitational Pull of Softmax and Delightful Gradients Accelerate Corner Escape study slow escape under fixed rewards or modified gradients. Our setting has an additional difficulty: the evaluator's score margin can itself shrink as the policy changes. As a result, the total corrective drift can be finite even when the optimum remains correctly ranked and is compared infinitely often. The policy can then converge to a wrong vertex rather than merely recover slowly.