mlsanityData to 7 Oct 2026

Multinomial Subset Routing with Sum-Max Rewards and Operational Constraints

arXiv 2608.16375 ↗First posted 17 Aug 2026cs.LG cs.AIcited by 0

Not on the map. Why?

Abstract (arXiv)

We study online routing to subsets of experts under aggregate bandit feedback and long-run operational constraints. Expert contributions can be complementary: for each task dimension, the best selected expert determines the contribution, and the total reward aggregates these dimension-wise maxima. At the same time, capacity, budget, and fairness requirements impose lower and upper bounds on long-run expert activation frequencies. A fixed deterministic subset cannot generally satisfy such heterogeneous requirements, motivating a stochastic routing policy. We formalize this problem as Multinomial Subset Routing (MSR). The learner maintains a distribution (q) over (K) experts, samples an expert independently (M) times from (q), and routes each task to the distinct sampled experts. We propose OMD-Approachability, which combines online mirror descent with Blackwell's approachability to optimize MSR under two-sided operational constraints. We establish (O(T-1/2)) average reward regret and expected constraint violation. We also quantify the approximation gap induced by a linear surrogate, and evaluate the approach on a real-world crowdsourcing dataset.

Key facts. No citing papers in the map yet (data through 7 Oct 2026). Builds on 24 of its 33 references that are in the map. First posted on arXiv 17 Aug 2026.

Builds on

24 of 33 references.

References · 24

  1. 2017Outrageously Large Neural Networks: The Sparsely-Gated Mixture-of-Experts Layercited by 3,413
  2. 2021Switch Transformers: Scaling to Trillion Parameter Models with Simple and Efficient Sparsitycited by 3,014
  3. 2019Introduction to Online Convex Optimizationcited by 793
  4. 2024RouteLLM: Learning to Route LLMs with Preference Datacited by 633
  5. 2023Large Language Model Routing with Benchmark Datasetscited by 166
  6. 2013Bandits with Knapsackscited by 163
  7. 2024GraphRouter: A Graph-based Router for LLM Selectionscited by 154
  8. 2024RouterDC: Query-Based Router by Dual Contrastive Learning for Assembling Large Language Modelscited by 84
  9. 2014Bandits with concave rewards and convex knapsackscited by 83
  10. 2015Linear Contextual Bandits with Knapsackscited by 82
  11. 2014Combinatorial Multi-Armed Bandit and Its Extension to Probabilistically Triggered Armscited by 78
  12. 2018Thompson Sampling for Combinatorial Semi-Banditscited by 78
12 more
  1. 2018Adversarial Bandits with Knapsackscited by 73
  2. 2013Thompson Sampling for Complex Bandit Problemscited by 43
  3. 2015An efficient algorithm for contextual bandits with knapsacks, and an extension to concave objectivescited by 43
  4. 2024MetaLLM: A High-performant and Cost-efficient Dynamic Framework for Wrapping LLMscited by 39
  5. 2020FrugalML: How to Use ML Prediction APIs More Accurately and Cheaplycited by 33
  6. 2022Contextual Bandits with Packing and Covering Constraints: A Modular Lagrangian Approach via Regressioncited by 30
  7. 2017Combinatorial Semi-Bandits with Knapsackscited by 23
  8. 2023Combinatorial Stochastic-Greedy Banditcited by 18
  9. 2020Submodular Bandit Problem Under Multiple Constraintscited by 15
  10. 2025Learning to Route LLMs from Bandit Feedback: One Policy, Many Trade-offscited by 13
  11. 2021Efficient Online ML API Selection for Multi-Label Classification Taskscited by 11
  12. 2023Sum-max Submodular Banditscited by 3

Built on by

Not cited yet.