acceptodds
Under review as a conference paper at ICLR 2027

Multinomial Subset Routing with Sum-Max Rewards and Operational Constraints

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 over experts, samples an expert independently times from , 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 objective regret and constraint violation. We also quantify the approximation gap induced by a linear surrogate, and evaluate the approach on a real-world crowdsourcing dataset.

Primary area:
learning theory
Keywords:
Online Learning, Bandit Learning, Combinatorial Bandits, Constrained Online Learning, Expert Routing

Reviews

Among:
Shape:
1234this paper, Top 30%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.67 over 3 reviews, above 70% of the others.
Reviewer_LTjTOpenReview ↗
Rating
3(+1)
Confidence
3
Informativeness
2
Presentation
2
Soundness
1
Read review
Paper summary

This paper introduces Multinomial Subset Routing (MSR), an online expert routing framework with sum-max rewards, aggregate bandit feedback, and long-term operational constraints. The authors propose OMD-Approachability, combining online mirror descent with Blackwell approachability, and establish O(T−1/2)O(T^{-1/2}) reward regret and constraint violation bounds. Experiments on a crowdsourcing dataset demonstrate promising reward and feasibility performance.

Critical strengths

The paper addresses a relevant problem by jointly considering complementary expert contributions, limited feedback, and operational constraints. And the combination of OMD and approachability is technically interesting. The analysis of the approximation gap between the surrogate and original benchmarks is also valuable.

Critical weaknesses
  1. Potential invalidity of the main theoretical guarantee. The paper defines the original operational constraints as two-sided intervals, but the proof of Lemma 2 only establishes distance-transfer bounds for one-sided constraints. The stated guarantee does not appear to hold for general two-sided intervals, raising serious concerns about the validity of Theorem 2.

  2. Insufficient validation of the theoretical claims. The empirical regret is measured relative to the final learned policy rather than the hindsight-optimal feasible benchmark. Moreover, the experimental implementation differs from the theoretically analyzed algorithm. Consequently, the experiments do not directly substantiate the claimed convergence guarantees.

Questions for authors
  1. Could the authors clarify whether Lemma 2 and Theorem 2 apply to general two-sided constraints, and provide the necessary assumptions or a corrected proof?

  2. Could the authors explain the discrepancy between the theoretical regret definition and the empirical evaluation, and justify the batched implementation?

2 comments

Thank you for identifying these issues. We have uploaded a revised manuscript and the experimental code. Changes are highlighted in blue and include corrected proofs, additional theoretical results, and expanded experiments. All section, figure, and line references below refer to the revised manuscript.


Do Lemma 2 and Theorem 2 apply to general two-sided constraints?

Thank you for this comment. Appendix B.1 now provides this argument. The coordinate-wise bounds control both lower- and upper-bound violations, yielding the distance-transfer inequality in Lemma 2. We also corrected the support function used in the approachability update, so that both sides of the constraints are handled consistently.

The empirical regret uses the final learned policy rather than the hindsight-optimal feasible benchmark.

We replaced the final-policy reference with a fixed full-horizon hindsight-optimal policy over the surrogate-feasible set with the exploration floor (Section 6.2; Appendix A.2). Figure 1 now reports the reward gap to this benchmark.

the discrepancy between the theoretical regret definition and the empirical evaluation, and justify the batched implementation?

We now explicitly compare B=1B=1 and B=10B=10 (Section 6.3). Larger batches slow initial learning but give similar late-stage rewards and preserve feasibility across all seeds for OMD-Approachability. We use batching to reduce computational cost and average out noise in aggregate reward feedback, reducing the variance of the gradient estimates.

I appreciate the authors' thorough response. The revised manuscript and the added appendix (B.1) clarify how the theoretical results apply to general two-sided constraints.

I am also pleased to see that the empirical evaluation now uses a proper hindsight-optimal benchmark, which resolves my previous concern about the discrepancy between theory and experiments. The added analysis on the batched implementation is helpful.

I am willing to increase my score.

Reviewer_jh5SOpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper studies Multinomial Subset Routing (MSR), where an online learner routes tasks by sampling expert subsets from a learned distribution under aggregate sum-max reward feedback and two-sided long-run activation constraints. Using a linear surrogate to handle nonlinear activation probabilities, the authors propose OMD-Approachability, which combines Online Mirror Descent with Blackwell’s Approachability, and prove sublinear reward and constraint regret alongside an analysis of the surrogate approximation gap and experiments on a crowdsourcing dataset.

Critical strengths

The algorithmic logic is clear, and the paper explicitly quantifies the approximation gap between the surrogate benchmark and the original nonlinear benchmark. The paper is well-structured, and the theoretical proofs are rigorous.

Critical weaknesses

The multinomial sampling-with-replacement scheme used in this paper appears to be largely a mathematical compromise to borrow the concavity results from Pasteris et al. (2024). It is unnatural in practical routing scenarios that require fixed-size subsets, and the paper lacks comparisons with sampling without replacement or dependent rounding methods. In particular, if an expert is assigned a high probability weight, the same expert can easily be drawn multiple times within a single task, resulting in fewer than MM distinct experts in the selected team. Even before introducing the linear surrogate, the original benchmark OPTori\text{OPT}_{\text{ori}} restricts the comparator to subsets generated by repeated independent draws from a single probability vector over experts, rather than arbitrary distributions over subsets of size at most MM. Because a single multinomial distribution cannot represent deterministic teams of complementary specialists without incurring high collision probabilities, the benchmark itself can be strictly suboptimal compared to standard combinatorial bandit benchmarks. Assumption 1 (qi∗≥γq_i^* \ge \gamma for all i∈[K]i \in [K]) may be overly restrictive. Although needed to bound the variance of the gradient estimator, the optimal static benchmark in realistic routing or crowdsourcing scenarios with K=50 or more experts is typically sparse.

Questions for authors

Relaxing Assumption 1: Instead of assuming the optimal benchmark satisfies qi∗≥γq_i^* \ge \gamma for all i∈[K]i \in [K], could the authors bound the truncation bias between the unrestricted optimum on ΔK\Delta_K and the restricted optimum on {q∈ΔK:qi≥γ}\{q \in \Delta_K : q_i \ge \gamma\}, and then tune γ\gamma as a function of TT? Missing Appendix F in Table of Contents: On Page 12 ("Appendix Contents"), Appendix F (Suboptimality of the Surrogate-Restricted Benchmark: Proofs and Additional Bounds) is missing from the bulleted list. Contextual notation in Algorithm 2: In Algorithm 2 (Page 18, Step 4b), ut−1=∑i=1Kqt−1,i(x)ciu_{t-1} = \sum_{i=1}^K q_{t-1,i}^{(x)} c_i uses the current context x=xtx = x_t instead of the context xt−1x_{t-1} played at round t−1t-1. As noted in Remark 2, the shared dual update must use the actually played distribution qt−1=qt−1(xt−1)q_{t-1} = q_{t-1}^{(x_{t-1})}.

2 comments

Thank you for these constructive comments. We have uploaded a revised manuscript and the experimental code. Changes are highlighted in blue and include corrected proofs, additional theoretical results, and expanded experiments. All section, figure, and line references below refer to the revised manuscript.


Missing comparisons with sampling without replacement or dependent rounding; repeated draws may yield fewer than (M) distinct experts.

Theory: We added a “Multinomial sampling” paragraph on page 3 explaining that sampling with replacement achieves a (1-e^{-1}) approximation relative to the optimal subset when only the M-cardinality constraint is imposed. Sum-max rewards are monotone submodular, and this factor is optimal in general for polynomial-time algorithms, since this class includes Maximum Coverage.

Experiments: We added the heuristic baseline “OMD no-replace,” which uses sequential weighted sampling without replacement and adapts the gradient estimator accordingly (Appendix A.3; results in Section 6.3).

The original benchmark restricts the comparator to multinomial policies rather than arbitrary distributions over subsets of size at most M.

Thank you for this comment. We strengthened Corollary 1 to compare against arbitrary distributions over subsets of size at most M, under upper-only constraints. This broader benchmark, (OPT_{\mathrm{set}}), is defined in Eq. (10).

Assumption 1 may be overly restrictive. Could the authors bound the truncation bias and tune the exploration floor?

Thank you for this comment. We added Section 5.3 to bound this truncation bias and replace Assumption 1 with the weaker requirement that a surrogate-feasible reference distribution with full support exists. Tuning the exploration floor then yields a slightly weaker average reward regret bound of (O(T^{-1/3})).

The optimal static benchmark in realistic routing or crowdsourcing scenarios is typically sparse.

We agree that optimal routing distributions may be sparse; the analysis in Section 5.3 now accommodates this possibility. In our motivating applications, however, concentrating traffic on a small pool of experts can overload those experts while leaving capacity elsewhere unused. This motivates imposing two-sided constraints on long-run activation rates alongside the sum-max objective.

Missing Appendix F in Table of Contents.

Thank you. We have added it.

Contextual notation in Algorithm 2.

Thank you. We corrected the notation so that the shared dual update uses the distribution actually played at each round, and updated the proof of Corollary 2 accordingly.

Thank you again for your feedback. When you have a chance to look over the revised manuscript, could you let us know if you have any remaining questions or concerns? We’d be happy to discuss them further.

Reviewer_MrkgOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

This paper studies online routing to subsets of experts under aggregate bandit feedback. They propose to combine online mirror descent for the concave reward with Blackwell approachability for a linear surrogate of the operational constraints. They establish O(T^-.5) average regret and constraint violation bounds.

Critical strengths

The paper is overall well-written. The problem is interesting.

The proposed combination of OMD and Blackwell approachability is intuitive, and the paper makes the connection and present the theoretical guarantees.

Critical weaknesses

The main two challenges to motivate the work are the nonlinearity of the constraints which is resolved by linearisation and having aggregated reward of the sampled subsets which is resolved using the concavity of the expected sum-max reward from (Pasteris et al., 2024). Thus, my main concern is the contribution level. The reward structure and its concavity and gradient structure are taken from existing sum-max bandit work, while the constraint-control component are form online convex optimization and approachability techniques. The paper should clearly state which parts of the algorithm and analysis are novel beyond combining these ingredients. Moreover, the theoretical results are based on the surrogate formulation and is limited by that. Although the paper provides bounds on the approximation gap, these do not establish that the surrogate is sufficiently tight in general.

The experimental result does not show evidently that the proposed method is outperforming the existing approaches. The comparison has several baselines but the feedback available to these methods is aggregate team reward, which is assigned to every selected arm as a proxy for its contribution. This approximation may affect the relative performance of the baselines and thus not fair to them although they seem to perform well. The authors should provide stronger evidence of robustness, and include ablations that isolate the contributions of the surrogate constraints and the approachability update.

Questions for authors

See above.

2 comments

Thank you for these constructive comments. We have uploaded a revised manuscript and the experimental code. Changes in the manuscript are highlighted in blue and include corrected proofs, additional theoretical results, and expanded experiments. All section, figure below refer to the revised manuscript.


The paper should clearly state which parts of the algorithm and analysis are novel beyond combining existing ingredients.

We revised the contributions and related work. We credit Pasteris et al. for the reward concavity and gradient structure, and existing work for the approachability framework. Our contributions are the treatment of two-sided nonlinear activation constraints, the surrogate-to-original constraint guarantee, the coupled reward and constraint analysis, and bounds quantifying the losses from surrogate restriction, multinomial sampling, and the exploration floor (Sections 4–5).

The approximation bounds do not establish that the surrogate is sufficiently tight in general.

The revised Section 5.2 clarifies when the surrogate admits meaningful guarantees. Proposition 1 gives a gap bound under a strict-feasibility margin, while the strengthened Corollary 1 establishes a tight (1-(1-1/M)^M) approximation against arbitrary feasible subset distributions under upper-only constraints with a dull action. We do not claim that the surrogate is tight in general.

The experimental result does not show evidently that the proposed method is outperforming the existing approaches.

The previous Figure 3 showed rewards alone and did not show that some methods with higher rewards also violated the constraints. We replaced it with a figure showing both reward and constraint violation. Under tight constraints, OMD-Approachability is feasible across all seeds and achieves higher reward than KL-Projected OMD, which is also feasible throughout. Our conclusions therefore emphasize the reward–feasibility trade-off. For example, although Joint TS-BwK incurs only small violations under tight constraints with (B=10), it is feasible in only 35% of runs.

Assigning aggregate reward to individual arms may disadvantage the baselines.

We now explicitly describe those adaptations as heuristics (Appendix A.3). To address the concern about per-arm proxy assignment, we also added Joint TS-BwK, which updates a joint posterior directly from aggregate subset feedback.

Stronger evidence of robustness and ablations isolating the surrogate constraints and approachability update are needed.

Experiments: We expanded the experiments across constraint levels and batch sizes (B\in{1,10}), using 20 seeds (Section 6.3). We also added KL-Projected OMD, which uses the same surrogate constraints but replaces approachability with direct projection.

Theory: Section 5.2 quantifies the surrogate restriction through Proposition 1 and improved Corollary 1.

Thank you again for your feedback. When you have a chance to look over the revised manuscript, could you let us know if you have any remaining questions or concerns? We’d be happy to discuss them further.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.