acceptodds
Under review as a conference paper at ICLR 2027

Context-Aware Preference Bandits with Heterogeneous Human Feedback

Abstract

In context-aware preference learning, an online learner infers user preferences from sequential feedback. We study this problem under the contextual bandit framework, where each arm is associated with an unknown feature vector. However, context dictates not only the optimal arm but also alters the evaluation scale itself, in that user feedback across scenarios is inherently uncalibrated and highly heterogeneous. To capture these effects, we model the linear utility of each arm via a context-dependent affine calibration, parameterized by a multiplicative scale and an additive offset. We propose a phased elimination algorithm that combines pilot-estimation sample splitting with a one-step Newton correction. For pointwise rating feedback, we group contexts using score binning and learn each group separately, achieving a near-optimal regret, where parameterizes the tail decay rate of the score bounds. For pairwise comparison feedback, the additive offset cancels out exactly, yielding a near-optimal regret for any . We further establish lower bounds for both feedback protocols, matching the common estimation term in our upper bounds. Experiments on synthetic data and benchmark datasets validate our theoretical findings.

Primary area:
learning theory
Keywords:
Online Learning, Preference Bandits, Human Feedback, Regret Bounds

Reviews

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

This paper studies contextual preference bandits with KK arms whose latent utilities ⟨zt,θi⋆⟩\langle z_t, \theta_i^\star \rangle pass through a context-dependent affine calibration, st,i=αt⟨zt,θi⋆⟩+βts_{t,i} = \alpha_t \langle z_t, \theta_i^\star \rangle + \beta_t. The sensitivity αt>0\alpha_t > 0 and the common offset βt\beta_t are revealed before each action and may be unbounded, subject to empirical exponential tail conditions. Feedback is either a pointwise rating Bernoulli(σ(st,at))\mathrm{Bernoulli}(\sigma(s_{t,a_t})) or a pairwise comparison Bernoulli(σ(st,at−st,bt))\mathrm{Bernoulli}(\sigma(s_{t,a_t} - s_{t,b_t})), in which the offset cancels. The proposed algorithm, BinPilot, assigns rounds to bins according to a bound on the logit magnitude, runs EXP4.P (pointwise) or Sparring EXP4.P (pairwise) during a bin-specific startup phase, and then applies phased elimination with a pilot logistic estimate followed by a one-step Newton correction on held-out samples (following Bae & Lee, 2026). The main results are O~(dKT+poly(d,K) T1/(1+ρpt))\tilde{O}(\sqrt{dKT} + \mathrm{poly}(d,K)\, T^{1/(1+\rho_{\mathrm{pt}})}) regret for pointwise feedback and O~(dKT+poly(d,K) T1/(2+ρpr))\tilde{O}(\sqrt{dKT} + \mathrm{poly}(d,K)\, T^{1/(2+\rho_{\mathrm{pr}})}), hence O~(T)\tilde{O}(\sqrt{T}) for any positive sensitivity tail rate, for pairwise feedback. These are complemented by Ω(dKT)\Omega(\sqrt{dKT}) lower bounds for both protocols and an Ω(T1/(1+ρpt))\Omega(T^{1/(1+\rho_{\mathrm{pt}})}) pointwise lower bound (Appendix D.3). Experiments use a synthetic two-arm instance and PrivacyLens contexts with synthetic arms and calibration.

Critical strengths
  1. A relevant phenomenon with a clean protocol-level insight. Feedback saturation under unbounded calibration is a natural model of heterogeneous evaluation standards. The paper identifies why pairwise feedback is more robust: the offset cancels, and at elimination levels ℓ≥3\ell \ge 3 all compared score differences lie in [−1,1][-1, 1], so the leading pairwise estimation term is free of the curvature constant κm\kappa_m (Appendix C.1.3).
  2. A complete picture in the horizon exponent. The pointwise lower bound in Appendix D.3, which front-loads saturated rounds so that the learner cannot exploit later informative ones, is a neat construction showing that the T1/(1+ρpt)T^{1/(1+\rho_{\mathrm{pt}})} term is unavoidable.
Critical weaknesses
  1. Unexpectedly high regret in the synthetic experiment. Under the construction in Section 4.1, always selecting the wrong arm yields regret ∑t2αt≈2.10×106\sum_t 2\alpha_t \approx 2.10 \times 10^6 at T=221T = 2^{21}, and uniform random play about half of that. The reported pointwise regret for b=0.05b = 0.05 is 1.86×1061.86 \times 10^6 (Appendix E.1), which is close to the maximum and well above random play; similarly, at T=28T = 2^8 all four curves in Figure 1(a) lie close to the maximum (≈253\approx 253). This is hard to reconcile with the described algorithm and may indicate an implementation issue or a mismatch with the described setup. Until this is clarified, it is difficult to read Figure 1(a) as support for the theory.

  2. Interpretation of the slow-tail results. Even setting this aside, the slow-tail curve seems to reflect the per-bin design rather than intrinsic hardness. Under b=0.05b = 0.05, with the experimental startup length ⌈80κm⌉\lceil 80\kappa_m \rceil, bins with m≥8m \ge 8 cannot leave startup within T=221T = 2^{21} rounds, and about 70% of rounds fall into such bins. Since all bins share the same two contexts and the same θ⋆\theta^\star, a learner that pools information across bins could likely avoid much of this cost. This also raises the question of why bins are learned separately when the calibration is known.

  3. Gap between the analyzed and the evaluated algorithms. The startup phase uses EXP4.P over a policy class whose size is exponential in dKdK (Appendix A.3.3), which is not mentioned in the main text, and the experiments use simplified variants of the method (Appendix E). On PrivacyLens, the comparison mainly contrasts using versus ignoring the known calibration, rather than evaluating the proposed components. In addition, the pairwise difference in Table 2 is not statistically significant, which seems at odds with the claim in Section 1 that the method "consistently achieves lower regret".

  4. Scope of the model and of the optimality claims. The calibration is assumed to be known exactly, so the setting does not cover feedback with unknown or misspecified calibration, which appears central to the motivation. Furthermore, the claim of an optimal O~(dKT)\tilde{O}(\sqrt{dKT}) rate in the uncalibrated case hides a constant growing like eLS/2e^{LS/2} in the pointwise bound (through κm\kappa_m in Appendix C), whereas the matching lower bound uses near-zero logits. Reporting the dependence on LL, SS, and the tail constants in Theorem 3.2 would make the result easier to interpret.

Questions for authors
  1. Could the authors explain the regret levels in Figure 1(a) and Appendix E.1? Under the construction of Section 4.1, always choosing the wrong arm yields ≈2.10×106\approx 2.10 \times 10^6 at T=221T = 2^{21} and uniform random play ≈1.05×106\approx 1.05 \times 10^6 in expectation, yet the reported pointwise regret is 1.86×1061.86 \times 10^6, and at T=28T = 2^8 all four curves are close to the maximum. Please report per-horizon values together with a uniform-random reference, and split the regret into startup and post-startup rounds: since most slow-tail rounds lie in bins that never leave startup, where ratings are nearly uninformative, one would expect that phase to perform close to uniform play.
  2. Is per-bin isolation necessary for the guarantees? Since the calibration is known, a single estimator that pools all post-startup samples with curvature-dependent weights would seem to retain the confidence analysis while avoiding the per-bin initialization cost Im\mathcal I_m. More generally, when the directions encountered on saturated rounds are also covered by unsaturated rounds, as in the synthetic instance, can the T1/(1+ρpt)T^{1/(1+\rho_{\mathrm{pt}})} term be avoided? In the construction of Theorem D.1, the saturated rounds precede the informative ones.
  3. (Minor) Lines 85–88: the sentence "For pairwise comparisons, we prove a near-optimal regret bound of O~(T)\tilde{O}(\sqrt{T}) under any positive sensitivity tail rate" appears twice.
Reviewer_jvfeOpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

The paper studies contextual preference bandits with unknown linear arm utilities and known context-dependent affine calibration. Binary ratings follow a logistic model of the calibrated score, whereas comparisons depend on score differences and remove the common offset. Regret measures calibrated utility gaps. The authors propose an algorithmic framework (BINPILOT) which combines calibration bins, protocol-specific startup, phased elimination, and pilot estimation with a one-step correction. Under empirical exponential calibration tails, the paper obtains pointwise rating regret O~(T+T1/(1+ρpt))\widetilde O(\sqrt T+T^{1/(1+\rho_{\rm pt})}) and pairwise comparison regret O~(T)\widetilde O(\sqrt T) for fixed problem parameters. The supplement gives estimation lower bounds and an additional rating lower bound supporting the horizon-rate separation in its stated dimensional regime. Experiments include a controlled synthetic instance and a semi-synthetic PrivacyLens environment.

Critical strengths
  • A worst-case separation between feedback protocols as given by Theorem D.1. For d≥2d\geq2 in the stated model and ρpt<1\rho_{\rm pt}<1, the poorer rating exponent is an information limitation, not just an artifact of BINPILOT's separate learners.

  • A carefully integrated analysis of heterogeneous calibration. The supplement makes concrete how conditional sample separation, pilot-centered regularization, elimination-induced curvature, and a protocol-specific startup combine to control regret.

Critical weaknesses
  • The practical scope is substantially narrower than the broad motivation suggests. Appendix A.3.3 explicitly states that startup may require exponentially many experts in D=dKD=dK, and that the construction has no polynomial-time guarantee. The common routine also assumes exact constrained pilot minimization and incurs O(D3)O(D^3) dense factorization cost. The experiments use modified procedures, so they do not demonstrate practical feasibility of the theorem's algorithm. Moreover, exact calibration values must be supplied before every action; the method does not learn heterogeneous human standards themselves. The paper should highlight these restrictions. Its optimality claim also concerns horizon dependence: Theorem D.1 assumes d≥2d\geq2, and the lower bounds do not match the dimension and arm-count factors in the initialization terms.

  • The experiments support calibration awareness, but do not highlight BINPILOT's contribution. PrivacyLens uses real embeddings with constructed utilities, calibration, and feedback. The proposed learner receives the true calibration while the baseline assumes unit sensitivity and zero offset; routing and action selection also differ. A global calibration-aware baseline is still missing.

Questions for authors
  • Can the main claims explicitly distinguish fixed-parameter horizon optimality from joint optimality in (d,K,T)(d,K,T), and specify the dimensional regime of the separation? Theorem D.1 uses d≥2d\geq2 and does not settle the d=1d=1 tail-dependent case. Is that case intentionally outside the claimed lower-bound result?

  • Does the PrivacyLens pointwise advantage persist against a global learner given the same true calibration and comparable initialization and action-selection rules? Such a comparison would distinguish the benefit of calibrated likelihoods from the benefit of binning.

  • Which theoretical components can be implemented at the reported experimental scales without enumerating the finite policy class?

1 comment
AuthorsOpenReview ↗

Response to Reviewer jvfe

Thank you for your careful review and for recognizing the theoretical guarantees and the comparison between feedback protocols. We have revised the manuscript in response to your feedback.

Regret optimality.

We agree that our leading regret terms are tight in their dependence on TT up to logarithmic factors, with the other problem parameters held fixed, consistent with our focus on optimality in TT as in prior work. The common dKT\sqrt{dKT} term is tight jointly in dd, KK, and TT up to logarithmic factors, as shown by our lower bound under constant calibration. The optimal dependence of the initialization terms on dd and KK remains open. We tried to obtain a stronger lower bound by making the learner search among many arms separately in different contexts. These constructions did not improve the powers of dd and KK in our lower bound.

We thank the reviewer for pointing out the missing one-dimensional case. Appendix D.3 now includes Lemma D.2, which proves a pointwise lower bound of Ω(Kρpt/(1+ρpt)T1/(1+ρpt))\Omega\bigl(K^{\rho_{\mathrm{pt}}/(1+\rho_{\mathrm{pt}})}T^{1/(1+\rho_{\mathrm{pt}})}\bigr) for d=1d=1, K≥2K\ge2, and 0<ρpt<10<\rho_{\mathrm{pt}}<1. This matches the slow-tail horizon exponent also in one dimension.

Calibration-aware global baseline.

We have added Calibrated GLM-UCB in the Figure 2 of the revised manuscript, which maintains one global model and uses the true αt\alpha_t and βt\beta_t. The calibrated and uncalibrated controls share the same update and action-rule family and are tuned separately on development seeds. All methods use the same 345/148 historical/online split, with paired context orders and feedback random numbers.

For pointwise feedback, mean regret is 68.215 for Ours, 82.370 for the uncalibrated control, and 68.467 for the calibrated control. Our practical learner is competitive with the calibrated baseline and reduces regret by 17.2% relative to the uncalibrated baseline. Over the last 148 rounds, the corresponding means are 18.578, 25.349, and 19.046, showing that the improvement extends into continued online learning. The revised introduction and experimental discussion now state this conclusion.

Pointwise PrivacyLens results are provided in the revised manuscript (Tables 4–5). Differences are Ours minus the GLM-UCB control, with paired 95% bootstrap intervals from 50 seeds and 2,000 resamples.

RoundsBaseline methodOursBaseline regretDifference95% CI
All 493Uncalibrated68.21582.370-14.155[-20.347, -8.142]
All 493Calibrated68.21568.467-0.252[-6.703, 6.214]
Last 148Uncalibrated18.57825.349-6.770[-8.898, -4.457]
Last 148Calibrated18.57819.046-0.467[-2.910, 2.027]

Both calibrated methods account for changes in rating probability caused by sensitivity and offset, and use optimistic arm selection. These shared features help explain their competitive performance and support the practical value of our pilot/correction adaptation. The global baseline uses a different estimator, so this comparison does not isolate binning. Pooling observations in a single calibrated model is possible; binning provides local curvature and initialization control in our current proof, without being established as intrinsically necessary.

Theory and implementation.

The analyzed algorithm has no polynomial-time guarantee because its EXP4.P-based startup can enumerate exponentially many policies in dKdK. Binning, pilot fitting, and one-step correction can be implemented without that enumeration. Sections 4.1–4.2 and Appendix E now document the practical choices: shorter synthetic startup, adjusted sample-assignment thresholds, and confidence multiplier 1.25; PrivacyLens uses a 32-observation pilot, sequential correction with Sherman–Morrison updates, and two median-based bins initialized from the same historical state. It replaces the theoretical startup and layered procedure.

We hope the new one-dimensional lower bound, calibrated baseline, and implementation clarifications address your concerns about the theoretical guarantees and experimental evidence.

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

This work study the problem of context-aware preference learning, where context alters the evaluation scale itself and user feedback across scenarios is inherently uncalibrated and highly heterogeneous. To capture these effects in the classic contextual bandit models, this work adopts the linear utility, parameterized by a multiplicative scale and an additive offset. It proposes a phased elimination algorithm that, under pointwise rating feedback, achieves O~(T+T1/(1+ρ))\tilde O(\sqrt{T}+T^{1/(1+\rho)}) regret, where ρ\rho relates to the user sensitivity and acceptance standards, Under pairwise rating feedback, this algorithm achieves O~(T)\tilde O(\sqrt{T}) for any ρ\rho. Lower bound and empirical results are provided accordingly.

Critical strengths
  1. The paper's results provide informative comparisons between different feedback regimes.
  2. The paper provides strong theoretical guarantees for the proposed algorithm, which seems to be empirically validated.
Critical weaknesses

The assumptions of this paper are too strong.

  1. I think the biggest weakness of this paper is the assumption that the offsets αt,βt\alpha_t,\beta_t are known to the algorithm, which is usually not the case in practice. Furthermore, the paper assumes that these calibration preserves the ranking of arms. How are the required calibration values obtained in an actual application?
  2. The tail rate assumption in Assumption 2.2 needs real-world insights.
  3. The displayed lower bound matches the common dKT\sqrt{dKT} term, but the upper bounds contain substantial dimension- and arm-dependent terms. Hence there is actually a gap (of d,Kd,K) between the upper and lower bounds, even for the pairwise feedback case, and the paper should clearly state or discuss this gap.

The empirical performance of the algorithm in the pairwise feedback setting is not significantly different from the usual GLM-UCB. The marginal improvement of adopting the method seems minimal, especially in this setting where authors claim to achieve an optimal regret rate in horizon TT.

Questions for authors
  1. In the pairwise feedback setting, can the algorithm choose the same arm twice?
3 comments
AuthorsOpenReview ↗

Response to Reviewer c2HW

Thank you for your careful review and for recognizing the theoretical guarantees and the comparison between feedback protocols. We have revised the manuscript in response to your feedback.

W1/W2: Calibration assumptions.

Our model separates topic-specific evaluation conditions, captured by αt\alpha_t and βt\beta_t, from user-specific preferences, captured by the latent utilities. Sensitivity αt\alpha_t controls how strongly feedback responds to utility, while offset βt\beta_t sets the baseline log-odds of a positive pointwise rating. This follows the standard known-link modeling convention while allowing the evaluation scale to vary across topics.

Some control of this scale is necessary for sublinear worst-case score regret: an unrestricted common offset can make pointwise ratings nearly identical across arms throughout the horizon, even when known. Standard bandit models control the score scale by bounding features and parameters. Our empirical exponential-tail condition generalizes uniformly bounded calibration and is motivated by settings where most topics have moderate evaluation scales and extreme sensitivities or thresholds occur infrequently. Every uniformly bounded calibration sequence satisfies the condition for suitable tail constants, and the algorithm does not require the tail rates as input.

We tried to obtain a stronger lower bound by making the learner search among many arms separately in different contexts. These constructions did not improve the powers of dd and KK in our lower bound.

W4: Updated experiments.

We have added Calibrated GLM-UCB, a global learner using the true calibration. Revised Figure 2 and Tables 4–5 report 50 paired seeds over all 345 historical and 148 online rounds. For pointwise feedback, our practical learner reduces mean regret by 17.2% relative to Uncalibrated GLM-UCB and is competitive with Calibrated GLM-UCB. Accounting for the offset helps distinguish changes in approval probability from changes in arm quality.

The updated curves are shown in Figure 2 of the revised manuscript: panel (a) reports pointwise feedback and panel (b) reports pairwise feedback. They show cumulative regret over 493 rounds, including 345 historical rounds. Means are over 50 paired seeds; shading denotes 95% seed-bootstrap intervals.

For pairwise feedback, Ours reduces mean regret by 9.5% and 11.0% relative to the uncalibrated and calibrated controls. Both paired intervals favor Ours over the full trajectory. Retaining an optimistic arm while exploring an uncertain challenger can reduce exploration cost, although estimation and tuning also differ.

PrivacyLens results from revised manuscript Tables 4–5.

Both controls are GLM-UCB-style learners. Differences are Ours minus the control, with paired 95% bootstrap intervals. Means use all 493 rounds, including historical initialization.

RoundsFeedbackBaseline methodOursBaseline regretDifference95% CI
All 493PointwiseUncalibrated68.21582.370-14.155[-20.347, -8.142]
All 493PointwiseCalibrated68.21568.467-0.252[-6.703, 6.214]
All 493PairwiseUncalibrated62.46469.044-6.581[-11.875, -1.440]
All 493PairwiseCalibrated62.46470.191-7.728[-13.762, -2.292]

Q1/W3: Optimality and repeated arms.

Our optimality claim concerns TT with other parameters fixed. The dKT\sqrt{dKT} estimation term is matched, while the optimal d,Kd,K dependence of initialization remains open. Yes, repeated arms are allowed: when at=bta_t=b_t, the learner commits to one arm without requesting an informative comparison, as stated in Section 2.1.

We hope these clarifications and new experimental results address your concerns.

I thank the authors for the rebuttal, however, it does not address my previous concerns. In particular, authors do not explain what drives the gap between the upper and lower bound, and, though authors provide interpretations on αt\alpha_t and βt\beta_t, the current rebuttal does not explain why they are known to learners. What happens if the two parameters are misspecified? Due to strong assumptions and coarse theoretical insights, I choose to keep my current score.

AuthorsOpenReview ↗

Official Comment by Authors

We thank the reviewer for the careful follow-up and constructive comments.

As in the prior work discussed in our rebuttal, our optimality claim concerns dependence on TT, up to logarithmic factors, with other problem parameters fixed. The common dKT\sqrt{dKT} estimation term is also optimal up to logarithmic factors when the model degenerates to the uncalibrated case αt=1\alpha_{t}=1 and βt=0\beta_{t}=0, as studied in prior work. The remaining gap concerns the powers of dd and KK in the additional terms under general calibration. Using constructions that require the learner to search among many arms separately in different contexts, we were unable to obtain stronger lower bounds in dd and KK.

On the upper-bound side, closing this gap faces several obstacles. Our regret bound follows from a trade-off between the cost of collecting pilot and correction samples and startup regret, while accounting for the frequency of difficult rounds. The current analysis has a O~((dK)5/2)\widetilde O((dK)^{5/2}) dependence on dimension and arm count in the per-bin initialization bound, which produces the additional dimension factors after this balancing. Otherwise, a few extreme calibration values could determine the curvature bound for the entire interaction. First, the startup thresholds are chosen to cover this worst-case initialization cost and do not adapt to how informative the observations in a particular bin actually are. They can therefore be excessive on simple instances. Second, after startup, our algorithm checks confidence widths from the first level with all arms active on each round. Even when the optimal arm has a large advantage, an overly wide confidence interval can force further exploration before elimination is permitted. Thus, the gap involves both startup and subsequent estimation, and closing it may require entirely new ideas.

Regarding known calibration, we treat αt\alpha_{t} and βt\beta_{t} as supplied information specifying the topic-dependent evaluation rule. This extends the usual known logistic feedback model, which fixes αt=1\alpha_{t}=1 and βt=0\beta_{t}=0, to allow heterogeneous evaluation scales. Exact knowledge is an explicit modeling assumption. When the system sets the scoring protocol, it can supply the topic-specific sensitivity and offset before the learner acts. For recurring topics with a stable evaluation rule, these parameters can instead be estimated offline from repeated ratings of reference responses with distinct utility values anchored on a common scale. A conceptual contribution of our work is this calibrated feedback model, which provides a setting for studying both more efficient algorithms and learning with imperfect calibration.

We agree that exact calibration values are difficult to obtain in practice. We therefore provide additional regret guarantees under bounded calibration errors in the newly added Supplementary Material. For bounded additive calibration error, it is easy to use the standard likelihood-ratio change-of-measure argument to obtain the original regret rates plus O~(εT)\widetilde O(\varepsilon T) for fixed dd and KK. The supplement further provides an explicit additional term of O~(ε(dKT)3/4)\widetilde O(\sqrt{\varepsilon}(dKT)^{3/4}) in the expected regret bounds for both protocols when 0≤ε≤10\le\varepsilon\le1.

We will incorporate the extension and the proofs into the revised manuscript. We thank the reviewer for prompting these developments and hope they address the remaining concerns.

Comments on the paper

4 comments
AuthorsOpenReview ↗

Response to the Area Chair and Reviewers

Dear Area Chair and Reviewers,

We sincerely thank you for the constructive evaluation of our manuscript. We have revised the manuscript in response, with changes marked in blue. Below, we address the three shared concerns.

  • Regret optimality.

We agree that our leading regret terms are tight in their dependence on TT up to logarithmic factors, consistent with our focus on optimality in TT as in prior work. The common lower bound matches the dKT\sqrt{dKT} term under constant calibration, and the optimal dependence of the initialization terms on dd and KK remains open.

Building on the sample splitting and one-step correction of Bae and Lee (2026), we extend the analysis to heterogeneous calibration in a common framework for ratings and comparisons. For pairwise, we retain the O~(dKT)\widetilde{O}(\sqrt{dKT}) rate without the feature diversity conditions used by Saha (2021) and Bengs et al. (2022). For pointwise, our bounds match in TT up to logarithmic factors in both the fast- and slow-tail regimes covered by our lower bounds. For ρpt<1\rho_{\mathrm{pt}}<1, the optimal horizon dependence is T1/(1+ρpt)T^{1/(1+\rho_{\mathrm{pt}})} up to logarithmic factors under Theorem D.1's conditions. We will state these conditions explicitly, including d≥2d\ge 2 for the tail-dependent lower bound, and clarify the upper bounds' dependence on norm and tail parameters.

  • Known calibration.

Affine calibration shared across arms in round tt takes the form αtut,i+βt\alpha_{t}u_{t,i}+\beta_{t}, where ut,iu_{t,i} is arm ii's latent utility. We assume both coefficients are known to the learner, following the standard known-link convention while allowing topic-dependent links. If both are unknown, the more general problem lacks a bounded score scale: even with two arms, pointwise ratings can remain nearly uninformative throughout the horizon and force linear worst-case score regret.

The motivation of our model is to separate topic-specific evaluation conditions, captured by αt\alpha_{t} and βt\beta_{t}, from user-specific preferences, captured by the latent utilities. The sensitivity αt\alpha_{t} controls how strongly feedback responds to changes in utility, and the offset βt\beta_{t} sets the baseline log-odds of a positive rating. Some control of the feedback scale is necessary for sublinear worst-case score regret. For example, an unrestricted common offset can make ratings nearly identical for both arms throughout the horizon, even when the offset is known. Standard bandit models control the score scale by bounding features and parameters. Our empirical exponential-tail condition generalizes a uniform bound on calibration. It is motivated by settings where most topics use moderate evaluation scales and extreme thresholds or sensitivities occur only occasionally. Every uniformly bounded calibration satisfies the condition for suitable tail constants, and the condition also allows occasional calibration values whose magnitudes grow with TT. The algorithm does not require the tail rates as input.

We futher provide additional regret guarantees under bounded calibration errors in the Supplementary Material. For bounded additive calibration error, an explicit additional term of O~(ε(dKT)3/4)\widetilde O(\sqrt{\varepsilon}(dKT)^{3/4}) in the expected regret bounds is given for both protocols when 0≤ε≤10\le\varepsilon\le1.

  • Computation and experiments.

We agree that BINPILOT is purely theoretical and its analyzed implementation is currently impractical at the scales considered. We aim to provide a unified framework with regret guarantees for ratings and comparisons and explain the trade-offs between these protocols.

We have checked that binning is needed because a few extreme calibration values can otherwise determine the curvature bound for all rounds; it lets us control their contribution using the tail condition. For a fixed bin, the startup length is polynomial, but can be too long for our experiments. Policy enumeration in the startup phase is the only step that can take exponential time in dKdK. We can replace EXP4.P with uniform exploration and Sparring EXP4.P with MinMaxDB (Saha and Krishnamurthy, 2022) using a polynomial-time online logistic regression oracle (Foster et al., 2018) (c.f. Supplementary Material). We use EXP4.P for its simplicity and ease of analysis, as our main contributions lie in the estimation and elimination stages after startup. Our regret proof relies on binning to control curvature and startup costs.

In synthetic experiments, we retain binning, layered pilot estimation, and one-step correction with practical thresholds, and report normalized regret curves and separate startup and post-startup regret. For PrivacyLens, our practical implementation replaces the theoretical startup and layered procedure with pilot estimation and sequential one-step correction, using median-based bins initialized from the same historical state. We have also added a calibrated global GLM-UCB baseline.

Sincerely, The Authors

AuthorsOpenReview ↗

Response to Reviewer WFhg

Thank you for carefully checking the numerical results. Your comments led us to correct the synthetic results, report phase-specific costs, and qualify the experimental claims. We have revised the manuscript in response to your feedback.

Q1/W1/W2: Corrected synthetic results.

We agree that the earlier values were inconsistent with the stated setup. We corrected the inconsistent results in the revised PDF (Section 4.1, Figure 1; Appendix E.1, Tables 2-3). The random and maximum references are Rrand=∑tαtR_{\mathrm{rand}}=\sum_t\alpha_t and Rmax⁡=2RrandR_{\max}=2R_{\mathrm{rand}}. Selected horizons are below; Table 2 reports all horizons. Means use ten paired seeds, with a=2a=2.

TTPointwise b=2b=2Pointwise b=0.05b=0.05PairwiseRandomMaximum
282^8118.9127.6128.1126.7253.3
2162^{16}26,059.932,681.022,691.432,765.365,530.5
2182^{18}61,140.6129,737.951,043.9131,068.9262,137.8
2212^{21}211,821.61,004,393.5166,716.21,048,572.42,097,144.8

At T=221T=2^{21}, fast-tail pointwise and pairwise regret are 79.8%79.8\% and 84.1%84.1\% below random play. Their declining R(T)/TR(T)/T and slopes 0.5880.588 and 0.5600.560 in Figure 1 are qualitatively consistent with square-root growth up to logarithmic factors. Fast offset tails produce fewer hard bins, allowing most rounds to reach post-startup learning. Offset cancellation leaves pairwise bin assignments and feedback unchanged across both settings.

The endpoint decomposition follows (full results: Appendix E.1, Table 3). Round fractions and regret shares are distinct.

FeedbackStartup roundsStartup regretPost-startup regretStartup regret share
Pointwise b=2b=20.66%16,346.6195,474.97.7%
Pointwise b=0.05b=0.0578.46%840,473.7163,919.883.7%
Pairwise (both bb)1.60%45,316.1121,400.127.2%

Slow-tail pointwise startup regret is close to random play on the same rounds (843,486.8843{,}486.8), while post-startup regret is about 20%20\% below its corresponding random reference. Repeated initialization is the main finite-horizon bottleneck here; fast-tail pointwise and pairwise learning incur much smaller startup costs.

Q2/W2/W3/W4: Known calibration, binning, and computation.

Calibration depends on context history rather than unknown arm parameters, separating topic-level scales from preferences; it may be calibrated offline from historical responses. This follows the known-link convention; our guarantees exclude unknown or misspecified calibration. Known offsets can still saturate ratings.

A single worst-case curvature bound charges all rounds for a few extremes; binning localizes this cost. Curvature weights alone do not ensure the pilot accuracy needed to compare estimated and true curvature and control the correction remainder. We do not establish that isolated bins are intrinsically necessary. Pooling may reduce initialization here, but shared directions alone do not invalidate Theorem D.1, whose saturated rounds come first.

Startup visit thresholds are polynomial in d,Kd,K for a fixed bin, but EXP4.P can enumerate exponentially many policies. We use it for simplicity and ease of analysis; our main contributions concern post-startup estimation and elimination. Uniform exploration can replace EXP4.P, and MinMaxDB (Saha and Krishnamurthy, 2022) with a polynomial-time online logistic regression oracle (Foster et al., 2018) can replace Sparring EXP4.P, avoiding enumeration but not resolving exact pilot minimization.

Sections 4.1-4.2 and Appendix E document the practical thresholds, confidence multiplier 1.251.25, and PrivacyLens pilot/correction procedure replacing theoretical startup and layering. Optimality concerns TT with other parameters fixed.

W3: PrivacyLens comparison.

The revised PDF adds Calibrated GLM-UCB (Section 4.2, Figure 2; Appendix E.2, Tables 4-5). Below are all-493-round results, including 345 historical rounds. Differences use unrounded means (Ours minus baseline), with 95% paired intervals from 50 seeds and 2,000 bootstrap resamples.

FeedbackGLM-UCBOursBaselineDifference95% CI
PointwiseUncalibrated68.21582.370-14.155[-20.347,-8.142]
PointwiseCalibrated68.21568.467-0.252[-6.703,6.214]
PairwiseUncalibrated62.46469.044-6.581[-11.875,-1.440]
PairwiseCalibrated62.46470.191-7.728[-13.762,-2.292]

Ours improves on the uncalibrated baseline under both protocols, is competitive with the calibrated baseline for pointwise feedback, and reduces full-trajectory pairwise regret by 9.5%9.5\% and 11.0%11.0\% against the two controls. Retaining an optimistic arm can lower exploration cost; estimation and tuning also differ.

We hope these revisions and new results address your concerns.

Thank you for your detailed response and for correcting the synthetic results. The corrected values resolve the inconsistency I raised, and the phase decomposition and the Calibrated GLM-UCB baseline are helpful additions. However, the new results also support my remaining concerns. In the slow-tail setting, pointwise regret stays close to random play at all reported horizons, with most of it incurred during repeated per-bin startup, which suggests that this behavior reflects the per-bin design rather than intrinsic hardness. On PrivacyLens, the pointwise advantage disappears against the calibrated baseline, so it mainly reflects the use of calibration, while the pairwise improvement is a useful new result. Together with the remaining theoretical limitations, namely the exactly known calibration and the exponential-time startup, I maintain my score.

We thank the reviewer for the careful follow-up and for confirming that the corrected synthetic results resolve the earlier concern. We also appreciate the reviewer’s constructive comments.

We agree that pointwise regret in the slow-tail setting is close to that of uniform random play at the reported horizons. This setting deliberately allows large calibration offsets to occur frequently, making pointwise ratings weakly informative and learning difficult at these horizons. This behavior is consistent with our lower bound, which shows that slow offset tails can worsen the worst-case regret rate for any pointwise learner. As the offset-tail decay rate approaches zero, the lower-bound exponent 1/(1+ρpt)1/(1+\rho_{\mathrm{pt}}) approaches one. Our synthetic experiment compares the two feedback protocols by varying the offset tail. Large offsets can push pointwise feedback probabilities close to zero or one, making ratings less informative, while the common offset cancels exactly in pairwise comparisons.

We would like to highlight that the goal of our work is not only to provide learning algorithms but also to offer theoretical guidance on which type of feedback to collect when training models from preferences. Many preference-learning systems use pairwise comparisons, and our analysis identifies conditions under which they offer a better worst-case regret rate. On PrivacyLens, we agree that the pointwise results primarily show the value of incorporating calibration. The pairwise improvement persists against the calibrated baseline over the full trajectory.

A conceptual contribution of this work is the calibrated feedback model. It provides a setting in which to study more efficient algorithms and learning with imperfect calibration. When the system sets the scoring protocol, it can supply the topic-specific sensitivity and offset before the learner acts. For recurring topics with human ratings, these parameters can be estimated offline from repeated ratings of reference responses with distinct scores on a common utility scale.

We provide two extensions in the newly added Supplementary Material. First, replacing policy enumeration during startup with uniform sampling for pointwise feedback and with MinMaxDB combined with online logistic regression for pairwise feedback yields polynomial running time under exact calibration and preserves the original regret bounds up to logarithmic factors. Second, for bounded additive calibration error, it is easy to use the standard likelihood-ratio change-of-measure argument to obtain the original regret rates plus O~(εT)\widetilde O(\varepsilon T) for fixed dd and KK. The supplement further provides an explicit additional term of O~(ε(dKT)3/4)\widetilde O(\sqrt{\varepsilon}(dKT)^{3/4}) in the expected regret bounds for both protocols when 0≤ε≤10\le\varepsilon\le1.

We will incorporate these extensions and their proofs into the revised manuscript. We thank the reviewer for prompting these developments and hope they address the remaining concerns.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.