Conceptio › Archive › arXiv CS

arXiv CSopen access

Online Learning-to-Defer with Varying Experts

2026 · arxiv_cs

arXiv CS · Papers · License: Open Access · 2026

Open Source ↗Direct PDF ↓

neural-networks

machine learning, deep learning, neural networks

Online Learning-to-Defer with Varying Experts

Dang Hoang Duy∗,1

Yannis Montreuil∗,1,4,5

Maxime Meyer∗,1,4

arXiv:2605.12340v1 [stat.ML] 12 May 2026

Axel Carlier2,4 Lai Xing Ng3,4 Wei Tsang Ooi1,4 1 School of Computing, National University of Singapore, Singapore 2 Fédération ENAC ISAE-SUPAERO ONERA, Université de Toulouse, France 3 Institute for Infocomm Research, A*STAR , Singapore 4 IPAL, IRL 2955, Singapore 5 CNRS@CREATE LTD, 1 Create Way, Singapore

Abstract 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 2/3 regret guarantees of O((n √ + ne )T ) 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 Learningto-Defer to settings with varying expert availability and reliability.

INTRODUCTION

Learning-to-Defer (L2D) is a framework for integrating machine learning models with human experts—or more broadly, auxiliary decision-makers—to enhance the reliability of automated systems. The central idea Proceedings of the 29th International Conference on Artificial Intelligence and Statistics (AISTATS) 2026, Tangier, Morocco. PMLR: Volume 300. Copyright 2026 by the author(s).

is to let a predictive model handle routine or lowrisk inputs autonomously, while deferring uncertain or high-stakes cases to more competent agents such as domain experts, larger models, or specialized subsystems (Madras et al., 2018; Mozannar and Sontag, 2020; Verma et al., 2022). This deference mechanism enables L2D systems to balance predictive accuracy against consultation cost, leveraging the scalability of machine learning while preserving safety through expert oversight. For instance, in medical diagnostics, a model may issue a confident prediction for straightforward cases but defer ambiguous ones to a clinician, thereby reducing risk without overburdening human resources (Johnson et al., 2016, 2023; Strong et al., 2024). While L2D has shown promise, existing formulations rely on assumptions that rarely hold in practice. They posit a fixed pool of experts available throughout deployment and require predictions from every expert in training. In reality, expert availability and reliability are dynamic: clinicians may be available only during scheduled shifts, their accuracy may degrade under fatigue, and automated subsystems may be restricted by budget or resource constraints. Moreover, many applications generate data sequentially, demanding decisions in an online rather than batch setting. These conditions expose a fundamental gap between classical L2D assumptions and the requirements of real-world deployment. To the best of our knowledge, we present the first online Learning-to-Defer framework, where both the data distribution and the pool of experts may evolve over time. The formulation further accounts for experts whose reliability may drift, and, unlike classical L2D methods, it only requires feedback from the experts that are actually queried, rather than predictions from all experts to compute the loss. To assess the theoret-

Online Learning-to-Defer with Varying Experts

ical performance of our approach, we analyze regret, which measures the gap between the learner’s cumulative performance and that of the best strategy in hindsight over T rounds. We prove that our algorithm achieves regret sublinear in T , ensuring that the average per-round regret vanishes asymptotically. Our main contributions are as follows: (i) We introduce a general framework for online Learning-toDefer under bandit feedback, where both the number of experts and the data distribution may vary over time. (ii) We extend the notion of H-consistency bounds to the online setting, whereas previous analyses were limited to batch learning. (iii) We propose the first online algorithm for this setting, achieving√regret O((n + ne )T 2/3 ) in general and O((n + ne ) T ) under a low-noise assumption. (iv) We empirically validate our approach on both synthetic and real-world datasets, demonstrating its competitiveness and robustness across diverse scenarios.

RELATED WORK

Learning-to-Defer. Learning-to-Defer (L2D) generalizes selective prediction (Chow, 1970; Bartlett and Wegkamp, 2008; Cortes et al., 2016; Geifman and ElYaniv, 2017) by allowing a model not only to abstain on uncertain inputs but also to defer them to external experts (Madras et al., 2018; Mozannar and Sontag, 2020; Verma et al., 2022). Prior work has focused exclusively on the batch-learning setting. The score-based formulation of Mozannar and Sontag (2020) introduced the first Bayes-consistent surrogate, which has since become the standard for onestage frameworks. Subsequent work has refined calibration (Verma et al., 2022; Cao et al., 2024), improved surrogate design (Charusaie et al., 2022; Mao et al., 2024a; Montreuil et al., 2026a), and established guarantees such as H-consistency and realizability (Mozannar et al., 2023; Mao et al., 2024b, 2025). Applications span diverse classification tasks (Kerrigan et al., 2021; Keswani et al., 2021; Hemmer et al., 2022; Verma et al., 2022; Benz and Rodriguez, 2022; Cao et al., 2024; Tailor et al., 2024; Liu et al., 2024), while a special case of this formulation is the two-stage framework, in which the base predictor and experts are trained offline and only the allocation function is learned (Narasimhan et al., 2022; Mao et al., 2023a). Extensions of two-stage approaches further address regression (Mao et al., 2024c), multi-task learning (Montreuil et al., 2025b), adversarial robustness (Montreuil et al., 2025a, 2026c), and applied systems (Strong et al., 2024; Palomba et al., 2025; Montreuil et al., 2026b).

Online-Learning. The most relevant line of work to our paper is bandit multiclass classification. A common approach employs proper learning algorithms that fix a hypothesis before the next input (Kakade et al., 2008). Subsequent papers refine this idea (Hazan and Kale, 2011; Beygelzimer et al., 2017; van der Hoeven, 2020; van der Hoeven et al., 2021), with van der Hoeven (2020) exploiting the gap between surrogate and zero-one loss. We also use a proper learner, but we evaluate performance directly in terms of the zeroone loss rather than only through a surrogate. Our distributional assumptions are broader than those in Crammer and Gentile (2013), which treat a specific label distribution, while our results cover arbitrary label distributions. Another relevant line of work is online logistic regression. Foster et al. (2018) give a statistically optimal strategy that is not computationally practical. Jézéquel et al. (2020) provide an efficient algorithm in the binary case. More recent work (Jézéquel et al., 2021; Agarwal et al., 2022) develops algorithms with near-optimal regret and efficient running time, and shows how to use them for bandit classification. Our analysis follows this template. We first study the underlying online convex optimization problem and then combine it with a separate argument to obtain guarantees for multiclass bandit classification. With a fixed number of experts per round, our setting reduces to contextual multi-armed bandits (Auer et al., 2002; Li et al., √ 2010). In this regime it is known that Rℓdef (T ) = Ω( T ) (Daniely and Helbertal, 2013). This lower bound motivates our focus on additional structure beyond a generic contextual-bandit reduction and explains why controlling the true zero-one loss within a proper-learner framework is natural for our setting.

PRELIMINARIES

Multiclass Classification. We consider the standard multiclass classification setting. The input space is X = {x ∈ Rd : 1 ≤ ∥x∥2 ≤ R} for some radius R > 0, and the label space is Y = [n] := {1, . . . , n} with n ≥ 2 classes (Mohri et al., 2012). The predictions are obtained through a hypothesis h : X × Y → R, via the decision rule h(x) = arg maxj∈Y h(x, j). The performance of h is measured by the 0–1 loss ℓ(h(x), y) = 1{h(x) ̸= y}, which directly captures misclassification error. Since the 0–1 loss is nondifferentiable, learning algorithms typically minimize a surrogate that approximates it (Zhang, 2002; Steinwart, 2007). We denote by Φ01 : H × X × Y → R+ a general surrogate loss. Two prominent families are of particular interest: (i) the cross-entropy family Φcse 01 ,

Dang, Montreuil, Meyer, Carlier, Ng, and Tsang

which includes the exponential and logistic losses, and (ii) the constrained surrogate family Φcstnd , which in01 cludes constrained hinge-type losses (Awasthi et al., 2021, 2022a; Mao et al., 2023c). A surrogate Φ01 is said to be H-consistent if minimizing its excess surrogate risk ensures recovery of the Bayes-optimal predictor within the hypothesis class H. Writing the risk of a loss ℓ as Eℓ (h) = E[ℓ(h(x), y)] in batch-learning, this property is formally characterized by consistency bounds (Awasthi et al., 2022a). Definition 3.1 (H-Consistency Bounds). Suppose the surrogate Φ01 is H-consistent w.r.t the 0-1 loss ℓ01 for any distribution D. Then, there exists a nondecreasing function Γ : R+ → R+ such that, for all h ∈ H,

Directly minimizing ℓbatch is intractable due to its def non-differentiability (Zhang, 2002; Steinwart, 2007). Following Mozannar and Sontag (2020); Mao et al. (2024a), we instead optimize a convex surrogate loss that is Bayes and H-consistent for ℓbatch def , and has since become the standard formulation. Definition 3.3 (Score-Based Surrogate). Let x ∈ X , y ∈ Y, and h ∈ H. The score-based surrogate is Φbatch def (h, x, y) = Φ01 (h, x, y) ne X + (1 − cj (x, y)) Φ01 (h, x, n + j), j=1

EXTENDING LEARNING-TO-DEFER TO THE ONLINE-LEARNING SETTING

4.1

Problem Formulation

Eℓ01 (h) − Eℓ∗01 ,H − Uℓ01 ,H ≤ Γ EΦ01 (h) − EΦ∗ 01,H − UΦ01,H . Here Uℓ01 ,H = Eℓ∗01 ,H − Ex inf h∈H Ey|x ℓ01 (h(x), y) is the minimizability gap, quantifying the irreducible approximation error due to the expressive limitations of H. When H is sufficiently rich—such as H = Hall —this gap vanishes, and the inequality recovers standard Bayes-consistency guarantees (Steinwart, 2007; Awasthi et al., 2022a). Batch Learning-to-Defer. Standard batch L2D assumes access to a fixed pool of ne experts G = {g1 , g2 , . . . , gne }, each being a mapping gi : X → Y (Madras et al., 2018; Mozannar and Sontag, 2020). Training examples (x, y) are drawn i.i.d. from an unknown distribution D, and for every input x we observe the tuple (y, g1 (x), g2 (x), . . . , gne (x)). The learner then has to decide, for each input, whether to predict directly or defer to an expert. To formalize this, we define the augmented label space Y = Y ∪{n+ j : gj ∈ G}, where indices 1, . . . , n correspond to class predictions and indices n + j correspond to deferral to expert gj . The goal of the learner is to find a hypothesis h : X × Y → R that minimizes the true score-based loss: Definition 3.2 (True Score-Based Loss). Let x ∈ X , y ∈ Y, and h ∈ H. The true score-based loss is ( ℓbatch def (h(x), y) =

1{h(x) ̸= y}

if h(x) ∈ Y,

cj (x, y)

if h(x) = n + j.

Here, cj (x, y) accounts for both the misclassification and the query cost of expert gj . We denote by cj ≥ 0 and cj ≤ 1 the finite lower bound and upper bound of cj , that is cj (x, y) ∈ [cj , cj ] for all (x, y) ∈ X × Y.

Problem Setup. Prior work assume access to a fixed pool of experts (Madras et al., 2018; Mozannar and Sontag, 2020; Verma et al., 2022), but this assumption rarely holds in practice. In realistic deployments, the set of available experts may evolve over time: human annotators can join or leave, domain specialists may be consulted only intermittently, and automated subsystems may become unavailable due to resource or reliability constraints. This motivates the introduction of the online framework, in which the learner receives information and makes decision sequentially. To capture this, we denote by A ⊆ P(G) the collection of feasible expert subsets, and X = X × A the augmented input space. That is the augmented inputs x = (x, A) consist of both the classical input x ∈ X and the set of available experts A ∈ A. The interaction protocol is as follows: (i) At each round t, the adversary selects an augmented input xt ∈ X adversarially (Hazan, 2016), which is then revealed to the learner. (ii) A label y is drawn from a fixed but unknown distribution p(· | xt ), depending only on xt . (iii) The learner commits to a prediction yt′ from the augmented label set with experts available at round t, namely Y At = [n] ∪ {n + j : gj ∈ At }. (iv) The learner then incurs a loss determined by its prediction. We use the bold notation to denote a sequence of objects. Hence the sequence of inputs (x1 , x2 , . . . , xT ) ∈ T X is denoted x. Bandit Feedback. We work in the bandit feedback setting, where the learner only observes feedback about the chosen action. If it predicts a label yt′ ∈ [n],

Online Learning-to-Defer with Varying Experts

it does not receive the true label yt but only a binary signal indicating correctness, 1{yt′ = yt }. If it defers to expert gj (i.e., yt′ = n + j), it observes whether the expert was correct, 1{gj (xt ) = yt }, together with the associated cost cj (xt , yt ). In contrast, in the batch Learning-to-Defer framework the learner observes the true label and the correctness of all experts during training, regardless of whether they are queried. This restriction makes the bandit setting not only substantially more challenging but also more faithful to practical applications than standard supervised classification, where the learner always receives the full label information. Hypothesis Set. As for standard batch L2D, we consider that the learner predicts through a hypothesis h : X × Y → R. For every augmented input xt = (xt , At ), the prediction of the learner is then h(xt ) = arg maxy∈Y A h(xt , y). We only consider the t linear hypothesis set, id est hypothesis in the form h(x, y) = ⟨wy , x⟩ + by where wy is a vector of some weight matrix W ∈ RN ×d , by is the corresponding bias, and N = n + ne is the size of the augmented label set. We denote by H the set of such hypotheses. Note that in this work, we only consider proper learning algorithms. That is the hypothesis ht ∈ H at each round t is generated before seeing input xt . Finally, the goal of the learner is to minimize the gap between his sequence of hypotheses h and the best hypothesis in hindsight h.

qt ∈ ∆Y A : t

qt = (1 − γt )eht (xt ) +

γt 1, |Y At |

where ey is the unit vector in the direction of y and γt ∈ (0, 1) is the exploration rate. 4.2

Loss Formulation

As introduced in Definition 3.2, the classical Learningto-Defer formulation (Mozannar and Sontag, 2020) is defined in a batch-learning setting, assuming access to a fixed dataset and a fixed pool of experts. To relax these assumptions, we introduce a true deferral loss, which naturally generalizes Definition 3.2 to accommodate scenarios where the set of available experts may be restricted. Definition 4.1 (True Deferral Loss). The true deferral loss is defined as follows for any h ∈ H and (x, y) = ((x, A), y) ∈ X × Y ( 1{h(x ̸= y} if h(x) ∈ Y, ℓdef (h, x, y) = cj (x, y) if h(x) ∈ {n + j : gj ∈ At }. Moreover, let the online learner predict according to a distribution q ∈ ∆Y A . The corresponding true deferral loss with respect to the learner is defined by h ℓdef (q, x, y) = Ey′ ∼q 1{y ′ ∈ Y}1{y ′ ̸= y} i X cj (x, y)1{y ′ = n + j} . + n+j∈Y A

Semi-Adversarial Setting. We deliberately adopt a semi-adversarial framework, where inputs xt may be chosen adversarially while labels are drawn from a fixed distribution p. This choice reflects the core structure of Learning-to-Defer: in realistic deployments, the instances presented to the system—such as medical cases, flagged content, or decision-support queries—may arrive in arbitrary or even adversarial ways, yet both the learner and the experts must ultimately be evaluated against the same ground-truth distribution. Without this structure, the notion of deferring to experts would be ill-posed, since expert reliability can only be assessed relative to a consistent source of truth. To denote the induced distributions, given any finite set S, we thus define ∆S ⊂ R|S| as the set of standard |S|-dimensional simplexes representing distributions over S. We denote by D a set of conditional distributions over Y, indexed by x, that is, D ⊆ {p : X → ∆Y }. For ease of notation, write p(x, y) = P(Y = y|X = x). This setting forces us to randomize the learner’s predictions, as discussed in Appendix A. At each round t, we thus sample the predictions from a distribution

Note that our true deferral loss, introduced in Definition 4.1, directly extends the formulations of Mozannar and Sontag (2020); Verma et al. (2022); Mao et al. (2024a). Since ℓdef is non-differentiable, the standard practice in online classification is to replace it with a convex surrogate Φdef that upper bounds ℓdef , and then optimize Φdef using Online Convex Optimization (OCO) (Hazan, 2016) methods such as Online Gradient Descent (OGD) (Zinkevich, 2003). Definition 4.2 (Varying Multiclass Surrogate Loss). For each expert set A, let ΦA 01 : H × X × Y A be the standard Y A -class classification surrogate. The varye ing multiclass surrogate loss ( Φ01 : H ×X ×Y is defined A e 01 (h, x, j) = Φ01 (h, x, j) if j ∈ Y A , as follows Φ 0 otherwise. Intuitively, this definition guarantees that the surroe 01 is unaffected by the scores of experts that are gate Φ not available. Building on this property, any multie 01 can be naturally extended to class surrogate loss Φ obtain an online equivalent of Definition 3.3.

Dang, Montreuil, Meyer, Carlier, Ng, and Tsang

Definition 4.3 (Surrogate Deferral Loss). , then for any h ∈ H and (x, y) = ((x, A), y) ∈ X × Y, e 01 (h, x, y) Φdef (h, x, y) = Φ X e 01 (h, x, n + j). + (1 − cj (x, y))Φ n+j∈Y A

4.3

Regret Formulation

We can now formalize the goal of the learner, which is to minimize the gap between the cumulative risk of his sequence of hypotheses, and the cumulative risk of the best hypothesis in hindsight. At every round t, the conditional ℓdef -risk is defined by Cℓdef (ht , x̄t ) = Eyt ∼p(x̄t ) [ℓdef (ht , x̄t , yt )]. We can now analyze the cumulative ℓ -risk R (h, x̄) = def ℓ def P C (h , x̄ ) and the optimal cumulative risk in ℓ t t def t∈[T ] hindsight R∗ℓdef ,H (x̄) = inf h∈H Rℓdef (h, x̄). The objective of the learner is to minimize the true deferral regret Rℓdef (T ) = Rℓdef (q, x̄) − R∗ℓdef ,H (x̄).

(1)

In particular, the goal is to achieve sublinear regret scaling in T , that is Rℓdef (T ) = o(T ). This enR (T ) converges to zero sures that the average regret ℓdef T as T → ∞, meaning that the learner’s performance asymptotically approaches that of the best fixed strategy in hindsight. The regret typically depends on the (ℓdef , H)minimizability gap Mℓdef ,H (x̄) = R∗ℓdef ,H (x̄) − P ∗ t∈[T ] Cℓdef ,H (x̄t ). The minimizability gap measures the discrepancy between selecting the best hypothesis adaptively at each round and selecting the best single hypothesis in hindsight.

H-CONSISTENCY BOUND FOR ONLINE LEARNING

A central property in batch learning is consistency, which ensures that minimizing a surrogate risk recovers the Bayes-optimal solution. This property has been extensively studied in the classical setting (Zhang, 2002; Steinwart, 2007; Bartlett et al., 2006), but remains largely unexplored in online learning, despite being crucial for understanding how well surrogate minimization minimizes the true loss. To address this gap, we introduce the notion of H-consistency bounds in the online setting, drawing parallels to the bounds developed in Bartlett et al. (2006); Awasthi et al. (2022a); Mao et al. (2023c). Formally, our goal is to relate the true deferral regret Rℓdef (T ) = Rℓdef (q, x) − R∗ℓdef ,H (x) to the surrogate deferral regret RΦdef (T ) = RΦdef (h, x) − R∗Φdef ,H (x).

This reduction is valid whenever the underlying mule 01 admits an H-consistency bound ticlass surrogate Φ with respect to ℓ01 : that is, there exists a concave, non-decreasing calibration function Γ : R+ → R and a tolerance ϵ ≥ 0 such that, for all h ∈ H, x ∈ X , and p ∈ D, ∆Cℓ01 ,H (h, x)1{∆Cℓ01 ,H (h, x) > ϵ} ≤ Γ ∆CΦ e 01 ,H (h, x) . It follows that the surrogate provides a calibrated upper bound on the true deferral regret. Theorem 5.1. (Distribution-Dependent Γ-Bound) e 01 admits an H-consistency bound w.r.t Assume that Φ ℓ01 with a concave, non-decreasing calibration function T Γ : R+ → R with Γ(0) = 0. Then for any x ∈ X and any distribution p ∈ D, suppose the online learner generates corresponding hypotheses h and samples from q defined in Section 4.1, we have, P γ Rℓdef (T ) + Mℓdef ,H (x) − c t t∈[T ] −ϵ T RΦdef (T ) + MΦdef H (x) ≤ max S(xt ) Γ . T mint∈[T ] S(xt ) t∈[T ] P Here, S(xt ) = + p(xt , y) y∈Y P P and c is 1 − y∈Y p(xt , y)cj (xt , y) n+j∈Y A t

the upper bound on the expert cost c = maxj {cj }. The proof is deferred to Appendix C. Note that the minimizability gap vanishes when the Bayes optimal cmulative risk coincides with the best-in-class cumulative risk, that is R∗ℓdef ,H (x) = Rℓdef ,Hall (x), this implies the following corollary. e 01 admits an HCorollary 5.2. Assume that Φ consistency bound with respect to the multi-class zeroone classification loss ℓ01 . Then, for all h ∈ H, any T x ∈ X and any distribution such that R∗Φdef ,H (x) = R∗Φdef ,Hall (x), the following bound holds: P γ t Rℓdef (q, x) − R∗ℓdef ,H (x) c t∈[T ] − −ϵ T T ∗ RΦdef (h, x) − RΦdef ,H (x) ≤ max S(xt ) Γ . T mint∈[T ] S(xt ) t∈[T ] In the limit, this bound recovers an online analogue of the standard Bayes-consistency notion defined in Bartlett et al. (2006).

REGRET BOUNDS FOR ONLINE L2D

We can now derive explicit regret bounds from the H-Consistency Bound defined in the previous section.

Online Learning-to-Defer with Varying Experts

Indeed, such bounds can be obtained directly by minimizing the right-hand side in Theorem 5.1. Since the minimizability gap MΦdef ,H (x) depends only on the hypothesis class H and the input sequence x, minimizing the right-hand side effectively becomes an online optimization problem of minimizing the surrogate deferral regret RΦdef (T ) with bandit feedback. The resulting bound is especially tight when the bestin-class hypothesis coincides with the Bayes hypothesis, i.e., R∗Φdef ,H (x) = R∗Φdef ,Hall (x), as Corollary 5.2 then a true deferral regret bound of Rℓdef (T ) = implies O TΓ

RΦdef (T ) T

If we restrict the setting to bandit feedback with fixed number of experts, it becomes a special case of contextual multi-armed bandits (Auer et al., 2002; Li et al., √ 2010). A lower bound Rℓdef (T ) = Ω( T ) is known (Daniely and Helbertal, 2013), but can only be reached by algorithms that are hard to implement in practice, such as EXP4 (Auer et al., 2002). We show that even relaxing to a varying number of experts, we can still match this lower bound with an efficient implementation. The key idea is to select a surrogate loss Φdef that admits a linear calibration function Γ in Theorem 5.1, which yields the reduction Rℓdef (T ) = O(RΦdef (T )). We then show that there exists an online algorithm with surrogate deferral re√ gret RΦdef (T ) = O( T√), thereby achieving the desired bound Rℓdef (T ) = O( T ). In particular, we establish this result using the constrained hinge loss, and we present the corresponding algorithm and analysis in Section 6.1. 6.1

Constrained OCO with constrained hinge loss Φcstnd hinge

When the surrogate is chosen as the constrained hinge cstnd loss ΦA 01 = Φhinge (Lee et al., 2004), the induced surrogate deferral loss takes the form X e hinge (−h(x, y ′ )) Φdef (h, x, y) = Φ y ′ ∈Y A \{y}

(1 − cj (x, y))

e hinge (−h(x, y ′ )), Φ

Since H is the set of linear hypotheses, we can write H = {h := (W, b) ∈ RN ×(d+1) |h(x, y) = ⟨wy , x⟩ + by } where wy ∈ Rd is the y-th row of W , and b ∈ RN is the bias column. For ease of notation, denote f = (W, b) ∈ RN ×(d+1) and w f. W ey the y-th row of W f interchangeably when it is clear from We use h and W the context. We place a bound on hypothesis’s norm, f ∈ RN ×(d+1) | ||W f ||F ≤ B}. We note that is H = {W that previous results for H-consistency bound w.r.t constrained hinge loss still holds for our hypothesis set H with a suitably chosen bound B. The discussion is deferred to Appendix B. For each P expert set A ∈ A, we define KA = {h ∈ Hall | y∈Y A h(x, y) = 0, ∀x ∈ X } as the unbounded minimum feasible hypothesis set w.r.t expert set A. f whose That is KA is the set of weight matrices W column sums to 0 over rows in Y A . Denote h|KA the projection of a hypothesis h ∈ H onto KA . Our setting differs from previous constrained OCO problems in that there potentially exists only the trivial hypothesis in the intersection of all feasible sets, that is, ∩t∈[T ] KAt = {0} in the worst case. This renders previous approaches, which rely on minimizing regret against the optimal feasible hypothesis R∗Φdef ,H (x) = inf h∈∩t∈[T ] KAt RΦdef (h, x), ineffective in our problem. To address this, we devise a variant of the OGD algorithm that allows us to minimize regret against the best hypothesis after projection in the original hypothesis set H. In other wordswe deT ∗ fine RΦdef ,H (x) = inf h∈H RΦdef h|KAt t=1 , x . The key idea is to utilize important properties of projections onto KA , which are described in the following proposition. Proposition 6.1. (Properties of ΠKA ) For any linear f ∈ H and expert set A ∈ A, we have hypothesis h = W the following properties: f |K = W f − µT 1 1. W ei |KA )N A i=1 , where µ = Y A = (w P 1 w e , w e | = w e − µ if i ∈ YA and i KA i i∈Y A i |Y A | w ei |KA = w ei otherwise. 2. (Maxima preserving) For any x = (x, A) ∈ X , then h(x) = h|KA (x).

y ′ ∈Y A \{n+j}

n+j∈Y A

P subject to the constraint y∈Y A h(x, y) = 0. The resulting learning problem is therefore a constrained online convex optimization problem. Problem 1 (Constrained Online Convex Optimization). RΦdef (T ) = RΦdef (h, x̄) − R∗Φdef ,H (x̄), X subject to ht (x̄t , y) = 0, ∀t ∈ [T ].

minimize

y∈Y A

Proposition 6.1 implies that projection onto KA preserves the hypothesis’s predictions on rounds whose label set is Y A . As a result, if h = (h1 , h2 , . . . , hT ) is any sequence of hypotheses generated, then h = T ΠKAt (ht ) t=1 . That is the sequences of projected hypotheses, satisfies Rℓdef (h, x) = Rℓdef (h, x). In particular, when h = (h∗ )Tt=1 is the fixed sequence of best-in-class hypothesis, this implies that the objective true deferral regret Rℓdef (T ) is preserved, that is Rℓdef (h, x) = Rℓdef (h, x) = R∗ℓdef ,H (x).

Dang, Montreuil, Meyer, Carlier, Ng, and Tsang

Algorithm 1 OGD with Projected Gradients 1: Input: Learning rate ηt > 0, and exploration rate

γt f1 = 0 ∈ RN ×(d+1) 2: Initialize: W 3: for t = 1 to T do 4: Obtain xt = (xt , At )

i∈Y At

6: 7:

ft to feasible hypothesis set: W ft |K = Project W At ft ΠKAt W Let yt∗ = arg maxy ⟨wt,y , xt ⟩ + bt Set qt = (1 − γt )eyt∗ + |Yγt | 1

Predict with label yt′ ∼ qt

bt W ft |K Obtain feedback and compute Φ acAt cordingly b t = ∇Φ bt W ft |K 10: Compute gradient ∇ and its At b b projection onto KAt : ∇t |KAt = ΠKAt (∇t ) ft+1 = W ft − ηt ∇ b t |K 11: Update W At 12: end for 9:

We now introduce our algorithm, with full details provided in Algorithm 1. At round t, let wt,y deb t denote the esnote the y-th row of Wt , and let Φ timated loss function constructed from the available feedback. In the full-feedback setting, the estimate coincides with surrogate deferral loss, i.e., the true b f f Φt Wt |KAt = Φdef Wt |KAt , xt , yt . In the banditfeedback setting, we have X bt W f = e 01 W f , xt , n + j (1 − cj (xt , yt )) Φ vt,j Φ n+j∈Y At

′

e 01 W f , xt , y , ∀W f ∈ H. + vt,0 Φ t When ΦA 01

′ = Φcstnd hinge , let yt denote the learner’s ran-

domized prediction sampled from qt , and define vt,0 = 1{yt′ ∈[n]}1{yt′ =yt } 1{y ′ =n+j} and vt,j = qtt(n+j) . The learner’s qt (yt′ ) exploration rate γt , introduced in Section 4.1, is set to γt = 0 in the full-information case, and to γt = min{ 12 , √γt } in the bandit case, for some constant γ > 0 specified later. h i b t is always convex and Ey′ ∼q Φ b t (W f) = Note that Φ t t f , xt , yt regardless of the feedback scenario. Φdef W f ∗ is the best-in-class hypotheSuppose h∗ = W sis w.r.t surrogate loss h∗ = deferral Φ, i.e. T arg minh∈H RΦdef h|KAt t=1 , x . For any expert set P A, denotes µ∗A = |Y1 | i∈Y A w ei∗ , the following lemma A gives an upper bound on the surrogate loss difference between learner’s generated hypothesis and best-inclass hypothesis. b t,i be the gradient of the i-th row Lemma 6.2. Let ∇ b b f b t,i |K of ∇t = ∇Φt Wt |K in round t ∈ [T ], and ∇ At

b t |K = the projected gradient onto KAt , that is ∇ At N b (∇t,i |KAt )i=1 . We have X bt W b t,i |K , w ft |K −Φ bt W f ∗ |K ≤ et,i − w ei∗ ⟩. Φ ⟨∇ At At At

The proof is deferred to Appendix E. By applying Lemma 6.2 to every round and summing up, we obtain the following bound on the surrogate regret. Theorem 6.3. (Surrogate regret bound) Running Al1 B gorithm 1 with ηt = √N R , γt = min 21 , t1/3 for t2/3 t = 1, . . . , T , we have the following surrogate regret bound X ft |K , xt , yt − Φdef W f ∗ |K , xt , yt Φdef W At At t∈[T ]

= O N 3/2 B R T 2/3 . b t,i |K , w The key idea is to bound ⟨∇ et,i − w ei∗ ⟩ together At on rounds t ∈ [T ] in which label i is available and apply Lemma 6.2. The proof is analogous to Theorem 2.13 in Orabona (2019) and is deferred to Appendix E.1. Note that by Proposition 6.1, we have X ft f∗ ℓdef W , xt , yt − ℓdef W , xt , yt K K At

t∈[T ]

ft , xt , yt − ℓdef W f ∗ , xt , yt ℓdef W

t∈[T ]

Combining Corollary 5.2 and Theorem 6.3, we achieve the following true deferral regret bound. Theorem 6.4. (True Deferral Regret Bound) Under the same assumptions in Corollary 5.2 and TheoB rem 6.3. Running Algorithm 1 with ηt = √N Rt ,t = 2/3 1 1 1, . . . , T , γt = min 2 , t1/3 gives us the following expected regret bound X f ∗ , xt , yt Rℓdef (T ) = ℓdef qt , xt , yt − ℓdef W t∈[T ]

= O N 3/2 BRT 2/3 . 1 , Proof. Note that when γt = min 21 , t1/3 P cγt −1/3 ). Hence, applying Corollary 5.2 = O(T t∈[T ] T and Theorem 6.3 directly gives us the desired bound. Near-Realizable Assumption. We make use of the following definition for any x = (x, A) ∈ X and y ∈ Y  p(x, y) if y ∈ Y, s(x, y) = 1 − P ′ ′ y ′ ∈Y p(x, y )cj (x, y ) if y = n + j. To obtain the probability representation, we denote s(x, y) = s(x,y) S(x) the normalized counterparts of s(x, y),

Online Learning-to-Defer with Varying Experts

P where S(x) = s(x, y). Intuitively, s(x, y) iny∈Y A dicates the expected ”score” of label y given input x. By making further assumptions on the score distribution given an input √ x, we can improve the O(T 2/3 ) regret bound to O( T ). Given input x ∈ X , let ymax be the label with highest score, that is ymax = arg maxy∈Y s(x, y). Under the assumption that s(xt , ymax ) is close to 1, we can show the following regret result.

Table 1: Characteristics of the experts in our different settings Varying Expertise ✗

Varying Availability ✗

✗

✓

Theorem 6.5. (Near-Realizable Assumption) Under the same assumptions in Corollary 5.2 and Theorem 6.3, suppose that √ for any t ∈ [T ] we have s(xt , ymax ) ≥ 1 − 1/ T . Running p Algorithm 1 with B √ ηt = and γ = B RN 5/2 (N + 4) gives 1/2 4RN

(N +4)t

us the following regret deferral bound X f ∗ , xt , yt Rℓdef (T ) = ℓdef qt , xt , yt − ℓdef W t∈[T ]

p = O B R3 N 7/2 T The proof works by giving a tighter analysis of the gap between ∆Cℓdef H (q, x) and ∆CΦdef ,H (h, x). The details are deferred to Appendix E.2. Remark 6.6. Further analysis of the minimizability gap is conducted in Appendix E.3.

EXPERIMENTS

Expert systems in deployment rarely operate under fixed conditions. Human and automated experts differ not only in accuracy but also in when they can be consulted, and both factors fluctuate over time due to workload, fatigue, or shifting domains. To examine how an online Learning-to-Defer algorithm adapts under such nonstationarity, we vary two fundamental axes of uncertainty: expertise and availability. This yields three regimes of increasing complexity—ranging from fully static to fully dynamic—allowing us to isolate the effect of each source of variability. 7.1

Overall Setting

Our experiments study the effectiveness of Algorithm 1 under a variety of expert settings described in Table 1, both for synthetic and real-world datasets. Each expert gj has expert cost cj (x, y) = 1{gj (x) ̸= y} + 0.1. Further details of each setting are deferred to Appendix F.1. Notice that the third setting is especially challenging, as a given expert is allowed to drift between 100% accuracy and totally random over time. We show that across all settings, our algorithm correctly adapts to varying expert expertise and availability. It consistently learns the right boundary between

Setting Description The experts have constant expertise and are always available. Expertise is fixed, availability varies. Both expertise and availability vary (fully dynamic setting).

deferring and predicting, and preserves high accuracy with low deferral loss. In the main paper, we focus on the most challenging setting and report results on the Reuters4 dataset (Kakade et al., 2008). Additional experiments on Reuters4, synthetic datasets, and CIFAR10H are deferred to Appendix F. 7.2

Real-world Dataset: Reuters4

For real-world datasets, we make use of the Reuters4 dataset, commonly used for bandit classification experiments (Kakade et al., 2008; Crammer and Gentile, 2013; Beygelzimer et al., 2017). This dataset is generated from the RCV1 dataset (Lewis et al., 2004), extracting 685,071 examples that have exactly one label from the set {CCAT, ECAT, GCAT, MCAT}. It contains 47,236 features and 4 classes, denoted 1,2,3,4. For this experiment, we use the first 100,000 examples. We generate 3 experts with overlapping knowledge regions. At initialization t = 0, expert gj is knowledgeable on labels {j, j + 1}, j = 1, 2, 3. That is, expert gj predicts correctly on inputs from classes {j, j + 1} while predicting uniformly at random on other classes. These regions remain fixed for the first two settings, and evolve in the final setting. We slightly modify the update step of Algorithm 1 by the one from the Adagrad algorithm (Duchi et al., 2011) with base learning rate 0.1 and exploration rate 10 γt = min{ 21 , √ }. t Results under Drifting Availability and Drifting Expertise. Figure 2 summarizes our results. The varying expert expertise is shown in Figure 1. Even under challenging conditions with simultaneously varying availability and expertise, our approach maintains strong performance and adapts effectively to the evolving environment.

Dang, Montreuil, Meyer, Carlier, Ng, and Tsang Expert g1 Expert g2 Expert g3

0.6 0.4 0.2

0.65

0.8

0.60

0.6 0.4

0.55 0.50

Random Our

0.45 0.40

Mean Accuracy

0.8 Mean Accuracy

Mean Accuracy

0.8

1.0

Expert g1 Expert g2 Expert g3

Mean Deferral Loss

1.0

0.35

0.2

0.6

0.4 Expert g1 Expert g2 Expert g3

0.2

0.30

0.0

20000

Class 1

0.4 0.2

0.5

0.6

20000

40000 60000 round t

20000

40000

60000 round t

80000

100000

80000

100000

0.4

Class 3

0.0

1.0 Expert g1 Expert g2 Expert g3

0.4

0.2

0.0

100000

Expert g1 Expert g2 Expert g3

20000

40000 60000 round t

80000

0.3

0.2

100000 0.1

Random Our

0.8 Mean Accuracy

Mean Accuracy

0.8

0.6

0.0

80000

(a) Average true deferral (b) Accuracy of queried exloss. perts.

1.0

Expert g1 Expert g2 Expert g3

0.8

60000 round t

Class 2

Deferral Ratio

1.0

40000

0.6

0.4

0.2

Class 4 0.0

Figure 1: Expert Accuracies by Regions on Reuters4.

20000

40000

60000 round t

80000

100000

0.0

20000

40000

60000 round t

80000

100000

(d) Average accuracy.

Figure 1 illustrates the evolution of expert expertise over time. In particular, expert g1 gradually shifts from classes {1, 2} to classes {3, 4}, expert g2 shifts from classes {2, 3} to classes {1, 4}, and expert g3 shifts from classes {3, 4} to classes {1, 2}. Figure 2 indicates that our method tracks these moving regions, defers with high frequency to the currently competent experts, and preserves stable calibration as expertise evolves. Therefore, overall task accuracy and deferral loss remain strong and comparable to the fixedexpertise baseline (reported in Appendix F.3) throughout the drift. Remaining Reuters4 experiments are deferred to Appendix F.3. We also include experiments on synthetic datasets in Appendix F.2. These experiments are designed to closely mirror the Reuters4 setting, while providing a more controlled environment in which the optimal deferral behavior is explicit. As such, they provide additional evidence for the same conclusions suggested by the Reuters4 results. Finally, Appendix F.4 reports an image classification experiment on CIFAR10H, where the predictor is a WideResNet rather than a linear hypothesis and the experts are constructed from real human annotations. In this setting, we also compare against a confidence-based baseline that defers uniformly at random to an available expert whenever the classifier confidence falls below a fixed threshold. The results again show that our method achieves lower deferral loss and higher accuracy, indicating that the learned policy not only defers under uncertainty, but also makes better use of the available experts.

CONCLUSION

We introduced the first framework for Online Learning-to-Defer (L2D) with bandit feedback and

Mean Expert Availability

1.0 0.8 0.6 0.4 0.2 0.0

Expert g1 Expert g2 Expert g3 20000

40000

60000 round t

80000

100000

(e) Expert availability. Figure 2: Results of experiment on Reuters4 for setting 3: drifting availability and drifting expertise. Whiskers denote standard deviations computed over 5 independent runs.

dynamically varying experts. Our analysis extends classical H-consistency bounds to the online setting and establishes sublinear regret guarantees√of O((n + ne )T 2/3 ) in the general case and O((n + ne ) T ) under a near-realizable condition. These results demonstrate that consistent surrogate-based methods can be made robust to both adversarial environments and varying experts. We validated the practicality of our algorithm across synthetic and real-world datasets, showing that it maintains strong performance even under adversarial expert availability and drifting expertise.

Acknowledgments Yannis Montreuil and Maxime Meyer are supported by the National Research Foundation, Singapore under its AI Singapore Programme (AISG Award No: AISG2PhD-2023-01-041-J and AISG Award No: AISG3PhD-2026-01-068T). Yannis Montreuil is also supported by A*STAR, and is part of the programme DesCartes which is supported by the National Research Foundation, Prime Minister’s Office, Singapore under its Campus for Research Excellence and Technological Enterprise (CREATE) programme.

Online Learning-to-Defer with Varying Experts

References Naman Agarwal, Satyen Kale, and Julian Zimmert. Efficient methods for online multiclass logistic regression. In International Conference on Algorithmic Learning Theory, pages 3–33. PMLR, 2022. Peter Auer, Nicolo Cesa-Bianchi, Yoav Freund, and Robert E Schapire. The nonstochastic multiarmed bandit problem. SIAM journal on computing, 32(1): 48–77, 2002. Pranjal Awasthi, Natalie Frank, Anqi Mao, Mehryar Mohri, and Yutao Zhong. Calibration and consistency of adversarial surrogate losses, 2021. URL https://arxiv.org/abs/2104.09658. Pranjal Awasthi, Anqi Mao, Mehryar Mohri, and Yutao Zhong. Multi-class h-consistency bounds. In Proceedings of the 36th International Conference on Neural Information Processing Systems, NIPS ’22, Red Hook, NY, USA, 2022a. Curran Associates Inc. ISBN 9781713871088. Pranjal Awasthi, Anqi Mao, Mehryar Mohri, and Yutao Zhong. Multi-class h-consistency bounds. Advances in neural information processing systems, 35: 782–795, 2022b. Peter Bartlett, Michael Jordan, and Jon McAuliffe. Convexity, classification, and risk bounds. Journal of the American Statistical Association, 101:138– 156, 02 2006. doi: 10.1198/016214505000000907. Peter L. Bartlett and Marten H. Wegkamp. Classification with a reject option using a hinge loss. The Journal of Machine Learning Research, 9: 1823–1840, June 2008. Nina L Corvelo Benz and Manuel Gomez Rodriguez. Counterfactual inference of second opinions. In Uncertainty in Artificial Intelligence, pages 453–463. PMLR, 2022. Alina Beygelzimer, Francesco Orabona, and Chicheng Zhang. Efficient √ online bandit multiclass learnIn Doina Precup ing with Õ( T ) regret. and Yee Whye Teh, editors, Proceedings of the 34th International Conference on Machine Learning, volume 70 of Proceedings of Machine Learning Research, pages 488–497. PMLR, 06–11 Aug 2017. URL https://proceedings.mlr.press/ v70/beygelzimer17a.html. Yuzhou Cao, Hussein Mozannar, Lei Feng, Hongxin Wei, and Bo An. In defense of softmax parametrization for calibrated and consistent learning to defer. In Proceedings of the 37th International Conference on Neural Information Processing Systems, NIPS ’23, Red Hook, NY, USA, 2024. Curran Associates Inc.

Mohammad-Amin Charusaie, Hussein Mozannar, David Sontag, and Samira Samadi. Sample efficient learning of predictors that complement humans. In International Conference on Machine Learning, pages 2972–3005. PMLR, 2022. C. Chow. On optimum recognition error and reject tradeoff. IEEE Transactions on Information Theory, 16(1):41–46, January 1970. doi: 10.1109/TIT. 1970.1054406. Corinna Cortes, Giulia DeSalvo, and Mehryar Mohri. Learning with rejection. In Ronald Ortner, Hans Ulrich Simon, and Sandra Zilles, editors, Algorithmic Learning Theory, pages 67–82, Cham, 2016. Springer International Publishing. ISBN 978-3-31946379-7. Koby Crammer and Claudio Gentile. Multiclass classification with bandit feedback using adaptive regularization. Machine learning, 90(3):347–383, 2013. Amit Daniely and Tom Helbertal. The price of bandit information in multiclass online classification. In Conference on Learning Theory, pages 93–104. PMLR, 2013. John Duchi, Elad Hazan, and Yoram Singer. Adaptive subgradient methods for online learning and stochastic optimization. Journal of machine learning research, 12(7), 2011. Dylan J Foster, Satyen Kale, Haipeng Luo, Mehryar Mohri, and Karthik Sridharan. Logistic regression: The importance of being improper. In Conference on learning theory, pages 167–208. PMLR, 2018. Yonatan Geifman and Ran El-Yaniv. Selective classification for deep neural networks. In I. Guyon, U. Von Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 30. Curran Associates, Inc., 2017. URL https://proceedings. neurips.cc/paper_files/paper/2017/file/ 4a8423d5e91fda00bb7e46540e2b0cf1-Paper.pdf. Elad Hazan. 2016. doi: 10.1561/2400000013. Elad Hazan and Satyen Kale. Newtron: an efficient bandit algorithm for online multiclass prediction. Advances in neural information processing systems, 24, 2011. Patrick Hemmer, Sebastian Schellhammer, Michael Vössing, Johannes Jakubik, and Gerhard Satzger. Forming effective human-AI teams: Building machine learning models that complement the capabilities of multiple experts. In Lud De Raedt, editor, Proceedings of the Thirty-First International Joint Conference on Artificial Intelligence, IJCAI22, pages 2478–2484. International Joint Conferences on Artificial Intelligence Organization, 7 2022.

Dang, Montreuil, Meyer, Carlier, Ng, and Tsang

doi: 10.24963/ijcai.2022/344. URL https://doi. org/10.24963/ijcai.2022/344. Main Track.

3461702.3462516. URL https://doi.org/10. 1145/3461702.3462516.

Dan Hendrycks and Thomas Dietterich. Benchmarking neural network robustness to common corruptions and perturbations. arXiv preprint arXiv:1903.12261, 2019.

Alex Krizhevsky. Learning multiple layers of features from tiny images. 2009. URL https://api. semanticscholar.org/CorpusID:18268744.

Rémi Jézéquel, Pierre Gaillard, and Alessandro Rudi. Efficient improper learning for online logistic regression. In Conference on Learning Theory, pages 2085–2108. PMLR, 2020.

Yoonkyung Lee, Yi Lin, and Grace Wahba. Multicategory support vector machines: Theory and application to the classification of microarray data and satellite radiance data. Journal of the American Statistical Association, 99(465):67–81, 2004.

Rémi Jézéquel, Pierre Gaillard, and Alessandro Rudi. Mixability made efficient: Fast online multiclass logistic regression. Advances in Neural Information Processing Systems, 34:23692–23702, 2021.

David D Lewis, Yiming Yang, Tony G Rose, and Fan Li. Rcv1: A new benchmark collection for text categorization research. Journal of machine learning research, 5(Apr):361–397, 2004.

Alistair Johnson, Tom Pollard, Lu Shen, Li-wei Lehman, Mengling Feng, Mohammad Ghassemi, Benjamin Moody, Peter Szolovits, Leo Celi, and Roger Mark. Mimic-iii, a freely accessible critical care database. Scientific Data, 3:160035, 05 2016. doi: 10.1038/sdata.2016.35. Alistair Johnson, Lucas Bulgarelli, Lu Shen, Alvin Gayles, Ayad Shammout, Steven Horng, Tom Pollard, Benjamin Moody, Brian Gow, Li-wei Lehman, Leo Celi, and Roger Mark. Mimic-iv, a freely accessible electronic health record dataset. Scientific Data, 10:31, 01 2023. doi: 10.1038/ s41597-023-01945-2. Sham M Kakade, Shai Shalev-Shwartz, and Ambuj Tewari. Efficient bandit algorithms for online multiclass prediction. In Proceedings of the 25th international conference on Machine learning, pages 440– 447, 2008. Varun Kanade and Thomas Steinke. Learning hurdles for sleeping experts. ACM Transactions on Computation Theory (TOCT), 6(3):1–16, 2014. Gavin Kerrigan, Padhraic Smyth, and Mark Steyvers. Combining human predictions with model probabilities via confusion matrices and calibration. In M. Ranzato, A. Beygelzimer, Y. Dauphin, P.S. Liang, and J. Wortman Vaughan, editors, Advances in Neural Information Processing Systems, volume 34, pages 4421–4434. Curran Associates, Inc., 2021. URL https://proceedings. neurips.cc/paper_files/paper/2021/file/ 234b941e88b755b7a72a1c1dd5022f30-Paper.pdf. Vijay Keswani, Matthew Lease, and Krishnaram Kenthapadi. Towards unbiased and accurate deferral to multiple experts. In Proceedings of the 2021 AAAI/ACM Conference on AI, Ethics, and Society, AIES ’21, page 154–165, New York, NY, USA, 2021. Association for Computing Machinery. ISBN 9781450384735. doi: 10.1145/

Lihong Li, Wei Chu, John Langford, and Robert E Schapire. A contextual-bandit approach to personalized news article recommendation. In Proceedings of the 19th international conference on World wide web, pages 661–670, 2010. Shuqi Liu, Yuzhou Cao, Qiaozhen Zhang, Lei Feng, and Bo An. Mitigating underfitting in learning to defer with consistent losses. In International Conference on Artificial Intelligence and Statistics, pages 4816–4824. PMLR, 2024. David Madras, Toni Pitassi, and Richard Zemel. Predict responsibly: improving fairness and accuracy by learning to defer. Advances in neural information processing systems, 31, 2018. Anqi Mao, Christopher Mohri, Mehryar Mohri, and Yutao Zhong. Two-stage learning to defer with multiple experts. In Thirty-seventh Conference on Neural Information Processing Systems, 2023a. URL https://openreview.net/forum?id=GIlsH0T4b2. Anqi Mao, Mehryar Mohri, and Yutao Zhong. Crossentropy loss functions: Theoretical analysis and applications. In International conference on Machine learning, pages 23803–23828. PMLR, 2023b. Anqi Mao, Mehryar Mohri, and Yutao Zhong. Crossentropy loss functions: Theoretical analysis and applications. In International conference on Machine learning, pages 23803–23828. PMLR, 2023c. Anqi Mao, Mehryar Mohri, and Yutao Zhong. Principled approaches for learning to defer with multiple experts. In ISAIM, 2024a. Anqi Mao, Mehryar Mohri, and Yutao Zhong. Realizable h-consistent and bayes-consistent loss functions for learning to defer. Advances in neural information processing systems, 37:73638–73671, 2024b. Anqi Mao, Mehryar Mohri, and Yutao Zhong. Regression with multi-expert deferral. In Proceedings of the 41st International Conference on Machine Learning, ICML’24. JMLR.org, 2024c.

Online Learning-to-Defer with Varying Experts

Anqi Mao, Mehryar Mohri, and Yutao Zhong. Mastering multiple-expert routing: Realizable $h$consistency and strong guarantees for learning to defer. In Forty-second International Conference on Machine Learning, 2025. Mehryar Mohri, Afshin Rostamizadeh, and Ameet Talwalkar. Foundations of machine learning. MIT Press, 2012. Yannis Montreuil, Axel Carlier, Lai Xing Ng, and Wei Tsang Ooi. Adversarial robustness in two-stage learning-to-defer: Algorithms and guarantees. In Forty-second International Conference on Machine Learning, 2025a. Yannis Montreuil, Yeo Shu Heng, Axel Carlier, Lai Xing Ng, and Wei Tsang Ooi. A two-stage learning-to-defer approach for multi-task learning. In Forty-second International Conference on Machine Learning, 2025b. Yannis Montreuil, Axel Carlier, Lai Xing Ng, and Wei Tsang Ooi. Why ask one when you can ask $k$? learning-to-defer to the top-$k$ experts. In The Fourteenth International Conference on Learning Representations, 2026a. URL https: //openreview.net/forum?id=mGbEv4kVoG. Yannis Montreuil, Yeo Shu Heng, Axel Carlier, Lai Xing Ng, and Wei Tsang Ooi. Optimal query allocation in extractive QA with LLMs: A learningto-defer framework with theoretical guarantees. In The 29th International Conference on Artificial Intelligence and Statistics, 2026b. URL https:// openreview.net/forum?id=kEVupwepTq. Yannis Montreuil, Yu Letian, Axel Carlier, Lai Xing Ng, and Wei Tsang Ooi. Adversarial robustness in one-stage learning-to-defer. In The 29th International Conference on Artificial Intelligence and Statistics, 2026c. URL https://openreview.net/ forum?id=gF8tv1SaR2. Hussein Mozannar and David Sontag. Consistent estimators for learning to defer to an expert. In Proceedings of the 37th International Conference on Machine Learning, ICML’20. JMLR.org, 2020. Hussein Mozannar, Hunter Lang, Dennis Wei, Prasanna Sattigeri, Subhro Das, and David A. Sontag. Who should predict? exact algorithms for learning to defer to humans. In International Conference on Artificial Intelligence and Statistics, 2023. URL https://api.semanticscholar.org/ CorpusID:255941521. Harikrishna Narasimhan, Wittawat Jitkrittum, Aditya K Menon, Ankit Rawat, and Sanjiv Kumar. Post-hoc estimators for learning to defer to an expert. In S. Koyejo, S. Mohamed, A. Agarwal,

D. Belgrave, K. Cho, and A. Oh, editors, Advances in Neural Information Processing Systems, volume 35, pages 29292–29304. Curran Associates, Inc., 2022. URL https://proceedings. neurips.cc/paper_files/paper/2022/file/ bc8f76d9caadd48f77025b1c889d2e2d-Paper-Conference. pdf. Francesco Orabona. A modern introduction to online learning. arXiv preprint arXiv:1912.13213, 2019. Filippo Palomba, Andrea Pugnana, Jose Manuel Alvarez, and Salvatore Ruggieri. A causal framework for evaluating deferring systems. In The 28th International Conference on Artificial Intelligence and Statistics, 2025. URL https://openreview.net/ forum?id=mkkFubLdNW. Joshua C Peterson, Ruairidh M Battleday, Thomas L Griffiths, and Olga Russakovsky. Human uncertainty makes classification more robust. In Proceedings of the IEEE/CVF international conference on computer vision, pages 9617–9626, 2019. Ingo Steinwart. How to compare different loss functions and their risks. Constructive Approximation, 26:225–287, 2007. URL https://api. semanticscholar.org/CorpusID:16660598. Joshua Strong, Qianhui Men, and Alison Noble. Towards human-AI collaboration in healthcare: Guided deferral systems with large language models. In ICML 2024 Workshop on LLMs and Cognition, 2024. URL https://openreview.net/forum?id= 4c5rg9y4me. Dharmesh Tailor, Aditya Patra, Rajeev Verma, Putra Manggala, and Eric Nalisnick. Learning to defer to a population: A meta-learning approach. In Sanjoy Dasgupta, Stephan Mandt, and Yingzhen Li, editors, Proceedings of The 27th International Conference on Artificial Intelligence and Statistics, volume 238 of Proceedings of Machine Learning Research, pages 3475–3483. PMLR, 02–04 May 2024. URL https://proceedings.mlr.press/ v238/tailor24a.html. Dirk van der Hoeven. Exploiting the surrogate gap in online multiclass classification. Advances in Neural Information Processing Systems, 33:9562–9572, 2020. Dirk van der Hoeven, Federico Fusco, and Nicolò CesaBianchi. Beyond bandit feedback in online multiclass classification. Advances in neural information processing systems, 34:13280–13291, 2021. Rajeev Verma, Daniel Barrejon, and Eric Nalisnick. Learning to defer to multiple experts: Consistent surrogate losses, confidence calibration, and conformal ensembles. In International Conference on Artificial Intelligence and Statistics,

Dang, Montreuil, Meyer, Carlier, Ng, and Tsang

2022. URL https://api.semanticscholar.org/ CorpusID:253237048.

3. For all figures and tables that present empirical results, check if you include:

Tong Zhang. Statistical behavior and consistency of classification methods based on convex risk minimization. Annals of Statistics, 32, 12 2002. doi: 10.1214/aos/1079120130.

(a) The code, data, and instructions needed to reproduce the main experimental results (either in the supplemental material or as a URL). [Yes] (b) All the training details (e.g., data splits, hyperparameters, how they were chosen). [Yes] (c) A clear definition of the specific measure or statistics and error bars (e.g., with respect to the random seed after running experiments multiple times). [Yes] (d) A description of the computing infrastructure used. (e.g., type of GPUs, internal cluster, or cloud provider). [Yes]

Martin Zinkevich. Online convex programming and generalized infinitesimal gradient ascent. In Proceedings of the 20th international conference on machine learning (icml-03), pages 928–936, 2003.

Checklist The checklist follows the references. For each question, choose your answer from the three possible options: Yes, No, Not Applicable. You are encouraged to include a justification to your answer, either by referencing the appropriate section of your paper or providing a brief inline description (1-2 sentences). Please do not modify the questions. Note that the Checklist section does not count towards the page limit. Not including the checklist in the first submission won’t result in desk rejection, although in such case we will ask you to upload it during the author response period and include it in camera ready (if accepted). In your paper, please delete this instructions block and only keep the Checklist section heading above along with the questions/answers below. 1. For all models and algorithms presented, check if you include: (a) A clear description of the mathematical setting, assumptions, algorithm, and/or model. [Yes] The mathematical setting and assumptions are described in Sections 3 and 4. Our main algorithm is clearly described in Algorithm 1. (b) An analysis of the properties and complexity (time, space, sample size) of any algorithm. [Yes] It is provided in Appendix. (c) (Optional) Anonymized source code, with specification of all dependencies, including external libraries. [Yes] 2. For any theoretical claim, check if you include: (a) Statements of the full set of assumptions of all theoretical results. [Yes] (b) Complete proofs of all theoretical results. [Yes (c) Clear explanations of any assumptions. [Yes]

4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets, check if you include: (a) Citations of the creator If your work uses existing assets. [Yes] (b) The license information of the assets, if applicable. [Not Applicable] (c) New assets either in the supplemental material or as a URL, if applicable. [Not Applicable] (d) Information about consent from data providers/curators. [Not Applicable] (e) Discussion of sensible content if applicable, e.g., personally identifiable information or offensive content. [Not Applicable] 5. If you used crowdsourcing or conducted research with human subjects, check if you include: (a) The full text of instructions given to participants and screenshots. [Not Applicable] (b) Descriptions of potential participant risks, with links to Institutional Review Board (IRB) approvals if applicable. [Not Applicable] (c) The estimated hourly wage paid to participants and the total amount spent on participant compensation. [Not Applicable]

Discussion of benchmarks

The objective in online learning is to minimize regret, the most general formulation of which is R(T ) = Rℓdef (q, x) − Rℓdef (h∗ , x). Where q = (q1 , q2 , . . . , qT ) is the learner’s prediction distribution at round t (defined in Section 4.1 and h∗ = (h∗1 , h∗2 , . . . , h∗T ) ∈ HT is the best sequence of hypotheses. How h∗ is defined directly implies the difficulty of our problem. We present and discuss some natural definitions below No Restrictions. Note that if no restriction is placed on h∗t , then the regret is always R(T ) = Ω(T ) for any online algorithm. To see this, consider the setting where in each round t ∈ [T ], the adversary chooses yt uniformly at random. The optimal sequence of hypotheses is h∗t such that h∗t (xt ) = yt . Assuming all experts are wrong, the learner incurs an expected regret of at least (n − 1)/n each round while the comparator h∗t incurs zero loss. Policy Regret. We consider a more restrictive notion, called policy regret (adapted from Kanade and Steinke (2014), van der Hoeven et al. (2021)). We no longer allow h∗t to adapt to input-label (xt , yt ) in each round, but ), where hA ∈ H is the best-in-class hypothesis only to the expert set At ∈ A. In other words, h∗t (xt ) = hAt (xtP over all rounds with expert set A. That is hA = arg minh∈H t∈[T ],xt =(xt ,A) ℓdef (h, xt , yt ). Intuitively, h∗ is determined by the best policy mapping from the set of expert sets A to the set of best-in-class hypotheses. Note that we assume x can be chosen adversarially. Under such assumptions, we show that the regret bound for policy regret grows exponentially w.r.t the number of experts ne . To see this, we first provide a lower bound for the standard online bandit classification problem, where input-label pairs are chosen adversarially. Theorem A.1. (Daniely and Helbertal (2013), Theorem 4) Consider the standard online bandit classification problem with n ≥ 2 classes and adversarial assumptions. For any (possibly randomized) online algorithm and any√ integer T ≥ 1, there exists an environment E in which the algorithm must incur a true regret of at least Ω( nT ). Note that while input-label pairs in our setting are chosen semi-adversarially, we make no assumptions about experts’ performance. By applying Theorem A.1, we can show a lower bound on our problem when the number of experts is fixed, i.e. At = {g1 , g2 , . . . , gne }, ∀t ∈ [T ]. Corollary A.2. Consider the online learning-to-defer problem with bandit feedback a fixed number of experts ne ≥ 2. For any (possibly randomized) online algorithm and any integer √ T ≥ 1, there exists an environment E in which the algorithm must incur an expected true regret of at least Ω( ne T ). Proof. Consider a uniform label distribution p ∈ D, that is, p(x, y) = n1 ∀ x ∈ X , y ∈ Y. Any algorithm that picks a true label incurs an expected cost of n−1 E (for the n . By Theorem A.1, there exists an environment √ bandit classification problem) in which the algorithm must incur a true regret of at least Ω( ne T ). In other words, there exist a sequence (xt , yt )t∈[T ] and a fixed comparator h∗ ∈ H such that X p (1{yt′ ̸= yt } − 1{h∗ (xt ) ̸= yt }) = Ω( ne T ), t∈[T ]

where yt′ is the algorithm’s (possibly randomized) predictions. Now we consider an environment E ′ (for the bandit learning-to-defer problem), with label distribution p defined above and experts performance defined as follows: In round t ∈ [T ], expert cost of gyt is 0, while the other experts suffer cost n−1 n . Define the new ∗ ∗ ∗ comparator h such that h (xt ) = h (xt ) + n. Then over all rounds t ∈ [T ], the algorithm suffers a cumulative cost of at least X X p n−1 min{ , Ey∼pt [cyt′ (xt , y)]} ≤ Ey∼pt [cyt′ (xt , y)] ≤ Ey∼pt [ch∗ (xt ) (xt , y)] + Ω( ne T ), n t∈[T ]

t∈[T ]

which ends our proof. Now we are ready to show the following lower bound in the general varying number of expert case, which has an exponential dependence on ne

Dang, Montreuil, Meyer, Carlier, Ng, and Tsang

Theorem A.3. Consider the online learning-to-defer problem with bandit feedback and varying experts. Suppose the number of unique experts after T rounds is ne ≥ 2 and let A′ = {A ∈ A : |A| ≥ 2}. For any (possibly randomized) online algorithm, p there exists an environment E in which the algorithm must incur an expected policy regret of at least Ω( T min{T, |A′ |}). Proof. In the case of |A| = min{T, |A|}, we divide T into |A| segments T1 , T2 , . . . , T|A| (WLOG assume |A| divides T ). Each segment Ti is of length m = T /|A| and corresponds to a unique expert set Ai where {i(g) : g ∈ Ai } ∈ 2{n+1,...,n+ne } and |Ai | ≥ 2. For each segment Ti , based on Corollary A.2, there exists an environment Ei and a comparator h∗i such that X

p (ℓdef (qt , xt , yt ) − ℓdef (h∗i , xt , yt )) = Ω( |Ti |).

t∈Ti

Choosing h(x, Ai ) = h∗i and consider the environment E as the combination of Ei , we have R(T ) ≥

(ℓdef (qt , xt , yt ) − ℓdef (h∗i , xt , yt )) =

i∈A t∈Ti

p p Ω( |Ti |) = Ω( T |A|).

i∈A

In the case T = min{T, |A|}, the adversary can choose a different expert set At for each round. In round t, based on Corollary A.2, there exists an environment Et and a comparator h∗t such that the expected regret is at least some constant c > 0. Choosing h∗ = h∗t and consider the environment E as the combination of Et , the expected regret is at least cT ∈ Ω(T ), which ends our proof. As a result, to further relax this notion, we consider the overall best-in-class hypothesis as presented in our paper.

Discussion of bound B on the hypothesis set

In this section, we present a suitable choice for bound B. We make use of the characteristic of the minimizability gap for the constrained hinge loss. From Theorem E.5, we have shown that the minimal conditional surrogate Φdef -risk can be obtained by a hypothesis of the form ( h(x, y) =

|Y A | − 1 −1

if y = ymax , otherwise.

(2)

Therefore, it suffices to show that there exists a bound B on the hypothesis set H such that for any x, y, such hypothesis h defined in (2) belongs in H. Given any input x = (x, A) ∈ X . Let W |Y A be weight matrix f = (W, b) ∈ H such that W |Y A = yx⊺ , b = 0. This gives us W restricted to Y A . Then we can choose W ||x||2 ||y||2 W |Y A x + b = y and (W |Y A , b|Y A ) ∈ KA . Furthermore, ||W |Y A ||F = ||x|| ≤ |YA | ≤ N . From this, a suitable 2 bound B is B = N .

f ∈ H, it is clear that ||W f |K ||F ≤ ||W f ||F ≤ B, so W f |K ∈ H. Projection onto KA preserves bound. Given W A A

Proof of H-consistency bound for online learning

For any x = (x, A) ∈ X , we denote by H(x) the set of labels generated by hypotheses in H: H(x) = {h(x) : h ∈ H} ∩ Y A . With this, we can write the conditional risk and calibration gap of the deferral loss as follows. C.1

Calibration gap for true deferral loss

Lemma C.1. For any x ∈ X , the minimal conditional ℓdef -risk and the calibration gap for ℓdef can be expressed as follows: Cℓ∗def ,H (x) = 1 − max s(x, y), y∈H(x)

Online Learning-to-Defer with Varying Experts

∆Cℓdef ,H (h, x) = max s(x, y) − s(x, h(x)). y∈H(x)

Proof. The conditional ℓdef -risk of h can be expressed as follows: Cℓdef (h, x) = Ey∼p(x) ℓdef (h, x, y)  X = Ey∼p(x)1{h(x) ̸= y}1{h(x) ∈ [n]} +

 cj (x, y)1{h(x) = n + j}

n+j∈Y A

s(x, y)⊮{h(x) ̸= y}1{h(x) ∈ [n]} +

y∈Y

1 − s(x, n + j) 1{h(x) = n + j}

n+j∈Y A

= 1 − s(x, h(x)) 1{h(x) ∈ [n]} +

1 − s(x, h(x)) 1{h(x) = n + j}

n+j∈Y A

= 1 − s(x, h(x)). Then, the minimal conditional ℓdef -risk is given by Cℓ∗def (H, x) = 1 − max s(x, y), y∈H(x)

and the calibration gap can be expressed as follows: ∆Cℓdef ,H (h, x) = Cℓdef (h, x) − Cℓ∗def (H, x) = max s(x, y) − s(x, h(x)), y∈H(x)

which completes the proof. C.2

Calibration gap for surrogate deferral risk

Lemma C.2. For any x ∈ X , the conditional surrogate Φdef -risk and calibration gap can be expressed as follows: X CΦdef (h, x) = s(x, y)ℓ(h, x, y), y∈Y A

∆CΦdef (h, x) =

s(x, y)Φ01 (h, x, y) − inf

h∈H

y∈Y A

s(x, y)Φ01 (h, x, y).

y∈Y A

Proof. By definition, the conditional Φdef -risk CΦdef (h, x) can be expressed as follows:

CΦdef (h, x) = Ey∼p(x) [Φdef (h, x, y)] X

= Ey∼p(x) [ℓ(h, x, y)] +

Ey∼p(x) (1 − cj (x, y)) Φ01 (h, x, n + j)

n+j∈Y A

s(x, y)Φ01 (h, x, y) +

y∈Y

X y∈Y A

which ends the proof.

X n+j∈Y A

s(x, y)l(h, x, y),

s(x, n + j)Φ01 (h, x, n + j)

Dang, Montreuil, Meyer, Carlier, Ng, and Tsang

We also make use of the following result for the zero-one loss ℓ01 (h, x, y) = 1{h(x) ̸= y} with label space Y A and the conditional probability vector s(x, ·), which characterizes the minimal conditional ℓ01 -risk and the corresponding calibration gap. C.3

Calibration gap for zero-one loss

Lemma C.3. (Awasthi et al. (2022b) Lemma 3) For any x ∈ X , the minimal conditional ℓ01 -risk and the calibration gap for ℓ01 can be expressed as follows: Cℓ∗01 (x) = 1 − max s(x, y), y∈H(x)

∆Cℓ01 (h, x) = max s(x, y) − s(x, h(x)). y∈H(x)

Now we show that the surrogate upper bound on the calibration gap of the zero-one loss ℓ01 implies a surrogate upper bound on the calibration gap of the deferral loss ℓdef . Lemma C.4. Given Φ01 is a surrogate loss for the multi-class zero-one classification loss ℓ01 defined in Definition 4.2, Φdef is the corresponding surrogate deferral loss. Assume that there exists a concave function Γ : R+ → R and ϵ ≥ 0 such that the following holds for all h ∈ H, x ∈ X and p ∈ P : [∆Cℓ01 ,H (h, x)]ϵ ≤ Γ(∆Cℓ,H (h, x)). T

Then for any x = (x1 , x2 , . . . , xT ) ∈ X , any h = (h1 , h2 , . . . , hT ) ∈ HT used by the randomized learner in Section 4.1, and any distribution p ∈ P, [∆Cℓdef ,H (q, x)]ϵ ≤ S(x)Γ

1 ∆CΦdef ,H (h, x) + cγ. S(x)

Proof. The calibration gap can be written as follows

[∆Cℓdef ,H (q, x)]ϵ = (1 − γ)[∆Cℓdef ,H (h, x)]ϵ +

γ X [∆Cℓdef ,H (y, x)]ϵ |Y A | y∈Y A

≤ [∆Cℓdef ,H (h, x)]ϵ + cγ = [ max s(x, y) − s(x, h(x))]ϵ + cγ

(Lemma C.1)

y∈H(x)

= S(x)[ max s(x, y) − s(x, h(x))]ϵ + cγ y∈H(x)

= S(x)[∆Cℓ01 ,H (h, x)]ϵ + cγ

(Lemma C.3)

≤ S(x)Γ(∆CΦ01 ,H (h, x)) + cγ   X X = S(x)Γ  s(x, y)Φ01 (h, x, y) − inf s(x, y)Φ01 (h, x, y) + cγ h∈H

y∈Y A



= S(x)Γ 

1  S(x)

 X

s(x, y)Φ01 (h, x, y) − inf

y∈Y A

= S(x)Γ

which completes the proof.

1 ∆CΦdef ,H (h, x) + cγ S(x)

h∈H y∈Y A

(Lemma C.2),

s(x, y)Φ01 (h, x, y) + cγ

Online Learning-to-Defer with Varying Experts

C.4

Proof of H-consistency bounds for surrogate deferral losses (Theorem 5.1)

e 01 admits an H-consistency bound w.r.t ℓ01 Theorem 5.1. (Distribution-Dependent Γ-Bound) Assume that Φ T with a concave, non-decreasing calibration function Γ : R+ → R with Γ(0) = 0. Then for any x ∈ X and any distribution p ∈ D, suppose the online learner generates corresponding hypotheses h and samples from q defined in Section 4.1, we have, P Rℓdef (T ) + Mℓdef ,H (x) − c γ t t∈[T ] −ϵ T RΦdef (T ) + MΦdef H (x) . ≤ max S(xt ) Γ T mint∈[T ] S(xt ) t∈[T ] P P P Here, S(xt ) = y∈Y p(xt , y) + n+j∈Y A 1 − y∈Y p(xt , y)cj (xt , y) and c is the upper bound on the expert t

cost c = maxj {cj }. Proof. By definition, the LHS term can be written as follows: 1 Rℓdef (s, x) − R∗ℓdef ,H (x) + Mℓdef ,H (x) T   1 X ∆Cℓdef ,H (st , xt ) T t∈[T ]   1 X ≤ [∆Cℓdef ,H (st , xt )]ϵ  + ϵ T t∈[T ] P c( t∈[T ] γT ) 1 X 1 ≤ S(xt )Γ ∆CΦdef ,H (ht , xt ) + + ϵ (Lemma C.4) T S(xt ) T t∈[T ] P c( t∈[T ] γT ) 1 X 1 ≤ max{S(xt )} Γ ∆CΦdef ,H (ht , xt ) + +ϵ T S(xt ) T t∈[T ] t∈[T ]   P X c( t∈[T ] γT ) 1   ∆CΦdef ,H (ht , xt ) + +ϵ ≤ max{S(xt )}Γ T S(xt ) T t∈[T ] t∈[T ] P c( t∈[T ] γT ) 1 ∗ = max{S(xt )}Γ RΦdef (h, x) − RΦdef ,H (x) + MΦdef ,H (x) + + ϵ. T mint∈[T ] {S(xt )} T t∈[T ] =

when Γ is linear we have 1 Rℓdef (q, x) − R∗ℓdef ,H (x) + Mℓdef ,H (x) T c P γ t∈[T ] t 1 ≤Γ RΦdef (h, x) − R∗Φdef ,H (x) + MΦdef ,H (x) + + ϵ, T T which completes the proof.

Examples of H-consistency bound for common surrogate losses

D.1

Φ01 being adopted as comp-sum losses P ′ Example: Φ01 = Φexp . Plug in Φ01 = Φexp = y′ ̸=y eh(x,y )−h(x,y) in Definition 4.3, we obtain X X X h(x,y′ )−h(x,n+j) ′ Φdef = eh(x,y )−h(x,y) + 1 − cj (x, y) e . y ′ ̸=y

n+j∈Y A

y ′ ̸=n+j

Dang, Montreuil, Meyer, Carlier, Ng, and Tsang

By Mao et al. (2023b), Theorem 1, Φexp admits an H-consistency bound with respect to ℓ01 with Γ(t) = using Corollary 5.2, we obtain P 1/2 √ Rℓdef (q, x) − R∗ℓdef ,H (x) c( t∈[T ] γt ) RΦdef (h, x) − R∗Φdef ,H (x) − − ϵ ≤ 2 max S(xt ) . T T T mint∈[T ] S(xt ) t∈[T ] Example: Φ01 = Φlog . Plug in Φ01 = Φlog = − log P

eh(x,y) eh(x,y′ ) y ′ ∈Y

√

2t;

in Definition 4.3, we obtain

eh(x,y) Φdef = − log P − ′) h(x,y y ′ ∈Y A e

X n+j∈Y A

eh(x,n+j) . 1 − cj (x, y) log P ′) h(x,y y ′ ∈Y A e

By Mao et al. (2023b), Theorem 1, Φlog admits an H-consistency bound with respect to ℓ01 with Γ(t) = using Corollary 5.2, we obtain P 1/2 √ Rℓdef (q, x) − R∗ℓdef ,H (x) c( t∈[T ] γt ) RΦdef (h, x) − R∗Φdef ,H (x) − − ϵ ≤ 2 max S(xt ) . T T T mint∈[T ] S(xt ) t∈[T ] Example: Φ01 = Φgce . Plug in Φ01 = Φgce = α1 1 − ( P

eh(x,y) )α eh(x,y′ ) y ′ ∈Y

√

2t;

in Definition 4.3, we obtain

Φdef =

α i 1 1h eh(x,y) 1− P + ′) h(x,y α α y ′ ∈Y A e

X n+j∈Y A

h α i eh(x,n+j) (1 − cj (x, y)) 1 − P . ′) h(x,y y ′ ∈Y A e

By Mao et al. (2023b), Theorem 1, Φgce admits an H-consistency bound with respect to ℓ01 with Γ(t) = using Corollary 5.2, we obtain P 1/2 √ Rℓdef (q, x) − R∗ℓdef ,H (x) c( t∈[T ] γt ) RΦdef (h, x) − R∗Φdef ,H (x) − − ϵ ≤ 2nα max S(xt ) . T T T mint∈[T ] S(xt ) t∈[T ] Example: Φ01 = Φmae . Plug in Φ01 = Φmae = 1 − P

eh(x,y)

y ′ ∈Y A e

eh(x,y) Φdef = 1 − P + h(x,y ′ ) y ′ ∈Y A e

X n+j∈Y A

h(x,y ′ )

√

2nα t;

in Definition 4.3, we obtain

eh(x,n+j) (1 − cj (x, y)) 1 − P h(x,y ′ ) y ′ ∈Y A e

! .

By Mao et al. (2023b), Theorem 1, Φmae admits an H-consistency bound with respect to ℓ01 with Γ(t) = nt; using Corollary 5.2, we obtain P Rℓdef (q, x) − R∗ℓdef ,H (x) c( t∈[T ] γt ) RΦdef (h, x) − R∗Φdef ,H (x) − −ϵ≤n . T T T D.2

Φ01 being adopted as sum losses

P sum ′ Example: Φ01 = Φsum sq . Plug in Φ01 = Φsq = y ′ ̸=y Φsq h(x, y) − h(x, y ) in Definition 4.3, we obtain X X X Φdef = Φsq h(x, y) − h(x, y ′ ) + (1 − cj (x, y)) Φsq h(x, n + j) − h(x, y ′ ) , y ′ ̸=y

n+j∈Y A

y ′ ̸=n+j

where Φsq (t) = max{0, 1 − t}2 . By Awasthi et al. (2022b), Table 2, Φsum admits an H-consistency bound with respect to ℓ01 with Γ(t) = sq using Corollary 5.2, we obtain P 1/2 Rℓdef (q, x) − R∗ℓdef ,H (x) c( t∈[T ] γt ) RΦdef (h, x) − R∗Φdef ,H (x) − − ϵ ≤ max S(xt ) . T T T mint∈[T ] S(xt ) t∈[T ]

√

Online Learning-to-Defer with Varying Experts sum Example: Φ01 = Φsum exp . Plug in Φ01 = Φexp =

Φdef =

′ y ′ ̸=y Φexp h(x, y) − h(x, y )

Φexp h(x, y) − h(x, y ′ ) +

y ′ ̸=y

(1 − cj (x, y))

in Definition 4.3, we obtain

Φexp h(x, n + j) − h(x, y ′ ) ,

y ′ ̸=n+j

n+j∈Y A

where Φexp (t) = e−t . By Awasthi et al. (2022b), Table 2, Φsum exp admits an H-consistency bound with respect to ℓ01 with Γ(t) = using Corollary 5.2, we obtain P 1/2 √ Rℓdef (q, x) − R∗ℓdef ,H (x) c( t∈[T ] γt ) RΦdef (h, x) − R∗Φdef ,H (x) − − ϵ ≤ 2 max S(xt ) . T T T mint∈[T ] S(xt ) t∈[T ] Example: Φ01 = Φsum . Plug in Φ01 = Φsum = ρ ρ Φdef =

Φρ h(x, y) − h(x, y ′ ) +

y ′ ̸=y

′ y ′ ̸=y Φρ h(x, y) − h(x, y )

(1 − cj (x, y))

√

2t;

in Definition 4.3, we obtain

Φρ h(x, n + j) − h(x, y ′ ) ,

y ′ ̸=n+j

n+j∈Y A

where Φρ (t) = min{max{0, 1 − t/ρ}, 1}. By Awasthi et al. (2022b), Table 2, Φsum admits an H-consistency bound with respect to ℓ01 with Γ(t) = t; using ρ Corollary 5.2, we obtain P Rℓdef (q, x) − R∗ℓdef ,H (x) c( t∈[T ] γt ) RΦdef (h, x) − R∗Φdef ,H (x) − −ϵ≤ . T T T D.3

Φ01 being adopted as constrained losses P cstnd ′ Example: Φ01 = Φcstnd hinge . Plug in Φ01 = Φhinge = y ′ ̸=y Φhinge −h(x, y ) in Definition 4.3, we obtain Φdef =

Φhinge −h(x, y ′ ) +

y ′ ̸=y

(1 − cj (x, y))

Φhinge −h(x, y ′ ) ,

y ′ ̸=n+j

n+j∈Y A

where Φhinge (t) = max{0, 1 − t} with the constraint

y∈Y A h(x, y) = 0.

By Awasthi et al. (2022b), Table 3, Φcstnd hinge admits an H-consistency bound with respect to ℓ01 with Γ(t) = t; using Corollary 5.2, we obtain P Rℓdef (q, x) − R∗ℓdef ,H (x) c( t∈[T ] γt ) RΦdef (h, x) − R∗Φdef ,H (x) − −ϵ≤ . T T T Example: Φ01 = Φcstnd . Plug in Φ01 = Φcstnd = sq sq X

Φdef =

Φsq −h(x, y ′ ) +

y ′ ̸=y

′ y ′ ̸=y Φsq −h(x, y )

in Definition 4.3, we obtain X

(1 − cj (x, y))

Φsq −h(x, y ′ ) .

y ′ ̸=n+j

n+j∈Y A

By Awasthi et al. (2022b), Table 3, Φcstnd admits an H-consistency bound with respect to ℓ01 with Γ(t) = sq using Corollary 5.2, we obtain P 1/2 Rℓdef (q, x) − R∗ℓdef ,H (x) c( t∈[T ] γt ) RΦdef (h, x) − R∗Φdef ,H (x) − − ϵ ≤ max S(xt ) . T T T mint∈[T ] S(xt ) t∈[T ] Example: Φ01 = Φcstnd . Plug in Φ01 = Φcstnd = ρ ρ Φdef =

X y ′ ̸=y

Φρ −h(x, y ′ ) +

′ y ′ ̸=y Φρ −h(x, y )

X n+j∈Y A

(1 − cj (x, y))

in Definition 4.3, we obtain X

y ′ ̸=n+j

Φρ −h(x, y ′ ) ,

√

Dang, Montreuil, Meyer, Carlier, Ng, and Tsang

where Φρ (t) = min{max{0, 1 − t/ρ}, 1} with the constraint

y∈Y A h(x, y) = 0.

By Awasthi et al. (2022b), Table 3, Φcstnd admits an H-consistency bound with respect to ℓ01 with Γ(t) = t; ρ using Corollary 5.2, we obtain P Rℓdef (q, x) − R∗ℓdef ,H (x) c( t∈[T ] γt ) RΦdef (h, x) − R∗Φdef ,H (x) − −ϵ≤ . T T T

Proof of constrained OCO with Φcstnd hinge

E.1

Proof of constrained OCO with Φcstnd hinge (Theorem 6.3)

We first give a proof for Lemma 6.2 b t,i be the gradient of the i-th row of ∇ b t = ∇Φ bt W ft |K b t,i |K the Lemma 6.2. Let ∇ in round t ∈ [T ], and ∇ At At b t,i |K )N . We have b t |K = (∇ projected gradient onto KA , that is ∇ t

i=1

X bt W ft |K −Φ bt W f ∗ |K ≤ b t,i |K , w Φ ⟨∇ et,i − w ei∗ ⟩. At At At i∈Y At

Proof. By convexity we have

bt W ft |K bt W f ∗ |K b t, W ft |K − W f ∗ |K ⟩F Φ −Φ ≤ ⟨∇ At At At At X b t,i , (w ⟨∇ et,i − µt ) − (w ei∗ − µ∗At )⟩ = i∈Y At

b t,i , w ⟨∇ et,i − w ei∗ ⟩ +

b t,i , µ∗A − µt ⟩ ⟨∇ t

i∈Y At

P X

b t,i , w ⟨∇ et,i − w ei∗ ⟩ +

i∈Y At

X i∈Y At

⟨

i∈Y At ∇t,i

|Y At |

,w ei∗ − w et,i ⟩

(3)

P X

b i∈Y A ∇t,i

b t,i − ⟨∇

|Y At |

i∈Y At

,w et,i − w ei∗ ⟩

b t,i |K , w ⟨∇ et,i − w ei∗ ⟩, At

i∈Y At

where ⟨⟩F denotes the Frobenius inner product, µt = |Y1 | At

et,i , µ∗A = |Y1 | i∈Y At w A

ei∗ . The first equality i∈Y A w

is due to ∇t,i = 0, ∀i ∈ / Y At , the third and fifth equalities are due to Proposition 6.1. b t,i |K , w To prove Theorem 6.3, we first show a bound on the sum of inner products ⟨∇ et,i − w ei∗ ⟩ for each label i At over rounds where i is available. Lemma E.1. Suppose that the row vector w e is taken from a non-empty closed convex set with diameter B and assume that ηt+1 ≤ ηt , t = 1, . . . , T . For any label y = i, let Si be the set of rounds where i is available, that is Si = {t ∈ [T ] : i ∈ Y At }, we have 2

b t,i |K , w ⟨∇ et,i − w ei∗ ⟩ ≤ At

t∈Si

where tk is the last round that i is available.

X B2 b t,i |K + ηt ∇ At η tk t∈Si

2 , 2

Online Learning-to-Defer with Varying Experts

Proof. Assume the label is available in rounds t1 , t2 , . . . , tk with (t1 < t2 < · · · < tk ), we have b t ,i |K ) − w ||w etj+1 ,i − w ei∗ ||22 = ||Π(w etj ,i − ηtj ∇ ei∗ ||22 j At j

b t ,i |K ≤ ||w etj ,i − ηtj ∇ −w ei∗ ||22 j At j

b t ,i |K = ||w etj ,i − w ei∗ ||22 + ηt2j ∇ j At

2 b t ,i |K , w − 2ηtj ⟨∇ etj ,i − w ei∗ ⟩. j At 2 j

Hence ||w etj ,i − w ei∗ ||22 − ||w etj+1 ,i − w ei∗ ||22 b t ,i |K + ηtj ∇ j At j ηtj

b t ,i |K , w 2⟨∇ etj ,i − w ei∗ ⟩ ≤ j At j

2 . 2

Summing over j we have X 1 1 b t ,i |K , w ||w et1 ,i − w ei∗ ||22 − 2⟨∇ ||w etk ,i − w ei∗ ||22 etj ,i − w ei∗ ⟩ ≤ j At j η t1 ηtk j∈[k] X 1 X 1 b t ,i |K + − ||w etj+1 ,i − w ei∗ ||22 + ηtj ∇ j At j ηtj+1 ηtj j∈[k−1] j∈[k] X 1 X 1 2 1 2 b t ,i |K ≤ B + − B2 + ηtj ∇ j At 2 j η t1 ηtj+1 ηtj j∈[k−1] j∈[k] X 1 1 1 2 2 b t ,i |K B + − B2 + η tj ∇ = j At 2 j η t1 ηtk η t1

2 2

j∈[k]

X B b t ,i |K + η tj ∇ j At j η tk

2 , 2

j∈[k]

where the second inequality is due to B being the diameter and ηtj ≥ ηtj+1 . This ends our proof. Next, we show that the projected gradient norm can be bounded. Lemma E.2. For any W ∈ H and any ((x, A), y) ∈ X × Y, the following upper bound holds √ ∇Φ01 (W, x, y) F ≤ N R. Proof. Due to the special properties of the projection, we can compute the exact form of ∇Φ01 (W, x, y) F . A subgradient of Φ01 (W, x, y) w.r.t rows of W is ∇wi Φ01 (W, x, y) = αi x,

(4)

where αi = 1{1 + ⟨wy′ , x⟩ + by > 0} if i ∈ Y A \ {y} and αi = 0 otherwise. Let α = (αi )⊺ ∈ {0, 1}|YA | , then ∇Φ01 (W, x, y) = αx⊺ .

(5)

By Proposition 6.1, for any 1 ≤ i ≤ N , (∇Φ01 (W, x, y)|KA )i = where s =

s αi − |Y A |

x⊺ ,

(6)

s2 s− ||x||22 . |Y A |

(7)

i∈[N ] αi . Therefore,

∇Φ01 (W, x, y)

2 = F

X αi − i∈[N ]

s |Y A |

||x||22 =

This implies ∇Φ01 (W, x, y) which completes our proof.

2 = F

√ s s 1− ||x||2 ≤ N R, |Y A |

(8)

Dang, Montreuil, Meyer, Carlier, Ng, and Tsang B Theorem 6.3. (Surrogate regret bound) Running Algorithm 1 with ηt = √N R , γt = min t2/3 t = 1, . . . , T , we have the following surrogate regret bound X ft |K , xt , yt − Φdef W f ∗ |K , xt , yt Φdef W At At

1 2 , t1/3

for

t∈[T ]

= O N 3/2 B R T 2/3 . Proof. For each label i ∈ [N ], let Si ⊆ [T ] be the set of rounds in which i is available, and let ηti = max Si be the last available round of i. Combining Lemma 6.2 and Lemma E.1 we have E X X D X ∗ b t,i bt W ft bt W f∗ , w e − w e ∇ ≤ 2 2 Φ − Φ t,i i K K K At

t∈[T ] i∈Y A

t∈[T ]

≤

X i∈[N ]

≤

B2 X b t,i ηt ∇ + KAt η ti

! 2 2

(9)

t∈Si

X N B2 bt ηt ∇ + KAt ηT

2 , F

t∈[T ]

where the last inequality is due to ηti ≤ ηT , ∀i ∈ [N ]. b t (W f ) = Φdef (W f , xt , yt ), ∀W f ∈ H. Next, we bound the expected gradient’s norm Note that Eyt′ ∼qt Φ

Eyt′ ∼qt =

≤

b t |K ∇ At

2 F

1 f , xt , yt )|K ∇Φ01 (W At qt (yt )

2 + F

N N R2 ≤ max{2N 2 R2 , N 2 R γt

√ 2

X n+j∈Y At

(1 − cj (xt , yt ))2 f , xt , n + j)|K ∇Φ01 (W At qt (n + j)

2 F

t},

whre the first inequality is due to Lemma E.2. Therefore, taking expectation on both sides in Inequality 9 gives

ft |K , xt , yt − Φdef W f ∗ |K , xt , yt Φdef W At At

t∈[T ]

≤ N 3/2 BR T 2/3 +

X t∈[T ]

max

2N 3/2 BR N 3/2 BR , t2/3 t1/3

= O(N 3/2 BR T 2/3 ).

which ends our proof. E.2

Proof of regret bound under near-realizable assumption (Theorem 6.5)

Consider an input xt = (xt , At ). The difficulty of achieving a strong regret bound comes from the fact that we only observe the loss function partially in most situations, thus may lead to large variance in the gradient updates (as seen in the analysis of Theorem 6.3). One exception is when |YAt | = 2. This occurs when n = 2 and no experts are available in round t. In such rounds, bandit feedback is equivalent to full feedback. In other words, the learner always observes the full loss function, and the gradient updates are computed exactly. To address the case when |YAt | ≥ 3, we give a tighter bound on the gap ∆CΦdef ,H (h, x) − ∆Cℓdef H (h, x). The analysis is inspired by van der Hoeven (2020). Given an input x, ymax is the label with the highest score, the multi-class label margin given is defined as s(x, ymax ) − arg maxy̸=ymax s(x, y). Note that the near-realizable condition directly√gives us a lower bound on the multi-class margin: for any t ∈ [T ] s(xt , ymax ) − arg maxy̸=ymax s(xt , y) ≥ 1 − 2/ T , which we will use extensively for the subsequent analysis.

Online Learning-to-Defer with Varying Experts

Lemma E.3. Under the near-realizable assumption, given any hypothesis h ∈ H and input x = (x, A) ∈ X . If |YA | ≥ 3 and h(x) ̸= ymax , we have the following bound √ 1 − 2/ T ∆CΦdef ,H (h, x) − ∆Cℓdef H (h, x) ≥ CΦdef (h, x). |Y A | + 4 √ Proof. Let c = 1 − 2/ T . Similar to Theorem E.5, define Y≤−1 = {y ∈ Y A : h(x, y) ≤ −1}, Y>1 = Y A − Y≤−1 , and ymax = arg maxy∈Y A s(x, y), we have S(x) − s(x, y) ≥ S(x) − s(x, ymax ) and X

1 + h(x, y) = |Y>−1 | −

y∈Y>−1

h(x, y) ≥ |Y>−1 | + |Y≤−1 | = |Y A |.

y∈Y≤−1

By Lemma C.2 and Theorem E.5, we can write X (1 + h(x, y))(S(x) − s(x, y)) CΦdef (h, x) = y∈Y>−1

(1 + h(x, y))(S(x) − s(x, ymax )) +

(1 + h(x, y))(s(x, ymax ) − s(x, y))

y∈Y>−1

≥ |Y A |(S(x − s(x, ymax )) +

(10)

(1 + h(x, y))(s(x, ymax ) − s(x, y))

y∈Y>−1 ∗ ≥ CΦ (x) + def ,H

(1 + h(x, y))(s(x, ymax ) − s(x, y)).

y∈Y>−1

We consider two cases. Case 1. h(x, ymax ) ∈ / Y>−1 , we have

(1 + h(x, y))(s(x, ymax ) − s(x, y))

y∈Y>−1

= (s(x, ymax ) − s(x, h(x))) + h(x, h(x))(s(x, ymax ) − s(x, h(x))) +

(1 + h(x, y))(s(x, ymax ) − s(x, y))

y∈Y>−1 \{h(x)}

≥ (s(x, ymax ) − s(x, h(x))) + h(x, h(x))c +

(1 + h(x, y))c

y∈Y>−1 \{h(x)

≥ (s(x, ymax ) − s(x, h(x))) + (|Y A | − 1)c. (11) Combining equations (10) and (11) we have c ∆CΦdef ,H (h, x) − ∆Cℓdef H (h, x) − CΦdef (h, x) |Y A | + 4 c ∗ = 1− CΦdef (h, x) − CΦ (x) − ∆Cℓdef H (h, x) def ,H |Y A | + 4 c c c ≥ 1− (|Y A | − 1)c − |Y A |(S(x − s(x, ymax )) − (s(x, ymax ) − s(x, h(x))) |Y A | + 4 |Y A | + 4 |Y A | + 4 ≥ 0,

(12)

where the first inequality is due to Theorem E.5 and the last inequality is due to S(x) − s(x, ymax ) ≤ |Y A | − 1 and |Y A | ≥ 3. Case 2. h(x, ymax ) ∈ Y>−1 . We have

Dang, Montreuil, Meyer, Carlier, Ng, and Tsang

(1 + h(x, y))(s(x, ymax ) − s(x, y))

y∈Y>−1

= (s(x, ymax ) − s(x, h(x))) + h(x, h(x))(s(x, ymax ) − s(x, h(x))) X + (1 + h(x, y))(s(x, ymax ) − s(x, y)) y∈Y>−1 \{h(x),ymax }

≥ (s(x, ymax ) − s(x, h(x))) + h(x, h(x))c +

(1 + h(x, y))c (13)

y∈Y>−1 \{h(x),ymax }

≥ (s(x, ymax ) − s(x, h(x))) + (

(1 + h(x, y)) − h(x, ymax ) − 2)c

y∈Y>−1

≥ (s(x, ymax ) − s(x, h(x))) + ( ≥ (s(x, ymax ) − s(x, h(x))) + (

1 2

(1 + h(x, y)) − 1)c

y∈Y>−1

|Y A | − 1)c, 2

where the second to last inequality is due to 1 + h(x, ymax ) ≤ 1 + h(x, h(x)), so 1 + h(x, ymax ) ≤ 12 h(x, y)). Combining equations (10) and (13) we have

y∈Y>−1 (1 +

c ∆CΦdef ,H (h, x) − ∆Cℓdef H (h, x) − CΦdef (h, x) |Y A | + 4 c ∗ = 1− (x) − ∆Cℓdef H (h, x) CΦdef (h, x) − CΦ def ,H |Y A | + 4 c c c |Y A | ≥ 1− − 1)c − |Y A |(S(x − s(x, ymax )) − (s(x, ymax ) − s(x, h(x))) ( 2 |Y A | + 4 |Y A | + 4 |Y A | + 4 ≥ 0,

(14)

where the first inequality is due to Theorem E.5 and the last inequality is due to S(x) − s(x, ymax ) ≤ |Y A | − 1 and |Y A | ≥ 3. Combining the two cases ends our proof.

Define δt = ∆CΦdef ,H (ht , xt ) − ∆Cℓdef H (ht , xt ). Recall that the estimated loss at round t is defined as bt W f = Φ

e 01 W f , xt , n + j (1 − cj (xt , yt )) vt,j Φ

n+j∈Y At

e 01 W f , xt , yt′ , ∀W f ∈ H. + vt,0 Φ b t |K ||2 is upper bounded by Φ b def (W ft |K , xt , yt ). The following lemma shows that ||∇ At At Lemma E.4. Define vmax = maxt,j vt,j , at any round t ∈ [T ], we have the following inequality √ b t |K ||2 ≤ 2vmax N R Φ b def (W ft |K , xt , yt ). ||∇ At At

(15)

Proof. We can write the gradient’s norm as follows 2 b t |K ||2 = vt,0 ft |K , xt , yt )|K ||2 + ||∇ ||∇Φ01 (W At At At

2 ft |K , xt , n + j)|K ||2 vt,j ||∇Φ01 (W At At

n+j∈Y At

ft |K , xt , yt )|K ||2 + ≤ vmax (vt,0 ||∇Φ01 (W At At

X n+j∈Y At

ft |K , xt , n + j)|K ||2 ). vt,j ||∇Φ01 (W At At

(16)

Online Learning-to-Defer with Varying Experts

We consider two cases. / {yt } ∪ {n + j : n + j ∈ Y At }. For y ̸= h(xt ), we have Case 1. h(xt ) ∈ ft |K , xt , yt ) ≥ 1 + h(x, h(x)) ≥ 1, Φ01 (W At therefore by Lemma E.2, ft |K , xt , y)|K ||2 ≤ ||∇Φ01 (W At At

√

NR ≤

√

ft |K , xt , y). N R Φ01 (W At

This gives us X

ft |K , xt , yt )|K ||2 + vt,0 ||∇Φ01 (W At At

ft |K , xt , n + j)|K ||2 ≤ vt,j ||∇Φ01 (W At At

√

b def (W ft |K , xt , yt ). NR Φ At

n+j∈Y At

(17) / {yt } ∪ {n + j : n + j ∈ Y At }. Suppose h(xt ) corresponds to indicator vt,j . Since qt (h(xt )) ≥ Case 2. h(xt ) ∈ 1 − γt ≥ 1/2, we have vt,j ≤ 2. Therefore X √ √ ft |K , xt , h(xt ))|K ||2 ≤ 2 N R ≤ N R( ft |K , xt , yt )). vt,j ||∇Φ01 (W vt,j Φ01 (W At At At i̸=j

Combining with Equation (15) gives us X ft |K , xt , yt )|K ||2 + vt,0 ||∇Φ01 (W At At

√ ft |K , xt , n + j)|K ||2 ≤ 2 N R Φ b def (W ft |K , xt , yt ). vt,j ||∇Φ01 (W At At At

n+j∈Y At

(18) Now from Equation (16) we can write b t |K ||2 ≤ vmax (vt,0 ||∇Φ01 (W ft |K , xt , yt )|K ||2 + ||∇ At At At

ft |K , xt , n + j)|K ||2 ) vt,j ||∇Φ01 (W At At

n+j∈Y At

√

ft |K , xt , yt ) + ≤ 2vmax N R(vt,0 Φ01 (W At

(19)

ft |K , xt , n + j)) Φ01 (W At

n+j∈Y At

√

b def (W ft |K , xt , yt ), ≤ 2vmax N R Φ At which ends our proof. We are now ready to prove Theorem 6.5. Theorem 6.5. (Near-Realizable Assumption) Under the same assumptions in Corollary 5.2 and Theorem 6.3, √ B suppose that for any t ∈ [T ] we have s(xt , ymax ) ≥ 1 − 1/ T . Running Algorithm 1 with ηt = √ 4RN 1/2 (N +4)t p and γ = B RN 5/2 (N + 4) gives us the following regret deferral bound X f ∗ , xt , yt Rℓdef (T ) = ℓdef qt , xt , yt − ℓdef W t∈[T ]

p = O B R3 N 7/2 T Proof. In Theorem 5.1, we upper bound [∆Cℓdef ,H (qt , xt )]ϵ by S(xt )Γ can rewrite the bound as follow

∆Cℓdef ,H (qt , xt ) ≤ ∆Cℓdef ,H (ht , xt ) + cγt = ∆CΦdef ,H (ht , xt ) + cγt − δt . Moreover, when h(xt ) = ymax , we have ∆Cℓdef ,H (ht , xt ) = 0 and

1 S(xt ) ∆CΦdef ,H (h, xt )

+ cγt . With δt we

Dang, Montreuil, Meyer, Carlier, Ng, and Tsang

∆Cℓdef ,H (qt , xt ) ≤ ∆Cℓdef ,H (ht , xt ) + cγt = cγt . Following the same arguments in Theorem 5.1 gives us  Rℓdef (q, x) − R∗ℓdef ,H (x) ≤ RΦdef (h, x) − R∗Φdef ,H (x) −

δt + c 

t∈[T ]

We want to want to show an upper bound on RΦdef (h, x) − R∗Φdef ,H (x) − shown that

 X

γt  .

(20)

t∈[T ]

t∈[T ] δt .

In Theorem 6.3, we have

X X N B2 bt b def,t W b def,t W ft f∗ ≤ + ηt ∇ 2 Φ − Φ KAt KAt KAt ηT

(21)

t∈[T ]

Therefore

RΦdef (h, x) − R∗Φdef ,H (x) −

t∈[T ]

 X N B2 b t |K δt = + Eyt ∼p(xt ),yt′ ∼qt  ηt ∇ At ηT

 2

− δt  ,

(22)

t∈[T ]

where the expectation is taken over the label distribution and the algorithm’s sampling distribution. On rounds t ∈ [T ] in which |YAt | = 2, the exact gradient is computed, hence 2

b t |K ηt ∇ At

= ηt ∇t |KAt

≤ 4ηt N R2 .

(23)

√ On rounds t ∈ [T ] in which h(xt ) = ymax , making use of the condition that s̄(xt , ymax ) ≥ 1 − 2/ T , we can bound the gradient as follows.

h Eyt ∼p(xt ),yt′ ∼qt 

b t |K ∇ At

1 f , xt , yt )|K ∇Φ01 (W = Eyt ∼p(xt )  At qt (yt ) ≤

X s(xt , y) qt (y)

y∈Y

y∈Y At \{ymax }

(

√

y∈Y At \{ymax } s(xt , y))|Y At |

≤O

|YAt |2 γ

n+j∈Y At

N R2 +

(1 − cj (xt , yt ))2 f , xt , n + j)|K ∇Φ01 (W At qt (n + j)

s(xt , n + j) f , xt , n + j)|K ∇Φ01 (W At qt (n + j)

s(xt , ymax ) f , xt , ymax )|K + ∇Φ01 (W At qt (ymax )

s(xt , y) f , xt , y)|K ∇Φ01 (W At qt (y)

≤

n+j∈Y At

≤

f , xt , y)|K ∇Φ01 (W At

 2



(24)

s(xt , ymax ) N R2 qt (ymax )

N R2 = O(N 5/4 R2 ).

On rounds t ∈ [T ] in which |YAt | ≥ 3 and h(xt ) ̸= ymax , combining Lemma E.3 and Lemma E.4 we have

 Eyt ∼p(xt ),yt′ ∼qt 

√ √ 1 − 2/ T − δt  ≤ 2ηt vmax N R CΦdef (ht , xt ) − CΦdef (ht , xt ). |YA | + 4 

t∈[T ]

b t |K ηt ∇ At

(25)

Online Learning-to-Defer with Varying Experts √

Note that by our choice of γ vmax = maxt,j vt,j ≤ N γ T } with large enough T . Moreover, our choice of ηt guarantees that √ 2ηt vmax

√ 1 − 2/ T CΦdef (ht , xt ) ≤ 0. N R CΦdef (ht , xt ) − |YA | + 4

(26)

Plugging inequalities (23), (24), and (26) into equation (22) gives us

RΦdef (h, x) − R∗Φdef ,H (x) −

X t∈[T ]

 X N B2 b t |K δt = ηt ∇ + Eyt ∼p(xt ),yt′ ∼qt  At ηT

 2

− δt 

t∈[T ]

NB ≤ + ηT

O(ηt N

5/4

(27)

p R ) = O B R3 N 7/2 T . 2

t∈[T ]

Combining with inequality (20), by our choice of ηt and γt we have p Rℓdef (q, x) − R∗ℓdef ,H (x) = O B R3 N 7/2 T ,

(28)

which ends our proof. E.3

Analysis of the minimizability gap

Theorem E.5. (Characterization of minimizability gaps) Assume that H is symmetric and complete, for any sequence of inputs x̄ = (x̄1 , x̄2 , . . . , x̄T ) and any distribution, the minimizability gaps can be characterized as follows: X MΦdef ,H (x̄) = R∗Φdef ,H (x̄) − |Y At | S(x̄) − s(x̄t , yt,max ) . t∈[T ]

Proof. By Lemma C.2 we can write the conditional surrogate Φdef -risk as follows: X CΦdef (h, x) = s(x, y)Φ01 (h, x, y) y∈Y A



 =

s(x, y) 

max{0, 1 + h(x, y ′ )}

y ′ ̸=y,y ′ ∈Y A

y∈Y A

max{0, 1 + h(x, y)}(S(x) − s(x, y)),

yY A

P where y∈Y A h(x, y) = 0. Define Y≤−1 = {y ∈ Y A : h(x, y) ≤ −1}, Y>1 = Y A − Y≤−1 . We can rewrite the conditional surrogate risk as CΦdef (h, x) =

1 + h(x, y) S(x) − s(x, y) .

y∈Y>−1

Define ymax = arg maxy∈Y A s(x, y), we have S(x) − s(x, y) ≥ S(x) − s(x, ymax ) and X X 1 + h(x, y) = |Y>−1 | − h(x, y) ≥ |Y>−1 | + |Y≤−1 | = |Y A |. y∈Y>−1

y∈Y≤−1

Combining the two aforementioned inequalities gives us CΦdef (h, x) ≥ |Y A | S(x) − s(x, ymax ) .

Dang, Montreuil, Meyer, Carlier, Ng, and Tsang

( Equality occurs when h(x, y) =

|Y A | − 1 −1

if y = ymax otherwise.

Note that there exists such h in H, which ends our proof.

Experiments

F.1

Details of Experiment Settings

F.1.1

Setting 1: Fixed Availability and Expertise

Here, all experts are continuously available, and each expert’s domain of competence remains stationary throughout the learning horizon. That is each expert achieves perfect accuracy on its region of expertise, but is uniformly random outside of it. This setting corresponds to the standard assumption in classical L2D frameworks (Madras et al., 2018; Mozannar and Sontag, 2020), but we study it here under the online learning protocol, where data arrives sequentially. A representative example is a clinical decision-support system that integrates several automated diagnostic models, each specialized for a distinct imaging modality (e.g., chest X-rays, MRIs, or CT scans). These expert models remain permanently accessible and their competence boundaries do not change over time, while the system continuously processes incoming patient data. This setup reflects realistic deployments where the expert pool is fixed but the input stream evolves, such as hospital triage platforms or other continuous-monitoring systems. F.1.2

Setting 2: Drifting Availability and Fixed Expertise

Let Gj,t ∈ {0, 1} denote whether expert gj is available at round t. Availability is sampled through Gj,t ∼ Bern(pj,t ), with pj,t following a random walk initialized at 0.7 with standard deviation σ = 2 × 10−3 on [0, 1]. A practical realization of this setting occurs in multi-model inference systems deployed under dynamic resource constraints. For example, a pool of pre-trained expert networks—each specialized for a distinct input modality or domain—may share a limited GPU or compute budget. At any given time, only a subset of models can be queried due to bandwidth or scheduling limitations, even though their predictive functions remain unchanged. Similar behavior appears in edge-device ensembles, where network connectivity or energy constraints temporarily restrict access to otherwise stable models. F.1.3

Setting 3: Drifting Availability and Expertise

Expert availability evolves as before, following the same random-walk process. Meanwhile, each expert’s region of expertise drifts gradually over time. We fix both the initial and final regions, separated by 105 rounds. With these boundaries fixed, the experts’ regional accuracies evolve according to a Brownian bridge. This construction models environments where both participation and competence vary over time while preserving the overall structure of the expert population. A concrete analogue arises in collaborative clinical decision-support systems. Clinicians differ in their availability due to shifts or workload, and their diagnostic expertise naturally evolves as they gain experience, adapt to new medical guidelines, or incorporate feedback from prior cases. The learning system must therefore adapt continuously to changing access to human experts and to gradual shifts in their decision boundaries. This dynamic also captures other human–AI ecosystems—such as annotation pipelines or hybrid moderation teams—where both availability and skill levels evolve throughout deployment. F.2

Details of Synthetic Datasets Experiments

We evaluate our approach on synthetic datasets with ne = 3 experts and n = 6 classes. Following the SynSep dataset in Kakade et al. (2008); van der Hoeven et al. (2021), we generate inputs xt ∈ Rd with d = 120. Each input–label pair (xt , yt )Tt=1 is sampled from one of n linearly separable clusters Ωy = {(xt , yt ) : yt = y}.

Online Learning-to-Defer with Varying Experts

To introduce label noise, for each xt ∈ Ωy we flip the true label to a uniformly random alternative class in [n]\{y} with probability py,t . The noise vector at round t is pt = (py,t )y∈[n] . We initialize p0 = [0.3, 0.3, 0.3, 0.3, 0.0, 0.0] and evolve it via a random walk with Gaussian perturbations of mean 0 and standard deviation σ = 2 × 10−3 . At initialization t = 0, expert g1 is knowledgeable on classes {1, 2} and predicts the post-noise labels correctly on inputs from Ω1 and Ω2 , while predicting uniformly at random on other clusters. Expert g2 is knowledgeable on {3, 4} with the same behavior. Expert g3 is a weak expert that predicts uniformly at random on all inputs. η0 where η0 is tuned to 5 × 10−4 . The exploration In all settings, we run our algorithm with learning rate ηt = √ t 10 is fixed to γt = min{ 12 , √ }. t

Note that in the first two settings where the expertise remains constant, our experiment design induces a clear optimal policy. A good learner must defer to experts when the input belongs to a region in {1, 2, 3, 4} and make its own prediction on regions {5, 6}. In the third and final setting, the experts expertise regions gradually drift among {1, 2, 3, 4}. Setting 1: Fixed Availability and Expertise. We report the results of this setting in Figure 3. Accuracies of experts are given in Table 2. Notice that those averages are significantly lower than the accuracy over queried rounds only (Figure 3b), which demonstrates our algorithm’s ability to query experts adequately. Table 2: Average Accuracies of Experts for setting 1. Expert g1

Expert g2

Expert g3

45.55

45.58

16.66

Accuracy

Our method rapidly converges to near-optimal predictive performance (Figure 3d) while maintaining a consistently low true deferral loss (Figure 3a), confirming an effective balance between autonomous prediction and expert deferral. Figures 3b and 3c show that experts g1 and g2 are queried most frequently and achieve nearperfect accuracy when selected, indicating that the algorithm learns to defer selectively to the most reliable experts. In contrast, the weaker expert g3 exhibits both low accuracy (Figure 3b) and a negligible deferral ratio (Figure 3c), demonstrating that the model efficiently avoids uninformative experts. As expected in this fixed setting, expert availability remains constant across all rounds (Figure 3e).

0.6

Mean Accuracy

Mean Deferral Loss

0.7

Random Our

0.5 0.4 0.3

1.0

0.5

0.8

0.4

0.6

Deferral Ratio

0.8

Expert g1 Expert g2 Expert g3

0.4

0.2

Expert g1 Expert g2 Expert g3

0.3

0.2

0.1

0.2 20000

40000

60000 round t

80000

0.0

100000

(a) Average true deferral loss.

20000

40000

60000 round t

80000

(b) Average accuracy of the experts queried by the algorithm.

1.0

Mean Expert Availability

Mean Accuracy

0.6

0.4

0.0

20000

40000

60000 round t

80000

100000

1.0

0.8

0.2

0.0

100000

Random Our 20000

40000

60000 round t

80000

(d) Average accuracy.

100000

0.8 0.6 0.4 0.2 0.0

Expert g1 Expert g2 Expert g3 20000

40000

60000 round t

80000

100000

(e) Expert availability.

Figure 3: Results of the synthetic experiment for setting 1: fixed availability and expertise. Error bars represent standard deviations across five independent runs.

Dang, Montreuil, Meyer, Carlier, Ng, and Tsang

Setting 2: Drifting Availability and Fixed Expertise. Accuracies of experts are given in Table 3.

We report results for this setting in Figure 4.

Table 3: Average Accuracies of Experts for setting 2. Expert g1

Expert g2

Expert g3

45.55

45.58

16.66

Accuracy

Compared to the previous experiment (Figure 3), overall performance declines slightly, as expected, due to the reduced and time-varying availability of experts. Nevertheless, once this availability constraint is taken into account, the observed deferral ratio remains effectively optimal (Figure 4c). Moreover, the near-perfect expert accuracy (Figure 4b) on deferred queries confirms that the algorithm maintains a well-calibrated decision boundary, consistently routing uncertain inputs to the most reliable experts.

Mean Accuracy

Mean Deferral Loss

0.7 0.6 Random Our

0.5 0.4 0.3

1.0

0.5

0.8

0.4

0.6

Deferral Ratio

0.8

Expert g1 Expert g2 Expert g3

0.4

0.2

0.2 20000

40000

60000 round t

80000

0.0

100000

(a) Average true deferral loss.

20000

40000

60000 round t

80000

0.0

100000

20000

40000

60000 round t

80000

100000

1.0 Mean Expert Availability

Mean Accuracy

0.2

(b) Average accuracy of the experts queried by the algorithm.

0.8

0.6

0.4

0.0

0.3

0.1

1.0

0.2

Expert g1 Expert g2 Expert g3

Random Our 20000

40000

60000 round t

80000

100000

(d) Average accuracy.

0.8 0.6 0.4 0.2 0.0

Expert g1 Expert g2 Expert g3 20000

40000

60000 round t

80000

100000

(e) Expert availability.

Figure 4: Results of the synthetic experiment for setting 2: fixed expert availability and expertise. Error bars represent standard deviations across five independent runs.

Setting 3: Drifting Availability and Expertise expertise of expert is shown in Figure 5.

We report results for this setting in Figure 6. Varying

Figure 5 shows that expert g1 gradually shifts its expertise from region 2 to region 1, while expert g2 moves in the opposite direction, from region 1 to region 2. Expert g3 has no region of expertise, as it is uniformly random. The results show that our algorithm adapts effectively to these dynamic shifts. Even as expertise regions drift, the model continues to defer to the appropriate experts with high frequency, demonstrating stable calibration under evolving expertise (Figure 6b). Consequently, task accuracy and deferral loss remain strong and comparable to the fixed-expertise baseline (Figures 6a and 6d).

Online Learning-to-Defer with Varying Experts 1.0

Expert g1 Expert g2 Expert g3

Mean Accuracy

0.8 0.6 0.4 0.2 0.0 Region 1

1.0

Expert g1 Expert g2 Expert g3

Mean Accuracy

0.8 0.6 0.4 0.2 0.0 Region 2

1.0

Expert g1 Expert g2 Expert g3

Mean Accuracy

0.8 0.6 0.4 0.2 0.0

20000

40000 60000 round t

80000

100000

Region 3

Figure 5: Evolution of the Expert Accuracies by Regions

Mean Accuracy

Mean Deferral Loss

0.7 0.6 Random Our

0.5

1.0

0.5

0.8

0.4

0.6

Deferral Ratio

0.8

Expert g1 Expert g2 Expert g3

0.4

Expert g1 Expert g2 Expert g3

0.3

0.2

0.4 0.2

0.1

0.3 20000

40000

60000 round t

80000

0.0

100000

(a) Average true deferral loss.

20000

40000

60000 round t

80000

(b) Average accuracy of the experts queried by the algorithm.

1.0

Mean Expert Availability

Mean Accuracy

0.6

0.4

0.2

20000

40000

60000 round t

80000

100000

(d) Average accuracy.

20000

40000

60000 round t

80000

100000

1.0

Random Our

0.8

0.0

100000

0.8 0.6 0.4 0.2 0.0

Expert g1 Expert g2 Expert g3 20000

40000

60000 round t

80000

100000

(e) Expert availability.

Figure 6: Results of the synthetic experiment for setting 3: drifting availability and drifting expertise. Whiskers denote standard deviations computed over 5 independent runs.

F.3

Details of Reuters4 Dataset Experiments

Setting 1: Fixed Availability and Expertise. The results are summarized in Figure 7. Accuracies of experts are given in Table 4. The results show that the algorithm makes good use of given experts, shown by high expert accuracy in queried rounds and a high expert deferral ratio. This leads to a faster convergence rate for accuracy.

Dang, Montreuil, Meyer, Carlier, Ng, and Tsang

Table 4: Average Accuracies of Experts for setting 1 in Reuters4. Expert g1

Expert g2

Expert g3

62.21

61.09

50.01

Accuracy

1.0

0.5

0.8

0.4

Expert g1 Expert g2 Expert g3

0.4

0.6

0.4

0.3

0.2

Random Our 20000

40000

60000 round t

80000

0.0

100000

(a) Average true deferral loss.

Deferral Ratio

0.5

Mean Accuracy

Mean Deferral Loss

0.6

Expert g1 Expert g2 Expert g3 20000

40000

60000 round t

80000

Mean Expert Availability

Mean Accuracy

20000

40000

60000 round t

80000

100000

1.0

Random Our

0.4

0.2

20000

0.0

100000

(b) Average accuracy of the experts queried by the algorithm.

0.6

0.0

0.2

0.1

1.0

0.8

0.3

40000

60000 round t

80000

0.8 0.6 0.4 0.2 0.0

100000

(d) Average accuracy.

Expert g1 Expert g2 Expert g3 20000

40000

60000 round t

80000

100000

(e) Expert availability.

Figure 7: Results of experiment on Reuters4 for setting 1: fixed availability and expertise. Whiskers denote standard deviations computed over 5 independent runs.

Setting 2: Drifting Availability and Fixed Expertise. Accuracies of experts are given in Table 5. Figure 8 show that the algorithm stays robust under varying expert availability. This is shown by the maintained high deferral ratio and high expert accuracies when queried. Table 5: Average Accuracies of Experts for setting 2 in Reuters4.

Accuracy

Expert g1

Expert g2

Expert g3

62.21

61.09

50.01

Setting 3: Drifting Availability and Drifting Expertise. Figure 10 summarizes our results. Varying expertise of expert is shown in Figure 9. Even under challenging conditions with simultaneously varying availability and expertise, our approach maintains strong performance and adapts effectively to the evolving environment. Figure 10 shows that expert g1 gradually shifts its expertise from classes 1 and 2 to classes 3 and 4, expert g2 shifts from classes 2 and 3 to classes 1 and 4, and expert g3 shifts from classes 3 and 4 to classes 1 and 2. The results show that our algorithm adapts effectively to these dynamic shifts. Even as expertise regions drift, the model continues to defer to the appropriate experts with high frequency, demonstrating stable calibration under evolving expertise (Figure 10b). Consequently, task accuracy and deferral loss remain strong and comparable to the fixed-expertise baseline (Figures 10a and 10d). F.4

Details of CIFAR10H Dataset Experiments

In this section, we report additional results on the CIFAR10H dataset (Peterson et al., 2019), which augments CIFAR10 (Krizhevsky, 2009) with real human-annotated labels. We aggregate the human annotations into three

1.0

0.5

0.6

0.8

0.4

0.5 0.4 0.3 0.2

0.6

0.4

0.2

Random Our 20000

40000

60000 round t

80000

0.0

100000

(a) Average true deferral loss.

Deferral Ratio

0.7

Mean Accuracy

Mean Deferral Loss

Online Learning-to-Defer with Varying Experts

Expert g1 Expert g2 Expert g3 20000

40000

60000 round t

80000

20000

40000

60000 round t

80000

100000

1.0 Mean Expert Availability

Mean Accuracy

0.0

100000

Random Our

0.4

0.2

20000

0.2

(b) Average accuracy of the experts queried by the algorithm.

0.6

0.0

0.3

0.1

1.0

0.8

Expert g1 Expert g2 Expert g3

40000

60000 round t

80000

0.8 0.6 0.4 0.2 0.0

100000

(d) Average accuracy.

Expert g1 Expert g2 Expert g3 20000

40000

60000 round t

80000

100000

(e) Expert availability.

Figure 8: Results of experiment on Reuters4 for setting 2: drifting availability and fixed expertise. Whiskers denote standard deviations computed over 5 independent runs.

groups, each treated as a human expert gi , i = 1, 2, 3. For an input image x, expert gi predicts by sampling uniformly at random from the labels in group i. We further introduce expert-specific noise regions to model heterogeneous expertise: g1 is knowledgeable on labels {6, 7, 8, 9}, g2 is knowledgeable on labels {0, 1, 2, 9}, g3 is knowledgeable on labels {1, 2, 3, 4}. The mean accuracy of each expert after noise injection is reported in Table 6. Each expert gj has expert cost cj (x, y) = 1gj (x)̸=y + 0.05. Table 6: Average accuracies of experts in CIFAR10H post-noise. Metric Mean Accuracy

Expert g1

Expert g2

Expert g3

0.445

0.443

0.432

For this experiment, we use a Wide Residual Network (WideResNet) as the predictor h ∈ H, instead of a linear hypothesis. To make expert consultation meaningful, we evaluate on corrupted inputs from CIFAR10C Hendrycks and Dietterich (2019) rather than on clean CIFAR10 images. In particular, we use 200,000 images corrupted with Gaussian noise at severity level 2. As a benchmark, we compare against a baseline that defers uniformly to one of the available experts whenever the classifier confidence falls below 0.5. The results under fixed availability and expertise settings are summarized in Table 7, and the learning curves are shown in Figure 11. Our method achieves both lower mean deferral loss and higher mean accuracy than the baseline. This indicates that the learned policy attains a better trade-off between prediction performance and consultation cost, rather than relying on deferral in a naive manner. The queried expert accuracies are also substantially higher under our method, showing that the algorithm does not defer uniformly, but instead routes examples toward more suitable experts. The deferral ratios further support this behavior: the algorithm learns a non-uniform consultation pattern, which suggests that it is able to distinguish between examples that should be handled by the classifier and those for which expert advice is more beneficial.

Dang, Montreuil, Meyer, Carlier, Ng, and Tsang 1.0

Expert g1 Expert g2 Expert g3

0.8 Mean Accuracy

1.0

Expert g1 Expert g2 Expert g3

0.6 0.4

0.2

0.0

0.0 Class 1

1.0

0.8 Mean Accuracy

Class 2

1.0

Expert g1 Expert g2 Expert g3

0.6 0.4 0.2 0.0

0.6 0.4 0.2

20000

40000 60000 round t

80000

100000

0.0

Expert g1 Expert g2 Expert g3

20000

40000 60000 round t

Class 3

80000

100000

Class 4

Figure 9: Expert Accuracies by Regions on Reuters4. Table 7: Comparison between our method and the baseline, averaged over 5 runs. Better results are highlighted. Metric

Our Method

Baseline

0.3953 0.6519 0.7253 0.7967 0.5764 0.3233 0.2266 0.3981

0.4133 0.6145 0.4228 0.3454 0.4291 0.1843 0.1850 0.1847

Mean Deferral Loss Mean Accuracy Expert g1 Queried Accuracy Expert g2 Queried Accuracy Expert g3 Queried Accuracy Expert g1 Deferral Ratio Expert g2 Deferral Ratio Expert g3 Deferral Ratio 1.0

0.5

0.8

0.4

Expert g1 Expert g2 Expert g3

0.55 0.50

Mean Accuracy

Mean Deferral Loss

0.60

Random Our

0.45 0.40 0.35

0.6

0.4

0.2

0.30 20000

40000

60000 round t

80000

0.0

100000

(a) Average true deferral loss.

Deferral Ratio

0.65

Expert g1 Expert g2 Expert g3 20000

40000

60000 round t

80000

(b) Average accuracy of the experts queried by the algorithm.

0.6

0.4

0.2

60000 round t

80000

(d) Average accuracy.

100000

20000

40000

60000 round t

80000

100000

1.0 Mean Expert Availability

Mean Accuracy

0.8

40000

0.0

100000

Random Our

20000

0.2

0.1

1.0

0.0

0.3

0.8 0.6 0.4 0.2 0.0

Expert g1 Expert g2 Expert g3 20000

40000

60000 round t

80000

100000

(e) Expert availability.

Figure 10: Results of experiment on Reuters4 for setting 3: drifting availability and drifting expertise. Whiskers denote standard deviations computed over 5 independent runs.

Online Learning-to-Defer with Varying Experts

Our Baseline

0.65

Mean Deferral Loss

0.60 Mean Accuracy

Our Baseline

0.60

0.55

0.50

0.45

0.55

0.50

0.45

0.40 0

50000

100000 round t

150000

(a) Average accuracy.

200000

50000

100000 round t

150000

200000

(b) Average true deferral loss.

Figure 11: Results of experiment on CIFAR10H with image corruption from CIFAR10C. Results are averaged over 5 independent runs.

Record · ID 178897 · SHA-256 7e2f2cd4f96874ff
Retrieved via Conceptio — every document is proof-bundled with source, license, and retrieval metadata.