acceptodds
Under review as a conference paper at ICLR 2027

Batched Combinatorial Semi-Bandits Problem

11 views

Abstract

In this paper, we study stochastic combinatorial semi-bandits with batched feedback, referred to as the batched combinatorial semi-bandit problem. For linear reward functions, Kim et al. (2025) showed that O(mloglogT) batches are sufficient to achieve near-optimal worst-case regret, where m is the number of base arms, and T is the time horizon. We propose SE-BC, which achieves near-optimal worst-case regret for general non-linear reward functions while removing the factor m from the batch complexity. We also prove a matching lower bound showing that any algorithm attaining worst-case optimal regret must use at least Ω(loglogT) batches. Therefore, the batch complexity of SE-BC is optimal up to constant factors. Simulation results show that SE-BC achieves lower regret while using fewer batches.

Primary area:
reinforcement learning
Keywords:
Combinatorial multi-armed bandits, batched feedback, regret bounds.

Reviews

Among:
Shape:
1234this paper, Top 49%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.33 over 3 reviews, above 51% of the others.
Reviewer_aLTEOpenReview ↗
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-α\alpha-regret of O~(κmkT)\widetilde O(\kappa\sqrt{mkT}), using O(log⁡log⁡T)O(\log\log T) batches. A matching Ω(log⁡log⁡T)\Omega(\log\log T) 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
  1. Improved regret–batch trade-off. SE-BC achieves near-optimal worst-case regret using only O(log⁡log⁡T)O(\log\log T) batches, improving upon the O(mlog⁡log⁡T)O(m\log\log T) batch complexity of prior work. The analysis also extends to nonlinear rewards under monotonicity and additive smoothness, making the result more applicable.
  2. Matching lower bound. The paper establishes an Ω(log⁡log⁡T)\Omega(\log\log T) 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
  1. 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.
  2. 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

W1. Clarify the computational limitations of Algorithm 1, the correctness of the greedy procedure in Appendix C, and whether it was used in the experiments.

We thank the reviewer for this concern. For more details, please see W1 & Q1 & Q2 to Reviewer NdSE.

W2 & Q1. Whether the multi-scale dyadic score is necessary for controlling estimation error?

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))O(\log(2k)) thresholds per batch, there are at most O(mlog⁡(2k))O(m\log(2k)) events that can change the scores. In contrast, the simpler weights (Ni+1)−1/2(N_i+1)^{-1/2} change after every sample.

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.

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

This paper proposed the SE-BC algorithm for Combinatorial Multi-Armed Bandits and proved that the algorithm achieves optimal regret with a batch complexity of O(log⁡log⁡T)O(\log\log T). The author also proved that the lower bound on the batch complexity for this problem.

Critical strengths
  1. The problem studied in this paper has practical significance: reducing feedback batches is suitable for deployment-constrained combinatorial decision scenarios. This paper also considered monotone nonlinear rewards.

  2. The exploration strategy has certain technical value. Dyadic deficiency relies only on counts and can adjust sampling allocation when there is no new reward feedback.

Critical weaknesses
  1. The regret upper bound in Theorem 1 contains the term Δmax⁡\Delta_{\max}. When the rewards are linear, Δmax⁡=k\Delta_{\max}=k, and the regret upper bound is O(kmT)O(k\sqrt{mT}). This is inconsistent with the regret bound O(kmT)O(\sqrt{kmT}) claimed in the paper.

  2. The author argues that the lower bound for the classic batched MAB does not apply to combinatorial semi-bandits. However, in fact, the batched MAB is itself a special case of CMAB. Let I={{1},...,{m}},k=1\mathcal{I}=\{\{1\},...,\{m\}\}, k=1 and rμ({i})=μir_{\mu}(\{i\})=\mu_i. This reduces to the standard MAB problem. Therefore, any batched CMAB algorithm that aims to achieve minimax-optimal regret over all problem instances considered in the paper must also provide the corresponding guarantee on this subclass. However, [1] has established that achieving minimax-optimal regret requires at least Ω(log⁡log⁡T)\Omega(\log\log T) batches. Therefore, the lower bound may not be appropriate to present as a previously unknown result.

  3. In Section 3, the paper defines regret in terms of pseudo-α\alpha-regret, whereas the lower-bound analysis switches to the special case of α=1\alpha = 1. This weakens the scope of the paper's conclusions, as the lower-bound proof may not necessarily extend to the case where α<1\alpha < 1.

[1] Zijun Gao, Yanjun Han, Zhimei Ren, and Zhengqing Zhou. Batched multi-armed bandits problem.Advances in Neural Information Processing Systems, 32, 2019.

Questions for authors
  1. Could the dependence on Δmax⁡\Delta_{\max} be removed by modifying the algorithm or refining the proof?

  2. Does the current lower bound still hold when considering pseudo-α\alpha-regret?

  3. [2] (Section 5) also considers the general reward setting. Although its setting differs from that of this paper, it seems possible to adapt the proposed algorithm to the batched setting. Could the authors provide some discussion on this possibility?

[2] Kim, J. H., Vojnovic, M., & Oh, M. H. Oracle-Efficient Combinatorial Semi-Bandits. Advances in Neural Information Processing Systems, 38, 2026.

3 comments

W1 & Q1. Clarification on the initialization term.

We thank the reviewer for identifying this. Please see W2 & Q3 to Reviewer NdSE.

W2. Clarify the additional contribution of the proposed batch lower bound beyond the existing Ω(log⁡log⁡T)\Omega(\log\log T) lower bound for batched MAB, a special case of CMAB.

We thank the reviewer for this comment. We agree that the existing batched MAB lower bound implies an Ω(log⁡log⁡T)\Omega(\log\log T) batch-complexity lower bound for the general CMAB class by considering the special case k=1k=1. However, this does not characterize the regret–batch tradeoff for general combinatorial action sizes.

In particular, when k>1k>1, each super-arm pull can provide observations from up to kk base arms, rather than a single observation as in MAB. This additional feedback may allow the learner to identify good actions with fewer adaptive batches. Thus, it is not immediately clear whether the Ω(log⁡log⁡T)\Omega(\log\log T) batch complexity remains necessary for genuinely combinatorial instances with larger kk.

A similar distinction arises in the fully sequential setting. While the classical MAB lower bound is Ω(mT)\Omega(\sqrt{mT}), Kveton et al. (2015) established an Ω(mkT)\Omega(\sqrt{mkT}) lower bound for stochastic combinatorial semi-bandits. This illustrates that lower bounds obtained from the MAB special case do not necessarily capture the dependence on kk.

Our lower bound goes beyond the MAB reduction by characterizing the joint dependence on mm, kk, TT, and MM, showing how combinatorial feedback affects the regret–batch tradeoff.

W3 & Q2. Whether the lower bound can extend from α=1\alpha=1 to pseudo-α\alpha-regret with α<1\alpha<1?

We thank the reviewer for the question. For α<1\alpha<1, lower bounds on pseudo-α\alpha-regret are less natural. Because αOPT\alpha\mathrm{OPT} is only an approximation guarantee, rather than an intrinsic limit on achievable reward. In many practical CMAB applications, given θ\theta and SS, we can evaluate rθ(S)r_\theta(S). With access to the feasible action family and sufficient computational resources, we can therefore obtain an exact optimizer through exhaustive enumeration. Thus, α\alpha is introduced to address computational limitations rather than the inherent statistical difficulty of learning. Our lower-bound focuses on the statistical difficulty imposed by batched feedback, so we use standard regret.

For upper-bound analysis, however, pseudo-α\alpha-regret is appropriate because exact offline combinatorial optimization can be NP-hard, and approximation oracles can reduce the computational burden. Following the classical CMAB framework of Chen et al. (2013, 2016), we use pseudo-α\alpha-regret for upper-bound analysis and standard regret for lower-bound analysis.

Q3. Whether the general-reward algorithm in Section 5 of Kim et al., (2025), can be adapted to the batched setting?

We thank the reviewer for this comment. The algorithms in Section 5 of Kim et al. (2025) can be adapted to batched feedback by treating intervals between successive updates as batches. For general reward functions bounded in [0,Λ][0,\Lambda], AROQ achieves O~(ΛmkT)\widetilde{O}(\Lambda\sqrt{mkT}) regret with O(mlog⁡log⁡(Tk/m))O(m\log\log(Tk/m)) batches, while SROQ achieves O~(ΛkmT)\widetilde{O}(\Lambda k\sqrt{mT}) regret with O(log⁡log⁡T)O(\log\log T) batches. Our SE-BC achieves a leading regret term of O~(κmkT)\widetilde{O}(\kappa\sqrt{mkT}) with O(log⁡log⁡T)O(\log\log T) batches, removing AROQ's additional batch factor mm and improving SROQ's dependence on kk under comparable reward scales. However, these results are not directly comparable because the assumptions differ: Kim et al. (2025) assume independent base-arm outcomes and bounded, coordinatewise monotone reward functions, whereas we allow correlated outcomes but require expected rewards to depend only on the mean vector and satisfy monotonicity and additive smoothness.

Thanks for the author's reply. The author resolved most of my confusion, except for the lower bound. The kk observations within each path are identical copies of a single Bernoulli outcome. Since this construction is equivalent to a d=m/kd=m/k-armed batched MAB with regret scaled by kk. Therefore, I think it cannot be shown that there are new difficulties in combinatorial information theory. Could the authors clarify the additional technical contribution beyond this reduction and the existing adaptive-grid argument?

We thank the reviewer for this observation. We acknowledge that our lower bound builds upon established techniques from batched MAB. However, we believe that the significance of our result lies in establishing a regret lower bound for batched CMAB parameterized by mm, kk, TT, and MM. The bounded Bernoulli setting restricts how the reward gaps can scale with the problem parameters, so the Gaussian bound of Gao et al. (2019) cannot be directly rescaled to obtain our result. We therefore jointly recalibrate the comparison grid and reward gaps in their analysis to establish the stated bound.

We will clarify this point in the revision. We also agree that further investigating the additional information theoretic challenges arising from general combinatorial structures is an important direction for our future research.

Reviewer_NdSEOpenReview ↗
Rating
3(+1)
Confidence
2
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper studies stochastic combinatorial semi-bandits with batched feedback. In this setting, the learner selects a super arm consisting of at most kk base arms from a collection of mm base arms, but the observations become available only at the end of each batch. The goal is to achieve low regret while using a small number of feedback batches.

The authors propose SE-BC, an elimination-based algorithm that uses O(log⁡log⁡T)O(\log\log T) batches. The main idea is to control exploration through a dyadic deficiency score defined for each super arm. This score aggregates the sampling deficits of its constituent base arms and can be updated using pull counts without receiving new reward observations. At the end of each batch, the algorithm updates confidence bounds and eliminates super arms whose optimistic rewards fall below a certified benchmark.

Under monotonicity, additive smoothness, and access to an offline α\alpha-approximation oracle, the paper establishes a high-probability pseudo-α\alpha-regret bound containing a term of order O~(κmkT)\widetilde O(\kappa\sqrt{mkT}), together with an additional reward-range-dependent term. The authors also provide a lower bound showing that Ω(log⁡log⁡T)\Omega(\log\log T) batches are necessary for near-optimal ordinary regret under the stated conditions. Experiments on Top-K selection and maximum spanning trees demonstrate promising empirical performance.

Critical strengths
  1. The paper studies a meaningful tradeoff between regret and feedback frequency. Batched feedback is relevant when observations are collected after a campaign or when frequent interactions with the environment are costly. Achieving strong regret guarantees with fewer batches is therefore an interesting theoretical and potentially practical objective.

  2. The dyadic deficiency score is an interesting algorithmic contribution. Although reward estimates cannot be updated within a batch, pull counts remain available. The proposed score uses this information to identify super arms that still require exploration while accounting for the fact that one action can sample several base arms simultaneously. The analysis connects these scores to confidence uncertainty and bounds the number of exploration rounds through a charging argument.

  3. The upper-bound framework accommodates nonlinear reward functions and approximate offline optimization. The assumptions of monotonicity and additive smoothness allow the analysis to extend beyond linear rewards, while the use of an α\alpha-approximation oracle is relevant when exact combinatorial optimization is computationally difficult. The model also permits correlations between base-arm outcomes within the same round.

  4. The experimental results are encouraging. SE-BC achieves lower average regret than CUCB and AROQ on both tested problems while using only five batches. The experiments are averaged over 100 independent runs, with the same mean vector shared across algorithms in each run and standard deviations reported.

Critical weaknesses
  1. The computational efficiency of the proposed algorithm is not fully established. Algorithm 1 explicitly scans the active super-arm family, whose size may be exponential in mm. Although Appendix C proposes a greedy procedure to avoid enumeration, its pruning rule does not appear sufficient to preserve the theoretical guarantee. A greedy completion whose optimistic reward exceeds the threshold certifies that an active completion exists. However, a greedy completion below the threshold does not imply that every possible completion is below it. Consequently, the procedure may discard a prefix that has a valid active completion.

    Moreover, Appendix C does not explain how to efficiently find an active super arm with deficiency score at least one, or certify that all active super arms have scores below one. This condition is required by the regret analysis. Therefore, while the regret bound may hold for the exhaustive algorithm, the paper does not establish that the same guarantee is retained by the proposed efficient implementation.

  2. The near-optimal regret claim requires further qualification. The bound in Theorem 1 contains a term of order O~(Δmax⁡mT)\widetilde O(\Delta_{\max}\sqrt{mT}), in addition to O~(κmkT)\widetilde O(\kappa\sqrt{mkT}). For standard linear rewards, κ=1\kappa=1 and Δmax⁡=k\Delta_{\max}=k, so the additional term becomes O~(kmT)\widetilde O(k\sqrt{mT}), which has worse dependence on kk than the target rate.

    Although the paper identifies this as an initialization term, its stated bound also grows as T\sqrt T, so it cannot automatically be treated as negligible. This does not show that the algorithm itself necessarily incurs larger regret, but the stated theorem does not establish the advertised dependence on all parameters without further restrictions.

  3. The experimental evaluation is limited to two small synthetic instances with linear rewards, exact oracles, and a single time horizon. As a result, the experiments do not evaluate the nonlinear-reward and approximate-oracle settings emphasized by the theoretical framework, or demonstrate scalability to larger problems. In addition, SROQ is not included, although it already uses O(log⁡log⁡T)O(\log\log T) batches and is a particularly relevant baseline for assessing the proposed regret–batch tradeoff. Experiments varying mm, kk, and TT would help clarify the practical significance of the claimed improvements.

Questions for authors
  1. In Appendix C, how can a greedy completion below the elimination threshold justify discarding a candidate prefix? Could another completion of the same prefix remain active? Can the authors establish that the proposed implementation preserves the conditions required by Theorem 1?

  2. Using the oracle in Assumption 3, how can the algorithm efficiently find an active super arm with deficiency score at least one, or certify that no such super arm exists, without enumerating the active family?

  3. For linear rewards, how should the Δmax⁡mT\Delta_{\max}\sqrt{mT} term be reconciled with the claimed O~(mkT)\widetilde O(\sqrt{mkT}) regret when Δmax⁡=k\Delta_{\max}=k? Can the initialization analysis be improved, or can the parameter regime in which the near-optimality claim holds be stated explicitly?

  4. Could the authors include comparisons with SROQ and evaluations with nonlinear rewards and approximate oracles? It would also be helpful to vary mm, kk, and TT to assess scalability and the dependence on super-arm size.

3 comments

W1 & Q1–Q2. Clarify the computational limitations of Algorithm 1 and the correctness issues in Appendix C. Discuss whether greedy procedure can efficiently implement exploration while preserving the regret guarantee.

We thank the reviewer for identifying this error. Algorithm 1 and our experiments use enumeration for active-family search and elimination, whose cost can be exponential in mm. The efficiency claim in Appendix C is incorrect in general: greedy pruning may discard prefixes with active completions, and the procedure does not guarantee finding an active action with deficiency score at least 11 whenever one exists. We apologize for this error. For linear rewards with I={S⊆[m]:∣S∣=k}\mathcal{I}=\{S\subseteq[m]:|S|=k\}, we establish a polynomial-time greedy variant with the same regret guarantee. We have removed the unsupported general efficiency claim from the main text and revised Appendix C to present this special-case algorithm and its analysis.

W2 & Q3. Clarification on the initialization term.

We thank the reviewer for this suggestion. Following classical CMAB literatures (Chen et al. 2016, Kim et al. 2025), we treat Δmax⁡\Delta_{\max} as a constant independent of mm, kk, and TT. Under this condition, the initialization term becomes O~(mT)\widetilde O(\sqrt{mT}). Therefore, our algorithm achieves the claimed near-optimal regret rate. Moreover, we have improved the initialization regret from O~(Δmax⁡mT)\widetilde{O}(\Delta_{\max}\sqrt{mT}) to O~(Δmax⁡T)\widetilde{O}(\Delta_{\max}\sqrt{T}), bringing it in line with existing results for classical batched bandits (Gao et al., 2019). We have incorporated this improvement into the revised manuscript.

W3 & Q4. Add experiments with nonlinear rewards and approximate oracles, compare with SROQ, and vary mm, kk, and TT.

We thank the reviewer for this suggestion. We have conducted the requested experiments and included the results in the revised paper.

For linear rewards, SE-BC achieves the lowest cumulative regret compared with CUCB, AROQ, and SROQ on both Top-K and MST instances. For nonlinear rewards, SE-BC also achieves lower regret than CUCB and Thompson Sampling on PMC instances. Comparing greedy and exact oracles, we find that greedy significantly reduces computational cost while achieving similar rewards and nearly identical regret. Finally, experiments varying mm, kk, and TT show that SE-BC maintains its regret advantage across different problem sizes and time horizons.

Dear Reviewer NdSE,

Thank you once again for your valuable comments on our submission.

In our rebuttal, we have carefully responded to your concerns by (i) clarifying the computational limitations, revising Appendix C, and providing a polynomial-time algorithm for the Top-K setting with the same regret guarantee; (ii) improving the initialization regret analysis; and (iii) conducting additional experiments with nonlinear rewards, approximate oracles, comparisons with SROQ, and varying problem sizes. We have incorporated these improvements into our revised manuscript.

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. Your response resolves my concern. I will increase the rate from 2 to 3.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.