Online Learning-to-Defer with Varying Experts

Problem Formulation
Learning-to-Defer (L2D) is a framework designed to integrate predictive models with external experts (human or automated) to enhance system reliability by routing uncertain or high-stakes inputs to more competent agents. While existing L2D research operates primarily in batch settings with fixed pools of experts and full supervision (observing all expert predictions during training), real-world deployments face significant challenges: data arrives sequentially, expert availability fluctuates (e.g., due to shifts or resource constraints), and expert reliability may drift over time. Furthermore, practical systems often operate under bandit feedback, where the learner only observes the outcome of the chosen action (prediction or specific expert query) rather than the ground truth or the performance of all available experts. This paper addresses the gap between classical L2D assumptions and these dynamic, online realities by introducing the first online L2D framework for multiclass classification with bandit feedback and a dynamically varying pool of experts.

Methodology
The authors propose a general framework where, at each round $t$, an augmented input $(x_t, A_t)$ is revealed, consisting of a feature vector $x_t$ and a set of available experts $A_t$. The learner must decide whether to predict a class label or defer to one of the available experts in $A_t$. The interaction follows a semi-adversarial setting: inputs may be chosen adversarially, but labels are drawn from a fixed (though unknown) distribution conditional on the input.

The core methodological contributions include:

1. True Deferral Loss and Surrogate: The authors define a true deferral loss $\ell_{def}$ that accounts for misclassification costs and expert query costs. Since this loss is non-differentiable, they introduce a convex surrogate loss $\Phi_{def}$ that extends standard score-based surrogates (like constrained hinge loss) to the online, varying-expert setting. This surrogate is designed to be unaffected by the scores of unavailable experts.
2. H-Consistency Bounds for Online Learning: A significant theoretical step is the extension of $H$-consistency bounds from batch learning to the online setting. The authors prove that minimizing the surrogate deferral regret in the online framework ensures a bounded true deferral regret, provided the underlying surrogate admits an $H$-consistency bound with respect to the zero-one loss.
3. Algorithm Design: The proposed algorithm (Algorithm 1) utilizes Online Gradient Descent (OGD) with projected gradients. To handle the constraint that the sum of scores for available labels must be zero (required for the constrained hinge loss), the algorithm projects the weight matrix onto a feasible subspace $K_{A_t}$ specific to the current set of available experts. This projection preserves the hypothesis's predictions on the available label set. The algorithm incorporates an exploration rate $\gamma_t$ to handle the bandit feedback, estimating the loss function based on the observed outcome of the sampled action.

Key Contributions
The paper claims four primary contributions:

1. First Online L2D Framework: It introduces the first framework for online Learning-to-Defer under bandit feedback where both the data distribution and the pool of experts can vary over time.
2. Theoretical Extension: It extends the notion of $H$-consistency bounds to the online setting, a property previously limited to batch learning analyses.
3. Regret Guarantees: The proposed algorithm achieves a regret bound of $O((n + n_e)T^{2/3})$ in the general case, where $n$ is the number of classes and $n_e$ is the number of distinct experts observed. Under a low-noise (near-realizable) assumption, this improves to $O((n + n_e)\sqrt{T})$.
4. Empirical Validation: The approach is validated on both synthetic and real-world datasets (Reuters4 and CIFAR10H), demonstrating its ability to adapt to varying expert availability and drifting expertise.

Results
Experiments were conducted under three regimes of increasing complexity: (1) fixed availability and expertise, (2) drifting availability with fixed expertise, and (3) fully dynamic settings with both drifting availability and drifting expertise.

• Synthetic Data: The algorithm successfully learned the optimal boundary between predicting and deferring, consistently routing inputs to the most competent available experts. It maintained low deferral loss and high accuracy even when expert regions of competence shifted over time.
• Real-World Data (Reuters4): In the most challenging setting (drifting availability and expertise), the method tracked moving expert competence regions effectively. It deferred with high frequency to currently competent experts, preserving stable calibration and achieving task accuracy comparable to fixed-expertise baselines.
• CIFAR10H: Using a WideResNet predictor and human-annotated experts, the method outperformed a confidence-based baseline that defers uniformly at random. The learned policy achieved lower deferral loss and higher accuracy, indicating it learned to route examples to the most suitable experts rather than deferring indiscriminately.

Significance
The paper positions itself as a foundational step toward making Learning-to-Defer systems viable for real-world, non-stationary environments. By moving beyond the assumption of fixed expert pools and full supervision, the authors demonstrate that consistent surrogate-based methods can be made robust to adversarial environments and varying expert reliability. The theoretical establishment of $H$-consistency in the online setting provides a rigorous guarantee that minimizing surrogate loss leads to minimizing true deferral regret, bridging a critical gap between theoretical L2D guarantees and the practical requirements of streaming data and dynamic expert systems.