# Multinomial Subset Routing with Sum-Max Rewards and Operational Constraints

arXiv: https://arxiv.org/abs/2608.16375 · HTML: https://mlsanity.com/paper/2608.16375/

## Key facts

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

## Builds on (most cited first, 24 of 24)

- [Outrageously Large Neural Networks: The Sparsely-Gated Mixture-of-Experts Layer](https://mlsanity.com/paper/1701.06538/) (2017)
- [Switch Transformers: Scaling to Trillion Parameter Models with Simple and Efficient Sparsity](https://mlsanity.com/paper/2101.03961/) (2021)
- [Introduction to Online Convex Optimization](https://mlsanity.com/paper/1909.05207/) (2019)
- [RouteLLM: Learning to Route LLMs with Preference Data](https://mlsanity.com/paper/2406.18665/) (2024)
- [Large Language Model Routing with Benchmark Datasets](https://mlsanity.com/paper/2309.15789/) (2023)
- [GraphRouter: A Graph-based Router for LLM Selections](https://mlsanity.com/paper/2410.03834/) (2024)
- [Bandits with Knapsacks](https://mlsanity.com/paper/1305.2545/) (2013)
- [RouterDC: Query-Based Router by Dual Contrastive Learning for Assembling Large Language Models](https://mlsanity.com/paper/2409.19886/) (2024)
- [Bandits with concave rewards and convex knapsacks](https://mlsanity.com/paper/1402.5758/) (2014)
- [Linear Contextual Bandits with Knapsacks](https://mlsanity.com/paper/1507.06738/) (2015)
- [Combinatorial Multi-Armed Bandit and Its Extension to Probabilistically Triggered Arms](https://mlsanity.com/paper/1407.8339/) (2014)
- [Thompson Sampling for Combinatorial Semi-Bandits](https://mlsanity.com/paper/1803.04623/) (2018)
- [Adversarial Bandits with Knapsacks](https://mlsanity.com/paper/1811.11881/) (2018)
- [Thompson Sampling for Complex Bandit Problems](https://mlsanity.com/paper/1311.0466/) (2013)
- [An efficient algorithm for contextual bandits with knapsacks, and an extension to concave objectives](https://mlsanity.com/paper/1506.03374/) (2015)
- [MetaLLM: A High-performant and Cost-efficient Dynamic Framework for Wrapping LLMs](https://mlsanity.com/paper/2407.10834/) (2024)
- [FrugalML: How to Use ML Prediction APIs More Accurately and Cheaply](https://mlsanity.com/paper/2006.07512/) (2020)
- [Contextual Bandits with Packing and Covering Constraints: A Modular Lagrangian Approach via Regression](https://mlsanity.com/paper/2211.07484/) (2022)
- [Combinatorial Semi-Bandits with Knapsacks](https://mlsanity.com/paper/1705.08110/) (2017)
- [Combinatorial Stochastic-Greedy Bandit](https://mlsanity.com/paper/2312.08057/) (2023)
- [Submodular Bandit Problem Under Multiple Constraints](https://mlsanity.com/paper/2006.00661/) (2020)
- [Learning to Route LLMs from Bandit Feedback: One Policy, Many Trade-offs](https://mlsanity.com/paper/2510.07429/) (2025)
- [Efficient Online ML API Selection for Multi-Label Classification Tasks](https://mlsanity.com/paper/2102.09127/) (2021)
- [Sum-max Submodular Bandits](https://mlsanity.com/paper/2311.05975/) (2023)

## 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.