PaperlayerView exact revision on arXiv

Source-linked AI summary

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

Yannis Montreuil, Axel Carlier, Lai Xing Ng, Wei Tsang Ooi

arXiv:2610.07084v1stat.MLcs.LG

TL;DR

Direct deferral deploys purchased expert answers unchanged, so predictable errors can make useful consultation look too costly. RESPONSE-AWARE UCB learns pre-purchase corrections and accounts for their learning error when routing. It achieves sublinear pseudo-regret under stated models, and its selected cubic policy has lower cost than seven direct-deferral baselines on four test streams.

  • Problem

    Direct deferral deploys purchased answers unchanged, so predictable expert errors can make potentially useful consultations unattractive.

    Source: §1 · p. 1

  • Method

    RESPONSE-AWARE UCB pools shared and expert-specific polynomial corrections and uses a bound on cumulative response-learning error to calibrate risk regression and exploration.

    Source: §1 · p. 2, §5.2 · p. 5, §5.3 · p. 7

  • Results

    The selected cubic policy has lower cost than seven direct-deferral baselines on four test streams, and the router matches or improves on tested UCB alternatives with a common correction learner.

    Source: §7 · p. 9, §8 · p. 10

  • Takeaways & Limitations

    The results show that response-aware routing can use corrected answers while accounting for correction-learning error, with consultation cost and query rates compared across six prices.

    Source: §7 · p. 9, §8 · p. 10

    The guarantee assumes bounded residuals and disagreements and optimal responses representable by a fixed feasible model; optimality is relative to the bounded response class.

    Source: §4 · pp. 3–4

Abstract

from arXiv · show

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 ORUCB, 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 $O(\sqrt T\log(T+1))$ over $T$ 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.

1 INTRODUCTION

Direct deferral purchases an expert’s answer but deploys it unchanged, so predictable answer errors can make useful consultation seem too costly. The paper learns a correction before purchase and accounts for correction-learning error when routing.

1 INTRODUCTION

  • Direct deferral uses purchased answers unchanged, tying consultation value to raw accuracy even when an expert’s errors are predictable.A stable bias can make an answer look too costly until it is corrected.Source: §1 · p. 1
  • The learner fixes an expert-specific correction before purchase, then applies it to the answer received; outcomes are revealed after every final prediction.Only the selected expert’s answer is observed.Source: §1 · p. 1
  • RESPONSE-AWARE UCB pools shared and identity-specific polynomial responses and bounds cumulative response-learning error to calibrate confidence-weighted risk regression and exploration.The shared fit proposes a correction for a new expert; the identity-specific fit retains what was learned when that expert returns.Source: §1 · p. 2
  • The conditional-law oracle chooses an expert and fixes its response before seeing the answer; calibrated RESPONSE-AWARE UCB achieves high-probability pseudo-regret O(√T log(T + 1)) for fixed problem parameters.The guarantee permits singular answer distributions and misspecified shared responses; a robustness extension quantifies supplied approximation errors.Source: §1 · p. 2
  • On four test streams, the selected cubic policy has lower cost than seven direct-deferral baselines; comparisons also examine routing with a common correction learner and cost and query rates at six prices.The external baselines deploy answers unchanged.Source: §1 · p. 2

2 RELATED WORK

Prior work studies learning when to defer and contextual-bandit methods for selected-action feedback. This paper adds the task of learning how to transform a purchased answer, with response-learning bias included in acquisition.

2 RELATED WORK

3 BACKGROUND

The background defines direct learning to defer as routing between a free prediction and unchanged expert answers, with loss plus fees as cost. In the online setting, availability and feedback vary over rounds, and unqueried experts’ losses are generally unavailable.

3 BACKGROUND

  • A router chooses the internal prediction or an available expert’s unchanged answer; cost is squared prediction error plus the consultation fee for an expert.The expert-query decision is favorable when conditional loss reduction exceeds its fee.Source: §3 · p. 3
  • Online routers act using current public input and history, while expert availability may change and expert identities persist (Duy et al., 2026).The internal predictor may also learn, with its current prediction included in the public input.Source: §3 · p. 3
  • Under bandit feedback, only the chosen action’s loss is revealed; when outcomes are always revealed but expert answers require purchase, unqueried experts’ losses are generally unavailable.The internal loss remains observable even when an expert is selected.Source: §3 · p. 3
  • Direct-deferral regret compares cumulative cost with the best fixed router in hindsight, whereas the later pseudo-regret compares conditional costs with an oracle choosing a feasible action and response each round.The hindsight router may select different experts at different inputs, but is used throughout the sequence.Source: §3 · p. 3

4 PROTOCOL AND COMPARATOR

The protocol requires the learner to choose an expert and fix its correction before seeing that expert’s answer, under a non-interventional setting. The comparator chooses the best feasible action and response before feedback, while the response class is bounded and polynomial in answer disagreement.

4 PROTOCOL AND COMPARATOR

  • The protocol hides the outcome and potential answers before action selection; purchasing reveals only the selected answer, applies the pre-fixed correction, and then reveals the outcome.The non-intervention assumption keeps purchasing from changing the conditional joint law of outcomes and answers.Source: §4 · p. 3
  • The response learns the expert residual from disagreement with the internal prediction, with |Yt − ht| ≤ R and |Mt,j − ht| ≤ D assumed almost surely.Centering the answer by the internal prediction gives a bounded response input without requiring bounded absolute prediction levels.Source: §4 · p. 3
  • Low-degree polynomial corrections are linear in their coefficients, allowing convex squared-loss fitting and online least-squares comparison without independent samples (Hu et al., 2020; Liu et al., 2021; Hazan, 2023).The fitting comparison is against a fixed feasible model.Source: §4 · pp. 3–4
  • Scaled Legendre features and a coefficient-norm constraint keep corrections bounded; the analysis requires bounded features and linear coefficients, not orthogonality under the answer distribution.The bounded classes need not be nested across polynomial orders, and other fixed bounded dictionaries can be used under corresponding models.Source: §4 · p. 4
  • For a query, the learner fixes a coefficient vector before purchase and deploys the expert answer plus the correction evaluated at its disagreement with the internal prediction.For the experiments, q = 3 gives four coefficients capturing bias correction, rescaling, and quadratic and cubic adjustments.Source: §4 · p. 4
  • The comparator chooses free prediction or an expert-response pair using current information, minimizing conditional risk plus fee before the answer is revealed.The paper’s pseudo-regret compares conditional expected costs with this feasible action-and-response oracle.Source: §4 · p. 4

5 RESPONSE-AWARE UCB

RESPONSE-AWARE UCB learns corrections while deciding whether to buy answers, accounting for the gap between observed loss under an unfinished response and the risk attainable with an optimal feasible response.

5 RESPONSE-AWARE UCB

  • The method fits corrections from past purchases, bounds their learning error, and uses that bound to decide whether an expert is worth buying.Only purchased answers update response fits and the selected identity’s pooling weights.Source: §5 · p. 4, §5.3 · p. 7

5.1 LEARNING THE RESPONSE

  • The deployed correction mixes identity-specific and shared proposals using their past losses, allowing shared information to help without requiring the shared model to be correct.The mixture remains feasible and its cumulative squared loss is bounded relative to either proposal sequence.Source: §5.1 · pp. 4–5

5.2 ACCOUNTING FOR RESPONSE ERROR

  • A cumulative response-error bound controls excess conditional prediction risk from learning corrections and grows logarithmically with purchases under fixed problem parameters.The router uses a deterministic horizon bound rather than estimating each unobserved response-learning gap.Source: §5.2 · pp. 5–6

5.3 CHOOSING AN ACTION

  • Public features separately model free and optimal queried risk, while confidence weighting caps the influence of queried observations so response error can be incorporated into risk estimates.The risk features are known before the current answer; response fitting and proposal-loss updates remain unweighted.Source: §5.3 · p. 6
  • The router scores free prediction against each expert’s estimated optimal queried risk plus fee, adding a bonus for uncertain queries and accounting for response-learning bias.It chooses the highest score, preferring free prediction on a tie, and queries only when an expert’s score is positive.Source: §5.3 · pp. 6–7

6 THEORY

The theory bounds regret against a conditional response oracle that chooses an expert and fixes its response before seeing the answer. Its guarantee combines response-learning error with confidence-weighted risk estimation under fixed feasible response and linear risk models.

6 THEORY

  • The oracle comparison includes both query mistakes and prediction error incurred while learning responses, rather than assuming corrections are already known.Against direct deferral, correction improves cumulative cost when the oracle’s cumulative correction gain exceeds the regret bound.Source: §6 · p. 7, §6.3 · p. 8

6.1 MODEL ASSUMPTIONS

  • The assumptions require a fixed feasible response model per expert and linear conditional models for free and optimal queried risk.The optimal response model need not represent the conditional mean residual; it represents a best correction within the prescribed ball.Source: §6.1 · p. 7

6.2 CONFIDENCE CALIBRATION

  • Confidence calibration combines noise and response-learning error so the queried-risk estimate supplies a lower confidence bound for optimal queried risk.The response-error contribution is bounded using capped queried-observation weights.Source: §6.2 · pp. 7–8

6.3 REGRET GUARANTEE

  • Under the bounded non-interventional protocol and assumptions 6.1 and 6.2, RESPONSE-AWARE UCB has, with probability at least 1 − δ, regret O(T log(T + 1)) for fixed problem parameters and δ = (T + 1)−2.Bounded one-round regret also gives vanishing expected average regret.Source: §6.3 · p. 8

7 EXPERIMENTS

The selected RESPONSE-AWARE UCB policy has lower test cost than the external baselines across four streams, and its cost remains lowest across six Jena consultation prices. Routing comparisons hold the correction learner fixed, matching a joint UCB router on three streams and improving on both alternatives on Delhi.

Evaluation setup

  • The evaluation compares fee-inclusive test costs against seven external baselines on four streams, tests six consultation prices, and examines routing with a common correction learner.The streams include synthetic regimes, Melbourne, Jena, and Delhi; the external baselines use answers unchanged.Source: §7 · pp. 8–9

Results

  • RESPONSE-AWARE UCB has lower mean test cost than every external baseline on all four streams.Table 1 reports mean fee-inclusive test cost across the test streams.Source: §7 · p. 9, Table 1 · p. 9
  • The method has the lowest cost at all six Jena consultation prices, while its query fraction falls from 96% to 0.1%.The query range spans frequent consultation to near-free prediction.Source: §7 · p. 9, Table 2 · p. 9

Extra experiments

  • With the cubic correction learner, pooling, and memory fixed, the router matches joint response UCB on three streams and improves on both alternatives on Delhi.The alternatives are joint and disjoint response UCB routers.Source: §7 · p. 9

8 CONCLUSION

RESPONSE-AWARE UCB learns corrections and accounts for their learning error when choosing which answers to buy; under the stated models, it achieves sublinear pseudo-regret against the conditional response oracle. The appendix specifies the information timing and notation, and the paper discloses its use of AI tools.

8 CONCLUSION

  • Under the stated response and risk models, calibrated RESPONSE-AWARE UCB achieves sublinear pseudo-regret against the conditional response oracle.The conclusion also notes an extension quantifying approximation-error effects and lower cost than seven direct-deferral baselines on four test streams.Source: §8 · p. 10

AI USE STATEMENT

  • The authors used AI tools to polish writing, check proofs, develop an example, generate synthetic data, and implement and debug methods and code.They state that they reviewed the AI-assisted material and take responsibility for the final text, claims, code, and results.Source: AI USE STATEMENT · p. 11

A.1 INFORMATION AND TIMING

  • The learner fixes the response before observing the queried answer, applies it afterward, and reveals the outcome for future updates.The current action and response coefficients are chosen from pre-query information; queried answers can enter later response fits.Source: Figure 1 · p. 17, §A.1 · p. 17
  • The conditional oracle uses a measurable response choice; returning identities retain learned state only when their conditional laws satisfy the same fixed parameter models.The oracle minimizes over a finite eligible set using a fixed tie rule.Source: §A.1 · p. 17

A.2 NOTATION GUIDE

  • The notation distinguishes shared and identity response proposals, free and optimal queried-risk regressions, and response-combination weights from risk-observation weights; dimensions count feature coordinates.The designs use rounds before t, while N_t,j includes round t; the tables distinguish decisions, responses, costs, and learning-state/confidence quantities.Source: §A.2 · p. 18, Table 3 · p. 18, Table 4 · p. 18

B IMPLEMENTATION AND EXPLICIT REGRET BOUND

This appendix details how RESPONSE-AWARE UCB learns responses and risks, calibrates its routing decisions, and bounds their cumulative cost. It also explains when correction can change which expert is worth querying.

B.4 RECURSIVE IMPLEMENTATION OF THE DEPLOYED POLICY

  • Before buying an answer, the algorithm freezes a pooled shared and identity-specific correction; after deployment, it updates response, pool, and queried-risk states.Free rounds update the free-risk fit, while queried-risk updates use the deployed prediction.Source: B IMPLEMENTATION AND EXPLICIT REGRET… · p. 19, §B.4 · p. 21

B.1 THE RESPONSE-LEARNING BOUND

  • The query-count-dependent bound E_t controls cumulative deployed-response loss relative to the fixed optimal identity response, in normalized units.The bound accounts for fitting and combining responses and is used to calibrate the router’s weighting threshold.Source: §B.1 · pp. 19–20

B.2 RISK REGRESSIONS AND CONFIDENCE CALIBRATION

  • The queried-risk forecast retains response-learning bias in its confidence calibration, while clipping the free-risk forecast cannot increase its distance from true free risk.The horizon calibration couples the confidence radius with the response-error envelope.Source: §B.2 · p. 20

B.3 COMPUTING THE RESPONSE FITS

  • The identity-response fit solves a positive-definite quadratic over the unit ball; the shared fit uses ridge regression and projects its proposal.When the unconstrained solution is infeasible, the constrained fit is found by a scalar root search.Source: §B.3 · p. 20

B.5 MODEL ASSUMPTIONS IN CONTEXT; B.6 A CONTINUOUS-CONTEXT EXAMPLE

  • The guarantee assumes feasible fixed identity-response models and linear models for free and optimal queried risk; a continuous-context example has varying optimal corrections but constant risks.In that example, the optimal queried risk is zero.Source: §B.5 · p. 22, §B.6 · p. 22

B.7 EXPLICIT FINITE-HORIZON BOUND

  • The explicit routing bound separates free-risk estimation, queried-risk estimation, and response learning; queried-risk terms depend on purchases, not all T rounds.The proposition is stated under the hypotheses and calibration of theorem 6.3.Source: §B.7 · pp. 22–23

C.1 PREDICTION GAIN AND APPROXIMATION

  • The squared-loss projection identity separates irreducible error after observing an answer from error due to approximating its conditional mean residual.The bounded response class adds approximation error relative to the unrestricted conditional response.Source: §C.1 · p. 24

C.2 WHEN CORRECTION CHANGES THE ACQUISITION DECISION

  • Correction improves oracle cost exactly when its prediction gain exceeds an expert’s direct-cost disadvantage.The comparison does not require response or risk realizability.Source: §C.2 · p. 24

C.3 AN EXAMPLE OF NONLINEAR CORRECTION

The example isolates the value of nonlinear correction. The proof then compares constrained response fits and their pool with the conditional optimum to support the routing guarantee.

C.3 AN EXAMPLE OF NONLINEAR CORRECTION

  • In the constant-context example, an affine response removes bias b but leaves risk ε^2/7, whereas a cubic response removes both error components.The answer is the only source of information about the current draw.Source: §C.3 · p. 25

D PROOF OF THE ROUTING GUARANTEE

  • The proof first bounds response regret on purchased observations, converts it to conditional excess risk, and uses that excess risk to control queried-risk bias.Confidence bounds then support a one-round comparison with the oracle.Source: D PROOF OF THE ROUTING GUARANTEE · p. 26

D.1 CONSTRAINED LEAST SQUARES ON SELECTED OBSERVATIONS

  • The constrained-regression comparison is deterministic and applies to selected observations with bounded features and targets, without requiring a covariance assumption.The identity-specific bound is summed over each expert’s query subsequence.Source: §D.1 · p. 26

D.2 POOLING AND CONDITIONAL EXCESS RISK

  • Exponential-weight pooling compares the deployed response with either candidate’s realized losses on the same queried observations, even when proposals change between queries.The conversion to conditional risk uses the constrained optimum’s variational inequality and covers zero answer variance, boundary optima, and nonunique optima.Source: §D.2 · pp. 27–28

D.3 PROOF OF THE RESPONSE-ERROR BOUND

The proof bounds cumulative response-learning error, then incorporates that error into simultaneous confidence bounds for the free- and queried-risk regressions.

D.3 PROOF OF THE RESPONSE-ERROR BOUND

  • Under the bounded protocol and Assumption 6.1, with exact response fits and pooling updates and 0 < η ≤ 1/2, with probability at least 1 − δ/3, simultaneously for all t, cumulative conditional response gaps are ≤ E_t = 2A_t + 64 log(3/δ), with E_t ≤ E_T for t ≤ T.Source: §D.3 · p. 28

D.4 RISK CONFIDENCE WITH RESPONSE-LEARNING BIAS

  • Simultaneous risk confidence combines the response bound with free- and queried-risk regression bounds, accounting for response-learning bias in queried labels.The three events have total failure probability at most δ.Source: §D.4 · pp. 28–29
  • The regression confidence argument requires predictable features and conditionally sub-Gaussian noise, but not independent covariates or rounds.Centered variables in an interval of length one satisfy the noise condition by Hoeffding’s lemma.Source: §D.4 · p. 29

D.5 PROOF OF THE ROUTING THEOREM

The proof bounds response-aware routing regret under exact models, then extends the guarantee to approximate response and risk models and states how approximation errors affect the rate.

D.5 PROOF OF THE ROUTING THEOREM

  • O(√T log(T+1)) pseudo-regret holds with high probability for fixed problem parameters under the theorem’s exact-model assumptions.The horizon-dependence argument gives this rate with constants independent of T and δ.Source: §D.5 · pp. 30–31

D.6 APPROXIMATE RESPONSE AND RISK MODELS

  • With approximate models, the bound adds terms linear in T up to logarithmic factors; zero approximation error recovers the original rate.The added terms depend on response and risk approximation tolerances.Source: §D.6 · p. 34
  • The approximation guarantee requires fixed feasible models and supplied error bounds; a substitute bound for cumulative response error must hold almost surely.A bound holding only with high probability requires its failure probability to be included.Source: §D.6 · pp. 31, 34

E ADDITIONAL EXPERIMENTS

  • Evaluation uses validation-selected hyperparameters and reports mean and sample standard deviation over five learner seeds on each fixed stream.The protocol evaluates on separate test data and retains each method’s prescribed online updates.Source: E ADDITIONAL EXPERIMENTS · p. 35

E.1 LEARNING ON THE FOUR BENCHMARK STREAMS

Across four streams, RESPONSE-AWARE UCB achieves lower fee-inclusive test cost than external baselines; price and matched-response studies further examine consultation and routing.

E.1 LEARNING ON THE FOUR BENCHMARK STREAMS

  • Figure 2’s final costs are 0.08092, 4.49069, 3.72844, and 2.59240 on synthetic, Melbourne, Jena, and Delhi, versus best-baseline costs of 0.08316, 4.61400, 4.02217, and 2.63729.The selected policy has the lowest final mean total cost among eight methods on all four streams.Source: §E.1 · p. 35, Figure 2 · p. 36

E.2 COST-SENSITIVE CONSULTATION

  • Table 5 reports lower cost than every external baseline at all six Jena prices, while query rates fall from 96% to 0.10%.The six measured query rates are 96%, 79.4%, 9.7%, 8.15%, 1.85%, and 0.10%.Source: §E.2 · p. 36, Table 5 · p. 37

E.3 ROUTING WITH THE SAME RESPONSE LEARNER

  • Table 6 shows RESPONSE-AWARE UCB has the lowest cost on all four streams, tying joint response UCB on three and improving on both UCB alternatives on Delhi.On Delhi, costs are 2.59240 for RESPONSE-AWARE UCB, 2.62820 for joint response UCB, and 2.62465 for disjoint response UCB.Source: Table 6 · p. 38, §E.3 · p. 38

F DATA AND EXPERT CONSTRUCTION

The evaluation combines synthetic and real temperature streams with distinct expert constructions, shared public information, and fixed availability schedules; the related-work discussion positions online correction of purchased answers among routing and bandit methods.

F DATA AND EXPERT CONSTRUCTION

  • The four streams use controlled simulated expert signals on synthetic and Melbourne data, and frozen model predictions on Jena and Delhi.All methods share each dataset’s prepared stream and expert availability schedule.Source: F DATA AND EXPERT CONSTRUCTION · p. 39

F.1 SHARED PREPROCESSING

  • Routers receive shared public features, internal predictions, availability, and fees, but never the current outcome or an unpurchased expert answer.Melbourne and Delhi use lagged measurements and calendar features; Jena also uses contemporaneous weather covariates.Source: §F.1 · p. 39

F.2 SYNTHETIC

  • The synthetic stream cycles through four regimes in which free prediction, direct deferral, linear correction, or nonlinear correction is favored.The regimes recur every 240 rounds, with 60 rounds per regime; the nonlinear regime uses a hyperbolic-tangent generating function.Source: §F.2 · p. 39

F.3 MELBOURNE

  • Melbourne’s twelve simulated sensors apply identity, rescaled, or saturating nonlinear responses to real temperatures, with reliability varying by season and recent temperature change.The construction combines real temperature dynamics with controlled measurement errors, and only purchased sensor answers are revealed.Source: §F.3 · p. 40

F.4 JENA

  • Jena uses twelve frozen experts from four model families, fitted on the initial 2000 observations, with identities cycling through fixed availability periods.The common internal ridge predictor updates after each outcome.Source: §F.4 · p. 40

F.5 DELHI

  • Delhi uses six frozen tree-based experts fitted on the initial 600 observations, alongside an internal ridge predictor updated after revealed outcomes.Four to six experts are available per round under a schedule shared by all methods.Source: §F.5 · p. 40

G EXTENDED RELATED WORK

  • Unlike direct-deferral baselines, this work transforms purchased answers and learns acquisition and responses online from selected answers; bounded features and linear coefficients support its polynomial response models.The related-work discussion distinguishes this approach from context- or action-based polynomial approximations and notes that it assumes neither smoothness nor distributional orthogonality.Source: G EXTENDED RELATED WORK · pp. 41–42
Loading 2610.07084v1…