Set-Size Dependent Combinatorial Bandits

Thank you for your reply.

The second key concern, apart from the position of the related works, is the lack of closely related works. The references mentioned in the rebuttal represent only a small subset of the extensive literature on submodular maximization. We appreciate adding those references. However, the authors are strongly encouraged to explore more.

The paper contains some incorrect statements: (Line 674: However, submodular functions require two key properties, i.e., monotonicity and submodularity. … Hence, our model is able to capture scenarios that submodular bandits cannot capture, especially when the reward for some base arms does not change monotonically with a growing set size.) And even in the rebuttal, the authors mentions ((iii) ...our setting (SSD-CMAB) does not assume the most important properties of submodular functions, i.e., monotonicity and submodularity.)

Submodular functions do not require monotonicity (though some algorithms' gurantees do, but not all). There is a significant body of research on non-monotonic submodular functions [4, 5, 6]. While the guarantees differ for non-monotonic submodular functions, it is misleading to claim that monotonicity is a necessary property of submodular functions. The authors must revise such statements and are encouraged to consult the references below and explore other recent closely related works:

[4] Feige, U., Mirrokni, V. S., & Vondrák, J. (2011). Maximizing non-monotone submodular functions. SIAM Journal on Computing.

[5] Niazadeh, R., Golrezaei, N., Wang, J. R., Susan, F., & Badanidiyuru, A. (2021, July). Online learning via offline greedy algorithms: Applications in market design and optimization. Proceedings of the 22nd ACM Conference on Economics and Computation.

[6] Fourati, F., Aggarwal, V., Quinn, C., & Alouini, M. S. (2023, April). Randomized greedy learning for non-monotone stochastic submodular maximization under full-bandit feedback. International Conference on Artificial Intelligence and Statistics.

A second incorrect claim is that an empirical comparison with submodular bandits is not feasible. While submodular bandit algorithms use the assumption of submodularity to derive theoretical guarantees, they do not require a submodular function to execute. In other words, submodularity is not a prerequisite for running the algorithms but rather for ensuring the guarantees. Therefore, an empirical comparison is certainly feasible and can provide valuable insights from an algorithmic perspective. The authors are strongly encouraged to consider some of the most recent submodular bandit algorithms for an empirical comparison, which could further strengthen the motivation for their studied settings.

The submodular bandit literature (monotone and non-monotone) addresses most of the proposed motivations and represent a strong and highly relevant benchmark for this work, yet they are overlooked in both the empirical study and theoretical analysis.

Thank you for your valuable advices!

1. For the concern about related works:

(i). For Your Concern About the Suitable Place of Related Work:

We have revised the Introduction section to include discussions of many of the most related works, particularly in paragraph 3.
Additionally, we have enriched the Related Work section in Appendix A to provide a more comprehensive overview.

(ii). For Your Concern About the Relationship Between Our Setting and CMAB with Submodular Functions:

We have emphasized this relationship in both the 3rd paragraph of the Introduction and the 2nd paragraph of the Related Works in Appendix A.
In our rebuttal revision, we have included all the papers referred to in your review.
Additionally, we have added discussions in Appendix A to highlight the key differences and motivations for our setting.

(iii). For Your Concern About Comparing Our Setting with "CMAB with Submodular Reward Functions" Theoretically and Empirically:

We would like to clarify that, although there are some similarities between the two settings, our setting (SSD-CMAB) does not assume the most important properties of submodular functions, i.e., monotonicity and submodularity. Specifically, the reward function for a super arm in CMAB with submodular functions is required to satisfy:

for all base arms $i$ and super arms $S, S'$ such that $S \subseteq S'$.

In contrast, the only assumption in our model is the order-preservation property for the reward means of base arms, which is significantly different from the submodular function. To illustrate this distinction, consider an SSD-CMAB instance with $M=L=4$. Let the reward mean for arm $i$ in a super arm with size $\ell$ be denoted by $\mu_{i(\ell)}$, where $i \in [M]$ and $\ell \in [L]$. The reward matrix for this instance is as follows:

This instance satisfies the order-preservation property and is therefore valid under our setting. However, the reward expectation of each base arm may increase or decrease with the set size. For example, the reward mean of base arm 1 decreases from 0.9 to 0.8 when the size grows from 1 to 2, but increases again to 0.9 when the size grows to 3. Using the terminology of submodular functions, we find that:

In this case, the reward function does not satisfy monotonicity or submodularity. Thus, while we can highlight the differences between the two settings, a direct theoretical or empirical comparison is not feasible due to the differing properties and assumptions.

Thank you for your reply. We appreciate your effort to improve the draft.

Related Works Problems:

While the authors removed the incorrect statement that submodularity requires monotonicity, we notice that some parts of the manuscript still implicitly use this misconception to argue the advantages of their work.

line 731-734: "However, one common property that submodular function requires is the submodular property. In contrast, SSD-CMAB only requires order-preservation, allowing base arm rewards to increase or decrease with super arm size. Hence, our model is able to capture many scenarios that submodular bandits cannot capture, especially when the reward for some base arms do not change monotonically with set size growing."

The authors should emphasize their actual advantages over submodular bandits beyond addressing monotonicity, as submodular bandits also accommodate non-monotonicity.

The authors in the main paper line 66-71: "Note that in the CMAB model the reward distribution of a base arm remains the same across all super arms. In contrast, SSD-CMAB models base arm rewards as dependent on the size of the super arm, with each base arm having L different reward distributions. This is the main distinction with CMAB where each base arm has only one fixed distribution (Gai et al., 2012; Combes et al., 2015b), even in non-linear reward settings (Chen et al., 2016b; 2021; Merlis & Mannor, 2019) or works that focus on the arms depending on the set (Chen et al., 2018; Takemori et al., 2020; Fourati et al., 2024).''

This statement is somewhat misleading. While CMAB with submodular rewards does assume submodularity, it does not necessarily imply that the reward distribution of a base arm remains the same across all super arms, similarly to SSD-CMAB (no contrast here). The authors should clearly and explicitly articulate the differences between their work and prior studies, avoiding any ambiguous or misleading statements.

Empirical Comparison:

You may believe that using submodular bandit algorithms in your setting might lead to linear regret (or at least perform significantly worse than other baselines, such as CombUCB1). However, an empirical comparison is essential to substantiate these beliefs.

We understand that your model has slightly different assumptions from those of submodular rewards, but this does not necessarily imply that submodular bandits will perform poorly under these slightly different assumptions (at least from an empirical perspective), especially that they have a lot in common (rewards being dependent on the set).

Combinatorial bandits are simple and easy to implement and do not require any GPU or extensive memory to test. Given their high relevance to your setting (higher than CombUCB), there is no reason to delay such a comparison to future works.

Thank you for your valuable advices. We address your concern of our paper as follows:

1. Concern about the computational complexity:

Thank you for your vital advices. We have added the complexity analysis in the end of Section 3 and describe which in detail in Appendix C. Indeed the computational complexity per time slot is no more than $O\left(M\log(M)\right)$, which is a low computation cost. Please let us know whether you have other problems about the implementation.

2. Concern About the Combinatorial Structure:

We introduce the term $L$ in our model because it is commonly used in prior works on CMAB, such as:

• "Kveton, B., Wen, Z., Ashkan, A., & Szepesvari, C. (2015, February). Tight regret bounds for stochastic combinatorial semi-bandits."
• "Gai, Y., Krishnamachari, B., and Jain, R. Combinatorial network optimization with unknown variables: Multi-armed bandits with linear rewards and individual observations."

These foundational papers on CMAB focus on linear reward functions and semi-bandit feedback, making the inclusion of a cardinality constraint natural. In our case, $L \leq M$, and setting $L = M$ represents a special case of CMAB without cardinality restriction. Thus, by adding this restriction, our model becomes more general and better reflects real-world scenarios.

3. Question about algorithm CTS:

We have noted the paper you mentioned that introduces the algorithm CTS. The reason we did not include this algorithm is that CTS is designed for CMAB with general reward functions and only achieves a suboptimal regret bound in the scenario of CMAB with linear reward functions.

More specifically, the regret upper bound of CTS in our model is:

whereas the regret upper bound of CombUCB1, one of the benchmarks we use, is:

Therefore, the best way to demonstrate the advantages of our algorithm is to compare it with CombUCB1 or MPMAB, which are more appropriate benchmarks in our context.

4. Question About the SD-CMAB Problem:

Taking paths as an example, we can model each edge in a graph as a base arm,
while the super arms represent paths formed by different combinations of these edges.
The reward of a path reflects its performance, which may vary depending on specific contexts.

Consider a scenario with four edges, denoted as $\{1,2,3,4\}$. If a particular property exists for edge 1—such as traversing edge 1 imposing an additional cost on subsequent edges—then we can group paths that include edge 1, such as $\{1,2\}$ or $\{1,3,4\}$, into a special class.

The concept of a "class" in this context generalizes the "Set-Size Dependent" (SSD) model discussed in previous sections. While SSD-CMAB classifies paths solely based on their set size (i.e. the number of edges in one path), SD-CMAB allows for classification based on additional factors, such as properties or characteristics specific to individual edges.

This broader framework enables a more flexible and detailed representation of combinatorial dependencies, extending the applicability of the model to more complex scenarios.

Thank you for the answer. Though the denominators in the upper bound of the CTS and the CombUCB1 are slightly different, the orders are still the same. I believe the CTS has to be compared in the experiment section. Also, if the proposed algorithm can avoid computation heaviness by some interesting techniques, it should be in the main text, not in the appendix. This is because in combinatorial bandit, I believe computational efficiency is one of the most important aspects.

We appreciate it for for your recognition of this paper and valuable advices.

1. Concern About Justification on the Problem Setup:

Thank you for your suggestion. We have discussed some important motivations in the Introduction, specifically in paragraph 2. Due to space limitations, it may be challenging to include additional motivations or detailed applications in the current version of the paper. If we identify more appropriate motivations or examples in the future, we will make sure to include them in the paper as soon as possible.

2. Concern about broader class seems out of place:

Thank you for the suggestion. We will keep doing experiments related to the SD-CMAB problem in the paper.

3. Concern About Perfect Lower and Upper Bound Matching:

Thank you for the advice. Currently, we analyze the relationship between the upper bound and lower bound in both the "Contributions" section and in Remarks 3 & 4 following Theorem 2. In particular, Remark 4 demonstrates that when the minimum of $\frac{\delta_{i(\ell)} - s_{i(\ell)}}{d_{\inf}(P_{i(\ell)}, \mu_{\ell^*(\ell)}, \mathcal{M}_{\ell})}$ for all $i \in [\ell^*+1, M]$ occurs at $L$, and $\ell^*$ is not approximately equal to $M$, the two bounds align with each other.

Since the gap between the two bounds primarily depends on the differences between individual base arms,
the gap itself is not the most significant factor in describing the advantage of our algorithms. Therefore, we analyze the relationship using remarks rather than introducing additional lemmas or corollaries.

We will continue exploring more appropriate ways to express the tightness of the two bounds in future revisions.

4. Concern about Experiment Replicability:

Thanks. We have added our code in the Rebuttal Revision.

5. Concern about pivoting paper around SD-CMAB:

The reason why we don't pivot the discussion around SD-CMAB is that our current two main results are based on the SSD-CMAB problem, including the upper bound and lower bound. Hence, it is more suitable to focus on SSD-CMAB in the main paper and treat SD-CMAB as a generalization problem.

We will continue researching the properties of the SD-CMAB problem to explore whether it can lead to more significant results in the future.

6. Concern about real-world datasets:

Thank you for your suggestions. We will focus on the real-world dataset experiments in the future.

7. Detailed discussion of the Oracle:

This Oracle is a novel contribution in our paper, which has not been included in previous CMAB studies. Due to space limitations, we have moved the detailed discussion of the Oracle to Appendix F.2. Please let us know if this section addresses your concerns effectively.

Thank you for your invaluable review and advices.

1. For the concern about the space of notations:

Thank you for your suggestions. We have simplified Section 2 by removing certain parts to address your concerns in the Rebuttal Revision. We appreciate your feedback and will continue revising the section to explore ways to streamline the content further while ensuring clarity and completeness.

2. For the concern about the definition of regret:

Thank you for your concern regarding the definition of regret. We would like to clarify that the optimal arm is fixed in every bandit instance. Since we consider the stochastic setting with linear rewards, each base arm has a fixed reward expectation within super arms of the same set size. Given the action set of super arms, denoted by $\mathcal{S} = \{S \subseteq [M] \mid |S| \leq L\}$, the optimal arm can be identified by finding the super arm with the highest reward mean.

For example, consider an SSD-CMAB instance with $M = L = 4$. Let the reward mean for base arm $i$ in a super arm of size $\ell$ be denoted by $\mu_{i(\ell)}$, where $i \in [M]$ and $\ell \in [L]$. The reward matrix for this instance is as follows:

In this case, the reward mean of the super arm $S^* = \{1, 2, 3\}$ is higher than any other combination of base arms. Specifically, the reward mean of $S^*$ is

$r(S^*)=\mu_{1(3)}+\mu_{2(3)}+\mu_{3(3)}=0.9+0.8+0.7=2.4$

as the size of $S^*$ is $3$. This value is greater than the reward mean of any other super arm in this instance.

3. For the concern about comparisons of regret bounds:

As explained in Section 4 of the Introduction, each SSD-CMAB instance can be viewed as a standard CMAB instance by treating each base arm in the super arms with varying set sizes as distinct base arms and independently learning their $ML$ distributions. Appendix B provides an algorithm to reduce any CMAB algorithm to handle the SSD-CMAB problem. However, standard CMAB algorithms do not account for the order-preservation property, preventing them from achieving optimal results. Consequently, the upper bound of any existing CMAB algorithm is inferior to ours (Theorem 1). This highlights the necessity of studying SSD-CMAB as a distinct research topic and developing algorithms tailored to its unique properties.

4. Addressing the Concern Regarding the "Partially Tight" Lower Bound:

The term "partially tight" is clarified in Remarks 3 and 4 on page 7. Specifically, the upper bound in Theorem 1 is given as
$O\left( \max\left(\frac{M\delta_{L,\max}}{\Delta_{L,\min}^2}, \frac{L^2}{\Delta_{S,\min}}\right)\log(T) \right),$
while the lower bound in Theorem 2 can be informally written as
$\Omega\left(\max\left(\min_{\ell\in[L]}\left(\frac{(M-L)\delta_{\ell}}{\Delta_{\ell}^2}\right),\frac{L^2}{\Delta_{S,\min}}\right)\log(T)\right),$
as stated in the Abstract. It is evident that the second term in both the upper and lower bounds, i.e., $\frac{L^2}{\Delta_{S,\min}}\log(T)$, aligns, indicating that the regret caused by the UCB phase in Algorithm 1 is unavoidable. Meanwhile, the discrepancy in the first term between the upper and lower bounds can reduce to zero under specific conditions—namely, when the minimum in the first term of Theorem 2 consistently occurs at $L$ across $\ell \in [L]$, and $\ell^*$ is not approximately equal to $M$. For a detailed explanation of the term "partially tight," we direct reviewers to Remark 4.

5. For the Concern About SSD-CMAB Instance:

Thank you for your suggestion. We have introduced the SSD-CMAB instance in Section 2, "THE SSD-CMAB PROBLEM," starting from the third paragraph of this section. We have also added a more detailed explanation of this term. Reviewers can refer to the "Rebuttal Revision" for the updated explanation.

6. For the Question of reduction to normal CMAB problem:

Yes, it can be reduced to CMAB problem. We introduce the approach to consider each SSD-CMAB instance as a normal CMAB instance in the 4th paragraph of the Introduction section (that is, treating each base arm in super arms with different set sizes as different base arms and independently learning $ML$ distributions). The detailed implementation is provided in Appendix B.

As stated in the Introduction section, using CMAB algorithms to solve the SSD-CMAB instance ignores the order-preservation property
and results in a sub-optimal bound, which is worse than that of Algorithm 1. Therefore, it is crucial to conduct research specifically on the SSD-CMAB problem.