acceptodds
Under review as a conference paper at ICLR 2027

A Query Is Not a Commitment: Learning to Correct Expert Answers in Online Deferral

Abstract

An inaccurate expert can still provide useful information after correction. We study online learning to defer in which the learner chooses an expert and fixes a correction function before purchasing its answer, then applies that function to the answer received. The difficulty is that observed losses reflect both expert quality and an unfinished correction: early errors can discourage queries that would be valuable after learning. We propose , which pools shared and expert-specific polynomial responses. A bound on cumulative response-learning error calibrates confidence-weighted risk regression and exploration, allowing the router to account for this error when deciding which answers to buy. Under bounded residuals and disagreements, a fixed feasible model of optimal responses, and linear models of free and optimal queried risk, the calibrated algorithm achieves high-probability pseudo-regret over rounds for fixed problem parameters. The guarantee permits singular answer distributions and misspecified shared responses; optimality is relative to the bounded response class. On four test streams, the selected cubic policy has lower fee-inclusive cost than seven baselines that deploy answers unchanged. Comparisons with a common correction learner examine routing, while six-price comparisons measure cost and query rates.

Primary area:
learning theory
Keywords:
learning to defer, selective prediction, online learning

Reviews

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

The paper considered the problem of learning from multiple experts. In the standard setting, based on observed features, the router can either use its own prediction, or alternatively, route these features to one of a set of possible experts, and use that prediction. The goal of the router is therefore to learn the best routing function to an expert (based on the observed features), in an online manner. In this paper, this standard setting is extended with the possibility of not accepting the expert decision as is, but rather correct it before making the final prediction, with a learnable correction function. Most of the paper is devoted to a description of the various components of this setting, and how each one of them is specifically performed, and also how the performance is measured. Theorem 6.3 is the main theoretical contribution, showing a universal regret of O(Tlog⁡TO(\sqrt{T}\log T. A few experiments show improvement in the prediction error.

Critical strengths
  1. The considered regret is a strong conditional version, in which the reference correction function is allowed to depend on the history.
Critical weaknesses
  1. The model is fairly complicated, and includes many “ad-hoc” assumptions on specific aspects – the specific structure of the correction based on residual, the polynomial correction function (rather than a general class), the shared representation setup, the pooling mechanism. Later on features given by ct,jc_{t,j} and so on. A “cleaner”, simpler, version of this setting would allow to highlight how the ability to correct an expert affects the regret (beyond Tlog⁡T\sqrt{T}\log T behavior).

  2. As a result, the organization is poor and difficult to follow. The setting, the algorithm solution, and the theoretical guarantees are all mixed throughout the paper, with the setting being partially described, then some algorithmic aspects such as response fit and pooling, then theoretical guarantee (Lemma 5.1), then back to more assumption on the setting, algorithmic aspect in (15) (with parameters θ\theta that appear out of the blue), along with early references to Section 6 (Theory). The paragraphs after (15) in Section 5.3. e.g. are difficult to read since they use many unexplained terms and refer to later equations and assumptions.

  3. While the regret bound is on the order o(T)o(T), it is not instance-dependent, and so it does not indicate how the complexity of the instance affects the difficulty of learning. This does not allow to capture which instances the correction of the expert is beneficial/non-beneficial but difficult/easy to learn.

Questions for authors
  1. Section “5.1 learning the response - response fits” is unclear. What is the role of the vectors ℓt,j\ell_{t,j} and st,js_{t,j}? Why does it make sense to assume that they are different at each round, and that they are available at each round? In (10) why is the projected shared proposal is denoted “population” when it is also an empirical quantity?

  2. Section “5.1 learning the response - pooling”: Why is exponential weighting reasonable for a regression problem? It seems that a convex mixture of coefficients can be beneficial. Can you justify it here?

  3. Comment: Lemma 5.1 seems out of place. It is based on future assumption and equations, and also seems technical.

  4. Comment: To add to the confusion, the Response-aware-UCB algorithm is never explicitly mentioned. It is probably described at the end of page 6, but this is just an (educated) guess.

  5. Clarification: What is “an unfinished response” (line 370)?

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

The paper studies online regression deferral in which the learner selects an expert and fixes a correction function before purchasing the expert’s answer. Outcomes are revealed every round, but only purchased answers are observed (lines 040–048, 142–159). Response-Aware UCB pools shared and identity-specific corrections and uses a cumulative response-error certificate to calibrate weighted risk regression (lines 210–277, 298–308). Under bounded observations and response/risk realizability, it achieves high-probability O(Tlog⁡(T+1))O(\sqrt{T} \log(T+1)) pseudo-regret, for fixed problem parameters, against a conditional-law oracle restricted to the same correction class (lines 181–200, 345–409). Experiments evaluate squared error plus consultation fees on four streams, including comparisons with unchanged expert answers and with a common correction architecture (lines 435–456, 1788–1794, 1952–1976).

Critical strengths

S1. A coherent guarantee that includes learning the corrections. The response-error certificate controls cumulative excess prediction risk from unfinished corrections and connects it to routing confidence and regret. Corrections are learned from purchased answers rather than assumed known (lines 253–277, 335–338, 1388–1440, 1488–1509). The argument also accommodates boundary optima, singular answer distributions, and a misspecified shared proposal (lines 345–352, 1419–1421). This provides a theoretical treatment of the feedback between learning to use answers and deciding which answers to acquire.

S2. Evidence that correcting purchased answers can be useful. The complete system has lower fee-inclusive test cost than all seven direct-deployment baselines on the four reported streams (Table 1, lines 435–456). The matched-response comparison is also a useful control for separating the correction architecture from the router (lines 1952–1976). These results support the practical motivation, although they provide weaker evidence for the additional routing mechanism itself.

Critical weaknesses

W1. The incremental value of the proposed routing mechanism has not been sufficiently established. The sublinear guarantee does not establish a better regret bound than the closest applicable alternatives under a common comparator and assumptions (lines 094–096, 396–409, 1120–1137). Empirically, with the correction architecture held fixed, ordinary joint response UCB matches the proposed method on three streams. Delhi improves approximately 1.36% (Table 6, lines 1952–1976). Moreover, the benchmark tunes the confidence multiplier and weighting threshold independently rather than using the theorem’s coupled calibration (lines 329–331, 388–400). The reported comparisons therefore do not convincingly establish a substantial advantage attributable to response-error protection, despite the complete system’s gains over baselines that deploy answers unchanged.

W2. The scope and practical implications of the guarantee remain insufficiently justified. The analysis simultaneously requires fixed feasible models of optimal correction coefficients and separate linear models of free and optimally corrected risks. The latter does not follow from the former (lines 345–365). The supporting construction has zero optimal corrected risk, whereas the approximation extension can incur terms linear in TT with logarithmic factors for fixed positive errors (lines 1107–1118, 1728–1738). It remains unclear how representative these joint conditions are for the benchmark feature construction (lines 982–988, 2037–2054). Although full parameter dependence is supplied in Appendix B.7, the paper should explain more directly how expert count, correction complexity, and risk dimension affect the usefulness of its guarantee (lines 369–405, 1120–1137).

Questions for authors

Q1. Clarification of the theoretical advance. Under the same feedback protocol and oracle, what regret or response-learning error guarantee is available for the closest applicable alternative? Please compare the dependence on expert count and model dimensions, and identify the improvement or trade-off provided by the proposed analysis (lines 094–096, 298–308, 396–409, 982–988, 1120–1137). This would clarify whether the main advance is a stronger guarantee, broader coverage, or the first guarantee for this particular formulation.

Q2. Clarification of the mechanism in the reported experiments. What confidence multiplier and weighting threshold were selected, how often were observations downweighted, and did the matched-response routers follow different acquisition trajectories on the three tied streams? Are results using the theorem’s calibration already available (lines 329–331, 388–400, 1952–1976)? It would help to compare the calibrated, independently tuned, and unit-weight versions at different consultation prices, using the same response learner. This would help show how much the proposed routing method actually improves performance (lines 452–456, 1869–1884, 1952–1965).

Q3. Clarification of the assumptions’ coverage. Which representative data-generating conditions make Assumptions 6.1 and 6.2 jointly valid with the chosen features, beyond the zero-risk construction? Does the synthetic benchmark satisfy them? If it instead tests misspecification, what approximation errors are involved, and how does the extension inform that experiment (lines 345–365, 982–988, 1107–1118, 1594–1609, 1728–1738, 2037–2054)? This would materially affect the assessment of the guarantee’s significance.

1 comment

Thank you for clarifying the theory and the experiments. Based on the paper and the authors' response, the submission makes a meaningful theoretical contribution. However, its theoretical advantage over the calibrated unit-weight router holds only in certain parameter regimes. The new experiments help explain when the sample weights affect routing decisions, but the gains over the unweighted UCB baseline using the same correction learner remain small. Also, although the calibration is key to the theoretical guarantee, it is still unclear how to obtain the required constants on the benchmarks. Thus, it remains unclear how to apply the theorem’s calibration to these benchmarks and how much it would help.

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

This paper investigates a practical challenge in learning to defer (L2D). During the early stages of training, the correction function may not yet be sufficiently optimized, and prematurely evaluating an expert under such conditions may lead to an inaccurate assessment and the subsequent rejection of that expert’s predictions. To address this issue, the proposed method uses Legendre polynomials for model correction and a contextual multi-armed bandit framework for expert selection. The authors further derive an upper bound on the pseudo-regret and empirically evaluate the proposed approach.

Critical strengths
  1. This paper is self-contained and studies a timely topic.

  2. A notable strength of the manuscript is its theoretical derivations of an upper bound on the pseudo-regret.

Critical weaknesses
  1. Several equations are not clearly defined when they first appear, this requires readers to consult the appendix or later sections for clarifications. This substantially disrupts the flow and readability of the main text. Equation (1) is such one example.

  2. The literature review in the Online Bandits section is outdated and should be expanded to include more recent advances, particularly those related to contextual bandits.

  3. The baselines used in the experimental evaluation are relatively dated. The authors are encouraged to include comparisons with more recent expert-routing and prediction-correction methods, such as approaches based on deep learning, meta-learning, and large language model fine-tuning or post-processing.

  4. The use of certain terminologies may cause conceptual confusion. In particular, the term loss conventionally refers to the optimization objective during model training, such as cross-entropy or mean squared error (MSE). In this paper, however, loss is used to denote the deployment-time combination of prediction error and consultation cost, which would more appropriately be described as cost or risk. This unusual usage may lead to misunderstandings and should be further clarified or revised.

Questions for authors
  1. Justification for (q=3) and its applicability to dynamic settings. The paper sets (q=3), but has this choice been justified theoretically or validated empirically? Given that the experts may change over time, is a fixed value of (q=3) still appropriate? The authors need to clarify the rationale for this choice and provide a sensitivity analysis to assess its suitability and robustness across different dynamic settings.

  2. The Oracle benchmark and the practical relevance of the theoretical regret bounds. The paper uses an Oracle with access to complete information as a benchmark for deriving regret bounds. However, whether the performance gap between the algorithm and the Oracle follows the theoretically predicted growth rate in practice requires further validation. The authors must clarify the implications of their theoretical results for cumulative regret growth and average regret convergence, and to empirically assess the consistency between the theoretical bounds and observed performance.

  3. Insufficient analysis of computational and space complexity. Although the paper establishes a high-probability upper bound on pseudo-regret, it does not adequately discuss the algorithm’s computational and space complexity. According to Equation (15), the system must maintain a separate covariance matrix for each expert and perform matrix inversion, which may incur substantial computational and storage costs. While Section 6 discusses scalability in practical deployment, it still lacks a quantitative theoretical analysis of these costs. The authors should provide the time complexity of matrix updates and inversions, the overall space complexity, and how these costs scale with the number of experts and the feature dimension.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.