Multinomial Subset Routing with Sum-Max Rewards and Operational Constraints

Quan Zhou; Yiyan Huang

cs.LGAug 17, 2026

Multinomial Subset Routing with Sum-Max Rewards and Operational Constraints

Authors: Quan Zhou, Yiyan Huang

Abstract

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.

Figures & tables

\begin{split}\max_{q\in\Delta_{K}:\;q\geq\gamma}&\quad q^{\top}g_{t-1}-\tfrac{\eta}{2}\|q-q_{t-1}\|^{2}\\ \text{s.t. }&w_{t}^{\top}\sum_{i=1}^{K}q_{i}\;c_{i}-h_{S}(w_{t})\leq 0\end{split}

(5)

Algorithm 1 Online Mirror Descent with Approachability Constraints

Figure 1: Empirical objective regret (top) and realized constraint regret (bottom) versus OMD update step $n=t/10$ , for $N=3$ (left) and $N=5$ (right). Curves show the mean $\pm$ one standard deviation over $5$ seeds; dashed curves show an $O(n^{-1/2})$ reference.

Figure 2: Constraint-tightness sweep with $K=50$ , $M=5$ , $N=3$ , $T=10{,}000$ , and $20$ seeds. The left column shows mean $\pm$ standard deviation of time-averaged reward, and the right column shows the percentage of feasible seeds. Rows correspond to the stationary and regime-switching environments.

Figure 3: Rolling-average reward (window $5{,}000$ ) under the tight (left) and loose (right) constraints across $20$ seeds. Rows correspond to the stationary and regime-switching environments. MoE and Random are omitted because their higher per-round variance obscures the comparison among the remaining methods.

Appendix figures & tables2 assets

Supplementary material from the paper’s appendix.

Appendix

Config	Budget margin	Expert cap $\alpha_{\mathrm{expert}}$
tight	$+0.0$	$2.0$
medium	$+0.1$	$2.5$
loose	$+0.5$	$5.0$
none	$-$	$\infty$

Appendix

Table 1: Constraint configurations used in the experiments.

\begin{split}q^{(x)}\leftarrow\arg\max_{q\in\Delta_{K}:\;q\geq\gamma}&\quad q^{\top}g^{(x)}-\tfrac{\eta}{2}\bigl\|q-q^{(x)}\bigr\|^{2}\\ \text{s.t. }&w_{t}^{\top}\sum_{i=1}^{K}q_{i}\;c_{i}-h_{S}(w_{t})\leq 0\end{split}

(16)

Appendix

Algorithm 2 Contextual OMD with Approachability Constraints

Blackwell Approachability

See all 10 papers

Online Learning with LLM Experts from Limited Feedback
Sep 5, 2026Wang Wei, Soumyabrata Pal, Koyel Mukherjee +4LLM Routing Multi-Armed Bandits
Virginia Tech · Adobe Research
BRANCH-MoE: Balance-Aware Tree Routing for Large Embedding Models
Oct 5, 2026Gang Fu, Adel Javanmard, MohammadHossein Bateni +1Expert Load Balancing Mixture-of-Experts Models
Google Research · University of Southern California
WISERouter: LLM Routing with Workload Budget Constraint
Jul 26, 2026Yifei Li, Zihui Gao, Laks V. S. LakshmananLLM Routing Contextual Bandits
The University of British Columbia

Sep 5, 2026J/K move · Enter open · S save

Online Learning with LLM Experts from Limited Feedback

Wang Wei, Soumyabrata Pal, Koyel Mukherjee, Franck Dernoncourt+3

Virginia Tech · Adobe Research

LLM Routing Multi-Armed Bandits Linear Contextual Bandits

Open paper AskPDF arXiv

We study adaptive routing of prompts to large language model (LLM) experts to maximize response quality in an online setting with limited feedback. We formulate it as a bandit problem with

K

actions that represent experts and

d

features that encode prompts, over a horizon of

T

rounds. We propose algorithms that strategically select and observe rewards to minimize regret. In the full-information setting, we achieve a regret of

\tilde{O}(d T / \sqrt{m})

, while in the bandit setting we achieve

\tilde{O}(d T \sqrt{K / m})

, where

m \ll T

is a budget on feedback. Our experiments show that we efficiently learn high-quality routing strategies across diverse LLMs from limited feedback.

Abstract

Blackwell Approachability

Explore similar work

Online Learning with LLM Experts from Limited Feedback

BRANCH-MoE: Balance-Aware Tree Routing for Large Embedding Models

WISERouter: LLM Routing with Workload Budget Constraint