Oracle-Efficient Combinatorial Semi-Bandits

We sincerely thank the reviewer for the thoughtful comments. Below, we provide point-by-point responses to each one.

$\bullet$ It would be interesting to also get log-type regret bounds for this algorithm.

Response: Thank you for your insightful comment. In this work, we focused on the gap-free setting as a foundational step toward oracle-efficient algorithms for combinatorial semi-bandits. Extending our frameworks to derive gap-dependent regret bounds is indeed a valuable direction for future work.

One natural approach would be to incorporate elimination-based strategies, as commonly used in the batched multi-armed bandit literature [14]. However, in the combinatorial setting, elimination becomes more involved due to the need to construct representative actions for each base arm, as described in Line 3 of Algorithm 2. These representative actions allow us to eliminate large sets of suboptimal actions by targeting individual suboptimal base arms. However, pulling representative actions does not guarantee a uniform number of base-arm observations across epochs. This mismatch can introduce inefficiencies and prevent standard elimination techniques from achieving tight gap-dependent bounds, thereby limiting their direct applicability in our combinatorial setting.

Nevertheless, we agree that developing gap-dependent variants within our oracle-efficient framework is a promising and important direction for future research.

$\bullet$ In section 6, why do you use the algorithm of [6] in your baseline when the algorithm of [16] achieves better performance? (Note that the algorithm of [6] is called CUCB, and CMAB is just the name of the problem.) This doesn't make for a fair comparison. It would be interesting to take a slightly larger time horizon to compare the methods better, as your AROQ-CMAB has a better upper bound than CUCB when is large enough.

Response: Thank you for pointing this out. You are absolutely right; we should refer to the algorithm from [6] as CUCB, not CMAB, since CMAB refers to the problem setting rather than the algorithm itself. We will revise the terminology accordingly in the final version.

Regarding the choice of baseline, all benchmark algorithms used in our experiments represent the state-of-the-art for each respective setting. For the linear reward setting, both [6] and [16] analyze the same CUCB algorithm. In fact, [16] refers to it as CombUCB1 (see the second paragraph of their introduction), but the algorithm remains unchanged. This is why we use the same name for the algorithm in both [6] and [16] in Table 1. The main difference lies in the analysis: [16] provides a tighter bound than that in [6], establishing a near-optimal regret of $\widetilde{O}(\sqrt{mdT})$. In our work, AROC-CMAB (Algorithm 1) achieves the same near-optimal regret order (up to logarithmic factors), while significantly reducing oracle complexity -- which is our primary focus.

We agree that evaluating longer horizons could further highlight the benefits of our algorithm.

We will revise the terminology, clarify our choice of benchmarks, and elaborate on additional experiments in the final version.

$\bullet$ For the experiments in the appendix, it is even less clear which algorithms you are talking about. If the readers are not very familiar with the literature on these extensions of CMAB, they won't know where these algorithms are from.

Response: Thank you for the helpful comment. We agree that the appendix could be made clearer for readers who may not be deeply familiar with the literature on CMAB extensions. Regarding baselines, each representing the state of the art in its respective setting, we provide a brief summary here:

• Worst-case linear reward setting: We use CUCB [6, 16] as the benchmark, which applies a standard UCB strategy by computing confidence bounds for each base arm and summing them over the selected actions. This algorithm was introduced in [6] and further analyzed in [16].

• Covariance-dependent setting: We use OLS-UCB-C [26], a covariance-adaptive algorithm that estimates the noise structure online and selects actions optimistically based on this estimation.

• General reward setting: We use SDCB [5], which estimates the reward distributions of individual arms and constructs stochastically dominant confidence bounds for action selection.

We will revise the appendix in the final version to clearly reference the sources of these algorithms and provide brief descriptions to help guide the reader.

$\bullet$ If the time and space permit in the final version of the paper, it would be interesting to have different experiment ratios of $d$ and $m$ to get a better picture of the trade-offs (in particular, the query-cost vs regret between your two methods).

Response: Thank you for the constructive suggestion. We appreciate your point about exploring different ratios of $d$ (number of base arms) and $m$ (action size) to better understand the trade-offs between query cost and regret.

We agree that varying these parameters could reveal interesting regime-dependent behaviors between our two algorithms. In particular, increasing $m$ may widen the regret gap between the methods, while increasing $d$ may amplify differences in oracle adaptivity complexity.

For example, in additional experiments when increasing $d$ from 20 to 30, the synchronized algorithm of SROQ-CMAB (Algorithm 2) demonstrated a substantial advantage in oracle adaptivity complexity. The total adaptivity complexities were: SROQ-CMAB (Algorithm 2): 6, ARQO-CMAB (Algorithm 1): 73, and CUCB: 19,999 -- reflecting the theoretical improvements achieved by the synchronized update mechanism.

When we increased $m$ from 3 to 5, the regret of SROQ-CMAB became much larger than that of AROQ-CMAB and CUCB. Specifically, the cumulative regret at time $T$ was: SROQ-CMAB: 1140, ARQO-CMAB: 678, and CUCB: 659 -- consistent with our theoretical result that the synchronized version incurs an additional $\sqrt{m}$ factor in regret.

We will add such an ablation study in the final version.

We sincerely thank the reviewer for the thoughtful comments. Below, we provide point-by-point responses to each one.

$\bullet$ Discussion on Gap-Dependent Regret Bounds

Response: Thank you for your insightful comment. In this work, we focused on the gap-free setting as a foundational step toward oracle-efficient algorithms for combinatorial semi-bandits. Extending our frameworks to derive gap-dependent regret bounds is indeed a valuable direction for future work.

One natural approach would be to incorporate elimination-based strategies, as commonly used in the batched multi-armed bandit literature [14]. However, in the combinatorial setting, elimination becomes more involved due to the need to construct representative actions for each base arm, as described in Line 3 of Algorithm 2. These representative actions allow us to eliminate large sets of suboptimal actions by targeting individual suboptimal base arms. However, pulling representative actions does not guarantee a uniform number of base-arm observations across epochs. This mismatch can introduce inefficiencies and prevent standard elimination techniques from achieving tight gap-dependent bounds, thereby limiting their direct applicability in our combinatorial setting.

Nonetheless, we consider the development of gap-dependent oracle-efficient algorithms an exciting and important direction for future work.

$\bullet$ There is no validation on real-world datasets.

Response: Thank you for the thoughtful comment. We appreciate the importance of real-world validation, particularly in application-driven domains. However, in the bandit literature, particularly in combinatorial and semi-bandit settings, the primary focus is on theoretical contributions [6, 5, 16, 10, 20, 26]. Even when experiments are included, they are typically conducted on controlled synthetic environments to precisely validate regret behavior and algorithmic properties.

Our main objective in this work is to investigate oracle efficiency in combinatorial semi-bandits from a theoretical standpoint. Accordingly, our synthetic experiments are conducted to support and illustrate the theoretical guarantees, in line with standard practice in the literature.

While real-world datasets are outside the scope of this work, we believe that incorporating domain-inspired structures (e.g., recommendation or routing) could be an interesting extension for future empirical validation.

$\bullet$ Minor Presentation Issues: In line 140, the proof of Theorem 1 is said to be in Appendix B.2, but the citation appears to be off. In line 175, the proof of Theorem 2 is listed incorrectly; it should refer to Appendix B.4.

Response: Thank you for your helpful comments. You are correct - the appendix references for the proofs of Theorems 1 and 2 were mistakenly interchanged. We will correct these citations to ensure that each theorem properly points to its corresponding appendix section.

$\bullet$ Minor Presentation Issues: In line 174, the adaptivity complexity uses $\Theta(\log\log T)$; However, there is no lower bound showing lower bound results.

Response: Thank you for pointing this out. To clarify, the oracle adaptivity complexity of $\Theta(\log\log T)$ in Theorem 2 is not derived from a lower-bound analysis, but rather corresponds to the explicit number of synchronized update steps used by Algorithm 2. Specifically, the algorithm sets the number of updates to $M = \Theta(\log\log T)$, as stated in Section 3.2 (Lines 170-173). As shown in Lines 763-766 of the appendix, since each update requires a round of oracle queries, the total adaptivity complexity directly follows from this setting of $M$. For a more detailed explanation regarding synchronized updates, please refer to Appendix B.1.

We will revise the main text to better explain this connection and avoid confusion regarding the interpretation of this complexity term.

We sincerely thank the reviewer for the thoughtful comments. Below, we provide point-by-point responses to each one.

$\bullet$ Algorithm 2 takes in the pre-determined sequence of policy updates.

Response: You are correct that Algorithm 2 relies on a pre-determined sequence of policy updates. This design choice is intentional and central to our goal of reducing oracle adaptivity complexity: it enables synchronized oracle queries that further reduce adaptivity complexity, even beyond what is achieved by Algorithm 1. Reducing oracle adaptivity is essential to reduce computation cost, and using pre-scheduled, infrequent updates aligns with prior research on batched bandit algorithms [14, 19], which inspired our framework as discussed in the main text.

In practice, a fixed update schedule is rarely a significant limitation. In many real-world applications, computational budgets and synchronization constraints are known in advance, making it natural to plan update schedules accordingly. Moreover, as shown in Figures 2, 3, and 4, our approach with synchronized updates achieves the best runtime performance compared to other algorithms.

Developing an adaptive version of the synchronized update scheme could be an interesting direction for future research. We will include this discussion in the final version.

$\bullet$ Authors must discuss the findings of the evaluation results in details and must elaborate why the algorithms behave as they do.

Response: Thank you for your helpful feedback. We agree that interpreting evaluation results is important, and we are happy to elaborate further.

As predicted by our theoretical analysis, the proposed algorithms significantly reduce oracle complexity through rare update policies. This is clearly demonstrated in Figure 2(a) and 2(b), where the oracle query and adaptivity complexities of baseline methods grow linearly with time, whereas our algorithms exhibit sublinear growth. This results in substantial computational savings, as shown by the faster runtime in Figure 2(d), and reduced total oracle usage in Figures 2(e) and 2(f).

As expected, the infrequent updates result in slightly higher regret in the early rounds (Figure 2(c)). However, as more information is accumulated, the performance of our algorithms improves and eventually approaches that of the baseline, while maintaining significantly better oracle efficiency. This improvement occurs as the cumulative information gained over time mitigates the impact of rare updates. Similar trends are also observed in the covariance-dependent and general reward settings (Appendix B.11).

We will clarify these points and expand the discussion in the final version to better guide the reader through the observed behavior.

$\bullet$ In the appendix, new algorithms are introduced without description.

Response: Thank you for your comments. We clarify that each algorithm introduced in the appendix is referenced and motivated in the main text.

Specifically, Algorithm 5 in Appendix B is introduced in connection with the discussion of $\alpha$-approximation oracles in the last paragraph of Section 3.1 of the main text (Lines 147-154). Algorithms 6 and 7 in Appendix B correspond to our oracle-efficient methods for the general reward setting, as indicated in Section 5 of the main text (Lines 255-258). Furthermore, Algorithm 8 in Appendix B formalizes our extension from discrete to continuous reward distributions, which is referenced in footnote 2 of Section 5.

We will make these cross-references more explicit in the final version to improve clarity and readability.

$\bullet$ It is a good practice to remind the reader what the baseline algorithms are and how do they work.

Response: Thank you for your suggestion. Regarding baselines, each representing the state-of-the-art in its respective setting, we provide a brief summary here:

• For the worst-case linear reward setting, CUCB [6, 16] serves as our benchmark. It uses a standard UCB strategy by constructing upper confidence bounds for each base arm and summing them over actions.

• For the covariance-dependent setting, we use OLS-UCB-C [26] as a benchmark, which is a covariance-adaptive algorithm that estimates the noise structure online and selects actions optimistically based on this estimation.

• For the general reward setting, SDCB [5] is the benchmark. It estimates the distributions of the reward variables and constructs stochastically dominant confidence bounds for action selection.

A key difference is that all baseline methods require an oracle call at every round, whereas our algorithms significantly reduce oracle usage while maintaining competitive regret. We will clarify these baselines and their connections to our methods in our final version.

$\bullet$ I think the authors have incorrect references. The proof of Theorem 1 maps to the proof of Theorem 2.

Response: Thank you for pointing this out. You are correct. The references to the appendix for the proofs of Theorems 1 and 2 were mistakenly interchanged. We will revise the text to ensure that each theorem correctly points to its corresponding appendix section.

Overall: We sincerely appreciate the reviewer’s constructive feedback, which has helped us clarify and improve our work. We hope that the responses and clarifications above address the concerns raised, and we would be grateful if the reviewer would consider them in their final evaluation. We would be happy to provide further clarifications if needed.