- 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 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
-
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.
-
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
-
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?
-
Could the authors explain the discrepancy between the theoretical regret definition and the empirical evaluation, and justify the batched implementation?
2 comments
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.
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.
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.
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.
We now explicitly compare B=1 and B=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.