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(Tlog(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 ± 0.00389
5.42987 ± 0.15762
4.11937 ± 0.04932
2.74807 ± 0.04935
NeuralUCB
0.10183 ± 0.00604
5.58128 ± 0.26329
4.18453 ± 0.13384
2.92431 ± 0.20347
Table 1: Mean test cost, including consultation fees. Entries show mean ± sample standard deviation across five learner seeds. Lower is better.
Method
×1
×3
×5
×7.5
×12.5
×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 ± 0.049
4.167 ± 0.040
4.177 ± 0.036
4.233 ± 0.044
4.250 ± 0.065
4.182
NeuralUCB
4.185 ± 0.134
4.223 ± 0.108
4.190 ± 0.069
4.169 ± 0.045
4.189 ± 0.020
4.182
Table 2: Mean Jena test cost at six consultation prices. Columns scale the base fee (≈0.17) . Entries show mean ± 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
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 Δ 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.
Ft
Information available before the round- t query.
Et,At
Available identities and the eligible subset with fees below R2 .
It,βt,j
Chosen action ( 0 means free prediction) and the fee for expert j .
ht,Mt,j,Yt
Internal prediction, potential expert answer, and outcome.
dt,j,et,j
Disagreement Mt,j−ht and expert residual Yt−Mt,j .
Appendix
Table 3: Decisions, responses, and costs. All risks exclude consultation fees.
Symbol
Meaning
ℓt,j∈Rdℓ,st,j∈Rds
Public features for identity and shared responses.
Θt,j,Ψt
Response matrices of sizes dℓ×(q+1) and ds×(q+1) .
wt,jH,wt,jP,η
Proposal mixture weights and their exponential-weights rate.
xt0∈Rd0,ct,j∈Rdc
Public features for free and optimal queried risk.
Λv,Vtv,θtv
Prior, pre-round design, and risk estimate, for v∈{0,∗} .
λv,Qv,Bv
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
×1
×3
×5
×7.5
×12.5
×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 ± 0.049
4.167 ± 0.040
4.177 ± 0.036
4.233 ± 0.044
4.250 ± 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.
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+ne)T2/3) in general and O((n+ne)T) under a low-noise condition, where T is the time horizon, n is the number of labels, and ne is the number of distinct experts observed across rounds. The analysis builds on novel 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.
Dang Hoang Duy, Yannis Montreuil, Maxime Meyer +3
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 is a fundamental problem in online learning. When the time horizon T is known in advance, the minimax cumulative regret over n experts is asymptotically 2Tlnn. This is achieved by the Multiplicative Weights Update algorithm with a learning rate tuned to T, and is known to be tight. If instead the regret bound is required to hold simultaneously at every time t, the best known guarantee has been tlnn---a factor of 2 worse---and it has remained unknown whether this factor of 2 is necessary. We show that it is not. We give an algorithm, requiring no knowledge of the horizon, whose cumulative regret satisfies Rt≤(1+O(lnlnn/lnn))tlnn/2 simultaneously for every t≥1.
Yang Cai, Vineet Gupta, Yanchen Jiang +4
Google Research · Yale University · Google DeepMind
Learning-to-defer (L2D) lets a predictor decide, at each round, whether to issue its own forecast or pay for an expert's. In non-stationary time series this decision must keep adapting, although deployment reveals only the consulted expert's forecast while a historical archive records every expert with the target. L2D-SLDS learns from this archive a switching state-space model of the target and all expert forecasts, whose shared and expert-specific states describe how experts move together and apart. Its predictive law supplies the internal forecast and the expected cost of every consultation, which a greedy router minimizes, and one consultation also updates the beliefs about unconsulted and unavailable experts. We prove sublinear regret against a changing conditional-risk oracle without exploration, when the candidate models are accurate and either the archive separates them or live feedback reveals cost differences. On three real datasets, L2D-SLDS has the lowest cost among eight bandit routers and adapts its consultation rate to the fee.
Yannis Montreuil, Letian Yu, Axel Carlier +2
School of Computing National University of Singapore · Université de Toulouse Fédération ENAC ISAE-SUPAERO ONERA · Institute for Infocomm Research A*STAR, Singapore