Search papers, labs, and topics across Lattice.
This paper introduces Multinomial Subset Routing (MSR), a novel online routing framework that utilizes a multinomial routing policy to sample experts, allowing for a more flexible and effective selection process compared to traditional deterministic methods. The approach addresses the limitations of existing combinatorial bandits by accommodating a reward structure based solely on the best-performing expert in the routed subset, while also adhering to long-term operational constraints. Empirical validation on a real-world crowdsourcing dataset demonstrates that the proposed method achieves $O(1/\sqrt{T})$ regret in both reward and constraint violation, highlighting its practical applicability.
Sampling experts from a multinomial policy can significantly enhance routing efficiency while satisfying operational constraints, achieving low regret in real-world applications.
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.
