Online Learning-to-Defer with Varying Experts

Learning-to-Defer (L2D) methods route each query either to a predictive model or to external experts. While existing work studies this problem in batch settings, real-world deployments require handling streaming data, changing expert availability, and shifting expert distribution. We introduce the first online L2D algorithm for multiclass classification with bandit feedback and a dynamically varying pool of experts. Our method achieves regret guarantees of O((n+n_e)T^{2/3}) in general and O((n+n_e)\sqrt{T}) under a low-noise condition, where T is the time horizon, n is the number of labels, and n_e is the number of distinct experts observed across rounds. The analysis builds on novel H-consistency bounds for the online framework, combined with first-order methods for online convex optimization. Experiments on synthetic and real-world datasets demonstrate that our approach effectively extends standard Learning-to-Defer to settings with varying expert availability and reliability.