acceptodds
Under review as a conference paper at ICLR 2027

The Price of Calibration in Learning from Comparisons

Abstract

We study numerical regret when each round permits at most a fixed number of comparisons and at most of rounds receive numerical audits. We first classify comparison-only learnability for arbitrary families of continuous symmetric links. Sublinear regret is possible exactly when one polynomial of degree at most the label cap recovers every numerical half-gap up to an unknown positive scale bounded away from zero. The minimax rate is then square-root; otherwise it is linear. Thus known-link reconstruction, shared numerical interpretation, and uniform signal strength are distinct requirements. We then quantify the cost of missing calibration. For a smooth one-parameter family, three labels give uniformly bounded unbiased gap estimation when calibration is known. For fixed actions and unknown parameter in a radius- interval, the minimax regret becomes . The lower bound allows audits selected after complete current transcripts. A fixed latent comparison distribution extends the same budget law to a quintic family and every fixed cap , with -dependent constants. In recorded LLM-judgment and human-score replays, a direct-judge baseline outperforms the audited methods on the principal training task; removing its rule does not reverse the reported training differences. These observations separate a worst-case need for numerical information from its finite-task value.

Primary area:
learning theory
Keywords:
comparison learning, numerical audits, minimax regret, calibration uncertainty

Reviews

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

The paper studies online learning with numerical regret. At each round, the learner draws two actions, accrues their average utility, gets at most m binary comparisons of that pair, and can buy exact numerical scores for at most BB of the TT rounds. The authors characterize when comparisons alone achieve sub-linear regret. For a cubic link family, they show that known calibration gives regret of order T\sqrt{T} without audits, while unknown calibration within radius rr adds a linear term. They extend this to a quintic family and to smooth changes of link shape. On recorded HelpSteer2 judgments, a baseline that follows the critic judge outperforms all audited methods, and audits do not improve over comparison-only learning.

Critical strengths
  1. The main contribution is Theorem 3.1, which gives a necessary and sufficient condition for comparisons alone to achieve sublinear regret under a fixed label cap. The condition requires one polynomial of degree at most m that recovers every numerical gap up to a positive scale. This separates three failure modes: a non-polynomial inverse, inconsistent shapes across the family, and vanishing signal strength. A notable consequence is that under the standard logistic link, any fixed cap gives linear regret even when the temperature is known.

  2. The audit lower bound is technically careful and general. It bounds score information conditional on every pre-audit transcript, including same-type audits, rather than only matching the marginal comparison laws. Proposition J.2 shows that the cost arises for any regular C2C^2 change of link shape, by fixing the latent comparison distribution and varying only its numerical interpretation. The phenomenon is therefore not an artifact of the cubic construction, although the paper gives this argument only one paragraph in Section 4.3.

Critical weaknesses
  1. The writing is disorganized to the point that the paper is very difficult to follow. Some examples include:
  • Several key terms and quantities are used before they are defined. For instance, half-gap, admission, and transcript appear early without definition, and θ and D_θ are used in Figure 1 and Section 2, while the link family they refer to is only given in Section 3.2.
  • The cubic family in (3.2) is introduced without motivation, and the reason for its form appears only later in the lower-bound construction.
  • Equation (4.3) relies on quantities that are not defined in the main text.
  • Section 2 is too brief. It should be expanded to define the protocol, the link family, and the minimax values before they are used.
  1. The experiments do not test the theoretical model, and the empirical conclusions are fragile. Some examples include:
  • The theory assumes m conditionally independent comparisons of the same pair from a fixed link. The replay uses a single recorded judgment per pair, so this setting never occurs.
  • Algorithm 1 is never evaluated. Its nominal route requires a declared radius r within the cubic family, which has no meaning for real judges. The evaluated Audit+comparison method is a heuristic advice mixture without a numerical-regret guarantee for its comparison component.
  • The best learning method is Audited-mean, a greedy baseline with no adversarial guarantee. This suggests that the worst-case analysis does not explain the observed behavior.
  • The strong direct-critic result depends heavily on which critic is followed. Following GPT-4o gives training regret of 0.92, while following Gemini or Nemotron gives 12.81 and 17.31, and the ranking changes on validation (Table 3).
Questions for authors
  1. How can the experiments be modified to better reflect the theory?

  2. The matching upper bound selects either the nominal route or the audit-only route before the run. Can comparisons and audits be combined to improve on both? In Theorem 4.1, the lower-bound constant decreases with m, while the upper bound does not depend on m, which suggests such a combination could help when m is large.

  3. Why does adding audits to the comparison advice increase regret in the replay (96.69 for Audit+comparison versus 90.45 for comparison-only in Table 2)? Is this caused by the learning rate or exploration choices dictated by the worst-case analysis?

1 comment

We are sorry that the original presentation did not guide readers through the model and reasoning. We have revised the paper around the specific problems you identified.

  1. Definitions and the cubic construction

Section 2 now defines the feedback protocol, half-gap, transcript, link family and minimax benchmark before the results. We removed “admission.” Section 4.1 explains the cubic choice before giving its formula: three independent judgments can estimate a cubic inverse without bias, allowing us to isolate the cost of an unknown link. The endpoint and interpolation conditions then determine its coefficients. Section 4.2 defines the conditional audit distribution before the KL bound. Figure 1 no longer introduces θ or Dθ before their definitions.

  1. “How can the experiments be modified to better reflect the theory?”

We now evaluate Algorithm 1 under its stated model: utilities from the cubic lower-bound construction, three independent judgments of the same pair from its link, a declared radius r and a prescribed audit budget. The algorithm selects its route from the regret bounds before each run (§6.1; Appendix H.1). Averaged over the two environments at K=2, T=131,072 and r=1/16, known-link regret is 1787.95, below the 1997.29 lower bound for unknown-link learners with at most three judgments per round and no audits. Algorithm 1 with B=0 gives 2073.47.

The human panels in §6.2 separately test gap estimation with three judgments per pair. The recorded-answer replay has one verdict per pair and does not instantiate the repeated-comparison model. It evaluates Audit+comparison, whose guarantee against the best fixed rule comes from updates using audited ratings and holds for any predictable comparison adviser (Appendix D.6). This gives no numerical-regret guarantee for the adviser alone and requires no cubic-family radius for real judges.

On the GPT-4o training replay, Audited-mean remains the strongest learning baseline, with regret 67.38. The worst-case bound does not explain this empirical ranking. We also report all three direct critics on both splits. GPT-4o leads on training, whereas Nemotron leads on validation for helpfulness (Tables 8–9). The empirical conclusions are therefore stated for the corresponding critic and split.

  1. Can a joint update improve both routes, especially for large m?

Your observation about the m-dependent lower-bound constant is correct. It leaves room for better constants and for improvement as m grows. Corollary F.3 shows only that, for each fixed K and m≥3, arbitrary joint use of comparisons and audits has minimax rate Θ_{K,m}(√T+T min{r,(B+1)^(−1/2)}). The constants may depend on m. The optimal dependence on a growing judgment cap remains open.

  1. Why is 96.69 higher than 90.45, and is tuning responsible?

In the GPT-4o training setting you cite, that comparison changes both feedback and initial weights. Audit+comparison initially gives 0.9 to the comparison adviser and 0.1 to fixed rules. Freezing these mixture weights, while letting the adviser continue learning, adds 9.00±1.30 regret relative to comparison-only. Updating the same mixture from ratings recovers 2.76±0.89, leaving the observed 6.24 excess.

The initial mixture thus accounts for most of the excess. The 0.9/0.1 split is a design choice; the guarantee allows other positive initial rule weights, with a corresponding change in its bound. Separately, dividing the denominator offset by four lowers regret by 1.76±0.60; dividing only the learning rate raises it by 1.66±0.81. Appendix I.5 reports all 126 settings; these tuning effects are not distinguishable from zero on validation. Intervals are paired 95% Monte Carlo intervals.

We would be grateful for the opportunity to have the revised paper reconsidered.

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

The paper studies online learning from comparisons, in which the feedback to the learner is obtained after the rewards are passed through a "link function". The formal model is as follows: there are KK arms that an algorithm can pull. At each step, the algorithm must commit to some distribution over the arms. The environment then fixes the rewards u_t. Two indices I_t and J_t are sampled from the algorithm's distribution, and it receives a feedback about which of the two is better (i.e., if u_t[I_t] > u_t[J_t]) or vice versa. The way it receives feedback is indirect though, governed by p(u_t[I_t] - u_t[J_t]), where p() is a link function). The algorithm can either work with this feedback, or it can "audit", in which case it sees the true values of u_t[I_t] and u_t[J_t]. The paper studies the trade-offs between the number of audits and the regret that the algorithm can achieve.

Critical strengths
  • It is nice that the authors can precisely characterize what link functions allow a "no audit" \sqrt{T} regret algorithm. Informally, we require the p() to be able to provide sufficient information about the sign of u_t[I_t] - u_t[J_t]. This is captured by the conditions in Theorem 3.1.

  • Overall, the paper provides both upper and lower bounds, and discusses what happens for various choices of the link function p; i.e., it gives a good understanding of the problem landscape.

Critical weaknesses

The biggest drawback with the paper is that it's heavily AI written. It is difficult to read, the problem setting and motivation are not described sufficiently, and the authors have not put in the effort to add exposition. Given that the problem itself is of somewhat niche interest (the contribution is primarily to characterize p()), I feel that the paper needs much better motivation of the results and exposition and clarity of writing to be acceptable to ICLR.

Questions for authors

The authors must justify the model a bit more. For example:

  • Why are the actions both drawn independently from a distribution? Why can't the algorithm provide a joint distribution?
  • The term "calibration" has many meanings in ML, especially in the fairness literature; the paper needs to have a bit more discussion about prior and related (and unrelated!) work.
  • It will be nice if the paper gives a few cleanly motivated examples: one in which the link function allows for low regret with no audits, one where low regrets are possible with "few" audits, and one where regret is pretty bad unless we audit all the time. To me, this wasn't apparent from the paper..
2 comments

We are sorry that the original paper left the motivation and the model difficult to follow. We have rewritten the main text to fix this. The introduction now starts from online learning and regret, and then explains the motivation with a concrete application. Section 2 gives the protocol as three numbered steps. Every term is defined before it is used, and Figure 1(b) and Table 1 summarize the results.

Motivation.

Think of a service that chooses among several language models. Human evaluators find it easier to say which of two answers is better than to give each answer a score. But the service cares about total utility, and total utility depends on how much better an answer is. For example, a model that is slightly better on nine requests and much worse on the tenth wins most comparisons, yet its total utility is lower. The paper asks two questions. When are comparisons enough for this goal? And how much do occasional numerical ratings, which we call audits, help?

Why draw the two actions independently instead of from a joint distribution?

The learner may use any joint distribution (Section 2). Our algorithms use independent draws for one reason. The second action then acts as a random opponent whose expected utility is the same whichever action comes first. This lets us turn a comparison of two actions into a score for the first one (Section 5.1). Nothing is lost by this choice: our lower bounds hold for every joint distribution, so the rates are the same (Proposition G.1).

What does "calibration" mean here?

It means knowing the link, that is, the function that turns a utility difference into a preference probability. This differs from the usual meaning, in which predicted probabilities should match observed frequencies, as in forecasting and in the fairness literature (Guo et al., 2017; Kleinberg et al., 2017). The introduction now states this difference, and Appendix K discusses the related work.

Three clean examples (also in Table 1 and Figure 1(b)).

  1. No audits are needed. Compare two classifiers on one random test example. The link is linear, and one comparison per round gives Θ(√T) regret.
  2. A few audits are enough. In our cubic family the link is known only up to an error r. With B audits the regret is Θ(√T + T·min{r, 1/√(B+1)}). So √T audits, a vanishing fraction of the rounds, already give sublinear regret, namely Θ(T^(3/4)).
  3. Audits are needed all the time. Take a logistic link whose utility differences can be any value in an interval. No fixed number of comparisons per round is enough. The regret with B audits is Θ(T/√(B+1)), so √T regret requires auditing a constant fraction of the rounds (new Corollary 3.2).

We would be grateful for the opportunity to have the revised paper reconsidered.

Hi, and thanks for taking the time to review our paper. As the discussion period wraps up, we wanted to check whether we’ve addressed your concerns. If so, we’d really appreciate it if you’d consider raising your score.

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

This paper studies online learning with comparison feedback when the target is numerical utility. There are KK actions and TT rounds. In each round, the learner chooses a distribution qtq_t, and two actions are independently sampled from this distribution. The average utility of these two actions is counted as the learner’s reward. The regret is measured against the best fixed action in hindsight. The utilities can change over rounds.

The learner does not directly observe the utilities. It can receive at most mm comparison labels for the same selected pair in each round. These labels are assumed to be conditionally independent. Their distribution is determined by a link function pθp_\theta, which maps the numerical half-gap to the probability of winning a comparison. The link family is known, and the parameter θ\theta is fixed during the run. After seeing the comparison results, the learner can also request a numerical audit, which reveals the scores of the selected actions. There are at most BB audited rounds.

The paper first characterizes when comparison feedback alone is enough for sublinear numerical regret. The condition requires a common polynomial of degree at most mm to recover the numerical half-gap, up to a link-dependent positive scale. The scale must also be uniformly bounded away from zero.

The main separation is shown using a cubic inverse-link family and three comparison labels per round. When the learner knows θ\theta, a bounded unbiased gap estimator can be constructed, giving ΘK(T)\Theta_K(\sqrt{T}) regret without audits. When the learner only knows ∣θ∣≤r|\theta|\le r, the minimax regret becomes ΘK(T+Tmin⁡r,(B+1)−1/2)\Theta_K(\sqrt{T}+T\min\\{r,(B+1)^{-1/2}\\}).

For the upper bound, the algorithm chooses between two methods before the run. Both methods use exponential-weight updates. The first method uses comparison feedback and the central calibration θ=0\theta=0. This gives an approximate numerical-gap estimator, with bias controlled by rr, and obtains OK(T+rT)O_K(\sqrt{T}+rT) regret. The second method uses only audited numerical scores for its updates. It samples audit rounds using the remaining budget and remaining horizon, and corrects for both action-sampling and audit probabilities. This gives OK(T/B+1)O_K(T/\sqrt{B+1}) regret. Choosing the better guarantee gives the matching upper bound. The algorithm does not need to explicitly estimate θ\theta.

Critical strengths
  1. The comparison-only characterization is useful.

Theorem 3.1 gives both necessary and sufficient conditions. It separates whether one known link allows numerical recovery, whether different links share the same recovery rule, and whether the signal is uniformly strong enough.

  1. The lower-bound analysis considers adaptive audit decisions.

The learner can see the current comparison transcript before deciding whether to audit. The proof controls the numerical information conditional on this transcript. This makes the result stronger than a lower bound for a fixed audit schedule.

Critical weaknesses
  1. The repeated-comparison assumption needs more practical support.

The main result assumes that the learner can obtain independent labels for the same pair while the underlying utilities remain fixed. This gives more information than the usual one-label-per-round dueling feedback. The independence assumption is important for the polynomial estimator. For example, the identity E[W1W2W3∣x]=(E[W1∣x])3\mathbb{E}[W_1W_2W_3\mid x]=(\mathbb{E}[W_1\mid x])^3 generally does not hold for dependent labels. It is unclear whether the motivating judgment process provides this type of feedback. The recorded-data experiments do not directly check this assumption.

Questions for authors
  1. Can you give a concrete judgment process where repeated labels are conditionally independent and follow the same link pθp_\theta? Can this assumption be checked using repeated judgments?

  2. Which practically relevant link families support the known-versus-unknown calibration separation? How do the conclusions change when the inverse link is only approximately polynomial?

2 comments

Thank you for the careful review. We answer your questions one by one. All section numbers refer to the revised PDF.

Can a concrete judgment process give conditionally independent labels from the same link?

Yes. Here is a simple process in which both assumptions hold exactly. Take two classifiers and a labeled batch of examples. To compare them, draw one example at random and prefer the classifier that gets it right; if both or neither do, flip a coin. Each comparison uses a fresh example, so repeated comparisons are independent. The chance that a classifier is preferred depends only on the difference of the two accuracies, so every pair follows the same link, and this link is linear.

A second version of the test gives a logistic link. We ran it on real digit classifiers, and the observed frequencies match the predicted ones (Section 2, Appendix H.3, Table 5).

For human judges, independence holds when each judgment of a pair comes from a different person, drawn at random from one population. A common link is then a further assumption. Section 2 now says this explicitly.

Can repeated judgments check the assumptions?

Yes, and Section 6.2 does this on human data. In a published experiment, 119 people chose between two lines, for 60 pairs, and were paid in proportion to the length of the line they chose. So the true utility difference of every pair is known. We fitted one logistic curve on 59 people and used it to predict the choices of the other 60. It predicts well: the log loss is 0.488, against 0.560 for a prediction that ignores the pair. Adding other features of the pair improves this only to 0.484. One common link therefore explains most of what can be predicted.

An LLM judge behaves differently. Its repeated calls show no sign of dependence, but its preferences do not follow one common link with respect to human ratings (Appendix J.3). The replay of recorded data has one verdict per pair, so it cannot test the assumptions. Section 6.3 now presents it as outside the model.

What if the assumptions hold only approximately?

Then the guarantee degrades gradually (new Proposition 5.1). The result covers two kinds of error together: an inverse link that is only approximately polynomial, and labels that are dependent. The regret is at most a √T term plus 4T times the total error. A small violation therefore costs little, but sublinear regret needs the error to go to zero.

Audits reduce this cost. With B audits and a known link, an approximation error ε contributes only of order εT/√(B+1) (Theorem D.1). For the logistic link, more comparisons per round make ε smaller (Appendix G.2).

Which practical link families show the gap between a known and an unknown link?

The logistic (Bradley–Terry) link is the main case. The answer depends on which utility differences can occur.

  • If they can take any value in an interval, no fixed number of comparisons is enough, even when the link is known. Only audits help, and the regret with B audits is Θ(T/√(B+1)) (new Corollary 3.2).
  • If they take only a few known values, for example with utilities in {−1, 0, 1}, three comparisons are enough when the slope is known. The regret is Θ(√T) for a known slope and Θ(√T + T·min{r, 1/√(B+1)}) for a slope known only up to an error r (Proposition G.4). We reproduce this gap with judgments built from real classifier predictions: the regret is 631 with the known slope and about 1270 without it (Section 6.1, Appendix H.4).

More generally, the same lower bound holds for every smooth family in which the shape of the link changes (new Proposition 4.2).

We would be grateful for the opportunity to have the revised paper reconsidered.

Hi, and thanks for taking the time to review our paper. As the discussion period wraps up, we wanted to check whether we’ve addressed your concerns. If so, we’d really appreciate it if you’d consider raising your score.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.