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

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

stat.MLOct 5, 2026

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

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

Organizations: School of Computing, National University of Singapore · IRIT, Toulouse INP, France · Institute for Infocomm Research, A*STAR, Singapore

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 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.

Figures & tables

Method	Synthetic	Melbourne	Jena	Delhi
Response-Aware UCB	0.08092	4.49069	3.72844	2.59240
SleepingLinUCB	0.08488	4.61400	4.03045	2.66401
SharedLinUCB	0.08316	4.90137	4.02217	2.64185
D-LinUCB	0.08790	5.11775	4.07844	2.63729
LinTS	0.08609 $\pm$ 0.00389	5.42987 $\pm$ 0.15762	4.11937 $\pm$ 0.04932	2.74807 $\pm$ 0.04935
NeuralUCB	0.10183 $\pm$ 0.00604	5.58128 $\pm$ 0.26329	4.18453 $\pm$ 0.13384	2.92431 $\pm$ 0.20347

Table 1: Mean test cost, including consultation fees. Entries show mean

\pm

sample standard deviation across five learner seeds. Lower is better.

Method	$\times 1$	$\times 3$	$\times 5$	$\times 7.5$	$\times 12.5$	$\times 50$
Response-Aware UCB	3.711	3.984	4.024	4.079	4.117	4.174
SleepingLinUCB	4.030	4.277	4.240	4.444	4.417	4.190
SharedLinUCB	4.022	4.201	4.180	4.242	4.202	4.182
D-LinUCB	4.078	4.371	4.447	4.452	4.485	4.552
LinTS	4.119 $\pm$ 0.049	4.167 $\pm$ 0.040	4.177 $\pm$ 0.036	4.233 $\pm$ 0.044	4.250 $\pm$ 0.065	4.182
NeuralUCB	4.185 $\pm$ 0.134	4.223 $\pm$ 0.108	4.190 $\pm$ 0.069	4.169 $\pm$ 0.045	4.189 $\pm$ 0.020	4.182

Table 2: Mean Jena test cost at six consultation prices. Columns scale the base fee

(\approx 0.17)

. Entries show mean

\pm

sample standard deviation over five learner seeds. Bold marks the lowest mean per column. Fees and query percentages are in Appendix E.2 .

Appendix figures & tables7 assets

Supplementary material from the paper’s appendix.

Appendix

Panel of Figure 1 — Figure 1: Consultation with a learned response, with round and expert subscripts suppressed. The solid path shows our queried action; the dashed branch shows standard deferral for comparison. The entire function $\Delta$ is fixed before observing $M$ ; its value is evaluated afterward. Free prediction, omitted here, uses $h$ without paying a fee.

Symbol	Meaning
$K,T$	Registry capacity and interaction horizon.
$\mathcal{F}_{t}$	Information available before the round- $t$ query.
$\mathcal{E}_{t},\mathcal{A}_{t}$	Available identities and the eligible subset with fees below $R^{2}$ .
$I_{t},\beta_{t,j}$	Chosen action ( $0$ means free prediction) and the fee for expert $j$ .
$h_{t},M_{t,j},Y_{t}$	Internal prediction, potential expert answer, and outcome.
$d_{t,j},e_{t,j}$	Disagreement $M_{t,j}-h_{t}$ and expert residual $Y_{t}-M_{t,j}$ .

Appendix

Table 3: Decisions, responses, and costs. All risks exclude consultation fees.

Symbol	Meaning
$\ell_{t,j}\in\mathbb{R}^{d_{\ell}},\ s_{t,j}\in\mathbb{R}^{d_{s}}$	Public features for identity and shared responses.
$\Theta_{t,j},\Psi_{t}$	Response matrices of sizes $d_{\ell}\times(q+1)$ and $d_{s}\times(q+1)$ .
$w^{H}_{t,j},w^{P}_{t,j},\eta$	Proposal mixture weights and their exponential-weights rate.
$x_{t}^{0}\in\mathbb{R}^{d_{0}},\ c_{t,j}\in\mathbb{R}^{d_{c}}$	Public features for free and optimal queried risk.
$\Lambda_{v},V_{t}^{v},\widehat{\theta}_{t}^{v}$	Prior, pre-round design, and risk estimate, for $v\in\{0,*\}$ .
$\lambda_{v},Q_{v},B_{v}$	Minimum prior eigenvalue, prior-norm bound, and noise-plus-prior radius.

Appendix

Table 4: Learning state and confidence quantities. Dimensions count feature coordinates.

Figure 2: Fee-inclusive test learning curves on all four streams. Every scored round is included, with linear cost axes starting at zero. Running means start at the first scored round. Shading shows one learner-seed standard deviation where nonzero.

Fee multiplier	$\times 1$	$\times 3$	$\times 5$	$\times 7.5$	$\times 12.5$	$\times 50$
Fee per query	0.17	0.51	0.85	1.28	2.13	8.52
Response-Aware UCB	3.711	3.984	4.024	4.079	4.117	4.174
SleepingLinUCB	4.030	4.277	4.240	4.444	4.417	4.190
SharedLinUCB	4.022	4.201	4.180	4.242	4.202	4.182
D-LinUCB	4.078	4.371	4.447	4.452	4.485	4.552
LinTS	4.119 $\pm$ 0.049	4.167 $\pm$ 0.040	4.177 $\pm$ 0.036	4.233 $\pm$ 0.044	4.250 $\pm$ 0.065	4.182

Appendix

Table 5: Jena test performance against external baselines at six prices. Panels share the same methods and six prices; fees and total costs are in squared-temperature units. Entries show mean and nonzero sample standard deviation. Bold marks minimum displayed total cost in each column; query percentages are not ranked. The configuration-selection protocol is stated above.

Figure 3: Six-price test comparison with external baselines: total cost and query fraction. The fee axis is logarithmic. Error bars show one sample standard deviation when nonzero; lines join the measured prices without smoothing. The cost axis has a nonzero origin.

Router	Synthetic	Melbourne	Jena	Delhi
Response-Aware UCB	0.08092	4.49069	3.72844	2.59240
Joint response UCB	0.08092	4.49069	3.72844	2.62820
Disjoint response UCB	0.08358	4.62449	3.74382	2.62465
Cyclic response	0.15557	5.66927	3.97404	2.84056
Free prediction	0.10949	5.40136	4.18186	2.72163

Appendix

Table 6: Matched-response routing: mean total test cost on all four streams. All querying methods can correct the selected expert’s answer. Bold values mark the minimum per dataset.

Explore similar work

Online Learning-to-Defer with Varying Experts
May 12, 2026Dang Hoang Duy, Yannis Montreuil, Maxime Meyer +3Learning-Augmented Algorithms Experts
School of Computing, National University of Singapore, Singapore · IPAL, IRL 2955, Singapore · Department of Mathematics, National University of Singapore, Singapore, 117543 +2
Prediction with Expert Advice: Anytime Regret with Many Experts Matches the Fixed-Time Constant
Sep 23, 2026Yang Cai, Vineet Gupta, Yanchen Jiang +4\Widetilde{\Mathcal{O}}(\Sqrt{T})$ Regret Regret
Google Research · Yale University · Google DeepMind
Learning-to-Defer in Non-Stationary Time Series via Switching State-Space Models
Jan 30, 2026Yannis Montreuil, Letian Yu, Axel Carlier +2Non-Stationarity
School of Computing National University of Singapore · Université de Toulouse Fédération ENAC ISAE-SUPAERO ONERA · Institute for Infocomm Research A*STAR, Singapore

May 12, 2026, stat.MLJ/K move · Enter open · S save

Online Learning-to-Defer with Varying Experts

Dang Hoang Duy, Yannis Montreuil, Maxime Meyer, Axel Carlier+2

School of Computing, National University of Singapore, Singapore · IPAL, IRL 2955, Singapore · Department of Mathematics, National University of Singapore, Singapore, 117543+2

Learning-Augmented Algorithms Experts Bandits

Open paper AskPDF arXiv

Learning-to-Defer (L2D) methods route each query either to a predictive model or to external experts. While existing work studies this problem in batch settings, real-world deployments require handling streaming data, changing expert availability, and shifting expert distribution. We introduce the first online L2D algorithm for multiclass classification with bandit feedback and a dynamically varying pool of experts. Our method achieves regret guarantees of

O((n+n_e)T^{2/3})

in general and

O((n+n_e)\sqrt{T})

under a low-noise condition, where

T

is the time horizon,

n

is the number of labels, and

n_e

is the number of distinct experts observed across rounds. The analysis builds on novel

\mathcal{H}

-consistency bounds for the online framework, combined with first-order methods for online convex optimization. Experiments on synthetic and real-world datasets demonstrate that our approach effectively extends standard Learning-to-Defer to settings with varying expert availability and reliability.

Abstract

Explore similar work

Online Learning-to-Defer with Varying Experts

Prediction with Expert Advice: Anytime Regret with Many Experts Matches the Fixed-Time Constant

Learning-to-Defer in Non-Stationary Time Series via Switching State-Space Models