提出新型多专家路由框架，兼顾收益与运营约束。
Coverage-Maximizing Multinomial Subset Routing under Operational Constraints
- 用多项式策略随机选专家，替代固定组合选择
- 在带约束的在线学习中实现收益与违规量双优（1/√T）
- 适用于真实众包场景，适合需动态调度的系统
我们提出多专家路由（MSR）框架，在K个专家上进行在线决策。学习者维护一个多项式路由策略，每轮独立采样M个专家，形成去重后的路由子集；奖励仅取决于该子集中表现最佳的专家。这一奖励机制自然出现在专业模型间路由场景，但传统组合强化学习与子集选择方法难以建模，因其通常优化确定性子集且假设奖励可加。在仅有每轮胜出者奖励反馈的条件下，需满足多个长期双向运营约束。我们提出基于在线镜面下降与布莱克韦尔可接近性的算法（OMD-Approachability），理论证明其在奖励与约束违反上均达到O(1/√T)的后悔率。框架在真实众包数据集上得到实证验证。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。