Online Learning-to-Defer with Varying Experts

Dang Hoang Duy, Yannis Montreuil, Maxime Meyer, Axel Carlier, Lai Xing Ng, Wei Tsang Ooi

TL;DR

Traditional Learning-to-Defer (L2D) systems assume a static pool of human experts who are always available and fully evaluated during training. This paper introduces the first online, multiclass L2D framework that handles streaming data, dynamically changing expert availability, drifting expert reliability, and partial (bandit) feedback, all backed by solid sublinear regret guarantees.

What Problem Does This Paper Address?

Learning-to-Defer (L2D) is a crucial framework for safe AI deployment, balancing automated machine learning predictions with human expertise. When an AI model is uncertain or faces a high-stakes scenario, it defers the decision to a competent human expert (like a clinician or domain specialist).

However, real-world deployments are rarely static. Human experts have shifts (varying availability), get tired or face domain shifts (drifting reliability), and you only find out if an expert was correct after you choose to route a query to them (bandit feedback). Existing L2D methods are mostly batch-based and assume full information—meaning they require predictions from every single expert during training. This paper bridges the gap between theory and practice by moving L2D into a sequential, semi-adversarial online learning environment.

Methods

The authors propose an Online Gradient Descent (OGD) algorithm with Projected Gradients (Algorithm 1) to handle the fluid nature of real-world expert pools.

Key innovations include:

  • Bandit Feedback Formulation: The learner only observes correctness for the selected action (either a direct class prediction or a specific expert deferral), rather than receiving full label feedback.
  • Projected Online Convex Optimization: To handle varying expert sets on the fly, the algorithm dynamically projects the model's weight matrix onto a zero-sum subspace ($K_A$) specific to the experts available at that exact round. The weights are also constrained within a bounded Frobenius ball ($\mathcal{H}_B$).
  • Online $\mathcal{H}$-Consistency Transfer Bound: The authors derived a new mathematical bridge that connects the regret of a convex surrogate loss (specifically, a constrained hinge loss) directly to the true zero-one deferral regret, explicitly accounting for exploration rates and minimizability gaps.

Datasets

The framework was evaluated across three distinct environments:

  1. Synthetic Datasets: A modified version of the SynSep dataset (6 classes, 3 experts, 120 features) used to simulate controlled random walks of drifting expert availability and expertise.
  2. Reuters4: A real-world text classification dataset (4 classes, 47,236 features, 100,000 examples) where the authors simulated three experts with overlapping, shifting knowledge regions.
  3. CIFAR10H: An image dataset containing real human annotations. To make the task challenging, the authors evaluated it using a Wide Residual Network (WideResNet) predictor on images corrupted with Gaussian noise from CIFAR10C.

Key Insights and Ideas

  • The Power of Dynamic Projections: By centering and projecting weights based on who is currently available, the algorithm effectively ignores the scores of missing experts without corrupting or biasing the model's long-term learning history.
  • Overcoming the Bandit Penalty: Usually, partial bandit feedback slows down learning rates to a regret of $O(T^{2/3})$. However, the authors prove that under a "concentrated-score condition" (a low-noise regime where one action clearly dominates), a calibration-slack term cancels out high-variance importance weights, recovering the optimal $O(\sqrt{T})$ rate.
  • Semi-Adversarial Realism: The paper adopts a setting where inputs can arrive adversarially (e.g., sudden spikes in specific types of medical cases), but the underlying ground-truth label distribution remains consistent. This ensures that expert reliability can be fairly and consistently assessed over time.

Key Results

  • Adaptability to Drift: On the Reuters4 dataset with jointly drifting availability and expertise, the algorithm successfully minimized true deferral loss and steadily increased overall task accuracy over 100,000 rounds, outperforming random routing baselines.
  • Superiority Over Confidence Baselines: On the CIFAR10H image task, the proposed method achieved a lower mean deferral loss (0.3953 vs. 0.4133) and higher mean accuracy (0.6519 vs. 0.6145) compared to a standard confidence-threshold baseline.
  • Selective Routing: The algorithm demonstrated an ability to learn non-uniform routing patterns, successfully identifying which specific expert was best suited for a given image corruption rather than deferring naively.

Limitations and Future Work

  • Low-Noise Assumptions for Faster Rates: The optimal $O(\sqrt{T})$ regret bound relies heavily on the "concentrated-score condition." In highly chaotic or inherently ambiguous real-world environments, this condition might not hold, reverting the algorithm to the slower $O(T^{2/3})$ rate.
  • Linear Theory vs. Deep Empirical Models: While the core theoretical proofs are built around linear hypothesis sets, the empirical validation on CIFAR10H successfully utilized a deep WideResNet. Extending full theoretical consistency guarantees to deep neural network architectures remains an open challenge for future research.

Summary updated

Abstract

Learning-to-Defer (L2D) methods route each query either to a predictive model or to external experts. Real-world deployments require handling streaming data, changing expert availability, shifting expert reliability, and feedback observed only for the selected action. We introduce an online multiclass L2D algorithm that combines queried-action bandit feedback with a dynamically varying pool of experts. Let $N=n+n_e$, let $B$ bound the Frobenius norm of the linear score matrix, and let $ρ$ bound the augmented input norm. Assuming linear calibration and zero surrogate minimizability gap for the projected comparator class, our method achieves expected true-deferral regret $O((BN^{3/2}ρ+1)T^{2/3})$, improving to $O(BN^{3/2}ρ\sqrt T+B^2N^3ρ^2)$ under a concentrated-score condition. The analysis combines an online $\mathcal H$-consistency transfer bound with projected online convex optimization. Experiments on synthetic and real-world datasets demonstrate selective routing under varying expert availability and reliability.
BibTeX
@inproceedings{duy2026online,
  author = {Dang Hoang Duy and Yannis Montreuil and Maxime Meyer and Axel Carlier and Lai Xing Ng and Wei Tsang Ooi},
  title = {{Online Learning-to-Defer with Varying Experts}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2026},
  url = {https://openreview.net/forum?id=1lix8ppUJ7},
}
Figure