May 12, 2026 · stat.MLJ/K move · Enter open · S save
Dang Hoang Duy, Yannis Montreuil, Maxime Meyer, Axel Carlier+2
School of Computing, National University of Singapore, Singapore · IPAL, IRL 2955, Singapore · Department of Mathematics, National University of Singapore, Singapore, 117543 · F´ed´eration ENAC ISAE-SUPAERO ONERA, Universit´e de Toulouse, France · Institute for Infocomm Research, A*STAR, Singapore
Learning-to-Defer (L2D) methods route each query either to a predictive model or to external experts. While existing work studies this problem in batch settings, real-world deployments require handling streaming data, changing expert availability, and shifting expert distribution. We introduce the first online L2D algorithm for multiclass classification with bandit feedback and a dynamically varying pool of experts. Our method achieves regret guarantees of
O((n+ne)T2/3) in general and
O((n+ne)T) under a low-noise condition, where
T is the time horizon,
n is the number of labels, and
ne is the number of distinct experts observed across rounds. The analysis builds on novel
H-consistency bounds for the online framework, combined with first-order methods for online convex optimization. Experiments on synthetic and real-world datasets demonstrate that our approach effectively extends standard Learning-to-Defer to settings with varying expert availability and reliability.