Nearly Minimax Optimal Submodular Maximization with Bandit Feedback

Summary

The authors consider stochastic bandit submodular maximization. For this problem, there are two known regret upper bounds: a $\sqrt{T}$ regret upper bound with large coefficients obtained by naively considering the problem as the multi-armed bandit problem, and a $T^{2/3}$ regret upper bound with a relatively small coefficient obtained by the well-known greedy maximization procedure. This paper clarifies that the minimax regret of stochastic bandit submodular maximization can be roughly characterized by the minimum of these two bounds. Additionally, the paper demonstrates that this minimax regret can be achieved by a UCB-based algorithm.

Strengths

In online submodular maximization with bandit feedback, the focus has often been on achieving a $T^{2/3}$ regret guarantee with reasonable coefficients, and focusing on the $\sqrt{T}$ regret upper bound obtained by naively applying MAB is new. To my knowledge, this paper presents the first lower bound for bandit submodular maximization, which is an important contribution to the community. Instead of using the commonly employed approximation regret in bandit submodular maximization, it uses regret defined based on the comparator determined by the greedy algorithm, which is somewhat appealing. Although the paper gives an impression of not being thoroughly proofread (see Weakness), it is overall easy to read.

Weaknesses

One of the major contributions of this paper is the lower bound, but its explanation could be improved. While an intuitive explanation is provided from Lines 168 to 172, it is unclear why regret minimization algorithms (such as ETC and the "standard" MAB algorithm) appear in the discussion of the lower bound. The authors are expected to provide a more detailed explanation of existing algorithms in Section 3. The current explanation lacks clarity on how $\hat{f}$ is computed. The regret definition involves a comparison with $S^{k,\mathbf{0}}$. Although the authors state that comparing with $S^{k,\mathbf{0}}$ may be impossible in a noisy setting, can the authors present a lower bound for this statement? In Section 1.2, the authors mention the use of the Lovasz extension for online submodular maximization. Isn't this technique used for submodular minimization? Additionally, the paper overall gives the impression of not being thoroughly proofread. To highlight some minor points: L120-122: [22] in Theorem 4.1, [24] in Theorem 1, .... -> Theorem 4.1 in [22], Theorem 1 in [24], ...., L160: Showed -> showed, L232: abbreviation ETC is not defined, Sec3: There are $S^{i}$ and $S^{(i)}$, which are confusing, L268: UBC -> UCB.

Questions

The reviewer expects the authors to address the questions mentioned above.

Rating

5

Confidence

2

Soundness

3

Presentation

2

Contribution

3

Limitations

not appicable

Summary

The authors investigate lower bounds for regret for combinatorial multi-armed bandit (CMAB) problems under submodular rewards and bandit feedback. For stochastic environments, there has been an open question about the gap between $O(\sqrt{T})$ dependence typically seen in MAB problems (and submodular CMAB with extra feedback) and the $O(T^{2/3})$ dependence typically achieved using explore-then-commit (ETC) algorithms for bandit feedback in past works. The authors propose a related but different notion of regret then used in previous works and show this regret does indeed have a $\Omega(T^{2/3})$ dependence. Their formula generalizes the ``small’’ horizon $T$ regime studied in those past works and identify a minimax bound that interpolates $\Omega(T^{2/3})$ for small $T$ and $\Omega(\sqrt{T})$ for large $T$ (i.e. essentially large enough that separate super-arms can be treated as arms in a standard MAB algorithm). The authors include experiments on toy functions to illustrate the interpolation.

Strengths

### Major - This paper is among the first to tackle lower bounds for combinatorial (cardinality constrained) MAB with monotone submodular rewards and bandit feedback in stochastic environments. - To do so the authors argue that a notion of regret based on nesting of near-greedily selected sets, which the authors point out was implicit in the proofs of several prior papers (all of which adapted the same classic greedy approximation algorithm from the offline setting), should be used instead of the $1-1/e$-regret that has been used in the past. - For this alternative (greedy) regret, the authors prove a $\Omega(T^{2/3})$ lower bound (for the so called “small $T$” regime), strongly suggesting that there is indeed a hardness gap between CMAB problems with bandit feedback and other studied classes (standard MAB, linear CMAB, even submodular CMAB with semi-bandit feedback). - The authors also propose an algorithm with matching upper bound regret. The algorithm basically adapts the greedy algorithm (like previous ETC algorithms had) for some of the horizon and then switches to UCB-style over nesting super-sets) ### Minor - The lower bounds and algorithm proposed is not only for the so called “small” $T$ regime but for large enough $T$ that one can sample super-arms as regular arms in a standard MAB algorithm to get $\sqrt{T}$ dependence. The lower bound and their matching algorithm identify the trade-off (basically to what cardinality $i^*$ does one follow the greedy before switching to treating all (nesting) cardinality $k$ superarms as standard MAB arms). - The authors include experiments with two classes of toy functions to illustrate the trade-offs between ETC style algorithms (designed in prior works for “small” $T$) and UCB style (known to get $\sqrt{T}$ regret bound for very large $T$).

Weaknesses

### Major - [21] proved $\Omega(T^{2/3})$ lower bounds for the adversarial setting under a slightly different feedback model (though is relevant for any explore-then-commit strategies) and for a general class of problems (including submodular CMAB as a special case) which is not discussed. ### Minor - The experiment section does not clearly specify $n$ or $k$ or $i^*$ for the problem instances considered. In the main text, for $n$, there is only a mention in line 263 only for the weighted set cover “For $n=15$, we use…” but that makes it sound like you are using multiple values of $n$. Since $i^*$ is described as a “critical quantity” (line 231), its value should be transparent in the experiments. Only Figure 1’s caption, which is for the submodular cover, clearly mentions $n$ and $k$ (without mention of $i^*$’s value). - I think more discussion on what ``small’’ entails for some potential applications would be valuable. In line 169 the example of $T= O(n^4)$ is given. In the experiments even for a small $n$ and $k$ for toy experiments it is around $T$ is in the millions to billions that there is a tradeoff, though would such large $T$ be plausible for problems mentioned in the introduction as motivation? Would the rewards remain i.i.d. for each super-arm over such a large horizon? ### Very Minor - for the summary 127-133, this is pointing out that for instances of a special sub-class which have a strictly better $\alpha=1$ worst-case approximation guarantee, the $\alpha$-regret of the larger class with provably harder instances behaves weirdly (even giving negative regret values). That is an important observation, but $\alpha$-regret bounds are for a class of problems, arising from the worst cases, and there are harder cases for cardinality-constrained submodular optimization than modular functions, where the $(1-1/e)$ approximation coefficient comes from. - line 80 missing parentheses - line 268 “UBC” - line 287 ‘were’--> ‘where’ - In the experiments, 1-Gaussian noise seems strange given the functions are bounded in [0,1]. - Figure 2 legend use power of 10 notation, or add commas - I think the intro may flow better if you open with problems that are submodular and mention they are important, then say people have been trying to solve them but it is unclear the extent that current methods are the best that could be had

Questions

### Major 1. The greedy algorithm from Nemhauser and Wolsey is classic and was the most widely adapted for online settings, but there are other approximation algorithms for monotone cardinality-constrained submodular maximization that behave differently in subset selection, such as the threshold greedy https://theory.stanford.edu/~jvondrak/data/submod-fast.pdf. From a quick look it is not clear to me that the sets would satisfy a nesting like that in line 102 (though I didn’t check carefully, maybe it would in a different order than elements get added). So while the $R_{gr}$ lower bound is over any online algorithm, I would wonder if it is possible it might be too strict, in the sense that a different regret notion based on some structure underlying a different algorithm (like a ``$R_{thresh-gr}$’’ regret) could be defined, still with $ R_{1-1/e} \leq R_{thresh-gr}$ perhaps permitting $\sqrt{T}$ upper bound even in the regime where $T$ is small relative to $n$ choose $k$? 2. How would this work generalize to other problems, even similar but harder problems like monotone submodular maximization with knapsack constraints or intersections of matroid and knapsack constraints, or non-monotone problems? There are known approximation coefficients, so the $\alpha$ regret could be easily defined accordingly (of course with limitations on interpretability you point out) but would some analog of Lemma 1.1 need to be identified for each of those problem classes and then (3) defined, and in some sense would we need to choose a reference algorithm if there were more than one available that achieved the same approximation guarantee? ### Very Minor 3. Lemma 1.1 what is the definition of $S_{gr}^{k,\epsilon}$? $S_{gr}^{f}$ was defined earlier wrt exact value oracle for $f$. But $S_{gr}^{k,\epsilon}$ is ambiguous. If in Lemma 1.1 any set $S \in \mathcal{S}^{k,\epsilon}$ satisfies then I’d suggest the dummy variable $S$ for clarity. 4. what is the size of $i$ for which it is advantageous to be less than $k$? if in the “small T” regime, that is interesting. 5. Theorem 2.1 requires $k\leq \lfloor{n/3}\rfloor$ -- is there a simple reason for that? 6. In the experiments, there are no error bars on the figures – was each marker for a single run?

Rating

5

Confidence

3

Soundness

3

Presentation

2

Contribution

2

Limitations

Yes

Summary

The paper addresses the problem of stochastic submodular bandits. The main contributions are twofold: it provides a new lower bound for the problem and proposes a novel UCB-type algorithm whose regret matches this lower bound.

Strengths

- The paper introduces notation clearly and provides a sufficiently thorough comparison with related work. - The lower bound proof is new. While it adheres to the standard framework for proving regret lower bounds in stochastic bandits, the challenging aspect lies in constructing the problem instance. The problem instance constructed is original. - The proposed algorithm showcases an interesting insight on the hardness of the problem, even though it combines well-known approaches for online submodular maximization.

Weaknesses

- Sub-UCB is a modified version of the algorithm in Nie et al. (2022). While this algorithm has a lower regret upper bound, the algorithm itself is an incremental change compared to prior work. - The lower bound is demonstrated to hold for the minimax expected regret $R_{gr}$, which differs from the $\alpha$-regret commonly used in the literature. While the former is shown to be an upper bound for the latter, it can potentially be much larger. Consequently, a lower bound for $R_{gr}$ does not necessarily imply a corresponding lower bound for $R_\alpha$. Therefore, I believe it is not sound to argue for the minimax optimality of the problem at hand based on this specific change in the regret notion adopted and analyzed. - It seems that the lower bound result needs to be conditioned on a harsh prerequisite that T needs to be very large. For example, when $k=10$, T needs to be at least $10^11$ for the lower bound to hold.

Questions

I make the following suggestions: - It would be better to formally prove the constructed problem instances (both $k=2$ and general k cases) are submodular functions (possibly in a lemma). It is not obvious to me for general $k$ thy those functions are submodular. - Also, the minimax optimal version of the UCB or Thompson Sampling can be used in the second phase to fully match the lower bound.

Rating

4

Confidence

4

Soundness

3

Presentation

3

Contribution

2

Limitations

See Weakness and Questions.

Summary

This paper studies the stochastic submodular bandit problem. In this problem, the decision-maker needs to select a subset with size at most k from a known ground set, and then the decision-maker gains a stochastic reward associated with the subset. The expectation of the reward is a submodular function. This problem is a natural extension of combinatorial linear bandit which relaxed the linearity assumption of the reward function. This paper mainly focuses on the lower bound of the submodular bandit problem, which is a recognized open question. Different from other literature of submodular bandit, this paper defines a new notion of regret which is called robust greedy regret. Roughly speaking, the new regret compares the algorithm gained reward with the reward gained by the output subset of an offline “approximated” greedy algorithm. The authors prove a lower bound of their defined notion of regret. This lower bound changes from $kn^{1/3} T^{2/3}$ to $n^k T^{1/2}$ as the size of T, and this results implies that $T^{2/3}$-type regret is inevitable when T is relatively small(polynomial to k and n). This paper also proposed an algorithm that nearly match the lower bound. All their results are in the sense of the new defined “robust greedy regret” rather than commonly used γ-regret.

Strengths

The major contribution of this paper is the lower bound. Even though the first algorithm for (adversarial) submodular bandit has been proposed for 17 years, we do not have any regret lower bound now. Given this fact, I think a lower bound result on this problem should be extensively encouraged. Back to the previous algorithms for submodular bandit (both stochastic setting and adversarial setting), all these algorithms only achieve $O(T^{2/3})$ regret. The main reason is that these algorithms must clearly distinguish whether the current round is an exploration round or an exploitation round. The technique in this paper somewhat explains the intuition behind that. That is, the small size subset will bring more information but cost large regret, and the full-rank subset incurs low regret but bring less information. This naturally divide the subset with different size to exploration action and exploitation action. In this sense, I think this paper do give some intuition on the hardness of submodular bandit and this difficulty also suggests that the submodular bandit is completely different in nature from the linear bandit. Overall, this paper provides me important knowledge and I believe it will also bring new knowledge to the people who are working on submodular bandit.

Weaknesses

The main weakness of this paper is that the regret lower bound is in terms of the new defined notion of regret—“robust greedy regret”. However, almost all papers about submodular bandit or more generally combinatorial bandit are considering the notion of a scaled “$\gamma$-regret”. As the authors state, robust greedy regret is always larger than gamma regret, so a lower bound of robust greedy regret does not imply anything about the lower bound of $\gamma$-regret. Also, the major difficulty of proving the lower bound of $\gamma$-regret is “the immediate regret can be negative”, which does not exist in traditional 1-regret. However, by defining the notion of robust greedy regret, the authors can avoid this difficulty. The robust greedy regret lower bound is actually a traditional 1-regret lower bound in the hardcase authors have constructed. So I think this result is still quite far away from figuring out the hardness of $\gamma$-regret. As the author states, $\gamma$-regret may not be a good metric of submodular bandit problem or other combinatorial bandit problem. But the robust greedy result depends too much on the form of offline algorithm. Also, not all algorithms for submodular bandit are based on the greedy algorithm. For example, the algorithms in [1][2] are totally different from the offline greedy algorithm and they are also not based on the “offline algorithm to online” style. So it’s even hard to define a robust ”xxx” regret. These papers are also missed in the related literature. Thus, I think it’s inappropriate to state “$\gamma$-regret is not appropriate for this problem”. At least, $\gamma$-regret provides a way to evaluate all-type algorithm rather than restrict the algorithm in the category of “offline to online conversion”. Please note, even if I proposed this weakness. I still appreciate the author's contributions to the lower bound results and I think the contribution of this paper outweighs the weaknesses. [1] Zongqi Wan, Jialin Zhang, Wei Chen, Xiaoming Sun, Zhijie Zhang, "Bandit Multi-linear DR-Submodular Maximization and Its Applications on Adversarial Submodular Bandits", ICML 2023 [2] Stephen Pasteris, Alberto Rumi, Fabio Vitale, Nicolò Cesa-Bianchi, “Sum-max Submodular Bandits”, AISTATS 2024.

Questions

Some suggestions: 1. In page 19, the proof of lemma C.1 should be added. Although I have checked that the claim is correct, a proof is necessary for a complete paper or the authors can give the reference of the proof. 2. In abstract, the authors use the notation L. But in the main text, they use the notation i instead of L. 3. Line 80, there should be a “(” before “min”. 4. It’s better to remove the claim in line 132: “$R_{gr}$ is the more appropriate measure of performance … not $R_{\alpha}$”. Or use more rigorous language to limit the scope of the claim to those algorithms that use offline to online conversion. 5. Some related literature on submodular bandit has been missed, for example, [1][2]. Also, the current version of the literature review of online continuous submodular maximization looks very weird, the authors missed all the important papers in this field. For example, [3,4,5] and more. It is better to survey more in this field. [1]Zongqi Wan, Jialin Zhang, Wei Chen, Xiaoming Sun, Zhijie Zhang, "Bandit Multi-linear DR-Submodular Maximization and Its Applications on Adversarial Submodular Bandits", ICML 2023 [2]Stephen Pasteris, Alberto Rumi, Fabio Vitale, Nicolò Cesa-Bianchi, “Sum-max Submodular Bandits”, AISTATS 2024. [3]Zhang, M., Chen, L., Hassani, H., and Karbasi, A. “Online continuous submodular maximization: from full information to bandit feedback.” NeurIPS 2019 [4]Chen, L., Hassani, H., and Karbasi, A. “Online continuous submodular maximization”, AISTATS 2018 [5] Zhang, Q., Deng, Z., Chen, Z., Hu, H., and Yang, Y. “Stochastic continuous submodular maximization: Boosting via non-oblivious function”. ICML 2022

Rating

7

Confidence

4

Soundness

4

Presentation

2

Contribution

4

Limitations

Yes

Summary

The authors of this paper study the submodular maximization problem with bandit feedback. By adopting regret as the metric, the authors prove the minimax bound of the regret for their problem. A UCB-based algorithm is devised to tackle the submodular optimization problem and the authors prove that this algorithm's regret almost matches the minimax bound. In sum, this paper provides some new and solid theoretical results for submodular optimization.

Strengths

S1. The authors prove the minimax regret bound of the submodular maximization problem with bandit feedback. S2. The authors also devise the algorithm Sub-UCB that can match the minimax bound up to logarithmic factors. S3. The theoretical results in this paper seem correct.

Weaknesses

W1. There are some typos in the paper. For example, in the abstract "we prove, we prove that". W2. The experiment is not interesting as it is a pure numerical simulation. What about applications of submodular optimization such as influence maximization where the objective can only be obtained via sampling and is uncertain? W3. Instead of (1-1/e)-regret, the authors adopt regret as the metric for the reason that (1-1/e)-regret may be loose. Although the greedy solution's approximation is 1-1/e in theory, in practice the approximation ratio can often be close to 1. For example, for the modular objective case mentioned by the authors, greedy-based algorithm is actually optimal. Therefore, the justification of using regret rather than (1-1/e)-regret is not that strong.

Questions

W2

Rating

7

Confidence

3

Soundness

3

Presentation

3

Contribution

3

Limitations

W1, W2, W3

Response to rebuttal

There are two major contributions of this work, and here I address my concerns for each of them. 1. A regret lower bound is derived for submodular maximization with bandit feedback. If I understand correctly, the regret lower bound applies specifically on $R_{gr}$, which differs from the commonly referenced $R_\alpha$ in existing literature. While it is acceptable to use $R_{gr}$ for regret upper bound, as an upper bound on $R_{gr}$ suggests an upper bound on $R_\alpha$, the converse does not hold true for lower bounds. The modified definition of regret, $R_{gr}$, appears to be more aligned with algorithms of the Greedy+ETC style (thus not surprisingly leading to $T^{2/3}$), suggesting it may be a specialized metric rather than a universally applicable one. Consequently, it may be premature to assert the minimax optimality of the problem based solely on this particular shifted concept of regret. 2. An algorithm with regret upper bound matching the established lower bound is proposed. It's a mixture of the ETC and UCB strategies, which explains the presence of both $T^{1/2}$ and $T^{2/3}$ terms in the regret formula. To me, the alignment of the regret with the lower bound is expected given how it was formulated. Moreover, the selection process for the optimal stopping level $l$ remains unclear. Even it can be calculated efficiently, as indicated in Figure 2, an optimal stopping level does not indicate the best regret. Thus, how $l$ can be selected to get the best regret is questionable. I apologize I did not notice the new Lemma A.1 provided. However, the paper's contribution may not sufficiently meet the rigorous standards of novelty and impact that NeurIPS is known for. As such, I will maintain my current scoring, reflecting the above considerations.

Response to rebuttal

Thank you for the rebuttal to the review. I have reviewed the contents of the rebuttal and I will maintain my current score.