- Rating
- 2
- Confidence
- 3
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 3
Read review
Paper summary
This paper studies stochastic combinatorial semi-bandits with batched feedback, where super arms are selected but base-arm observations are revealed only at batch end points. The authors propose SE-BC, a successive-elimination algorithm that uses a dyadic deficiency score to guide exploration. Under assumptions, SE-BC achieves near-optimal worst-case pseudo--regret of , using batches. A matching lower bound establishes the order-optimality of the batch complexity for achieving near-optimal regret under the stated conditions. Experiments on Top-K selection and maximum spanning trees show lower regret than CUCB and AROQ with much fewer batches.
Critical strengths
- Improved regret–batch trade-off. SE-BC achieves near-optimal worst-case regret using only batches, improving upon the batch complexity of prior work. The analysis also extends to nonlinear rewards under monotonicity and additive smoothness, making the result more applicable.
- Matching lower bound. The paper establishes an lower bound for achieving near-optimal worst-case regret. Together with the upper bound, this indicates the optimality of the batch complexity under the stated conditions.
Critical weaknesses
- Computational efficiency. Algorithm 1 needs to examine all active super arms, which can be exponentially many. Appendix C proposed a greedy method to avoid this, but it may incorrectly discard valid super arms, since a greedy solution is not necessarily optimal. It is also unclear whether this method is used in the experiments.
- Necessity of the dyadic deficiency score. The proposed dyadic score seems unnecessarily complicated. A simpler score based directly on confidence uncertainty may provide similar theoretical guarantees. The authors should clarify why the multi-scale construction is needed and what advantages it offers. See Questions for Authors for details.
Questions for authors
The dyadic deficiency score is presented as a key technical contribution of the paper. However, I wonder whether the multi-scale construction is necessary for controlling the reward estimation error. For example, consider a simpler score:
\qquad g_\ell=\Theta\left(\sqrt{\frac{mk}{B_\ell}}\right).$$ Similar to the proposed dyadic score, this quantity depends only on pull counts and can be updated within each batch without observing reward. When $score_\ell(S;N)<1$, we have $$\sum_{i\in S}\frac{1}{\sqrt{N_i+1}}<g_\ell.$$ Consequently, \begin{aligned} |r_{\mu'}(S)-r_\mu(S)| \leq \kappa\sum_{i\in S}|\mu_i'-\mu_i| =O\left(\kappa\sqrt{\log(mT/\delta)} \sum_{i\in S}\frac{1}{\sqrt{N_i+1}}\right) =O\left( \kappa\sqrt{\frac{mk\log(mT/\delta)}{B_\ell}} \right), \end{aligned} where the three steps uses smoothness, Hoeffding bound, and plugging in $g_\ell$. This suggests that a simple aggregate uncertainty score is sufficient to establish the desired reward estimation accuracy without introducing multiple sampling scales. Could the authors clarify what additional theoretical advantage the dyadic deficiency score provides over this simpler uncertainty-based score? In particular, why is the multi-scale construction preferred over directly controlling the confidence uncertainty?4 comments
Dear Reviewer aLTE,
Thank you once again for your valuable comments on our submission.
In our rebuttal, we have carefully addressed your concerns by (i) clarifying the computational limitations and the implementation used in our experiments, revising Appendix C accordingly, and providing a polynomial-time algorithm for the Top-K setting with the same regret guarantee; and (ii) explaining the advantages of the dyadic deficiency score in reducing redundant computations.
As the discussion phase is approaching its end, we would greatly appreciate it if you could let us know whether our responses have addressed your concerns, either fully or partially. Should there be any remaining questions or points requiring further clarification, please do not hesitate to let us know.
We sincerely look forward to your feedback.
Thank you for the clarification. My concern is partially addressed. I agree that the dyadic score can reduce score updates. However, fewer score updates do not necessarily translate into fewer optimization-oracle calls, as the simpler count-based score could also benefit from lazy updates. Therefore, the computational advantage of the dyadic construction remains unclear.
Thank you for your follow-up and we add a discussion about this simple and nice idea from Line 297 to Line 300. However, We would like to emphasize that
1: your simple and nice idea share essentially the same idea with ours: using the pull counts of base arms to measure how much exploration a super arm still needs.
2: Although our dyadic score may look more complicated, the underlying idea is actually quite simple and intuitive. Instead of measuring uncertainty directly, we divide exploration into a few levels. At each level, we simply count how many base arms have not yet received enough samples. The final score combines these counts across different levels. Thus, both scores measure the same type of exploration deficiency, but in slightly different ways.
We thank the reviewer for this concern. For more details, please see W1 & Q1 & Q2 to Reviewer NdSE.
We thank the reviewer for this insightful question. We agree that this count-based score can also control the reward estimation error. Both scores share the same idea: using immediately available pull counts to adapt exploration decisions within each batch, without waiting for reward feedback.
However, although the dyadic construction seem to have a more complicated formula, the score is simply a sum of inverse exploration scales. As more samples are collected, fewer scales contribute to the score, reflecting more sufficient exploration. Moreover, this multi-scale construction reduces redundant score computations. The dyadic weights decrease only when pull counts cross prescribed thresholds, so action scores remain unchanged between threshold crossings and need not be recomputed after every pull. Since each arm crosses at most O(log(2k)) thresholds per batch, there are at most O(mlog(2k)) events that can change the scores. In contrast, the simpler weights (Ni+1)−1/2 change after every sample.