Coverage-Maximizing Multinomial Subset Routing under Operational Constraints

• URL: http://arxiv.org/abs/2608.16375v1
• Date: Mon, 17 Aug 2026 10:30:20 GMT
• Title: Coverage-Maximizing Multinomial Subset Routing under Operational Constraints
• Abstract summary: We introduce Multinomial Subset Routing (MSR), a new online routing framework over $K$ experts.<n>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.<n>The reward depends only on the best-performing expert(s) in the routed subset.
• Score: 6.499454916436427
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: 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.

Related papers

• Share First, Route What Remains: A Unified Framework for Token-Adaptive MoE Computation [49.8459545291965]
  Mixture-of-experts (MoE) models have recently moved beyond routing a fixed number of complete experts.<n>We study this dependency by decomposing sparsely upcycled feed-forward experts into key-value channels.<n>We instantiate it in UniF-MoE, a unified framework for token-adaptive MoE computation.
  arXiv  Detail & Related papers  (2026-08-11T02:40:58Z)
• Beyond Routing Weights: Faithful Response-Level Interpretation of Mixture-of-Experts Reward Models via Contribution Contrast [22.088665451247753]
  Mixture-of-Experts (MoE) reward models seek to improve interpretability by routing prompts to specialized experts.<n>We propose $textbfCo$ntribution-$textbfCo$ntrast ($textbfCo$) response-level interpretation.<n>CoCo yields more coherent, faithful, and specialized interpretations than router-based, score-based, and sparse autoencoder-based alternatives.
  arXiv  Detail & Related papers  (2026-07-31T17:43:30Z)
• Selective Ensemble Based on Preference-Directed Multi-Objective Bandits [90.75513823660775]
  We formalize a sequential decision problem under partially specified linear preferences.<n>We then propose a preference-directed upper confidence bound (PrefUCB) algorithm.<n> Experiments on large pre-trained model selective ensemble tasks and online asset allocation under institutional mandates validate our method.
  arXiv  Detail & Related papers  (2026-06-20T07:52:46Z)
• ProbMoE: Differentiable Probabilistic Routing for Mixture-of-Experts [32.864092506780004]
  Mixture-of-Experts (MoE) models scale by activating only a small subset of experts per token.<n>We introduce ProbMoE, a probabilistic routing framework that models expert selection as a distribution over cardinality-constrained expert subsets.
  arXiv  Detail & Related papers  (2026-06-01T00:16:36Z)
• The Sample Complexity of Multiclass and Sparse Contextual Bandits [106.74652380822778]
  We aim to identify an approximately optimal policy from a given class based on bandit feedback.<n>Motivated by bandit multiclass classification with zero-one rewards, we focus on the emph$s$-sparse setting.<n>We show that, with $s$-sparse rewards, the induced model class admits a sharp DEC bound that scales with $s$ and directly yields the optimal rate.
  arXiv  Detail & Related papers  (2026-05-28T09:12:20Z)
• Online Learning-to-Defer with Varying Experts [6.097236291317658]
  We introduce the first online L2D algorithm for multiclass classification with bandit feedback and a dynamically varying pool of experts.<n>Our method achieves regret guarantees of $O((n+n_e)T2/3)$ in general and $O((n+n_e)sqrtT)$ under a low-noise condition.<n>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.
  arXiv  Detail & Related papers  (2026-05-12T16:19:44Z)
• Expert Routing for Communication-Efficient MoE via Finite Expert Banks [3.8673630752805437]
  Resource-efficient machine learning increasingly uses sparse Mixture-of-Experts (MoE) architectures.<n>We treat the gate as a channel and use $I(X;T)$ to quantify the routing information available to the selected expert.<n>The proposed framework provides a practical tool for analyzing resource-aware MoE inference systems.
  arXiv  Detail & Related papers  (2026-05-06T16:00:46Z)
• UCB-type Algorithm for Budget-Constrained Expert Learning [71.67657715154034]
  algnameM-LCB is a UCB-style meta-algorithm that provides emphanytime regret guarantees<n>We show how algnameM-LCB extends the classical bandit paradigm to the more realistic scenario of coordinating stateful, self-learning experts under limited resources.
  arXiv  Detail & Related papers  (2025-10-26T12:36:17Z)
• Generalizing Behavior via Inverse Reinforcement Learning with Closed-Form Reward Centroids [37.79354987519793]
  We study the problem of generalizing an expert agent's behavior, provided through demonstrations, to new environments and/or additional constraints.<n>We propose a novel, principled criterion that selects the "average" policy among those induced by the rewards in a certain bounded subset of the feasible set.
  arXiv  Detail & Related papers  (2025-09-15T14:53:54Z)
• Patch-level Routing in Mixture-of-Experts is Provably Sample-efficient for Convolutional Neural Networks [74.68583356645276]
  In deep learning, mixture-of-experts (MoE) activates one or few experts (sub-networks) on a per-sample or per-token basis. We show for the first time that pMoE provably reduces the required number of training samples to achieve desirable generalization.
  arXiv  Detail & Related papers  (2023-06-07T00:16:10Z)
• SetRank: A Setwise Bayesian Approach for Collaborative Ranking from Implicit Feedback [50.13745601531148]
  We propose a novel setwise Bayesian approach for collaborative ranking, namely SetRank, to accommodate the characteristics of implicit feedback in recommender system. Specifically, SetRank aims at maximizing the posterior probability of novel setwise preference comparisons. We also present the theoretical analysis of SetRank to show that the bound of excess risk can be proportional to $sqrtM/N$.
  arXiv  Detail & Related papers  (2020-02-23T06:40:48Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.