Nearly Minimax Optimal Submodular Maximization with Bandit Feedback
Authors: Artin Tajdini
Lalit K Jain
Kevin Jamieson
Venue: NeurIPS 2024 poster (2024)
Keywords: Bandits
Submodular optimization
Minimax optimal
Primary area: bandits
TL;DR: We provide the first minimax regret lower bound for the online submodular maximization with stochastic bandit feedback, and an upperbound matching it in terms of time T and number of arms n.

Abstract: We consider maximizing an unknown monotonic, submodular set function $f: 2^{[n]} \rightarrow [0,1]$ with cardinality constraint under stochastic bandit feedback. 
    At each time $t=1,\dots,T$ the learner chooses a set $S_t \subset [n]$ with $|S_t| \leq k$ and receives reward $f(S_t) + \eta_t$ where $\eta_t$ is mean-zero sub-Gaussian noise. 
    The objective is to minimize the learner's regret with respect to an approximation of the maximum $f(S_*)$ with $|S_*| = k$, obtained through robust greedy maximization of $f$. 
    To date, the best regret bound in the literature scales as $k n^{1/3} T^{2/3}$. 
    And by trivially treating every set as a unique arm one deduces that $\sqrt{ {n \choose k} T }$ is also achievable using standard multi-armed bandit algorithms. 
    In this work, we establish the first minimax lower bound for this setting that scales like $\tilde{\Omega}(\min_{L \le k}(L^{1/3}n^{1/3}T^{2/3} + \sqrt{{n \choose k - L}T}))$.  For a slightly restricted algorithm class, we prove a stronger regret lower bound of $\tilde{\Omega}(\min_{L \le k}(Ln^{1/3}T^{2/3} + \sqrt{{n \choose k - L}T}))$.
    Moreover, we propose an algorithm Sub-UCB that achieves regret $\tilde{\mathcal{O}}(\min_{L \le k}(Ln^{1/3}T^{2/3} + \sqrt{{n \choose k - L}T}))$ capable of matching the lower bound on regret for the restricted class up to logarithmic factors.

Nearly Minimax Optimal Submodular Maximization with Bandit Feedback
Artin Tajdini, Lalit Jain, Kevin Jamieson
University of Washington, Seattle, WA
fartin, jaaiinaaammmeeeeii jamieson]@cs. washington edu, lalitjeuw.ed edu
Abstract
We consider maximizing an unknown monotonic, submodular set function f 2(m] - [0, with cardinality constraint under stochastic bandit feedback. At each time t == ==1.... T the learner chooses a set S, C [n|] with |S,l S k and receives reward f(S.) + T where TJ is mean-zero sub-Gaussian noise. The objective minimize the learner's regret with respect to an approximation of the maximum f(S.) with |S.| k, obtained through robust greedy maximization of f. To date, the best regret bound the literature scales as kn k And by trivially
treating every set as a unique arm one deduces that (*) is also achievable us- ing standard multi-armed bandit algorithms. In this work, we establish the first minimax lower bound for this setting that scales like Q(min 1/2n 1///n/3///// 1/322/3 +
(T)) For slightly restricted algorithm class, we prove stronger regret
lower bound of Q(min /3 / (T")) Moreover, we propose algorithm Sub-UCB that achieves regret (Lmingga + V( ((=1)T) capable of matching the lower bound on regret for the restricted class up loga- rithmic factors.
INTRODUCTION
Optimizing over sets of n ground items given noisy feedback is a common problem. For example, when a patient comes into the hospital with sepsis (bacterial infection of the blood), it is common for a cocktail 1) the set could be as effective (or more) than single drug alone, but each unit of the cocktail could be administered at far lower dosage to avoid toxicity, or 2) could by blocking number of different pathways that would have be overcome simultancously. 3) could cover a larger set of pathogens present in the population. In this setting the prescriber wants to balance exploration with exploitation over different subsets maximize the number of patients that survive. As a second example, we consider factorial optimization of web-layouts: you have n pieces of content and & locations the webpage to place metrics like dlick-throuu rate or engagement?
antibiotics to prescribed. This can be attractive for reasons including
more robust to resistance
do you choose subsets maximize
Given there are & ways to choose k items amongst set of this optimization problem is daunting. further complicated by the fact that for any set S, that we evaluate at time I, we only get observe noisy realization of namely y/- = /(S.)+ + where t)t is mean-zero, sub-Gaussian noise. the antibiotics case, this could be a Bernoulli indicating whether the patient recovered not, and in the web-layout case this could be Bernoulli indicating click or (clipped) real number to represent the engagement time on the website. To make this problem more tractable, practitioners make structural assumptions about f. A common assumption is to assume that higher-
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

order interaction terms are negligible [a0 [2] For example, assuming only interactions up to the second degree would mean that there exist parameters o(0) E IR 0(0) E R", and 0(2) E R such that
((S) 000)
Σ
However, this model can be very restrictive and even if true, the number of unknowns scales like n? which could still be intractably large.
remain within non-parametric class, but reduce our ambitions mea- suring performance relative to different benchmark which is easier to optimize. We say a set function / 2 + R is increasing and submodular if for all A c B C [n)] we have f(A) s f(B) and
An alternative strategy
((B)
Such a condition limits how quickly f can grow and captures some notion of diminishing returns. Diminishing returns is reasonable in both the antibiotics and webpage optimization examples. It is instructive to note that a sufficient condition for the parametric form of (II to be submodular is for maxi, 0 O. But in general, f still has s n² degrees of freedom even if it is monotonic and submodular. And it is known that for unknown f, identifying S := arg [s ((} may require evaluating f as many as n² times.
The power of submodularity made apparent through the famous result of [26] which showed that the greedy algorithm which grows set item time by adding the item with the highest marginal gain returns a solution that is within a (1-e- >mmultiplicatiie factor of the optimal solution. That is, if we begin with St. = and set gr < arg max ggl)ss, f(S (+}) until |S = k, then
f(SL.) 2 (1 - (s!) where sf == arg max sex))1()) ((S) if f is increasing and submodular. This result is complemented by [13]] which shows achieving any (1 e-l + -)-aprroximation is NP-Hard. Under additional assumptions like curvature, this guarantee can be strengthened.
Due to the centrality of the greedily constructed set to the optimization of a submodular function, it is natural define performance measure relative to the greedily constructed set. However, as discussed at length in the next section, because we only observe noisy observations of the underlying function, recovering the set constructed greedily from noiseless evaluations is too much hope for. Consequently, there is more natural notion of regret against a noisy greedy solution, denoted Agr. that actually appears in the proofs of all upper bounds found in the literature for this setting (see the next section for a definition).
For this notion of regret, previous works have demonstrated that regret bound of Rgr ((poly(4))11/3/2//3) is achievable (128), [36].. This T2/3 rate is unusual in multi-armed bandits, where frequently we expect regret bound to scale as 1/2 On the other hand, by treating each k-subset as a separate arm, one can easily adapt existing algorithms to achieve a regret bound of
(. This leads to the following question:
Does there exist an algorithm that obtains T regret for o(k) on every instance? And if not, what is the optimal dependence on is and n for a bound scaling like ?
To address these questions, we prove a minimax lower bound and complement the result with an algorithm achieving a matching upper bound. To be precise, the contributions of this paper include:
A minimax lower bound demonstrating that Rgr á (L /3/22/3
v ()) In words, for small T, 22/3 regret bound is inevitable, for large T the
( bound is optimal, with an interpolating regret bound for in between.
- For slightly restricted class of algorithms with non-adaptive greedy error threshold,
we have the improved Rgr = âx( miinos + (z)

---

We propose an algorithm that for any increasing, submodular f, we have Rgr Ô minogr + / (+=L)T). As this matches our lower bound, we conclude that this is the first provably tight algorithm for optimizing increasing, submodular func- tions with bandit feedback. Existing algorithms construct set by greedily adding items. Our main insight is that it actually optimal to build up a set up to a size i and then for the remaining stages play sets of size that include the initial set of size i", Our choice of i directly motivated by our lower bound.
In what remains, we will formally define the problem, discuss the related work, and then move to the statement of the main theoretical results. Experiments and conclusions follow.
1.1 Problem Statement
Let [n] {1.....7) ,.) denote the set of base arms, T be the time horizon, and & be given cardinality constraint. time t, the agent selects a set St C [n]] where |S.] < k. and observes reward f(S) + where 7/, is i.i.d. mean-zero Asub-Gaussian noise, and f 22m + [0, 1] is an unknown monotone non-decreasing submodular function defined for all sets of cardinality at most k.
Ideally, our goal would be minimize the regret relative to pulling the best set S arg max f(S) at each time. In general, even if we had the ability to evaluate the true function f()) (i.e. without noise), maximizing submodular function with cardinality con- straint is NP-hard. However, greedy algorithms which sequentially add points, ie. S6+1) arg ags0) f(S(() Ua), S I & guarantee that f(S()) 2 af(S*) with 2 1 - 1/e in worst-case. Unfortunately, since we do not know f(-) and instead only have access to noisy ob- servations, running the greedy algorithm on any estimate f(-) may not necessarily guarantee = (1 (1-10 a/ee)aaproximmtion f(
Consequently, a natural notion to address noisy observations is an e-approximate greedy set for E [0, 1... We define the following collection of sets size lc
sh.e = -S= = S(()) .... 5()) ,100)
max u(S()((a))) f(((((t)) $ se). ags()
Intuitively, any E the can be thought of as being constructed from process that adds an element at stage which is e--omimmal compared to the Greedy algorithm run on f. Such a set naturally arises as the output of the Greedy algorithm run on an approximation f. This set enjoys the following guarantee.
Lemma 1.1. (Theorem 6 in (50]) For any 2 O E Rk and Sfr E Shiee we have
f(S + 1 - (1---))((()))
Lemma is a noise-robust analogous result to the approximation ratio of the perfect greedy algo- rithm of [26]] that says (S 2 (1 --- Note that | is non-decreasing in 6; for all i E [Kt], so identifying a set in S is in some sense easier for a larger 1" Thus, to define an ap- propriate definition of regret, the measure must balance the facts that comparing with the noiseless greedy approximation in O may be impossible, but should account for identifying set in Sh.e is strictly easier for larger 1 e. Inspired by the above lemma define robust greedy regret
Rgr :
min R(Sh.) gr
TI
(3)
e0 Esk
where
R(S) = ((S) [=1
'The gap between maximum gain and rest of the elements in the greedy path for lower cardinalities can be arbitrary small, making them indistinguishable with 7' queries. Therefore, only making queries to sets of size k would give any information on the greedy solution.
3

---

Function Assumptions
Stochastic
Regret
Upper Bound
Lower Bound
Submodular+moontone
Rgy
kn ///2//
ming minn((I (I2/3n2/8q0.) + ((=1,
(Thic
Submsduula-mmonotone
R2
kn /3/2//
ming. ming(L (I (e=
(his min(Vn'T, VntT)
Degree Polynomial
R(S")
min( (VnTT, v(+T)
Submodnla--monodee
V
Rgr ming (ain
(L
(This work)
Table 1:
Best known regret bounds for combinatorial multiarmed bandits under different assump- tions. By lemma I our upperbound also be stated for R We note that our lower bound proven for the stochastic setting immediately applies to the adversarial setting in the table.
This notion of regret captures the fact that if the algorithm plays a set in Skk then they may be incurring up 1º extra regret. Note that when 0 achieves the minimum (which can happen if the "gaps" between the greedily added element and all other elements at each stage is large) then this notion of regret is relative to the greedy set constructed in the noiseless setting.
The definition of regret (G) is not novel to our paper. This notion is implicitly used in [66 in the proofs of Lemma 3 for the full-feedback setting and Theorem 13 for the bandit feedback setting, [28] in Theorem 4,1, [+1]] in Theorem 1, [27] in Theorem 2 for the full-feedhack setting and Theorem 4 for bandit feedback, and [MA]] in Theorem
However, readers of these papers will note that they report their results not in terms of Rgr. but a-Regret: for an E [0, 1]. define a-regret by, R2 = EF=1
f(S) where 5* == arg max (S)) Using Lemma 1, one immediately has that R. S Rgr for a - )). Thus, an upper bound on (L) immediately results in an upper bound on R., which is precisely what previous works exploit to obtain their upper bounds on Rt,
To summarize: all the analyses of these previous works concentrate on showing an upper bound on Rgr. and only at the last step argue that Ra < Rgr. and report an upper bound on Rg. But Ra can be a very loose lower bound on Rgr! For instance, when the function is modular (the inequalities of submodularity are tight), and the gap between the best set and worst set equal A < e then a random selection algorithm would get zero or even negative Ro regret, while Rgr would be linear AT, which is more natural. Thus, in studying regret against approximations attained by offline step-wise greedy procedure, Rgr can be a more appropriate measure than R.
1.2 Related Work
There has been several works on combinatorial multi-armed bandits with submodular assumptions and different feedback assumptions. Table @1 summarizes of the most relevant results as well as the results of this paper. For monotonic submodular maximization specifically, previous work use Lemma II with appropriate e to prove an upper bound on expected Regrett when the greedy result with perfect information gives an a-approximation of the actual maximum value.
Stochastic In the stochastic setting, when the expected reward function submodular and mono- tonic, 28] proposed an explore-then-commit algorithm with full-bandit feedback that achieves Rgr = (14/322// 1/3/p /3 Recently, [3I]] showed with the same ssplore-then-comme algorithm with different parameters, Hgrr Okn /3/2/3 + 2 is possible with delay feedback pa- rameter of d. Without the monotonicity, [15]] achieves Rg (nT2)33 with bandit feedback for semi-bandit feedback setting ([42), [455)), and others such as getting the marginal gain of each element after each query.
= 1/2. There have also been several works
Adversarial In the adversarial setting, the environment chooses arbitrary sequence of monotone submodular functions ,fi,...,fzi and the goal is to minimize regret against an approximation
of the reward of the best set in hindsight ([LZ), [ [x], [I]) [+ showed Ok- logn)
R Ru----ty-rege is possible with partially transparent feedback(whers after each round, f f()))) for
Moot previous works, P2 BT] state their result in terms of R., however, careful analysis of the proof's of
their main regret bounds show a stronger result in terms of Rgr-

---

all i is revealed instead of only f(S(k)) and OKkn /32//3372/3) Be--e-t--reret for the bandit- mendit-fedbbcck setting. [27 proposed generalized algorithm with (kk22/822/3) Bi-- 1y-regret with full ban- dit feedback, and showed all explore-then-commit greedy algorithms have 22(2233) regret, when applied to our setting. Without the monotone assumption, [27]] gets ( R(1/2)-regret with bandit feedback. The upper-bound results in the adversarial setting doesn't naturally lead to results in the stochastic setting as the function is submodular and monotone only in expectation in the stochastic setting.
Continuous Submodular There are several works on online maximization of the continuous extensions of submodular set functions
compact subspace such as Lovász and multilinear cXtensions([E),, [[=]].. With a stronger assumption
DRssubmodulariity it's possible to achieve
higher approximation ratio guarantees and lower regret bounds ([ā)) [ (33)). [[I]] uses multilin-
extension to achieve O(T2/3) Ry-gert-teeret for adversarial submodular maximization with partition matroid constraint.
Low-degree polynomial In general reward functions without the submodular assumption, [02]] showed if the reward function is d-degree polynomial, O (mmin(VnnT) Vn*T)) regret is optimal.
2 LOWER BOUND
Theorem 2.1. For any n 2 4, & S [n/3]. satisfying 512k3n < T E N, let F denote the set of submodular functions that non-decreasing and bounded by [0, 1] for sets of size is or less, with
f(0) = Then
inf sup B(Rgr] 2 (k - (3) 4 /
1
1 T
(m==))
n
Alg fEr
16
where the infimum is over all randomized algorithms and the supremum is over the functions in F. and 1 E [k] is the largest value satisfying niga T.
16
(n-
The lowerbound is intuitively mix of the greedy explore-ther then-committ algorithm for the first k - arms, and then a standard MAB algorithm between all superarms cardinality & that include those elements. For small T' (i.e. On)))) the regret would be 2(333/3/2/3/22/) and for large T(ie. T ((n3k-2)) the regret would be ((()) 1/2 /2/).. This lowerbound also immediately gives lower bound for the adversarial setting where fi = -f +O, 1) is the function chosen by the environment iime i.
Proof Sketch
We construct hard instance so that at each cardinality single set gives elevated reward. Focusing on for illustration, the instance would be the following:
[(ti)= 1/2
i (1}
=(1i))=1/2 -
if [1]
H, =
[(ti,i))3//
= if if E (() (1,2))
[(fi,j))=B) =
where A is the gap of the best set that will tune based on T. Pulling any arm of cardinality less than 2 would incur 2(1) regret, however, since there are only n such sets (compared to (?) sets of size 2). pulling these simple arms give more information the optimal set.
For set of alternative instances, we choose set of size and elevate its reward by 2A. We also elevate every prefix set of permutation of this set by 2A so that the new set can be found by
5

---

greedy algorithm. Again, for l = 2, and any {i,}} E [n]
[((i)) = 1/2
i (1}
-(11))=12++4 A
if e
= A
if E [n] {1,7]
H
f(fi.))= 3/4
if = = if (i,j) (i,J)
[((i:))= = 3/4 A
f((i,5))= A A
Otherwise
Note that, if A
16 for the 2 instance, All the functions submodular, [((a,
f((b)) s +22 < 1/2 - f(fa)) -(({)) for any a, E [n].
For Ho, if A for all i E [2]. then fni (5)r) - as the noisy greedy finds the best arm, and otherwise 1'c 2 A, so min.20 fH. (5)r) + 1-1 = 3. Similarly, mine20 f (Str) + 1
A. So for these instances Rg R(S").
We show that the KL divergence between an alternate instance and Hg small, then the algo- rithm cannot distinguish between the two environments and the maximum regret of the two would be ((TT). Let P;3. Eyz be the probability and expectation under H33. respectively when exe- cuting some fixed algorithm with observations being corrupted by standard Gaussian noise. Then L
A² [Eo] + 4Eo(Trz]) for k = 2, where T's is the number of pulls of set S, and
Eo Eo Rgrl -R, Rgr!
Eo Ti
AT 2
Po(T1.2 S 2)) + (Ti,(Ti,
(Ti,2 > 5)) Σ Eg [Ti)
:=1
E. [.]
AT exp( KT PT5))
AF exp
(EolTT Bo(Ta5)))
Since 7. were arbitrary, the following Lemma shows that there exist pair that are pulled for small number of times in expectation (see Lemma A.2 for general k).
Lemma 2.2. There exists a pair ž,3 such that
2 23, [T[T:]
T 2
Eo[Ty| + [o[]3 <
Proof. For a pair (i,j), define Q(t.)) = Bo[T.] + Bo [o]T. Then the sum of this term for all pairs not equal to 1,2 would be
Q = Σ
Qusi S (n-3)
Σ
Eo [T + Σ
Eo[Tiy S (n 3) > Eg [T] + T
(L.))(()
(x.2))
1./122
Then by Pigeonhole principal there exist a pair 7, such that
Q < 2
T
Q Q63 <
Eo
EolTi
+
(n-2)
Using the lemma, for some (i,7), we have
Ey Rgrl
E Rir
E.
AT To
+ 4 exp (-22²(
Σ
EolTi
T +
(1=3)) ))
T
n n-2
We choose appropriate A based value of i".

---

2A if 1, then for A T we have
n- S 1. either the KL divergence is less
than 2, then the regret is lowerbounded by T T2/3 or for KL. divergence to be larger than 2 we would have Σ, Bo[T.] 2 2 n//3 1/3, which from the above equation
shows the regret is 22(T2/3n1/3) This can be extended for expected value of pulls of each cardinality lower than 1" for general k.
If 2, then it can be shown that the term Σ Eg T3.
AT exp
with A = (" when Σ1=1 [o|Ti] = 0 i.e. zero single arm sets being pulled in expectation, so the regret would be 1 ("23 exp(-2).
2
2 E, BolTi + (T - Es
/ minimizes
n-2
This shows that the expected regret is (min, ((minn(22//))))) (12/3 VV (T)))) The instance of general k, and the detailed proof is in appendix A.
We define algorithm to be in non-adaptive greedy error-threshold class against Rgr regret, if selects ci....,y c at the start only dependent on parameters T, n, k before any arm pulls, and minimizes regret against f( fall within this restricted class, and with this extra assumption we can prove a stronger lower bound.
e'. All the algorithms from previous work in the literature
Theorem 2.3. For any n 2 4, k S [n/3], satisfying 5124 I E N, let denote the set of submodular functions that non-decreasing and bounded by [0. 1] for sets of size ls or less, with f(0) = 0. Then
inf sup TE [ 2 AICENAET JEF
- (
1 T1/2 4
("==)(
288
it
where the infimum lection, and the supremum is over the functions in F, and i" E [k]] is the largest value satisfying
all randomized algorithms with non-adaptive greedy error threshold
m T.
UCB UPPER BOUND
Algorithm SUB-UCB algorithm for set bandits with cardinality constraints
1: Input: T, m, greedy stop level
2: Initialization: g()) 0. T' for all A C [n:]
3: For each [m]. pull {a} exactly m times and update T(a) Update mn.
for iori=10 1,2,.....
5: Un
for a 16-1
6: while T s(r max
do
7:
Pull arm St S(i-1) U arg max. Ua, observe rs, and update Ts, + Ts, +
8:
for each o s(t do
Sa c- 5(1-1) {a]
10:
ūs. + Ts. Emn=s Pt
11:
Compute UCB: U. = jus_
Hlost Tea
12:
end for
13:
t 1
14:
end while
15:
Update the base set: s(0) 1) U {as} where a; == max, Ua
16:
end for
while
18: Run UCB on all size super-arms A where 50)) e A.
19:
end while
natural approach to minimizing regret to take an Siploor-Thee-Coomee strategy motivated by the greedy algorithm. Such an algorithm would be the following proceed in & rounds. Set 5 0.
7

---

In round i pull each set in the collection U a [n]\ m times. Use these samples to update estimate f of f on these sets, and set S(t) f arg max f(S approach has been pursued by existing works [28], and with an appropriate choice m results in Okkn2/872/3) regret.
u {a}). This
The disadvantage of this approach is that it can not achieve the correct trade-off between V and kn / exhibited by the lower bound. Motivated by the statement of the lower bound, our algorithm SUB- UCB attempts to interpolate between these different regret regimes. The critical quantity is i". For the first i-i cardinalities, our algorithm plays a UCB style strategy which more or less follows the ETC strategy described in the previous paragraph. After that, it defaults to UCB algorithm all subsets containing 5 total of ("**+* possible arms.
Theorem 3.1. For any S k SUB-UCB guarantees
T n k. Rl S (1 (11+4V2)11 23 1/3 (log 1) / + / / k: 1-1 log T
32 nn k
15 k - 1)
when = T2/3 -2// log T
2/3
Proof Sketch We show that for e == 2 log(2kn?z²) the greedy part of SUB-UCB with high probability adds an e-optimal arm in each step. Defining event G to be lās f(S) I
V 2T's log(2kn(72) for all iterations, we prove that this event is true with probability of at least
On Event G. We show that an e-good arm is selected at each step of the greedy algorithm for e 2V 12 Let be sub-optimal arm with expected reward value more than 2
22k
from the best arm in the i-th step i.e. Ago,a = max f(S U {a')) f(s u faa) 2
2 Bogg (2gn11 Then if arm a is added in i-th step, we have (t) 2 Ua-(t) 2 f(S())u(a),
and therefore,
2 2lg(22k77))
(a(t) - l(S (a}) Ast > 2/
m
2 22 m This a contradiction with event G, so on event G such an arm cannot be selected. Lastly, we expand the regret of two stages. As UCB the second part of the algorithm has the regret of 65, (T(=)) log T + 32 (+=t) against the best arm containing (see [244), it is an upper bound for the regret against the greedy solution were the first steps select e-good arm, and the last l / steps select the best arm, event G the regret can be
so Py f(S() U {a})
written against a set in Si,e where
2 loog(22)) 2km72)
Iee = le (k- 1 1)0 = 2
Therefore, the expected regret EE Rgr] on event Gi can be written as
log 22k + mn(k - (*) + 0.5 T n
32 (n k) log T+
2T1
m
k -
15 k -
for any choice of m and 211 (T)))) The detailed proof is in Appendix B
So for m = T2/3, log" 1/3 (2knT²² the above term becomes
4 EXPERIMENTS
For the experiments we compare SUB-UCB (!) for different greedy stop levels 1, SUB-UCB (k i") which selects the best stop level based on the regret analysis, the ETCG (explore-then-comel greedy) algorithm from [28], and UCB on all size & arms. Each arm pull has a 1-Gaussian noise, with 50 trials for each setting. The expected reward functions are the following.
8

---

SUB-UCBlours) size
ETCG
10
lotal regret
10
10
10"
10"
10
Figure 1: Regret comparison for weighted set cover with 15 and k 4
Functions:
-The Unique greedy path hard instance i.e.
Σ
St Σ
S= (1.....|11) S (I,..,,,|$1
f(s)
100
This function inspired by the hard instance in the proof of lower-bound. Note that this particular parameterization is submodular when S 7, not for general k.
Weighted set cover function i.c. fc(S) Ecec (S * 0} for partition C of []] and weight function on the partition. For n 15 and k 4, we use the partitions of size 5, 5, 4, with weights of 1/10, 1/10, 2/ 10, 1010 respectively.
Results: As illustrated in figure MI we observe that our algorithm with the level selection of k - i" outperforms both ETCG and naive UCB all size & arms, it combines the advantages of greedy approach for small Ts and UCB on many super arms for large T. For smaller T's compared to (2). both SUB-UCB and ETCG outperform normal UCB it doesn't 't have enough budget to find optimal sets of size k gets linear regret(as the other two get O(T2/3)). However, as T becomes larger the reverse happens as (w) 71/2 becomes smaller than T2/3 but SUB-UCB adopts to and continues to outperform the two until it converges with naive UCB for very large T.
SUR-U109001
SUE-UCE(1]
UE-UCC121
UCB131
SUB UC3/4)
total rogist
SUB-UCB/51
20000
1010000300
5030
100
10a
207
Figure 2: Comparison between all SUB-UCB greedy stop cardinality choices for the unique greedy path function with n 20 and ko The worst-case optimal stop cardinality 1 k is highlighted

---

In figure Z we compare the performance of SUB-UCB for different choices of greedy stop cardinal- ity, and observe that the best choice gradually decreases from k to 0 as T gets larger, and k i" is a practical selection of the best stop cardinality before running the algorithm. Note that the defined stop level was chosen to minimize the worst-case bound on the regret, and the gaps between arms on a particular instance are larger than the worst case, this stop level could be conservative. So k - near the optimal stop level, and not the exact one as seen these figures. Also, the empirical stan- dard derivation is much smaller than ( due the regret symmetry of non-optimal sets at each cardinality, and it's s not visible in the plots.
5 CONCLUSION
In this paper we showed that ming 23/333333 / ignoring logarithmic factors, is
lower bound the regret against robust greedy solutions of stochastic submodular functions, and a stronger lower bound the algorithm class is slightly restricted. We also matched this bound with algorithm. This work is the first minimax lower bound for submodular bandits, and beyond closing the k2/$ gap between the general lowerbound and upperbound, it remains open to prove similar minimax optimal bounds settings with different types of constraint such as matroid, or in general, any offline-to-one tonoinne greedy procedure that is robust to local noise (e.g. Non-monotonic submodular maximization where the greedy approach gets a 1/2-approximation of the function, or DR-submodular optimization for the continuous setting which also has (1 é >-approximation)
Acknowledgements
This paper is based work supported by Microsoft Grant for Customer Experience Innovation.
References
[1] Mridul Agarwal, Vancet Aggarwal, Christopher Quinn, and Abhishek Umrawal. DART: aDaptive Accept RejecT for non-linear top-K subset identification, November 2020. arXiv:2011.07687 [cs, stat].
[2] Mridul Agarwal, Vaneet Aggarwal, Christopher J. Quinn, and Abhishek K. Umrawal. Stochas- tic Top-$KS Subset Bandits with Linear Space and Non-Linear Feedback, October 2021.
arXiv:18111 1.1.811..1111 1925 [cs, stat].
[3] Francis Bach. Submodular functions: from discrete to continuous domains. Math. Program., 175(1))411459, May 2019.
[4] Maria-Florina Balean and Nicholas A Harvey. Learning Submodular Functions.
[5] Eric Balkanski and Yaron Singer. The adaptive complexity of maximizing submodular func- tion. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing. pages 1138 113--111, Los Angeles CA USA, June 2018. ACM.
[6] Andrew An Bian, Joachim M. Buhmann, Andreas Krause, and Sebastian Tschiatschek. Guar- antees for Greedy Maximization of Non-submodular Functions with Applications, May 2019. MeXiv:1703.021000 [cs, math].
[7] Andrew An Bian, Kfrr Y. Levy, Andreas Krause, and Joachim M. Buhmann. Continuous dr- submodular maximization: structure and algorithms. In Proceedings of the 31st International Conference on Neural Information Processing Systems, NIPS' 17, page 486496, Red Hook, NY, USA, 2017. Curran Associates Inc.
[8] Andrew An Bian, Baharan Mirzasoleiman, Joachim Buhmann, and Andreas Krause. Guar- anteed Non-convex Optimization: Submodular Maximization over Continuous Domains. In Aarti Singh and Jerry Zhu, editors, Proceedings of the 20th International Conference on Ar- rificial Intelligence and Statistics, volume 54 Proceedings of Machine Learning Research, pages 111-120, PMLR, 20-22 Apr 2017.
10

---

[9] Lin Chen, Hamed Hassani, and Amin Karbasi. Online continuous submodular maximiza- tion. In Amos Storkey and Fernando Perez-Cruz, editors, Proceedings of the Twenty- First International Conference on Artificial Intelligence and Statistics, volume 84 of Proceedings of Machine Learning Research, pages 1896-1905. PMLR, 09-11 Apr 2018.
[10] Wei Chen, Wei Hu, Fu Li, Jian Li, Yu Liu, and Pinyan Lu. Combinatorial Multi-Armed Ban- dit with General Reward Functions. In Advances in Neural Information Processing Systems, volume 29, Curran Associates, Inc., 2016.
[11] Wei Chen, Yajun Wang, Yang Yuan, and Qinshi Wang. Combinatorial Multi-Armed Bandit and Its Extension to Probabilistiially Triggered Arms, March 2016. utXiv:1407.8339 [cs].
[12] Xi Chen, Yanjun Han, and Yining Wang. Adversarial Combinatorial Bandits with General Non-linear Reward Functions, January 2021. 1tXiv:2101.01001 [cs, stat].
[13] Uriel Feige. A threshold of In n for approximating set cover. J. ACM, 45(4))633652, jul 1998.
[14] Moran Feldman and Amin Karbasi. Continuous submodular maximization: Beyond dr- submodularity. In H. Larochelle, M. Ranzato, R. Hadsell, M.F. Balcan, and H. Lin, editors, Advances in Neural Information Processing Systems, volume 33, pages 1404-1416. Curran Associates, Inc., 2020.
[15] Fares Fourati, Vaneet Aggarwal, Christopher Quinn, and Mohamed- Alouini. Random- ized greedy learning for non-monotone stochastic submodular maximization under full-bandit feedback. In Francisco Ruiz, Jennifer Dy, and Jan-Wer Willee de Meent, editors, Proceedings of The 26th International Conference on Artificial Intelligence and Statistics, volume 206 of Proceedings of Machine Learning Research, pages 7455 -771. PMLR, 25-27 Apr 2023.
[16] Michel X. Goemans, Nicholas J. A. Harvey, Satoru Iwata, and Vahab Mirrokni. Approximat- ing Submodular Functions Everywhere. In Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 535-544. Society for Industrial and Applied Math- ematics, January 2009.
[17] Daniel Golovin, Andreas Krause, and Matthew Streeter. Online submodular maximization under matroid constraint with application to learning assignments, 2014.
[18] Botao Hao, Tor Lattimore, and Mengdi Wang. High-Dimensional Sparse Linear Bandits, September 2021. D.Xiv:2011.04000 [cs, math, stat].
[19] Nicholas Harvey, Christopher Liaw, and Tasuku Soma. Improved Algorithms for Online Sub- modular Maximization via First-order Regret Bounds. In Advances Neural Information Processing Systems, volume 33, pages 123-133. Curran Associates, Inc., 2020.
[20] Daniel N Hill, Houssam Nassif, Yi Liu, Anand Iyer, and SVN Vishwanathan. An efficient ban- dit algorithm for realtime multivariate optimization. In Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pages 1813-18211 2017.
[21] Emilie Kaufmann, Olivier Cappé, and Aurélien Garivier On the Complexity of Best Arm Identification Multi-Armed Bandit Models, November 2016. M.KV:1400..444 [cs, stat].
[22] Michael Keams and Satinder Singh. Near-optimal reinforcement learning in polynomial time. Machine learning. 49(2):209-22 2002.
[23] Andreas Krause and Daniel Golovin. Submodular Function Maximization. In Lucas Bor- deaux, Youssef Hamadi, and Pushmeet Kohli, editors, Tractability, pages 71-104. Cambridge University Press, I edition, February 2014.
[24] Tor Lattimore and Csaha Szepesvari. Bandit algorithms. 2017.
[25] Tatsuya Matsuoka, Shinji Ito, and Naoto Ohsaka. Tracking Regret Bounds for Online Submod- ular Optimization. Proceedings of The 24th International Conference on Artificial Intelli- gence and Statistics, pages 3421-3429, PMLR, March 2021. ISSN; 2640-3498.
11

---

[26] George L Nemhauser and Laurence A Wolsey, Submodular set functions, matroids and the greedy algorithm: Tight worst-case bounds and some generalizations of the rado-edmonds theorem. Combinatorica, 3(3-4):257-268, 1978.
[27] Rad Niazadeh, Negin Golrezaei, Joshua Wang, Fransisca Susan, and Ashwinkumar Badani- diyuru. Online Learning via Offline Greedy Algorithms: Applications in Market Design and Optimization, February 2023, arXiv:2102.1 1050 [cs, math, stat].
[28] Guanyu Nie, Mridul Agarwal, Abhishek Kumar Umrawal, Vaneet Aggarwal, and Christo- pher John Quinn. An Explore-then-ommml Algorithm for Submodular Maximization Under Full-bandi Feedback. 2022.
[29] Guanyu Nie, Yididiya Y Nadew, Yanhui Zhu, Vaneet Aggarwal, and Christopher John Quinn. A framework for adapting offline algorithms to solve combinatorial multi-armed bandit prob lems with bandit feedback. In Proceedings of the 40th International Conference on Machine Learning, ICML'23 23. Jog..org, 2023.
[30] Stephen U. Pasteris, Alberto Rumi, Fabio Vitale, and Nicolò Cesa- Bianchi. Sum-max sub- modular bandits. In Sanjoy Dasgupta, Stephan Mandt, and Yingzhen Li, editors, Proceedings of The 27th International Conference on Artificial Intelligence and Statistics, volume 238 of Proceedings of Machine Learning Research, pages 2323-2331, PMLR, 02-04 May 2024.
[31] Mohammad Pedramfar and Vaneet Aggarwal. Stochastic Submodular Bandits with Delayed Composite Anonymous Bandit Feedback, March 2023, arXiv:2303. 13604 [cs].
[32] Tim Roughgarden and Joshua R. Wang. An optimal learning algorithm for online uncon- strained submodular maximization. In Sébastien Bubeck, Vianney Perchet, and Philippe Rigol- let, editors, Proceedings of the 31st Conference On Learning Theory, volume 75 of Proceed- ings of Machine Learning Research, pages 1307-1325. PMLR, 06-09 Jul 2018.
[33] Omid Sadeghi, Prasanna Raut, and Maryam Fazel. Improved Regret Bounds for Online Sub- modular Maximization, June 2021. arXiv:2106.07836 [es, math, stat].
[34] Max Simchowitz, Kevin Jamieson, and Benjamin Recht. Best-of-K Bandits, March 2016. arXiv:1603.02752 [cs, stat].
[35] Adish Singla, Sebastian Tschiatschek, and Andreas Krause. Noisy submodular maximiza- tion via adaptive sampling with applications to crowdsourced image collection summarization. In Proceedings of the Thirtieth AAAI Conference Artificial Intelligence, AAAI' 16, page 20372043. AAAI Press, 2016.
[36] Matthew Streeter and Daniel Golovin. An Online Algorithm for Maximizing Submodular Functions:. Technical report, Defense Technical Information Center, Fort Belvoir, VA, Decem- ber 2007.
[37] Matthew Streeter and Daniel Golovin. An Online Algorithm for Maximizing Submodular Functions. In Advances in Neural Information Processing Systems, volume 21. Curran Asso- ciates, Inc., 2008
[38] Matthew Streeter, Daniel Golovin, and Andreas Krause. Online learning of assignments. In Y. Bengio, D. Schuurmans, J. Lafferty, C. Williams, and A. Culotta, editors, Advances in Neural Information Processing Systems, volume 22. Curran Associates, Inc., 2009.
[39] Maxim Sviridenko, Jan Vondrák, and Justin Ward. Optimal approximation for submodular and supermodular optimization with bounded curvature, December 2014. arXiv:1311. 1iti:1311..729 [cs].
[40] Zoya Svitkina and Lisa Fleischer. Submodular approximation: sampling-bast based algorithms and lower bounds, May 2010. arXiv:0805. 1071 [cs].
[41] Zongqi Wan, Jialin Zhang, Wei Chen, Xiaoming Sun, and Zhijie Zhang. Bandit multi-linear DR-submodular maximization and its applications on adversarial submodular bandits. In Andreas Krause, Emma Brunskill, Kyunghyun Cho, Barbara Engelhardt, Sivan Sabato, and Jonathan Scarlett, editors, Proceedings of the 40th International Conference on Machine Learn- ing, volume 202 of Proceedings of Machine Learning Research, pages 35491-35524. PMLR, 23-29 Jul 2023.
12

---

[42] Zheng Wen, Branislav Kveton, Michal Valko, and Sharan Vaswani. Online influence max- imization under independent cascade model with semi-bandit feedback. In Proceedings of the 31s International Conference on Neural Information Processing Systems, NIPS' 17, page 30263036, Red Hook, NY, USA, 2017. Curran Associates Inc.
[43] Mingrui Zhang, Lin Chen, Hamed Hassani, and Amin Karbasi. Online continuous submod- ular maximization: From full-information to bandit feedback. In H. Wallach, H. Larochelle, Fox, and R. Garnett, editors, Advances in Neural Informa-
A. Beygelzimer, F. d' d'Alché-But fion Processing Systems, volume 32. Curran Associates, Inc., 2019.
[44] Qixin Zhang, Zengde Deng, Zaiyi Chen, Haoyuan Hu, and Yu Yang. Stochastic continuous submodular maximization: Boosting via non-oblivious function. In Kamalika Chaudhuri, Ste- fanie Jegelka, Le Song, Csaba Szepesvari, Gang Niu, and Sivan Sabato, editors, Proceedings of the 39th International Conference on Machine Learning, volume 162 of Proceedings of Machine Learning Research, pages 16-26331 PMLR, 17-23 Jul 2022.
[45] Junlong Zhu, Qingtao Wu, Mingchuan Zhang, Ruijuan Zheng, and Keqin Li. Projection-free decentralized online learning for submodular maxinization over time-varying networks. Jour- nal of Machine Learning Research, 22(51):1 2021.
13

---

A Lowerbound proofs
A.1 Proof of Theorem
For any (I1, T2....,, x&} E (Iu.)))...))) define instance Ho, H( H (o with reward functions follows:
(Ha
Hist+h H₂
Li=1
||
== (1,2..... |S|}
HIST+K - HR
Otherwise
H1 H2 A
S {Ii, 22, ................................ t1s1}
Pil (S) =
HI Hk
{1, 2..,.... |S|}
H1 H2 A
Otherwise
+1 Hs A
S [1, [1...., J1+1. +1s
[Hee on) (5)
HI HK
S= .1.
His
HA
Otherwise
where H, - E is the n-th harmonic number.
Lemma A.I. If A (1/812) then Hy and H H(ss...es) submodular.
Proof. for any E C [n] where [T] & (the function only defined on sets of cardinality at most k) and & T we have to show f(S + x) - f(S) 2 f(T + f(T).
f(T + x) - f(T)= T+k+1
22
2A
T + ++++1
4
K
4k
k
$ S +1+
22 < /(S + x) - ((S)
For Ho if e; < A at each step i of the greedy arm selection, then S#r = (l...., ,k,, otherwise fno. (Stee) + 1 H2 H2 A --A A Н2 H₁ fur (f1, ([ll...,,)), k)). So mine fni, (S 1'e fNo ((1,..., k}). This means that Similarly, mine J ( (S 1He H2* H4 + A Sz an ((v1,..,, showing that we can compute our regret against (..,...,... .
compute our regret against fro ((I,.... k}).
Let En and E(z.....z)) denote the probability law under Ho and H( respectively. For any C [m] let Ts denote the random variable describing the number of time the set S is played by a policy Define T; = Esch-) Ts-
Then by the definition of Ho we have
Eg Rg
(Jro (1,
max SN (S)) 8:19-=
+
Σ (fI......., - Sno (S))EE, S:1S|=k
1/(k + Eo
Σ
Eo|T (o
1=1
1=
( } (1.....)
AT
Ep [T) +
Po Po ( (T (1....)) T/22
2k
2
14

---

Similarly for H(r
we have
E |Rar
(x1.....2)
k-1
( (1:1,..., xk3) () -max fu (s).))e) [7i]]]
|s|=i
(f
) (S))
k-1 k
2
1/(k: + (a [Td] +
Σ
E [x (T (x
1=it1
AT
P
(0 (2)
m2) (T T/2).
2
Lemma A.2. For any S k here exist sequence (Ia...., where
Bol [1. 1.
1 Bolli] (n - kn k 1)
2
4
k kーj
T
Eo [1+1]] (n - k)(n t - 1) j=i+2
KolT']
+
11
(x-
Proof. For i S i and sequence (Iz,,.., define Q (asiiinnt))
Ej Eg [T (1....--1
Then we have
in k- jii + (n 2k + 1)!
1)((j - i 1)!
Eo ((A-)))(
(D..... (b..... k)
Then by Pigeonhole principle, the exists sequence (z (z....., 2x)) such that
Q (Z S
(n-h)) -1-1 1)!
n
(n k -j 1)10))(j--1 --- 1)!
(n 2k + i - 1)!(A:
i + 1)!
Eo [T]
B[Ta]
(n (c-kk) k:)!
(n k:)!
j=1
1
k-1
(j
ij - i 1)
Eo [Ti]
+
E[Ty]]
E
+
E[Ta]
n k
(n k)(n - k 1)
n k-2
(x-TT+1
j=i+1
j-i-2)
2
Eg [T:]
En [T++1]
n k
(n kn k 1)
k-1
k: -- j
T
Eu [Tjl
+
(n- kn
1:
2k
nーk
s=i+2
k-
Lemma A.3. For Ho and H(s)...)))) defined above, we have
[LP (F 21
Eg TT
-1 1,
Proof.
LL P (())))))))
Σ
EolT's (L(((()) (s))...)))))
(lemma 15.1 in [24])
S:ISISA
24 T 1
15

---

where Po(S) (f),,(S),1 and m)) (S) - Wf ( (S), 1) are the reward distribu- tions of arm S in Ho and H XN) respectively.
Using two above lemmas, we have,
2 max
Bo Rgrl
max I ( ()) (t.....)
E (a Rgrl)
2
max
Fso RgrR + E B( Ryrl
AT Po(TT11..... S T1/2) + P Par.....) (T > T/2)
max
1sish
AT
max
exp( (XPo-KL(Pol (s....a))))
(Using Pinsker's Inequality [24]]
of R))
AT
k
max
exp
22
Ep ( (1.....) 1.....11,........... (....,,,))
(Using lemma
j=i
AT
2
2
max exp
- 21²
Eo[Ti]
+
Bo Ti+1l
2
ISick
k
(n kn k
k-1
1
T
+
Ro
[Ty]
+
(Using Lemma A
(n k) 1: - 1)
2k
nー
j=i+2
4----1
2 max Isick 2
1
(k- - 1/331//3//////
exp
2T 2/3 - 22/2/3 2/33
1
Eo [T]
k
4
k- RolTy] +
T
R Bo(Ti+1]
(n (n 1: 1)
(n- kn 1: 1)
2h:
nーk
j=it2
k-++1)
(Setting A = ((k - (
2//3711/3
For 1 5 k 8t + 1,
2 1 by definition of i"; either the maximum re-
gret is larger than 2/ - 10)1/31p
1/3
1/3 -8). which proves the theorem, or - Eo[.] kーj En TjJ 2 3(1A²²). the third term is larger 2 n
(n- k-1 (i+ + kー Σ
Eo[y,] 2 (1-7')77 T n/ 1/3 which proves the lowerbound as than 1/2?, then Σ Σj=it 2h
(k-1)278 2 (k- 1/3 Therefore, the only remaining case is that either the first or second term is > 2/A². This means that for 1 < i k - 1' + 1. either ET[T.] > [k i²) 22)-2/322// /3 or To[T.+] 2 (n (k i*) 2/37
[ 10) 2/372/// 1/3 Therefore, for least half of the <i i g + 1, Eo [T) 2 } (1: - -1) 2/3 and
R- +1
k k-j [T]]T]
1 (k: - 13/33333333
(ggg 2
2
2h
8
Note that since T 7> 512k"n, n, we have A 5 1)1/3 < of A are submodular.
S1Z, so the functions with this selection
1
16

---

We now lower bound the regret in a different way. Let ;= Σ Limb-i+t 26 Bolad then A S 1, and using lemma A.2 we have that there exists a selection (Ziz.... T&) such that,
==
k
Epl T ( U [.),)))))
2=1
1
Bo[Ti]
2
Eo Eo[Ti+1]+ (n - k)(n - k - 1)
4
Σ
k-1
k k-j
Eo[T,]+
+
T
n -
k
(n - kn - k -1]
2k
(-i+1)
j=i+2
4
k
T
4
T
Bu [Ty]
XT
n
k j=i
2k:
(x=741)
kn-
k-it) )
n-k
So
max
[oo| Reol
max
E (x) Rgs)
(sish, ((......)))
max
BolBar] + E xx BAr
min max
XT +
AT
exp (-24²
Σ
k
Eol 1o
2
j=1
AT
4
T
min
max
Sisk
XT
+
2
exp
- 222
n1 k
XI
+
n-k
k-i+1
min
max
XI
+ 2
1/2
hi h- i [t1 1)
71 - k
1/2
exp
2
4 nー
(
(n k) -
xE 111
(Setting A = ((e=T+)//T)) (T)
n
k)
1/2
2 2
72/
-2
4T 3/2
The last inequality holds as log( minimizes in the last inequality. Combining the two parts of the proof we have
(e-1+))
S O, and the function relative to À is convex, À
[n-k]T
max Rgrh
max
E Ex x [arl
IsiSk,(m,
max (6 -k- - 1333/32// 1/30 1 T
n - k)
1/2
e 2)
2
1 (k (133 1/3 +
1 11/2
n - k)
1/2
c-2
16
4
A.2 Proof of Theorem
We generalize the lowerbound distance of Theorem by having the gap A in cardinality i. For any 22..,2..... x E (I)))......)) define instance Ho, H( i.....)) with reward functions as follows:
4
His +k H₂ Σ S
S (1,2, |S|}
(S):
i=1
His +k H₃ A A|sl
Otherwise
H|8| H4 + Ais
S {x1 22, 2
H| HR
S = {1, |
Hi HA Assi
Otherwise
l1 || H4 + AiSi
S [I,..., i Ii [1s
Minu (S)
H H|s H
S = (1,2,.... |S|}
1l (|stH H4 AJSi
Otherwise
17

---

The KL divergance between reward distribution of two instances is similarly:
& = Σ B T 1.....))))
L[Po (x)
j
Lemma A.4. For any S k here exist sequence (Ia..... ;b). where
2
A Bo [T (1... -odd--1,,, 111 1,
k AoBo[T.] +
(n k)(n h 1ol1Eoiitt1
6
+ (n k)(n k - 1)(n - - 2)
424
12
h --j Bo
T
+
+
(n k)(n k - 1) k: - 2)
2k:
j=4+3
k-++1
Proof. For i S k and sequence define Q (F شラ= 23100 [ 1.
Then we have
(n-k-j 1)1 -i 1)!
Q Σ
(p) mn)
(n 2k 1)!
(IiS....TTy kk
Then by Pigeonhole principle, the exists a sequence (z...... mx) such that
Q ((xeii22k)
(n-A) A)!
k-1
(n k 1 1)!
A + (n - 2k + 1)1(k= - - 1)! TM
(n (.-k)) k))
(n k)!
1=1
1
(j i)(i i 1)
Ao [Ti]
A [3 +
- E[Ti]
n K
(n - (n - k 1)
(11122
2)
(,:
1=
2
APEo[T:]+
A? Eo [Ti+1]
n K
(n kn - k - 1)
6
A A
(n (n
k
1)(n k 2)
12
k-1
kーj i
A&T
A3
+
(n- k) k- 1) - k: - 2)
2k
n-k
j=it3
We now assign A; for lower cardinalities based on the value of Ag. If1 e' S Fori S k 1, we assign A; = c/, so greedy procedure with e' will retrieve the best set, hence S (Ser + 1T 2 fno (f1...., k}) and f
For
(Ste 1 2 fMir...... (f1, (f,,..., i..,,,,,,200 2; .., xx Otherwise,
since the gap of any set of size & and the best set is at most 2Ax for both Ho and H())
fHo (Sh + 1 2 H2s H4 A + +24, = fna (f1,
..ll,...AAA .......,,)))))) and fn .2) (S + 1Tee'
H2 H4 - A + 2Ax 2 JH........ m Av Therefore, in both cases Rg 2 R(S*), and we give a lower bound for R(S*).
i 1, "..... });); so for < k - 1, and we assign
A; A
For the first part of the lower bound, we'll assign A = (k- (2)/33 Now similarly to proof of Theorem 1 we have
18

---

2 max [BolRy
E Ex xx (Bxr)
max
) (k.....))
T
m8x
exp
(
Bol [T (1..............)))
2
==ر
A
1
2
max exp
-2(
A [Ti]
A Bo(Ti+++
1Sisk
11 k
(n k)
k-
12
k-1
k k-j [T,]]
+ (n- - (n - k- - (n - - 2)
A +
(n kn k- - 1)(n - k-
2k
-=++3
A
n-k ))
(Using Lemma A.
1
2
(ks - (0--i)77 1233 1/3 exp (-21 2( k
A.E [T:]
A Eo [Tita]]]
max 1sigk
2
(n- (n-))(n- - h 1--1 -1
12
k-1
k k- j [T]]
1+2 +
(n- - k)n - k 1)(n - k 2)
(n - k)nn k - 1) - k -- 2)
2k
j=1+3
+ (k- - 1n
(Setting A == ((k: - 8 /')3)//
(++))
(2=5"")2,
- 12 2//2//3//3 S by definition of i": so either the
For S í S k +1,
(x=711)
(++1)
maximum regret is larger than TT2
'n')n!/² 1/3 exp( 100, which proves the theorem, or
1 A +
2
6
2 Eo [--1 + (n- k) - k- - 1)(n - k - 2) 4
n k
(n - k)(n k - 1)
12
h J
+ (n-k) kn k - kn k- 2)
Σ
A3E0
[T, 24
2k
j=i+3
If the forth term is larger than 1, then
k
k --j Eo|TT]
k- 1
k -ー 1T
Σ
2k
2k
j=1+3
j=it3
(n
kn k - 1)(n k - 2)
n²
12
96
So =
n2 2 36 - 1r) )n 1/3/2/33 which proves the lower bound.
2
2N
96 o.
Therefore, the only remaining case is that at least one of the first three terms is 2 1. This means
that for < i < k i" + 1, either Eg [T:) Z z... or Eo [T 2 uلi (n k 1) - or
Eo 2T 2 12
n (n k 1)(n k 2) Z 1202
Therefore, for at least 1/3 of the 1 i k 8' + 1, E.TT 2
1227 Let I be all cardinalities in which this inequality holds(so| | 2 أ-ي ); since Ei=l A < 24g. k. using Lemma GI we have k-r+
n
Eol Rgr 2
Σ
J Eo TT)
j-j n
> (k- 23)32/3,
2k
2k 12 288
j=1
jel
For the second part of the lower bound, using A, S 2A,, we have
k-1
K LL (z
1) 5 3
E (T ii.......e. 1,,
19

---

and the rest of the argument follows the proof of 2
B Proof of Theorem 3.
Proof. We use the notation / = k 1 to match our lowerbound, however as - i is arbitrary, can be used for any other choice of I as well. Define the event G == N (aejo))ssten) Ni ai, where
Σ (r. (r--1(((tDD & ( (2Tso- log
log log (2kn(22)
9i,
aStil= Sti (((
Now note that X, are i..d, sub-Gaussian random variables then
P(G
U
((ast
aE(n])(S(1-1)
T
Σ
CPUU
U
U =SP(S---
p((((((-)) =S)
sE(("!)
aE(n]SSt=1
P
((S -S)((ti-)) =
P(S((L)))
SE (,))
4E/n]iS
1=1
Σ Σ
P
(UI)
X.l V 21log(2nnT3] ((S((-1)== =)
SE [m]]
aE|n]is
1=1
Σ3ΣΣ
Σ Σ
P(S( 5) 1//T.
knT2
(E( eE(n]
Let & be the event that the arm selected the i-th step of the algorithm is within 2 the best possible arm that step, i.e.
2 2log (2kn21) of
log (2kn(
& max We prove that on event G, Ule(k->+jE true.
(($()) 22
1)
m
Let be a sub optimal arm with value more than 2 20g((AnTT)) from the best arm in the i-th step. That is, if a" = arg max f(S(i) {a')) and Agt,, := f(s() u {a*)) - f(S() U {a}), then assume that A A 2 2/
2 22og(2kn77)
Then on event and arm being added in i-th step,
m
Ua(t) 2 Un. (t) 2 f(S0) ((a))) f(s()) U {a}) + Agta
which implies
2 log 2log(2kn72)
Ua(t) - f(s Ufal) 2 Agco a > 2
m
But this implies that
log (2km222
(St))(a) s(S()) u U
which is contradiction of event G. Thus, on event G such an arm cannot be selected.
20

---

As UCB in the second part of the algorithm has the regret of 65 (T log T +
(==1)
32 15 k-
against
((k) which is the best size k arm containing S(k-i") (see [244]), on event G. it is an upper bound for the regret against the greedy solution were the first k i" steps select an e-good arm, and the last i*
steps select the best arm, so event G' the regret can be written against set in S where
log (2kn7²2
Iee = (k i = 2(k VVV
m
Therefore, we upper bound the regret relative to f(5*) + 2(k 1") it's greater than (1 ((S)). Let T; be the set of times where we pulled a set of cardinality i. From the while loop condition in the algorithm, we have [Til S Eaesu-n min { s² 1(1-1),a
(2kn7 as by Lemma 1_
.m I
(n + 1 1)m for i S i*. For e 2
1) 1
we have
B[ < PIG + Bl [GH - 7 + B[
R-1
$ +1+ Σ Σ (F(S(M) + (k- - ()e) - f(Sti-)) + E(r(s()) + (e)) f(S.)
i=1 EE
EE
$1+ -k- 1 1* TT + mn(k - m (onkk-i")][(S ()))((())))))))))))))))))))))))) + Σ ((((k)) - ((S.)
1E72
(f(S(i-1) U (a+))) 20)
22 -x))
2 Moog(knnT2 T2)
+ +mn(k= -1- + 65 T
11
32 n -
+1
15
1"
/2 (K-
(1ogg((2hnTT
1)1333 28T 1/3 1/3 (I: i (log(2knT2))) 1/3
32
+ + T
(Setting m 2 2/3 2/3 1/3 (2kn((2)
15
1
C Auxiliary Lemmas
Lemma C.1. For any sequence of numbers a,,... On bounded between a,,
then
n
n
C
Proof. If there exists j,k [n]
such that aj
<
ag. then for new sequence of
04g E {j. k)
we have
agtac 2
iE k}
1-2 - =a
2 2 4
+ ag
(a, ax)²
2 + a azaz
+ aj ag +2(a, ax + aaax - 8
o² aZ 2a,a
Therefore, the infimum value of Σ a-² over all such sequences is when all elements are equal, and
1
n²
Σ
n2
Σ a
C
21

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: We've stated all our results and the assumptions for them in the introduction. Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize other settings.
fine to include aspirational goals as motivation as long as it is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification: For our theoretical results, the assumptions are clearly stated, and our results are within these assumptions. We also state the experimental limitation of our algorithm in the experiments section.
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (c.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The au- thors should reflect on how these assumptions might be violated practice and what the implications would be.
The authors should reflect the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the ap- proach. For example, facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a speech-to-tex system might not be used reliably provide closed captions for online lectures because fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach ad- dress problems of privacy and faimeess.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community, Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
22

---

Answer: [Yes]
Justification: All the assumptions for each theorem are stated, a proof sketch is provided in the main text, and full proofs are in the appendix.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theo- rems.
The proof' can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be comple- mented by formal proofs provided in appendix supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main experimental results of the paper to the extent that it affects the main claims and/or conclu- sions of the paper (regardless of whether the code and data provided or not)?
Answer: [Yes]
Justification: Yes all the algorithms that are used in experiments and all the function defini- tions that are used as inputs are clearly written.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is a dataset and/or model, the authors should describe the steps taken make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, if the contribution is specific model and empirical evaluation, may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how replicate the results, access a hosted model (e.g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate the research performed.
While NeurIPS does not require releasing code, the conference does require all sub- missions to provide some reasonable avenue for reproducibility, which may depend on the nature the contribution. For example
(a) the contribution primarily a new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results way to re- produce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case au- thors are welcome to describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should possible for other researchers to have some path to reproducing or verifying the results.
23

---

5. Open access to data and code
Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Question:
Answer: [No]
Justification: This paper is theoretical work, and the experiments apply the proposed algorithm main text on synthetic functions which are fully defined in the main text. There are datasets used, and no code beyond the main algorithm implementation.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (httpps//nniss.ce)
hhboliccguiddee//eeeebbb.... son for more details.
While we encourage the release of code and data, we understand that this might not be possible, so No is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (c.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (ittps:)
ssiionolicy) for more details.
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data,
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Question:
Answer: [Yes]
Justification: We explain the functions used as inputs, and the synthetic noise applied to them. There other setting details as this is mainly theory paper and the experiments are trivial.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment Statistical Significance
Question:
Does the paper report error bars suitably and correctly defined or other appropri- ate information about the statistical significance of the experiments?
Answer: [Yes]
Justification: The empirical SDs are included in the plots, although hardly visible because of the logarithmic scale.
Guidelines:
The answer NA means that the paper does not include experiments.

---

The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall
with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
is OK to report I-sigma error bars, but one should state it. The authors should prefer- ably report a 2-sigma error bar than state that they have a 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not show in tables figures symmetric error bars that would yield results that are out of range (e.g. negative emror rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [NA]
Justification: There experiments that need anything more than laptop.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount compute required for each of the individual experimental runs as well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't 't make it into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics http::/hhwaari....cppppccc/cecec
Answer: [Yes]
Justification: Yes this paper conforms, in every respect, with the NeurIPS Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there is a special consid- eration due to laws or regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: This work is mainly theoretical, and there direct social impacts.
Guidelines:
25

---

The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negatíve societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact spe- cific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications,
authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
there are negative societal impacts, the authors could also discuss possible mitiga- tion strategies (e.g.. gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g.. pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
The paper doesn't pose any such risks is theoretical.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by re- quiring that users adhere to usage guidelines restrictions access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [NA]
Justification: No assets are used in this work.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset used and, possible, include a URL
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
26

---

If assets are released, the license, copyright information, and terms of use in the pack- age should be provided. For popular datasets, paperswithcode com/datasets has curated licenses for some datasets. Their licensing guide can help determine the li- cense of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information not available online, the authors are encouraged to reach out to the asset's s creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documenta- tion provided alongside the assets?
Answer: [NA]
Justification:
No new assets are released in this work.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/codeemoodel as part of their submissions structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the pa- per include the full text of instructions given to participants and screenshots, if applicable, well as details about compensation (if any)?
Answer: [NA]
Justification: he paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information the supplemental material is fine, but the main contri- bution of the paper involves human subjects, then as much detail as possible should be included the main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection. cura- tion, or other labor should be paid at least the minimum wage the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper deseribe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country institution) were obtained?
Answer: [NA]
Justification: the paper does not involve crowdsoureing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equiva- lent) may be required for any human subjects research. you obtained IRB approval, you should clearly state this in the paper.
27

---

We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
28


Reviews:
[{"review_id": "2lyln70Hsk", "reviewer": "Reviewer_LE4U", "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.", "questions": "W2", "limitations": "W1, W2, W3", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "S1. The authors prove the minimax regret bound of the submodular maximization problem with bandit feedback. \n\nS2. The authors also devise the algorithm Sub-UCB that can match the minimax bound up to logarithmic factors.\n\nS3. 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\".\n\nW2. 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?\n\nW3. 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate your review and valuable suggestions.\n\nRegarding your question on the applications of this setting, one example is antibiotic prescription, as mentioned in the introduction section. The reason for noisy feedback in this context is that patients come from a population with an unknown response distribution to an antibiotic for a specific disease. Our experiments were intended to demonstrate the theoretical interpolation between $T^{1/2}$ and $T^{2/3}$ regret bounds in our main theorems, and showing an application of submodular maximization wasn't our primary goal.\n\nWe agree with the reviewer's point W3 that the offline greedy solution for modular functions is optimal. In our paper, we also argue that regret against the greedy solution (which would be equal to $1$-regret) is more natural than $(1 - e^{-1})$-regret for these functions.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "AUj8omzkez", "reviewer": "Reviewer_yrL4", "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. \n\nThis 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). \nThis 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.", "questions": "Some suggestions:\n1. 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.\n2. In abstract, the authors use the notation L. But in the main text, they use the notation i instead of L. \n3. Line 80, there should be a “(” before “min”.\n4. 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.\n5. 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. \n\n[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\n\n[2]Stephen Pasteris, Alberto Rumi, Fabio Vitale, Nicolò Cesa-Bianchi, “Sum-max Submodular Bandits”, AISTATS 2024.\n\n[3]Zhang, M., Chen, L., Hassani, H., and Karbasi, A. “Online continuous submodular maximization: from full information to bandit feedback.” NeurIPS 2019\n\n[4]Chen, L., Hassani, H., and Karbasi, A. “Online continuous submodular maximization”, AISTATS 2018\n\n[5] Zhang, Q., Deng, Z., Chen, Z., Hu, H., and Yang, Y. “Stochastic continuous submodular maximization: Boosting via non-oblivious function”. ICML 2022", "limitations": "Yes", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 2, "contribution": 4, "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. \n\nBack 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.\n\nOverall, 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.\n\nAs 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”.\n\nPlease 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.\n\n[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\n\n[2] Stephen Pasteris, Alberto Rumi, Fabio Vitale, Nicolò Cesa-Bianchi, “Sum-max Submodular Bandits”, AISTATS 2024.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate your thorough review and valuable suggestions.\n\nWe agree that the statement in line 132 that $ R_{gr}$ is always more appropriate than $ R_{\\alpha}$ is too strong. We will change it to: \"In studying regret against approximations attained by an offline step-wise greedy procedure, $R_{gr}$ can be a more appropriate measure than $R_{\\alpha}$.\"\n\nRegarding Lemma C.1, it is a variant of Hölder's inequality. We will add a short proof in the Appendix to provide clarity and support.\n\nWe will expand the discussion on continuous submodular optimization within the Related Works section to survey important results in this area. Thank you for these additional references. Extending $R_{gr}$ to the continuous domain remains an interesting open problem that we will highlight.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "ECC9mn0Bdy", "reviewer": "Reviewer_eJpK", "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.", "questions": "I make the following suggestions:\n- 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.\n- Also, the minimax optimal version of the UCB or Thompson Sampling can be used in the second phase to fully match the lower bound.", "limitations": "See Weakness and Questions.", "rating": 4, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "- The paper introduces notation clearly and provides a sufficiently thorough comparison with related work.\n- 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.\n- 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.\n- 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.\n- 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your review.\n\nWe noticed that this review appears to be copied from a previous conference. We would like to highlight that the concerns raised have already been addressed in the current submission. Specifically:\n\n* In the introduction section (from line 119), we discuss the indirect use of $R_{gr}$ in previous works (i.e., the proofs are upper bounding this measure of regret), and then using Lemma 1.1 to upper bound $R_{\\alpha}$. We also argue that $\\alpha$-regret is zero or negative in many instances, and therefore a loose measure of regret in our setting.\n\n* The detailed proof of submodularity of the instance is provided in Lemma A.1 (with a proof sketch for $k=2$ on line 181).\n\n* We discuss the main novelty of our upper bound, which includes adding an optimal stopping cardinality to the greedy procedure depending on the time horizon.\n\n\nWe would appreciate receiving your feedback on the current version of the paper.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "a6BignU3Nf", "reviewer": "Reviewer_Tz5c", "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.", "questions": "### Major\n1. 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$?\n\n2. 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?\n\n### Very Minor \n3. 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.  \n4. 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.\n5. Theorem 2.1 requires $k\\leq \\lfloor{n/3}\\rfloor$ -- is there a simple reason for that?\n6. In the experiments, there are no error bars on the figures – was each marker for a single run?", "limitations": "Yes", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "### Major\n- 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.  \n    - 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.  \n    -  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).  \n  - 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)\n\n### Minor\n- 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).\n- 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\n- [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.\n\n\n### Minor\n- 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).\n- 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?\n\n\n### Very Minor\n- 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.  \n- line 80 missing parentheses\n- line 268 “UBC”\n- line 287 ‘were’--> ‘where’\n- In the experiments, 1-Gaussian noise seems strange given the functions are bounded in [0,1].\n- Figure 2 legend use power of 10 notation, or add commas\n- 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", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate your thorough review and valuable suggestions.\n\nIn [21], Theorem 7 provides a lower bound on the convergence rate of bandit Blackwell games. In our setting, as you correctly pointed out, this reduction implies that all explore-then-commit greedy algorithms in adversarial setting have $\\Omega(T^{2/3})$ regret, which is straightforward to show. In our work, we prove a lower bound on stochastic submodular maximization with cardinality constraint for any algorithm, not just explore-then-commit algorithms. We will add this to the related work section for completeness.\n\nThe time horizon can be very large for the web-layout example mentioned in the introduction, as the number of users can be much larger than ${n \\choose k}$. This makes the tradeoff relevant in these applications. It is reasonable to assume that reward of the users visiting the webpage are i.i.d.\n\nThe value of $i^*$ in the experiments is equal to the definition in line 219, and its value for each $T$ is highlighted in Figure 2. We will repeat the definition for clarity.\n\nRegarding your questions:\n\n1. The fast submodular algorithm in [1] is indeed an $\\epsilon$-greedy solution, given that the function is bounded by 1, as it is in our problem setting. In the proof of Claim 3.1, they first show that for the added element $a$, the inequality $f_S(a) \\ge (1 - \\epsilon)f_S(x)$ holds for any $x \\in O \\backslash S$, thus $f_S(a) \\ge \\max_{x \\in O \\backslash S} f_S(x) - \\epsilon$. The existence of another approximation for submodular maximization which achieves $1 - e^{-1}$ rate but is looser than the greedy procedure (specifically for modular or low-curvature submodular functions) that could achieve lower regret bounds is an interesting open problem.\n\n2. To generalize this to other problem domains, an equivalent of Lemma 1.1 is needed to show that a robust greedy solution approximates the optimal solution, similar to Definition 5 in [21]. Generalizing this, especially to the continuous domain DR-submodular maximization, is an interesting future direction.\n\n3. $S^{k, \\epsilon}_{gr}$ represents any set of robust greedy solutions $\\mathcal{S}^{k, \\epsilon}$, as defined in line 102. Thank you for the suggestion; we will simplify the notation in Lemma 1.1 for clarity.\n\n4. In the algorithm, a stop level $i$ less than $k$ is used when $T$ is large, allowing the algorithm to explore at least $\\binom{n}{k - i}$ sets of size $k - i$, thereby reducing the number of greedy steps needed.\n\n5. This choice is made for technical reasons in the proof to ensure that the class of alternate functions with different optimal sets and no intersection is sufficiently large (i.e., $\\binom{n - k}{k}$).\n\n\n[1] Ashwinkumar Badanidiyuru and Jan Vondrák, \"Fast algorithms for maximizing submodular functions\", SODA 2014, https://theory.stanford.edu/~jvondrak/data/submod-fast.pdf", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "P62DZCf1qf", "reviewer": "Reviewer_jwa8", "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.", "questions": "The reviewer expects the authors to address the questions mentioned above.", "limitations": "not appicable", "rating": 5, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 3, "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. \nWhile 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. \n\nThe 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.\n\nThe 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?\n\nIn Section 1.2, the authors mention the use of the Lovasz extension for online submodular maximization. Isn't this technique used for submodular minimization?\n\nAdditionally, the paper overall gives the impression of not being thoroughly proofread. To highlight some minor points:\nL120-122: [22] in Theorem 4.1, [24] in Theorem 1, .... -> Theorem 4.1 in [22], Theorem 1 in [24], ....,\nL160: Showed -> showed, L232: abbreviation ETC is not defined, Sec3: There are $S^{i}$ and $S^{(i)}$, which are confusing, L268: UBC -> UCB.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We are grateful for your review and suggestions.\n\nThe mention of two types of algorithms in the lower bound section is intended to provide more intuition for the $ T^{2/3} $ term of the lower bound, which is uncommon in the bandits literature. To avoid any confusion, we will move this intuition to the introduction section.\n\nTo answer your question about $\\mathcal{S}^{k, 0}$, the lower bound for regret against a noiseless greedy solution is $\\Omega(\\min(T, \\sqrt{\\binom{n}{k} T}))$, indicating that submodularity does not improve the regret. The intuition behind this is that the gap between the optimal set of cardinality $i$ and any other set of the same cardinality can be arbitrarily small (e.g., $T^{-10}$) for any $i < k$ and large only for sets of size $k$. This means that while the noiseless greedy solution can equal the optimal set of size $k$, distinguishing the optimal greedy elements in lower cardinalities with only $T$ queries is infeasible. Therefore, only querying sets of size $k$ provides any information about the optimal set. Although this is known in the literature, we will add it to the appendix to give more intuition on why robust greedy solutions are the appropriate benchmark for regret.\n\nIn the paragraph starting on line 155, we briefly mention two extensions of discrete submodular functions to the continuous domain and no-regret algorithms for these continuous functions, not as a technique for maximizing discrete submodular bandits. We will expand this paragraph to survey the domain expansion techniques for our problem setting (in which multilinear extension is used for maximization) as well. We also appreciate the proofreading corrections and will incorporate them.\n\nWe appreciate the reviewer for highlighting the typographical errors and will simplify the redundant notation in the upper bound section (e.g., only using $\\hat{\\mu}$ for estimation of the expected reward).", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: Reviewers expressed mostly positive opinions on the novelty and significance of this work. Still, some doubts were cast on the level of the authors' contributions due to a possibly not broad enough scope and some disagreement on the significance of the setting/novelty of the algorithmic ideas. Overall, I agree with the majority of the reviewers that the positives outweigh the negatives, and I recommend acceptance (poster).
Decision: Accept (poster)