Skip to content

Coverage-Maximizing Multinomial Subset Routing under Operational Constraints

Aug 2026 · 0 citations · 49 references
Computer Science

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.

View source

Similar papers

Sep 2026

Online Stochastic Allocation with Increasing Returns

We study online allocation with increasing returns, where an uncertain number of customers arrive sequentially and can be irrevocably assigned to any product with remaining capacity. Each assignment earns a base reward plus a bonus that is nondecreasing in the number of previous assignments to the same product. Prior w...

Shuo Sun, Yun-Duan Lin · 0 citations
Preprint Aug 2026

Reoptimization Algorithms for Contextual Bandits with Knapsack Constraints

A natural and simple extension of the Upper-Confidence-Bound (UCB) family of algorithms is proposed and it is shown that by taking advantage of re-optimization, the algorithm achieves an average regret of $O(\frac{(\ln T)^3}{T})$ where $T$ is the horizon length.

Zhen Xu · 1 citation
#machine learning Preprint Sep 2026

Online Learning with LLM Experts from Limited Feedback

This work studies adaptive routing of prompts to large language model experts to maximize response quality in an online setting with limited feedback and proposes algorithms that strategically select and observe rewards to minimize regret.

Wei Wang, Soumyabrata Pal, Koyel Mukherjee et al. · 1 citation
Preprint Sep 2026

Online Resource Allocation with Replenishable Budgets

This work develops a dual-based algorithm that recovers best-of-both-worlds guarantees for standard ORA when the replenishment factor $\beta = 0$, and improves them when $\beta>0$.

Eleonora Fidelia Chiefari, F. Stradi, A. Marchesi · 0 citations
#artificial intelligence Preprint Sep 2026

Drift-Aware LLM Routing with Sparse Contexts and Shared Budgets

This work proposes Drift-Aware Sparse Routing (DRS), a nonstationary sparse contextual routing with multiple knapsack constraints and an optional shadow-audit stream that evaluates a small fraction of prompts on several models.

Cheung-Hao Lee, Patrick Wong · 0 citations
#machine learning Preprint Sep 2026

Dynamic Regret in Online Convex Optimization with Indicator Switching Costs

A meta-learning framework: a set of randomized lazy FTRL base learners restarted at dyadic time scales, aggregated by a movement-aware master that mixes their proposal densities and samples actions via maximal coupling of consecutive mixtures is proposed.

N. Mhaisen, George Iosifidis · 1 citation

Related blog posts

MIT News · Artificial Intelligence Nov 17, 2026

Learning the language of machine learning

By studying the computational foundations of language learning, Associate Professor Jacob Andreas builds intelligent systems that can communicate effectively with humans.

Microsoft Research Blog Nov 16, 2026

TokenEconomizer: Learning from Experience to Make AI Coding Agents More Efficient

AI coding agents are increasingly help developers fix bugs and build features largely on their own, but every interaction with their models consumes tokens. In each session, an agent sends instructions, tool descriptions, and session history to its model. Most efforts to reduce this cost focus on individual tasks. Yet developers return to the same […] The post TokenEconomizer: Learning from Experience to Make AI Coding Agents More Efficient appeared first on Microsoft Research.

We use cookies to run the site and, with your consent, for analytics and to show ads. See our Cookie Policy.