Online Learning-to-Defer with Varying Experts
TL;DR
An online multiclass L2D algorithm that combines queried-action bandit feedback with a dynamically varying pool of experts is introduced that achieves expected true-deferral regret under a concentrated-score condition.
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 $\rho$ 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}\rho+1)T^{2/3})$, improving to $O(BN^{3/2}\rho\sqrt T+B^2N^3\rho^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.
