We introduce Multinomial Subset Routing (MSR), a new online routing framework over $K$ experts in which the learner keeps a multinomial routing policy instead of a deterministic subset of experts. At each round, the learner samples $M$ experts i.i.d. from the multinomial policy, and the resulting set of distinct sampled experts forms the routed subset. The reward depends only on the best-performing expert(s) in the routed subset. This reward structure arises naturally in routing across specialized models but is not captured by standard combinatorial bandits or subset-selection methods, which optimize deterministic subsets and typically assume additive rewards. We require the selection to satisfy several long-term, two-sided operational constraints under bandit feedback, observing only the winner's reward each round. We propose OMD-Approachability, combining online mirror descent with Blackwell's Approachability, and prove it achieves $O(1/\sqrt{T})$ regret in both reward and constraint violation. We ground the framework in practical application domains and validate it empirically on a real-world crowdsourcing dataset.
Active Domain Adaptation (ADA) enhances transfer learning by selecting the most informative samples from the target domain for annotation. The source-free variant, ASFDA, operates using only a pre-trained source model and unlabeled target data. However, existing approaches typically assume that distribution shift arises solely from changes in the feature or label distribution, thereby neglecting concept shift (the divergence of $p(y|x)$ across domains). In this paper, we propose ADA-CS, a plug-and-play module compatible with any ADA or ASFDA framework. Without requiring access to source data, ADA-CS isolates concept shift from other forms of shifts. The concept shift severity is quantified to prioritize samples exhibiting the largest discrepancy in $p(y|x)$ for annotation. We further introduce a CSS metric to quantify the Concept Shift Severity across domains, revealing that non-negligible concept shift exists in many transfer tasks. Extensive experiments on four vision benchmarks (Office-31, Digits, DomainNet, and Office-Home RSUT) and one large-scale tabular dataset (USAccident) show that ADA-CS improves performance when combined with a wide range of active learning, ADA, and ASFDA strategies. Moreover, the rapid decline of CSS during adaptation provides direct evidence of our approach's effectiveness in identifying and correcting concept shift.
