Source-linked AI summary
Coverage-Maximizing Multinomial Subset Routing under Operational Constraints
Quan Zhou, Yiyan Huang
TL;DR
Online subset selection with winner-takes-all rewards and multiple operational constraints is not addressed by prior bandit methods under aggregate-reward feedback. The paper proposes OMD-Approachability and shows sublinear reward regret and constraint violation with feasibility guarantees, including competitive empirical performance.
Problem
Prior work does not address online subset selection with sum-max rewards and multiple operational constraints under bandit feedback, where only aggregate reward is observed.
Method
OMD-Approachability combines online mirror descent with approachability constraints and uses surrogate constraint reformulation to handle non-convex operational constraints.
Results
The method achieves sublinear regret in reward and constraint violation with provable feasibility guarantees, while maintaining competitive reward and feasibility on a real dataset.
Takeaways & Limitations
The framework covers constrained winner-takes-all routing across specialist ensembles, crowdsourcing, advertising, and contextual decision settings.
Takeaways & Limitations
The analysis assumes a condition preventing gradient estimates from exploding when routing probabilities become too small.
Abstract
from arXiv · showhide
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.
1 Introduction
The paper introduces Multinomial Subset Routing for winner-takes-all expert consultation under bandit feedback, where routing must maximize coverage while satisfying long-term operational constraints. It proposes OMD-Approachability, extends the framework contextually, and validates competitive reward with feasibility on real-world data.
- Problem setting: MSR samples experts from a multinomial policy, forming routed subsets whose quality depends on the best-performing consulted specialist rather than additive contributions.The motivating application is ensemble consultation among specialized clinical models, with only aggregate reward observed after consultation.
- Operational constraints: The learner must maximize clinical coverage while ensuring specialties are consulted sufficiently often and computational resources remain balanced across servers.These requirements make a fixed deterministic subset inadequate for long-term operational needs.
- Contributions: The paper formulates online subset selection with sum-max rewards and multiple operational constraints under bandit feedback, a setting prior work does not address in full.Existing sum-max submodular bandits omit operational constraints, whereas knapsack-constrained bandits typically assume linear or modular rewards.
- Contributions: OMD-Approachability combines online mirror descent with approachability constraints to obtain sublinear reward regret and constraint violation, with provable feasibility guarantees.The framework also extends to contextual decisions and achieves competitive reward while maintaining feasibility empirically on a real dataset.
2 Related Works
Related work spans expert routing, constrained bandits, submodular optimization, and K-max or combinatorial bandits. MSR is distinguished by simultaneous subset routing, aggregated winner feedback, and multi-dimensional whole-horizon covering and packing constraints.
- Mixture-of-Experts: Mixture-of-Experts routes each input token to a learned subset of expert sub-networks, while capacity limits and load balancing prevent token dropping or expert collapse.Switch Transformer formalized expert capacity as a hard upper bound on tokens routable to each expert.
- LLM Routing: System-level LLM routing selects one model from a candidate pool per query, trading response quality against inference cost through offline optimization or supervised routing.These approaches use either performance-minus-cost objectives or labels from all candidate models.
- LLM Routing: MSR routes expert subsets simultaneously, observes only aggregated reward, and enforces multi-dimensional whole-horizon covering and packing constraints.The constraints generalize a single cost budget and can encode operational limits or fairness requirements.
- Bandits with Knapsacks: Bandits with Knapsacks study online decisions under resource-consumption constraints, with extensions to contextual, linear, combinatorial, adversarial, and dueling settings.Most approaches use UCB-style algorithms, while recent work also explores Thompson sampling.
- Submodular Maximization with Constraints: Submodular optimization and bandits address constrained subset selection under diminishing returns, with bandit variants restricting feedback to unknown basis weights, marginal gains, or kernel representations.Whole-horizon knapsack constraints couple decisions across rounds, unlike independently enforced per-round budgets.
- K-max Bandits: K-max bandits study maximum-reward subset selection, while combinatorial bandits typically select deterministic super-arms with reward structures often based on selected-arm rewards; MSR instead optimizes a multinomial routing policy.The directly related K-max setting defines per-round reward as the maximum outcome within a selected subset, and prior work is extended with knapsack constraints on action costs.
3 Motivating Examples
The framework is instantiated in three coverage-maximizing bandit applications: medical consultation, crowdsourcing team formation, and online ad allocation. Each uses aggregate feedback for the selected subset while accommodating domain-specific operational constraints.
- Overview: Three applications illustrate the breadth of the coverage-maximizing bandit setting.The applications are medical consultation via mixture-of-expert LLMs, crowdsourcing team formation, and online ad allocation.
- Medical Consultation via Mixture-of-Expert LLMs: Medical consultation selects up to M specialist LLMs from K, observes only aggregate consultation reward, and can impose specialty coverage and GPU load-balancing constraints.The specialists are trained on distinct datasets, while patient feedback evaluates the consultation as a whole rather than individual specialists.
- Crowdsourcing Team Formation: Crowdsourcing platforms assemble teams of up to M workers from K, observe only aggregate project quality, and can enforce wage-budget and group-fairness constraints.Workers are matched to sequentially arriving projects across skill dimensions, while requesters rate completed projects as wholes.
- Online Ad Allocation: Online ad allocation displays up to M ads each round, logs only aggregate slate engagement, and can impose budget and fairness constraints.Ad relevance varies across user-interest categories, and serving logs do not reliably attribute conversions to individual ads shown together.
4 Problem Setup and Notation
The problem studies online subset selection that maximizes cumulative reward while satisfying long-term operational constraints. Routing samples M actions from a multinomial policy, observes bandit reward feedback, and uses a safe linear surrogate to enforce expected cost feasibility.
- Problem parameters: The learner repeatedly selects action subsets to maximize cumulative reward while satisfying long-term operational constraints.The available actions are specialists, with K actions, maximum subset size M, and horizon T.
- Rewards and costs: Each round has a reward set function rt: 2^[K] → [0,1] with rt(∅)=0, while action i incurs known cost vector ci ∈ [0, c̄]^d.The target set Sori is an axis-aligned box constraining the time-averaged loss vector.
- Interaction protocol: At each round, the learner draws M i.i.d. actions from qt, forms the distinct subset At with |At| ≤ M, and observes only rt(At).Reward functions are fixed in advance by Nature but remain hidden from the learner.
- Constraint construction: Because expected costs are concave in qt, the formulation replaces them with a linear surrogate, yielding a convex compact safe inner approximation S of Sori.The construction uses the surrogate Σ_i qt,i ci and truncates the resulting set to a box without changing feasibility or constraint distance.
- Benchmark and performance: The benchmark is the best fixed feasible routing policy in hindsight, and performance is measured by objective regret and constraint regret relative to the original target set Sori.This compares against a routing policy rather than a deterministic subset and states constraint regret using realized costs.
5 Algorithm and Theoretical Guarantees
Algorithm 1 combines online mirror descent with approachability constraints, using a per-round quadratic-program policy and i.i.d. expert draws while a floor assumption stabilizes gradient estimates. Theorems establish sublinear reward and constraint regret, and the contextual extension preserves the constraint guarantee through shared dual updates.
- Theoretical guarantees: Assumption 1 requires a feasible benchmark with an optimal policy satisfying q_i ≥ γ for every expert, preventing gradient estimates from exploding when q_t,i is small.The assumption also ensures the quadratic program remains feasible at every round.
- Algorithm 1: Algorithm 1 uses a rescaled set, an OCO algorithm, cost vectors, floor γ, and learning rate η.The OCO decision set is the unit Euclidean ball.
- Algorithm 1: At each round, the algorithm solves for q_t and draws M experts independently from q_t.The routed subset is formed from these independent draws.
- Theoretical guarantees: Using online gradient descent, both reward and constraint regrets are O(1/√T), and therefore sublinear.The reward and constraint bounds are stated in Theorems 1 and 2, with OGD supplying the required O(√T) OCO regret.
- Contextual extension: In the contextual extension, separate primal iterates are maintained per context while one shared dual variable enforces the aggregate constraint.Only the primal iterate for the observed context is updated, and the contextual algorithm satisfies the same constraint guarantee as Theorem 2.
6 Numerical Experiments
Numerical experiments on the TREC 2010 Crowdsourcing Track dataset evaluate OMD-Approachability under stochastic and regime-switching environments. The results show convergence toward low objective and constraint regret and a strong reward–feasibility trade-off relative to alternative policies.
- Experimental setup: The study uses 677 workers, 2,275 tasks, and 12,863 annotations from the TREC 2010 Crowdsourcing Track dataset.Worker correctness is defined against recorded gold labels, with accuracy computed from binary responses.
- Experimental setup: OMD-Approachability is evaluated with K = 50, M = 5, T = 10,000, five seeds, N ∈ {3, 5}, and stochastic noise concentration κ = 20.The routing distribution is held fixed for B = 10 rounds and updated once per batch via a proximal QP step.
- Regret convergence: Both objective regret R1 and constraint regret R2 decay at the O(n^-1/2) rate predicted by theory, with R1 reaching near-zero by n = 10,000 for both N values.The empirical curves initially lie above the reference and show a short warm-up plateau before descending.
- Reward–feasibility trade-off: Under tight constraints, OMD-Approachability attains 100% feasibility in both stochastic and regime-switching environments while retaining near-optimal reward.TS-BwK is about 95–100% feasible in the stochastic environment, whereas CBwK achieves about 40% feasibility.
- Reward–feasibility trade-off: As constraints relax, feasibility reaches essentially 100% under loose and unconstrained settings, while several methods’ average rewards remain close to 3.0.CBwK remains consistently lower in average reward.
- Regime-switching environment: In the regime-switching environment, OMD-Approachability achieves higher rolling reward than other constraint-aware methods while maintaining full feasibility under tight and loose constraints.CBwK has a persistent reward gap, and TS-BwK is more sensitive to non-stationarity, with lower reward and reduced tight-constraint feasibility.
Appendix Contents
The appendices provide auxiliary lemmas, proofs of Theorems 1 and 2, and a contextual algorithm with a proof of Corollary 2.
- Appendix A contains the auxiliary lemmas.
- Appendix B presents the proof of Theorem 1.
- Appendix C presents the proof of Theorem 2.
- Appendix D contains the contextual algorithm and proof of Corollary 2.
A Auxiliary Lemmas
This section collects supporting lemmas for the proofs, defines the feasible regions and their per-context analogues, and establishes the filtration and measurability framework. It also states a convex-compact-set distance lemma whose proof uses a support-function argument.
- Auxiliary Lemmas: The section collects supporting lemmas used across the proofs and defines the feasible regions used in the analysis.It also references wt as defined in Algorithm 1.
- Auxiliary Lemmas: The feasible regions Fτ and F(x) are defined, along with their per-context analogues.The definition of F(x) replaces the universal condition over t ∈ [τ] with the restriction xt = x.
- Auxiliary Lemmas: The feasible regions are random because the algorithm randomly generates wt.The section introduces a filtration representing the history before sampling At for the measurability argument.
- Auxiliary Lemmas: The filtration Ht−1 contains the algorithm’s weights, policies, sampled actions, and observed rewards through round t−1.It is explicitly defined as the sigma-field generated by w1, ..., wt, q1, ..., qt, A1, r1(A1), ..., At−1, rt−1(At−1).
- Auxiliary Lemmas: By construction, qt and wt are Ht−1-measurable, whereas gt is Ht-measurable.This measurability statement follows directly from the construction of Algorithm 1.
- Auxiliary Lemmas: Lemma 4 considers distance to a convex and compact set and proves the result using the support function.Its proof follows Lemma 13.5 of.
B Proof of Theorem 1
The proof establishes Theorem 1 by showing the comparator remains feasible, deriving a telescoping proximal-optimization inequality, and bounding its stochastic terms. Combining these bounds with the simplex diameter and substituting the resulting value completes the theorem.
- Step 1: Lemma 4 ensures F°⊆F_t for every realization, so q⋆∈F_t almost surely at every round.This follows because every w_t generated by Algorithm 1 satisfies ∥w_t∥≤1.
- Steps 1–2: The proximal optimality condition for q_t+1 is combined with adding and subtracting g_t, then summed over t to obtain a telescoping inequality.The derivation uses the first-order condition from the proximal problem (6).
- Step 2: The final-term bound follows from Lemma 6.6 of [37], with expectations evaluated using the tower property.These steps control the stochastic contribution in the telescoped inequality.
- Step 3: Young’s inequality bounds the first inner-product term, while summing over i cancels the resulting second term against the third term in (9).Expectations are then taken and the bounds are summed over i.
- Step 4: Combining the derived bounds with ∥q⋆−q1∥2 ≤ 2 and substituting the resulting value proves Theorem 1.The final combination takes expectations on both sides of (8) and uses the Euclidean diameter bound of the simplex.
C Proof of Theorem 2
Theorem 2’s proof decomposes constraint regret into sampling and approachability errors. Separate bounds for these terms, followed by taking expectations, establish the result.
- Proof of Theorem 2: Constraint regret is decomposed into sampling error and approachability error using the triangle inequality and Lemma 2.The proof then treats the two terms separately.
- Approachability error: Lemma 5 bounds the average approachability error for Algorithm 1 when its routing policies are generated by an online convex optimization algorithm.Its proof invokes Theorem 13.7 of and the OCO guarantee of A.
- Sampling error: With probability at least 1 −δ, Lemma 6 bounds the sampling error for every coordinate j ∈[d].The argument uses martingale-difference properties and a Gaussian tail bound, with an absolute constant L > 0.
- Proof of Theorem 2: Taking expectations in (10) and applying Lemmas 5 and 6 completes the proof of Theorem 2.The sampling analysis defines the corresponding high-probability event as E(δ).
D Contextual Algorithm and Proof of Corollary 2
Algorithm 2 runs contextual OMD with Approachability constraints by maintaining a separate multinomial policy and gradient state for each context. The proof analyzes each context’s visits as a restricted Algorithm 1 sequence, derives a per-context regret bound, and aggregates the bounds across contexts using Cauchy–Schwarz.
- Algorithm 2: The algorithm uses the unit Euclidean ball B ⊂ R^d as the decision set for the OCO subroutine and sets the step-size constant a = 2.These are the stated inputs and decision-set configuration.
- Algorithm 2: For every context x, it initializes q(x)_i = 1/K, g(x) = 0, and the visit count n(x) = 0.Initialization is performed separately for each context.
- Algorithm 2: At each round, the method updates only the current context’s iterate using its stored gradient, samples M experts independently from q(x), and routes the distinct sampled set.The current context’s state is updated while sampling follows the context-specific multinomial policy.
- Proof of Corollary 2: For each context x, its iterates over T(x) visits evolve exactly as Algorithm 1 on the corresponding subsequence, with proximal parameters η_s(x) = a√s.The proof applies the one-step inequality from Theorem 1 using the context-process history and conditional expectation.
- Proof of Corollary 2: The proof derives the expected regret bound for each context, then sums over contexts and applies Cauchy–Schwarz to complete the result.The per-context analysis uses the same cancellation of inner-product terms as Theorem 1.