- Rating
- 2
- Confidence
- 3
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 2
Read review
Paper summary
This paper studies contextual preference bandits with arms whose latent utilities pass through a context-dependent affine calibration, . The sensitivity and the common offset are revealed before each action and may be unbounded, subject to empirical exponential tail conditions. Feedback is either a pointwise rating or a pairwise comparison , 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 regret for pointwise feedback and , hence for any positive sensitivity tail rate, for pairwise feedback. These are complemented by lower bounds for both protocols and an pointwise lower bound (Appendix D.3). Experiments use a synthetic two-arm instance and PrivacyLens contexts with synthetic arms and calibration.
Critical strengths
- 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 all compared score differences lie in , so the leading pairwise estimation term is free of the curvature constant (Appendix C.1.3).
- 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 term is unavoidable.
Critical weaknesses
-
Unexpectedly high regret in the synthetic experiment. Under the construction in Section 4.1, always selecting the wrong arm yields regret at , and uniform random play about half of that. The reported pointwise regret for is (Appendix E.1), which is close to the maximum and well above random play; similarly, at all four curves in Figure 1(a) lie close to the maximum (). 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.
-
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 , with the experimental startup length , bins with cannot leave startup within rounds, and about 70% of rounds fall into such bins. Since all bins share the same two contexts and the same , 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.
-
Gap between the analyzed and the evaluated algorithms. The startup phase uses EXP4.P over a policy class whose size is exponential in (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".
-
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 rate in the uncalibrated case hides a constant growing like in the pointwise bound (through in Appendix C), whereas the matching lower bound uses near-zero logits. Reporting the dependence on , , and the tail constants in Theorem 3.2 would make the result easier to interpret.
Questions for authors
- 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 at and uniform random play in expectation, yet the reported pointwise regret is , and at 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.
- 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 . More generally, when the directions encountered on saturated rounds are also covered by unsaturated rounds, as in the synthetic instance, can the term be avoided? In the construction of Theorem D.1, the saturated rounds precede the informative ones.
- (Minor) Lines 85–88: the sentence "For pairwise comparisons, we prove a near-optimal regret bound of under any positive sensitivity tail rate" appears twice.
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 T up to logarithmic factors, with the other problem parameters held fixed, consistent with our focus on optimality in T as in prior work. The common dKT term is tight jointly in d, K, and T up to logarithmic factors, as shown by our lower bound under constant calibration. The optimal dependence of the initialization terms on d and K 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 d and K 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)) for d=1, K≥2, and 0<ρ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 and β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.
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 dK. 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.