Batch-Size Independent Regret Bounds for Combinatorial Semi-Bandits with Probabilistically Triggered Arms or Independent Arms
Authors: Xutong Liu
Jinhang Zuo
Siwei Wang
Carlee Joe-Wong
John Lui
Wei Chen
Venue: NeurIPS 2022 Accept (2022)
Keywords: Combinatorial multi-armed bandits
Variance-aware
Triggering arms
Batch-size

Abstract: In this paper, we study the combinatorial semi-bandits (CMAB) and focus on reducing the dependency of the batch-size $K$ in the regret bound, where $K$ is the total number of arms that can be pulled or triggered in each round. First, for the setting of CMAB with probabilistically triggered arms (CMAB-T), we discover a novel (directional) triggering probability and variance modulated (TPVM) condition that can replace the previously-used smoothness condition for various applications, such as cascading bandits, online network exploration and online influence maximization. Under this new condition, we propose a BCUCB-T algorithm with variance-aware confidence intervals and conduct regret analysis which reduces the $O(K)$ factor to $O(\log K)$ or $O(\log^2 K)$ in the regret bound, significantly improving the regret bounds for the above applications. Second, for the setting of non-triggering CMAB with independent arms, we propose a SESCB algorithm which leverages on the non-triggering version of the TPVM condition and completely removes the dependency on $K$ in the leading regret. As a valuable by-product, the regret analysis used in this paper can improve several existing results by a factor of $O(\log K)$. Finally, experimental evaluations show our superior performance compared with benchmark algorithms in different applications.

Batch-Size Independent Regret Bounds for Combinatorial Semi-Bandits with Probabilistically Triggered Arms or Independent Arms
Xutong Liu The Chinese University Hong Kong Hong Kong SAR, China liuxtêcse. cuhk. edu. hk
Jinhang Zuo Carnegie Mellon University Pittsburgh, PA, USA jzuo@andrew. cmu,
Siwei Wang
Carlee Joe-Wone
Microsoft Research Beijing, China Exkeivvangdmiccosffft.com
Carnegie Mellon University Pittsburgh, PA, USA
cjoewong@andrew cmu. edu
John C.S. Lui The Chinese University of Hong Kong Hong Kong SAR, China
Wei Chen
Microsoft Research Beijing, China we reic@microooof com
cslui@cse. cuhk, edu, hk
Abstract
In this paper, we study the combinatorial semi-bandits (CMAB) and focus on re- ducing the dependency of the batch-size in the regret bound, where K is the total number of arms that can be pulled or triggered in each round. First, for the setting of CMAB with probabilistically triggered arms (CMAB-T T), we discover a novel (di- rectional) triggering probability and variance modulated (TPVM) condition that replace the previously-used smoothness condition for various applications, such as cascading bandits, online network exploration and online influence maximization. Under this new condition, we propose a BCUCB-T algorithm with variance-aware confidence intervals and conduct regret analysis which reduces the O(K) factor (log K') (log² K)) in the regret bound, significantly improving the regret bounds for the above applications. Second, for the setting of non-triggering CMAB with independent arms, propose SESCB algorithm which leverages the non-triggering version of the TPVM condition and completely removes the depen- dency K in the leading regret. As a valuable by-product, the regret analysis used in this paper can improve several existing results by a factor of Ollog K). Finally, experimental evaluations show our superior performance compared with benchmark algorithms in different applications.
1 Introduction
Stochastic multi-armed bandit (MAB) [26, 4] is classical model that has been extensively studied in online decision making. As an extension of MAB, combinatorial multi-armed bandits (CMAB) have drawn much attention recently, owing to its wide applications in marketing, network optimization and online advertising [13, 17, 7, 8, 29, 23]. In CMAB, the learning agent chooses a combinatorial action in each round, and this action would trigger a of arms (or super arm) be pulled simultancously. and the outcomes of these pulled arms are observed as feedback. Typically, such feedback is known the semi-bandit feedback. The agent's goal minimize the expected regret, which is the difference in expectation for the overall rewards between always playing the best action
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

Table 1: Summary of the algorithms and results for CMAB with probabilistically triggered arms.
Algorfthm
Smoothness
Independent Arms?
Computation
Regret
CUCB (29]
1-norm TPM, Bi
Not requized
Elficient
O(K Diejon
BOIM-CUCB (25, Section 4)"
I-norm TPM, Br
Required
Hard
Oillog KT Eistor
BCUCB-T
(Clla--TAlggriltnn (Alguritmn
TPVM B.,! A>
Not required
Efficient
Ollog Eaclml
RCUCR-T (Algorithm
T,VM,, B.. A-1
Not required
Efficient
O, K log Hih 2ielml (
BOIM CUCB (Appendix Cy
norm TPM. Bi
Required
Hard
Oglog Eiejml
o8 Agin
This work for specific application. but we treat it as general framewrk::
Generally, B, = O(Biv R)) and the existing regrei bound is improved
when B. R.yKK) Using our new analysis.
(i.e., the action with highest expected reward) and playing according to the agent's own policy, For CMAB, an agent not only need deal with the apploaation-eplooiaatoon tradeoff: whether the agent should explore arms in search for a better action, or should the agent stick to the best action observed so far to gain rewards; but also need to handle the exponential explosion of all possible actions.
To model a wider range of application scenarios where action may trigger arms probabilistically, Chen et al. [8] first generalize CMAB to CMAB with probabilistically triggered arms (or CMAB-T for short), which successfully covers cascading bandit [9] (CB) and online influence maximization (OIM) bandit [31] problems. Later on, Wang and Chen [29] improve the regret bound of [8] by introducing a smoothness condition, called the triggering probability modulated (TPM) condition, which removes factor of 1/p" compared [8], where p" is the minimum positive probability that any arm can be triggered. However, in both studies, the regret bounds still depend on factor of batch-size K, where K is the maximum number of arms that can be triggered, and this factor could be quite large, e.g., for OIM K can be as large as the number of edges in large social network.
Our Contributions. In this paper, we reduce or remove the dependency on K in the regret bounds. For CMAB-T, we first discover a new triggering probability and variance modulated (TPVM) bounded smoothness condition, which is stronger than the TPM condition, yet still holds for several applications (such as CB and OIM) where only the TPM condition is known previously. We observe that for these applications, the previous TPM condition bounds the global speed of reward change regarding the parameter change, which will cause a large K coefficient due to the rapid change at the boundary regions (i.e., when an arm's 's mean μ4; is close to 0 or 1). Our TPVM condition utilizes this observation by raising up the regret contribution of those boundary regions, leading to a significant reduction on the dependency of K. Second, we propose "variance-awart that adaptively changes the width of the confidence interval according to the (empirical) variance, cancelling out the large regret contribution raised by the TPVM condition at the boundary regions (where the variances are also very small). Combining these two techniques, we successfully reduce the batch-size dependence from O(K) to O(log K) or Ollog" K) for all CMAB-T problems satisfying the TPVM condition, leading to significant improvements of the regret bounds for applications like CB or OIM. As by-product, we also give refined proofs that shall improve the regret for several existing works by a factor of (log K). e.g.. [11, 23], which may be of independent interests.
BCUCB-T algorithm
In addition to the general CMAB-T setting, we show how a non-triggering version of the TPVM condition (i.e., VM condition) can help completely remove the batch-size K, under the additional independent arm assumption for non-triggering CMAB problems. In particular, we propose a novel Sub-Exponential Efficient Sampling for Combintorial Bandits Policy (SESCB) that produces tighter sub-exponential concentrated confidence intervals. In our analysis, we show that the total regret only depends on the arm that is observed least instead of all K arms, so that we can achieve a completely batch-size independent regret bound. Our empirical results demonstrate that our proposed algorithms can achieve around 20% lower regrets than previous ones for several applications. Due the space limit, we will move the complete proofs and empirical results into the appendix.
Related Work. The stochastic CMAB has received much attention recently. From the modelling point of view, these CMAB works can be divided into two categories: CMAB with or without probabilistically triggered arms (i.e. CMAB-T setting non-triggering CMAB). For CMAB-T, our work improves (a) the general framework in [8, 29]. (b) the combinatorial cascading bandit [17], (c) the online multi-layered network exploration [21] problem, (d) the online influence maximization bandits [29, 25]. by reducing or removing the batch-size dependent factor K in the regret bounds with our new TPVM condition and/or our refined analysis. We defer the detailed technical comparison to Section 3.1 and Section 5. For the algorithm, most CMAB-T studies use Combinatorial Upper Confidence Bound (CUCB) based on Chernoff concentration bounds [29], our BCUCB-T algorithm is different and uses the Bernstein concentration bound [2, 23] that considers variance of the arms

---

Table 2: Summary of the algorithms and results for non-triggering CMAB problems.
Algorithm
Smoothness
Independent Arms?
Computation
Regret
CUCB [29]
1-norm, B.
Not required
Efficient
O(K > Eie
#i log Ariin
CTS [30]*
1-norm, B.
Required
Efficient
O(K 2ie(mv)
Df log
ESCB [9]
1-norm, B1"
Required
Hard
( K)²
Lie(ml)
4 log
AESCB [10]
Linear
Required
Efficient
O(llog K)²
Sie [pn)
lor
BC-UCB [23]
VM, Bg
4
Not required
Efficient
Oillog K)²² E (e(pr))
2e Jog
CTS [30]*
Linear
Required
Efficient
Ollog K
Eve (ml
lor
SESCB (Algorithm 2)
VM, B,
Required
Efficient"
BC-UCB (Appendix C)
VM, B,*
Not required
Efficient
0.1ng K Eie(p)) [1]mm)
12" log
Requires exact offiine oraele instead (o, ())-opproximmte oracle; ! This work gives sufficient smoothness condition with factor Ty and translates B, 3v/27, in setting; Ussing
analysis.
"* This work for the linear case, but easily
generalize to I-norm case: Generally H, O(B, vK) and the existing regret hound is improved when f7, oBBi v/ R);
Efficient when the reward function is submodular, otherwise the computation is hard;
For non-triggering CMAB, [13] is the first study on stochastic CMAB, and its regret has been improved by Kveton et al. [18), Combes et al. [9]. Chen et al. [8], but they still have O(K) factor in their regrets. When arms mutually independent, Combes et al. [9] build tighter ellipsoidal confidence region for exploration, and devise the Efficient Sampling for Combinatorial Bandit policy (ESCB), which reduces the dependence on O()) to O(log" K) at the cost of high computational complexity (since combinatorial optimization over the ellipsoidal region is NP-hard in general [1]). Later on, the computational complexity is improved by AESCB [10] in the linear CMAB problem. Recently, Merlis and Mannor [23] focus the Probabilistic Maximum Coverage (PMC) bandit problem and propose the BC-UCB algorithm with the Gini-smoothness condition to achieve a similar improvement as ESCB/AESCE, but without the independent arm assumption. Our work is largely inspired by their work, however, our study generalizes theirs to the CMAB-T setting which can handle much broader application scenarios beyond the non-triggering CMAB (more detailed comparison is given in Section 3). In addition, we provide refined analysis that can save a Oloog K) factor for BC-UCB (or ESCB/AESCB) algorithm. Compared with other ESCB-type algorithms for independent arms, as far as we know, our SESCB algorithm are the first to completely remove the dependence of K the leading regrets, owing to our non-triggering version of the TPVM condition. The detailed comparisons are summarized in Table 1 and Table 2.
The usage of variance-aware algorithms give improved regret bounds be dated back to [2]. Recently, there is a surge of interest to apply the variance-aware principle in bandit [23, 28] and reinforcement learning (RL) settings [33, 32]. It is notable that Vial al. [28] share similar variance-aware principle as ours but focus on the distribution-indeeeeder regret bounds for the cascading bandits [28]. Our work is more general and achieves the matching regret bound when translating to the iistribution-indeeenne a different setting as we do not consider the state transitions.
regret bound. Compared with RL works, our paper studies
From the application's 's point of view, this paper covers the applications of PMC bandit [23], com- binatorial cascading bandits [17, 191, network exploration [21], and online influence maximiza- tion [31, 29, 20]. Our proposed algorithms can significantly reduce the regret bounds of them, e.g., from O(K) to Olog? K) for OIM where K can be hundreds of thousands in large social networks.
2 Problem Settings
We study the combinatorial multi-armer bandit problem with probabilistic triggering arms, which is denoted as CMAB-T for short. Following the setting from [29], a CMAB-T problem instance can be described by a tuple ([m), S, D. Ding; R),, where [m] = 21,2, m.. is the set of base arms; S is the set of eligible actions and S E S is action:' D is the set of possible distributions over the outcomes of base arms with bounded support [0. 1]m; Dung is the probabilistic triggering function and R is the reward function, the definitions of which will be introduced shortly.
In CMAB-T, the learning agent interacts with the unknown environment in a sequential manner as follows. First, the environment chooses distribution D D unknown to the agent. Then, at round
In some cases S is collection of subsets of [m]. in which case we often refer to S E S as super arm. In this paper treat S a general action space, same in [29].
3

---

t= 1,2,...... T. the agent selects an action St E S and the environment draws from the unknown distribution D a random outcome X; = (m.m) E [0, 1 Note that the outcome X, is assumed to be independent from outcomes generated in previous rounds, but outcomes Xx,, and Xt,j in the same round could be correlated. Let Dmn( (S, X) be a distribution over all possible subsets of [m], i.e. its support is 2/ml, When the action St is played on the outcome X,, base arms in a random set Ti Dug (St, X2) are triggered, meaning that the outcomes of arms in Tt, L... (Xt)ter. are revealed as the feedback to the agent, and are involved in determining the reward of action S,. Function Dai is referred as the probabilistic triggering function. At the end of the round I, the agent will receive a non-negative reward R[Sr Xx, Tt), determined by St, X and TІ. CMAB-T significantly enhances the modeling power of CMAB [7, 18] and can model many applications such as cascading bandits and online influence maximization [29], which we will discuss in later sections.
The goal of CMAB-T is to accumulate much reward as possible over T rounds, by learning distribution D or its parameters. Let μ = (H41,..., Mm) denote the mean vector of base arms' outcomes. Following [29], we assume that the expected reward E [[ X, r)] is function of the unknown mean vector μu, where the expectation is taken over the randomness of X
and T ~ Dung (S, X). In this context, we denote r(S; μ1) - E| X, +) and it suffices to learn the unknown mean vector instead of the joint distribution D, based on the past observation.
The performance of an online learning algorithm of the expected cumulative reward between always playing the best action S* - argmax r(S: μ)) and playing actions chosen by algorithm A. For many reward functions, it is NP-hard to compute the exact S* even when ja is known, so similar to [29], we assume that the algorithm A has access to an offline (a., (9. apprroxxxintoo oracle, which for mean vector l outputs an action S such that Pr pr) 2 a r(S": 1)] 2 B. Formally, the T-round (ax, ap-appooxi regret is defined as
measured by its regret, defined as the difference
Re a
T a. r(S": - E
Σ r(( p))
where the expectation is taken over the randomness of outcomes X1.... Xy, the triggered sets
Ti,... .., Tr, as well as the randomness of algorithm A itself.
In the CMAB-T model, there several quantities that are crucial to the subsequent study. We define triggering probability P; D. as the probability that base arm is triggered when the action is S. the outcome distribution is D, and the probabilistic triggering function is Duig. Since Dwig is always fixed in a given application context, we ignore it in the notation for simplicity, and use P: p. henceforth. Triggering probabilities P.S.s are crucial for the triggering prohability modulated bounded smoothness conditions be defined below. We define batch size K as the maximum number of arms that can be triggered, i.e., K = maxses 1 E [m] D.S > 0}|. Our main contribution of this paper is remove or reduce the regret dependency on batch size K, where K could be quite large, e.g., K can be hundreds of thousands in a large social network.
Owing to the nonlinearity and the combinatorial structure of the reward, it is essential to give some conditions for the reward function in order to achieve any meaningful regret bounds [7, 8, 29, 11, 23]. The following are two standard conditions originally proposed by Wang and Chen [29].
Condition (Monotonicity). We say that a CMAB-T problem instance satisfies monotonicity condi- tion, for any action S E S, any two distributions D, D' E DD with mean vectors u. [0, 1] such that μ4 S for all E [m)) we have r(S; 11) < r');
Condition (1-norm TPM Bounded Smoothness). We say that a CMAB-T problem instance satisfies the triggering probability modulated (TPM) by-boudded smoothness condition, for any action S S. any distribution D' D with mean vectors μ. p. E [0, 10mh we have (s:: r(S: p)1 S B₁ Exe(m) P; 114 -44.
D.5
The first monotonicity condition indicates the reward is larger if the parameter vector μ is larger. The second condition bounds the reward difference caused by the parameter change (from μ to ft'). One key feature is that the parameter change in each base arm i E [m] is modulated by the triggering probability P. D.S Intuitively, for base arm i that is unlikely to be triggered/observed (small p D.S). Condition 2 ensures that large change in μ4 only causes a small change (multiplied by p in the reward, and thus one does not need to pay extra cost to observe such arms. Many applications satisfy Condition I and Condition 2, including linear combinatorial bandits [18], combinatorial

---

cascading bandits [17]. online influence maximization [29], etc. With the above two conditions, Wang and Chen [29] show that a CUCB algorithm achieves the distribution-dependee regret bound of BiK log T where Arinn is the distribution-dependent reward gap, to be formally defined A
o [m]m]
in Definition 1. In the following sections, we will show how to remove or reduce the dependency on K' in the above bounds under our new conditions.
3 Algorithm and Regret Analysis for CMAB-T
In this section, for the CMAB-T framework with probabilistic triggering, we improve the regret dependency on the batch size from O(K) in [29] to Oloo K) or Ollo" K). Our main tool is new condition called triggering probability and variance modulated (TPVM) bounded smoothness condition, replacing the TPM condition (Condition 2). We will define the TPVM condition, comparing it with the TPM condition and the gini-smoothness condition of [23], show our algorithm and regret analysis that utilize this condition. Later in Section 5, we will demonstrate how this condition is applied to applications such as cascading bandits and online influence maximization.
3.1 Triggering Probability and Variance Modulated (TPVM) Bounded Smoothness Condition In this paper, we discover a new smoothness condition for many important applications as follows. Condition 3 (Directional TPVM Bounded Smoothness). We say that CMAB-T prob- lem instance satisfies the directional TPVM (Be, B1, X)-bounded smoothness condition (Be, 2 0, 2 1), if for any action S E S, any distribution D. E 'D with mean
vector u.p p E (0,1)", for any non-negative S.n E &0.,17 10,1]a s.t. 4i = p + S + 17, we have
G
((s:))))r)s)))1)1 S B.
(pF S. AE(m)
+ B1
Σ
Pj
D.S
1/c
(2)
(1 pi)m
*E(m)
Remark (Intuition for Condition 3). Looking at Eq. (2), if we ignore the (1 pi)p pr term in the denominator and set À 2, the RHS of Eq. (2) becomes B. Eieemm (p. PSp B, Eielm Pi D,S T/- which holds with B. = B3 K by applying the Cauchy-Sehward inequality to Condition 2. However, the regret upper bound following this modified Eq. (2) would not directly lead to the improvement in the regret due to the VK factor in B,, To deal with this issue, an important observation here is that for many applications, the reason B, is large is because that the reward changes abruptly when parameters JLg approaches 0 or 1. This motivates
to plug in the 1 1/(1 (4: p4) term in Eq. (2) to enlarge the square root term when J4g is close to 0 or 1, so that B. can be as small as possible. On the other hand, notice that when μı approaches 0 or 1, the variance V, S (1 p:) also very small, so the estimation of should be quite accurate. Therefore, the gap S: between our estimation and true value produces variance-related term which cancels the (1 - p4)p in the denominator. Since C in Eq. (2) is modulated by both triggering probability p; p. D.S and inverse upper bound of the variance 1/(1 - p.)ps we call Condition 3 the directional triggering probability and variance modulated (TPVM) condition for short, where the term "directional" is explained in the next remark. The exponent X > 1 on the triggering probability gives flexibility to trade-off between the strength of the condition and the quantity of the regret bound: With a larger X, we can obtain a smaller regret bound, while with smaller X, the condition is easier to satisfy and allows to include more applications.
Remark 2 (On directional TPVM vs. undirectional TPVM). the above definition, "directional" means that we have Ç. 17 2 O such that Jr' 2 yu in every dimension. This is weaker than the version of the undirectional TPVM condition, where (, E [-1, 1]"", and the 7ii in the right hand side of E2.(2) is replaced with ln./- The reason use the weaker version is that some of our applications considered in this paper only satisfy the weaker version. To differentiate, we use TPVM- when we refer to the directional TPVM condition.
Remark 3 (Relation between Conditions 2 and 3). First, when setting Ç to O, the directional TPVM condition degenerates to the directional TPM condition. However, Condition 2 is the undirectional TPM condition, which is typically stronger than its directional counterpart. Thus, in general Condition 3 does not imply Condition 2. Nevertheless, with some additional assumptions Condition 3 does imply
Forr bounded random variable X E [0, 1] with mean μas variance V, = [[ - _[x]² < [ ( I (1 pi)pi, where the equality is achieved when X is a Berouuli random variable.
5

---

Algorithm 1 BCUCB-T: Bernstein Combinatorial Upper Confidence Bound Algorithm for CMAB-T
I: Input: Base arms [m], computation oracle ORACLE.
2: Initialize: For each arm i, To, + 0, Ao.. 0, Vo,, O.
3: for L I..... do
4: For arm i, compute Pt,i according to Eq. (3) and set UCB value Ft.. = + Pe.s 1). pe,m).
5: St = -RRACLE(Ee.
Play S, which triggers arms Ti S [m] with outcome X1, 's for Tr.
For every E Tt, update Th 1,1 1, De, fr 1, (Xe, pr. T Ve,
Ti-1.
VV-1. + 1- (#e-1. )
T5.1
Tea
8: end for
Condition 2 with the same coefficient B1 (See Appendix A for an example of such assumptions). Conversely, by applying the Cauchy-Schwartz inequality, one can verify that a reward function is TPM By-boun By-bounded smooth, then it is (directional) TPVM (Bi / B1, Ab-buunded smooth for any X < 2. For applications considered in this paper, are able reduce their B, coefficient from Bi / /2 to a coefficient independent of K, leading to significant savings in the regret bound.
Remark 4 (Comparing with [23]). Merlis and Mannor [23] introduce Gini-smoothness condition to reduce the batch-size dependency for CMAB problems, which largely inspires our TPVM condition. Their condition is specified a differential form of the reward function, with parameters Yoo and % (See Appendix B for the exact definition). We emphasize that their original condition cannot handle the probabilistic triggering setting in CMAB-T. One natural extension is to incorporate triggering probability modulation into their differential form of Gini-smoothness. However, found that the resulting TPM smoothnessssss condition is not strong enough to guarantee desirable regret bounds (See Appendix B.1). This motivates us to provide new condition directly the difference form |r(S: - r(S; 1+),, similar to the TPM condition in [29]. Our TPVM condition (Condition 3) can be viewed as extending Lemma 6 of [23] to incorporate triggering probabilities and bound the difference form [r(S; 1²)) - r(S: |-] Intuitively, B1 and B, correspond to %oo and Yg. respectively, but since they are for different forms of definitions, their numerical values may not exactly match one another.
3.2 BCUCB-T Algorithm and Regret Analysis
Our proposed algorithm BCUCB-T is generalization of the BC-UCB algorithm [23, Algorithm 1] which originally solves the non-triggering CMAB problem. Algorithm maintains the empirical estimate fr, and Vr,, for the true mean and the true variance of the base arm outcomes. To select the action S, it feeds the upper confidence bound j. into the offline oracle, where tas optimistically estimates the μr by a confidence interval Pt.z- Compared with the CUCB algorithm [29, Algorithm
3logt for the CMAB-T problem, the novel part is 1] which uses confidence interval Pt.: V 27:
the usage of empirical variance V1 to construct the following "variance-aware" confidence interval:
/6V-1, 9logt
Pr.i
TI-1S
T--1
This confidence interval leverages on the empirical Bernstein inequality instead of the Chernoff-
Hoeffding inequality. As we will show in Appendix C.I, for the first term in Eq. (3), V,-1, is approximately equal to the true variance V, < (1 ji)y4 and this indicates the estimation of μ4; is more accurate when μ4, is close to or 1, which will cancel out the (1 14)m% coefficient of the B, discussed before. The second term of Eq. (3) is compensate the usage of the empirical variance V rather than the true variance V; which is unknown the learner.
term in Condition 3
To state the regret bound, we first give some definitions followed by our main result.
Definition 1 ((Approximation) Gap). Fix a distribution D E DD and its mean vector μt, for each action S S, we define the (approximation) gap as Åg = max(0, ar(S"; p1) - r(S; }. For each arm i, we define Amin inf ses.pp s0, As>0 As, A Amax sup 20.50.As>0 As. As convention, if
there is no action S E such that Pt D.S > and As 0, then Amin +00, Amax 0. We define Amin min A Amn and Amax maXie(m) Ain.

---

Theorem 1. For CMAB-T problem instance ((m), S, S.D. Drigg R) that satisfies monotonicity (Con-
dition 1), and < bounded smoothness (Condition 3) with coefficient (B,, B))
(1) if 1, BCUCB-T (Algorithm 1) with an (0t,8)-appran) -ppppopoinnnnooon oracle achieves an (ax, B)) approximate regret bounded by
0 log K KlogT
B1K m
Σ
B1 log"
log T
(4)
min
(E(m]
sE/m]
(2) if=11 1, BCUCB-T (Algorithm 1) with an (ax, (1,,8))apppe -pppprooxnnnnnoon oracle achieves an (ax, B)- approximate regret bounded by
o
Σ log [E|m)
B,K Amin
B log K logT
Σ 4E|m]
B1
log
B Amin
log T
(5)
A. min
Remark (Discussion for Regret Bounds). Looking at the above regret bounds, for >> 1 and
1, the leading terms are O B. log K log')" and -(== (log B.K B" log K log T When
A.
A
A
B, 2 Bi (which typically holds, see Section 5) and gaps are small (i.e., Aiin S 1/ log? K), the dependencies over K are (log K) and Ologg K). respectively. For the setting of CMAB-T, [29] is the closest work to paper, where the reward function satisfies Condition and Condition 2 with coefficient B1. As mentioned in Remark in Section 3.1, their reward function trivially satisfies our Condition with coefficient (B1 2, 2) so our work reproduces bound of B log K log TogT). matching [29] up a factor of Oloo K). As will be shown in Section Aqui
((EiE(m)
for applications that satisfy TPVM (or TPVM2) condition with non- trivial B,, i..,, B, = (BivK) K), work improves their regret bounds up to a factor of O O(K/ log K). As for the lower bound, according to the lower bound results by Merlis and Mannor [24], our regret bound is tight up to a factor of Olog" K) on the (degenerate) non-triggering CMAB case. We defer the details about the lower bound results and the iittribution-indeeeneet
regret bounds in the Appendix C.5.
Proof ideas. Our proof uses a few events to filter the total regret and then bound these event- filtered regrets separately. As will be shown in the supplementary material, the event that contributes to the leading regret is E, = (As, S (S.)), where the error term (x(S,) =
(2 O(Br E ( logt (p. P.S.)A + Bi B. Eies, logt (r. (x....))) To handle the probabilistic trigger- Ti
ing, our key ingredient is to use the triggering probability group technique proposed by Wang and Chen [29] in the definition of above events. For the X = 1 case, one new issue arises since the triggering probability group divides sub-optimal actions S into infinite geometrically separated bins (1/2, 1), (1/4, 1/2) (2-1, 2, 2- .... over p. ". and the regret should be proportional the number of bins (which are infinitely large). To handle this, we show that it suffices to consider the first j S jmmax = Oloo B.K) bins (which is why Eq. (5) has this additional factor in the leading Amin
term) and the regret of other bins (with very small p; D.S) can be safely neglected. To bound the leading regret filtered by Eg as mentioned carlier, we use the reverse amortization trick from Wang and Chen [29, 30] and adaptively allocates each arm's regret contribution (according to thresholds on the number of times arm is triggered). Note that these thresholds are carefully chosen for the error term (Sc). since trivially following the thresholds Wang and Chen [29] would either yield no meaningful bound or suffer from additional Olog T') or (log K) factors in the regret. As by-product, one can also use our analysis replace that of Merlis and Mannor [23] and Perrault et al. [25] (where similar error term ex (S.) appears) to improve their bound by a factor of O(log K). For the detailed proofs, we defer them the Appendix C.
4 Algorithm and Analysis For CMAB with Independent Arms
In this section, we aim to show that for the non-triggeiing CMAB, the assumption that all arms are independent, compounded with non non-triggering version of the above TPVM condition (named as VM condition below), together allow us completely remove the Ollog K) O(log K) dependence
7

---

Algorithm 2 SESCB: Sub-Exponential Sampling for Combinatorial Bandits with Independent Arms
I: Input: Base arms [m], sub-Gaussian parameter C1, VM smoothness coefficient Be. (a,, (8-
approximation ORACLE O. 2: Initialize: For each arm i, To, < 0, Po. = O.
3: for == I...., T do
4: For all 5 S, define min-count (-1.5
minics T3 1,5 let interval Pr(S)
Boy LiEs
C1 Ti-1. + max {SCIvInEs Eies
log ri
8Ci 1
T:-1.
T
5: For all S S, define optimistic reward F((S) = r(:::
(S)).
6:
Play S. (ir, T:) s.t. Pr (r:(S) 2 a (=()) 3,where S arg maxses (S()), and
observe outcome Xt,''s, f.r for i St.
7: For every E St. update TG, = 1. + 1. pe, = fa 1.4 + (Xe, - ft /.)
8: end for
in the existing regret bounds. In particular, we focus on the a non-triggering CMAB problem instance (mml, S, DD, Rt). Its setting is similar to CMAB-T, but here we assume that S are collections of subsets of [m]] and only arms pulled by action S. E S are revealed as feedback (i.e., Ti = =S)).
Condition 4 (VM Bounded Smoothness). We say that a non-triggeriin con-rriggginng CMAB problem instance (mm) S, D, R) satisfies the Variance Modulated (VM) (Bu, B1 2 0)- --bundddd smoothness condition, for any action S E S, any distribution D, D' E 'D with mean vector p. μ (0.1)) for any Ç. 17 E
[- s.t. μ² - we have (r(S: -') p S B Eies (1-p:)as + B1 Eie(m]] Indl-
St
Condition 5 (Independent base arms). We say that the base arms independent, for any D D, the outcome vectors X ~ D are independent (across base arms). i.e. D = Ose[m) D..
Condition (Ci - (4:) sub-Gaussian). The outcome distribution D; with mean μ4 is (1 Mau-Gaasiinn, where C₁ is known coefficient.
Remark 6 (Comparison with TPVM Condition and [23]). Condition is the non-triggering version p.s of TPVM, by setting p. = if E S and 0 otherwise. As shown in Appendix B.2, Condition can
be implied by the original Gini-smoothness condition [23] with (B,, B1) = (3 7so), so PMC application satisfies the VM condition (the fifth row in Table 3). But different from [23, Lemma 6] and TPVMc, the VM condition is the undirectional version (i.c., we allow C. 17 to be negative). This is important for using empirical means in the algorithm (as did in our SESCB policy), since they are not necessarily larger than the true means.
Remark 7 (Motivation and Feasibility for Condition 6). Condition 6 helps to cancel out the
(1- (1-p:)pe p:)p, effect in the VM condition without explicitly using the empirical variance that will bring in additional batch-size dependent errors. For Bernoulli arms with mean (4i we can compute the 1-2k4
explicit value of C1, i.e., C1= maxie[m] 2 2 11n(==n1)11--- ((- by [22]. Notice that Ci could be large
when μ4: is approaching 0 or 1, but is safe to consider (4; over bounded supports that are not too close to 0 or 1, e.g., when μ4 E [0.01, 0.99), C1 ~ 10.78.
SESCB Algorithm. Our proposed algorithm is shown in Algorithm 2. Instead of maintaining one upper confidence bound for each base arm i, we maintain an upper confidence bound for each super arm S. based the estimated reward of the empirical means and a confidence interval. In line 4, we compute the confidence interval (S) by taking the max of two tentative segments within the square root, which corresponds to two different segments of the concentration bound for the sub-exponential random variable [27]. Such a sub-exponential concentrated confidence interval comes from the VM condition by treating (Gi)es as [S] independent sub-Gaussian random variables, whose summation produces a more concentrated sub-exponential random variable compared with considering them as |S| possibly dependent variables. It is notable that for the second tentative interval, SESCB uses the min-counter Thin, instead of all counters T;-1, in S, which is the key ingredient that removes the Olog K)) factor as to be shown in the analysis. After getting Pt (S)., the optimistic reward is defined in Line 5 and the learner selects S, via the (a, B) approxximationn oracle Ô and updates the corresponding statistics.
Regret Bound and Analysis. The following theorem summarizes the regret bound for Algorithm 2. Theorem 2. For non-triggering CMAB problem instance (Im), S, D. R) that satisfies VM bounded smoothness (Condition 4) with coefficient (Bo, B1), Condition and Condition 6 with coefficient C₁.
8

---

SESCB (Algorithm 2) with an (a, (o. -approxxiinnnnnnnn oralce achieves (a, appproxiitt regret that is bounded by O [me(m)
B. log
B.nKK
+ +m mmAmax
A
Amin
Looking at the above regret bound, the leading term totally removes the (log ()) dependency compared with Theorem 1. Compared with [23]. our regret bounds improves theirs by Ollo" K).
Proof Ideas. Similar to the proof of Theorem 1, we first identify error term (e (S,) as Line 4 and consider the regret filtered by the event {As, I es(S.)). The key ingredient is by following Condition 4 and Condition 6, and bound [r(S; ju) - r(S: 14) S Be B Eies "i,3- where Vt,i is a (T.-1.) )-s.b Sub--Gaiaan Gaussian random variable. Let Yr,s Eies u One can show Yt,5 is " >uub----pnnoo random variable, so applying the concentration bounds on Y,, [27] and one can obtain the above (S,). Then we consider two cases based on the value of Eies,
(320? Eies T T ,44
For both cases, we use the reverse amortization trick from [29] but different
1. from Section 3.2, e (St) ensures that we only need to consider regret contributions from the min-arm (which is least played in S2) according to certain batch-size independent thresholds. This in turn gives batch-size independent regret bounds that totally removes Olog K) in the leading term. See Appendix D for more details.
Computational Efficiency. Notice that like other ESCB-type algorithms [9], for the general reward function r(S: Ju). there may not exist efficient O so one needs to enumerate over all possible actions S E S each round, where the time complexity could be as high as ((S))). However, when r(S; μ1) is a monotone submodular function (e.g, the reward function of the PMC problem [8]). we can modify (S) so that the optimistic reward (S) is also monotone submodular, which can be efficiently optimized with a greedy (1 - 1/e, 1) >aaproxximation oracle. Observe that the current pe (S) is not submodular since the maximum of two submodular functions are not necessarily submodular, but we know the summation of two submodular functions are submodular. Based on this obser-
vation, we change (c( to PS( = B C1_ + SC1 ExEs Te-1;
( 8C, log (2))))
Ti
Train
where max is replaced with a sum (+); and we prove Appendix D.3 that (S) is monotone submodular function. Now we can use the greedy oracle to maximize a new optimistic reward ((() = r(S: 11-1) + pl (S) our SESCB algorithm. As for the final regret, using (S) instead of Pc(S) only worsens the final regret by a constant factor of two.
Now compared with [23] that achieves (1 - 1/e, 1>-aprooximate regret bound for PMC problem, our SESCB achieves the same (1 - 1/e, 1) --approximate regret bound but completely removes the Ollo K) dependency. Moreover, our greedy oracle is efficient with computational complexity O(TLL), where T is the total number of rounds, K is the number of source nodes to be selected in each round and L the total number of source nodes, which is much faster than the enumeration method. For the regret analysis when using (S), see Appendix D.3 for more details.
Applications
In this section, we show how various applications satisfy our new TPVM, TPVM or VM smoothness condition and their corresponding (B., B1, A) coefficients with non-trivial B,, i.e., B, o(BiVK). which in turn improves the regret bounds over the batch-size dependence of K.
Theorem 3. The combinatorial cascading bandits [17], the multi-layered network exploration [21], the inftuence maximization problems [29] and the probabilistic maximum coverage problem [23] satisfy the TPVM (TPVM 2 or VM) conditions with coefficients (B,, B1, X), resulting regret bounds and improvements shown in Table 3.
Note that the first four applications in Table applies Theorem 1, while the last application applies Theorem 2. More specifically, the first two applications we consider are disjunctive and conjunctive cascading bandits [17], where m base arms represent web pages and routing edges in online advertis- ing and network routing, respectively. Batch-size K is the maximum size of the ordered sequence E S to be selected each round, which will trigger web pages/routing edge one by one until certain stopping condition is satisfied, i.c., click routing edge being broken. The reward is 1

---

Table 3: Summary of the coefficients, regret bounds and improvements for various applications.
Application
Condition
(1.1.2) [B..
Regret
Improvement
Disjunctive Cascuding Bundis (17)
TPVM,
OKKy log K)
Conjunctive Coscaling Banditx [17]
TPYM
(1.1.)
Li Newe
OLK (log log
New
Multi-hayeee Network Exploration [2]]
TPVM
O(vy log(n(VD)
Inlluence Musimizaaiin on DAG
TPVM
(VDIV) (V)))T
AUPiiNN O0 Bl/(1 log [6] log A
Probahilistic Maximum Coverage [23)*
Oflog R).
This now is for the application in Section 4 and the rest of rowe are for Section I: "IV,, (E), R. denotes the nimber of anget nodes, the number of edges that
can be diggered the set of soed nodes, the number of layens, the number of seed modes and the length the longes: directed path, respectively.
if any web page is clicked (or if all routing edges are live) and 0 otherwise. Compared with [29], K )) for the conjunctive case and an improvement
we achieve an improvement O(K/ (Kool K log Amm
OK// log K) for the disjunctive case, due to the same Bu, B1 1 but different orders A.
The third application is the mutli-layered network exploration (Mul aNN) problem [21], and the MuLaNE task is to allocate B budgets into n layers to explore target nodes V. In MuLaNE, the base arms form set A {(i, u, b) i [n], u [V]. b E [B]}, the batch-size K (n + 1)[V] and the reward is defined as the total reward give by the first visit of any target nodes. MuLaNE fits into our study, and compared with [21], the regret bound is improved by a factor of (nn/ log K).
Our fourth application is the online influence maximization (OIM) problems direct acyclic graphs (DAG). For this upplication, the goal is to select at most & seed nodes to influence many target nodes V as possible, where the influence process follows the independent cascade (IC) model [29] (see Appendix E for more details). The base arms are the edges with unknown edge probabílities and the batch-size K is the total number of edges that could be triggered by any set of k: seed nodes, denoted |E]. The improvements here are significant, improving the existing results [23] by factor of (( log [E] log Amio
For the PMC problem [23], we consider a complete bipartite graph with L source nodes on the left and [V] target nodes V on the right. The goal is to select & seed nodes from L nodes trying to influence as many target nodes, so the edges E are independent base arms and the batch-size is k| k.V. By using the computational efficient version of Algorithm 2 and applying Theorem 2. we achieve Olog" k) improvement compared with [23] while maintaining good computational efficiency.
Proof Ideas. For all above applications (except for the OIM on DAG), our proof involves the use of telescoping series to decompose the reward difference, together with a smart use of the Cauchy-Schwarz inequality aided by the variance terms. For disjunctive cascading bandits, for exam- ple, the reward difference |r(:; p2) - r(: 14) II.h (1 - -1s) - II (1 pis) can be telescoped as EiEjK (is - (4)) (1, - 14)) II 1 mb After this decomposition, we replace certain
terms with p. and bound above by ΣiE(K] SiP." D.S v /1 -1)) m4)) + Σie(K] TxP, P.S. Then we simultancously multiply and divide the variance term ((1 - 14)μ, on the first term and apply the Cauchy- inequality to move the summation over K into the square root, concluding the satisfaction of Condition 3 with B, = (i (1-)))
- (4)) S 1. As for the OIM 1 I
on DAG, since reward function have no closed-form solutions [5], the analysis is more involved with the need of advanced techniques such as the coupling technique [20], see Appendix for details.
6 Conclusion and Future Direction
This paper studies the CMAB problem with probabilistically triggered arms or independent arms. We discover new TPVM and VM conditions, and propose BCUCB-T and SESCB algorithms to reduce and remove the batch-size K the regret bounds, respectively. We also show that several important applications all satisfy our conditions to achieve improved regrets, both theoretically and empirically. There are many compelling directions for future study. For example, it would be interesting to study the setting of CMAB-T together with independent arms. One could also explore how to extend our application and consider general graphs in online influence maximization bandits.
Acknowledgments and Disclosure of Funding
The work of John C.S. Lui was supported in part by the HK RGC SRF2122-4202 The work of Siwei Wang was supported in part by the National Natural Science Foundation of China Grant 62 62666122
10

---

References
[1] Alper Atamtürk and Andrés Gómez. Maximizing class of utility functions over the vertices of polytope. Operations Research, 65(2):433-4455 2017.
[2] Jean-Yves Audibert, Rémi Munos, and Csaba Szepesvári. iitooration-explotttaiii tradeoff using variance estimates in multi-armed bandits. Theoretical Computer Science, 410(19): 1876-1902, 2009.
[3] Peter Auer, Nicolo Cesa-Bianchi, and Paul Fischer. Finite-time analysis of the multiarmed bandit problem. Machine learning. 47(2-3)):23 256, 2002.
[4] Sébastien Bubeck, Nicolo Cesa-Bianchi, et al. Regret analysis of stochastic and nonstochastic multi-armed bandit problems. Foundations and Trends@ in Machine Learning, 5(1):1-122, 2012.
[5] Wei Chen, Yajun Wang, and Siyu Yang. Efficient influence maximization in social networks. In Proceedings of the 15th ACM SIGKDD international conference on Knowledge discovery and data mining, pages 199-208, 2009.
[6] Wei Chen, Laks VS Lakshmanan, and Carlos Castillo. Information and influence propagation in social networks. Synthesis Lectures on Data Management, 5(4):1-177, 2013.
[7] Wei Chen, Yajun Wang, and Yang Yuan. Combinatorial multi-armed bandit: General framework and applications. In International Conference on Machine Learning, pages 151-159. PMLR, 2013.
[8] Wei Chen, Yajun Wang. Yang Yuan, and Qinshi Wang. Combinatorial multi-armed bandit and its extension to probabilistically triggered arms. The Journal of Machine Learning Research, 17 (1):1746-1778, 2016.
[9] Richard Combes, Mohammad Sadegh Talebi Mazrach Shahi, Alexandre Proutiere, al. Com- binatorial bandits revisited. Advances in neural information processing systems, 28, 2015.
[10] Thibaut Cuvelier, Richard Combes, and Eric Gourdin. Statistically efficient, polynomial-tim algorithms for combinatorial semi-bandits. Proceedings of the ACM on Measurement and Analysis of Computing Systems, 5(1):1-31, 2021.
[11] Rémy Degenne and Vianney Perchet. Combinatorial semi-bande with known covariance, In Advances in Neural Information Processing Systems, pages 2972-2980. 2016.
[12] Devdatt Dubhashi and Alessandro Panconesi. Concentration of measure for the analysis of randomized algorithms. Cambridge University Press, 2009.
[13] Yi Gai, Bhaskar Krishnamachari, and Rahul Jain. Combinatorial network optimization with unknown variables: Multi-an aamted bandits with linear rewards and individual observations. IEEE/ACM Transactions on Networking (TON), 20(5):1466 1478, 2012.
[14] Jean Honorio and Tommi Jaakkola. Tight bounds for the expected risk of linear classifiers and pac-bayes finite-sample guarantees. In Artificial Intelligence and Statistics, pages 384-392. PMLR, 2014.
[15] David Kempe, Jon Kleinberg, and Éva Tardos. Maximizing the spread of influence through a social network. In Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining, pages 137-146, 2003.
[16] Branislav Kveton, Csaba Szepesvari, Zheng Wen, and Azin Ashkan. Cascading bandits: Learning rank in the cascade model. In International Conference on Machine Learning, pages 767-776. PMLR, 2015.
[17] Branislav Kveton, Zheng Wen, Azin Ashkan, and Csaba Szepesvári. Combinatorial cascading bandits. In Proceedings of the 28th International Conference on Neural Information Processing Systems- Systems-Volume 1, pages 1450-1458, 2015.

---

[18] Branislav Kveton, Zheng Wen, Azin Ashkan, and Csaba Szepesvari. Tight regret bounds for stochastic combinatorial comi-bandits. In AISTATS, 2015.
[19] Shuai Li, Baoxiang Wang, Shengyu Zhang, and Wei Chen. Contextual combinatorial cascading bandits. In International conference machine learning, pages 1245-1253. PMLR, 2016.
[20] Shuai Li, Fang Kong. Kejie Tang. Qizhi Li, and Wei Chen. Online influence maximization under linear threshold model. Advances in Neural Information Processing Systems, 33:1 1204, 2020.
[21] Xutong Liu, Jinhang Zuo, Xiaowei Chen, Wei Chen, and John CS Lui. Multi-layered network exploration via random walks: From offline opumization to online learning. In International Conference on Machine Learning, pages 7057-7066. PMLR, 2021.
[22] Olivier Marchal and Julyan Arbel. On the uub-gaussianity of the beta and dirichlet distributions. Electronic Communications in Probability, 22:1-14, 2017.
[23] Nadav Merlis and Shie Mannor. Batch-size independent regret bounds for the combinatorial multi-armed bandit problem. In Conference on Learning Theory, pages 2465-2489. PMLR, 2019.
[24] Nadav Merlis and Shie Mannor. Tight lower bounds for combinatorial multi-armed bandits, In Conference on Learning Theory, pages 2830-2857. PMLR, 2020.
[25] Pierre Perrault, Jennifer Healey, Zheng Wen, and Michal Valko. Budgeted online influence maximization. In International Conference on Machine Learning, pages 7620-7633 PMLR, 2020.
[26] Herbert Robbins. Some aspects of the sequential design of experiments. Bulletin of the American Mathematical Society, 58(5):527-535, 1952.
[27] Roman Vershynin. High-dimensional probability: An introduction with applications in data science, volume 47. Cambridge university press, 2018
[28] Daniel Vial, Sujay Sanghavi, Sanjay Shakkottai, and R Srikant. Minimax regret for cascading bandits. arXiv preprint ar 22Xiv:2203.12577 2022.
[29] Qinshi Wang and Wei Chen. Improving regret bounds for combinatorial semi-bandits with probabilistically triggered arms and its applications. In Advances in Neural Information Processing Systems, pages 1161-1171, 2017.
[30] Siwei Wang and Wei Chen. Thompson sampling for combinatorial semi-bandits. In International Conference on Machine Learning, pages 51 14-5122, 2018
[31] Zheng Wen, Branislav Kveton, Michal Valko, and Sharan Vaswani. Online influence maxi- mization under independent cascade model with semi-bandit feedback. Advances in neural information processing systems, 30, 2017.
[32] Zihan Zhang, Jiaqi Yang, Xiangyang Ji, and Simon S Du. Improved variance-aware confidence sets for linear bandits and linear mixture mdp. Advances in Neural Information Processing Systems, 34:4342-4355, 2021.
[33] Dongruo Zhou, Quanquan Gu, and Csaba Szepesvari. Nearly minimax optimal reinforcement learning for linear mixture markov decision processes. In Conference on Learning Theory, pages 4572.4576.. PMLR, 2021.
12

---

Checklist
For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes] See Section 3.1 and Section 6.
(c) Did you discuss any potential negative societal impacts of your work? [N/A] Since this work is mainly about online learning models, algorithms and analytical techniques, there is no foreseeable societal impact.
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes] See Section 3.1 and Section 4.
(b) Did you include complete proofss of all theoretical results? [Yes] See the Appendix.
3. If you experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either the supplemental material or as URL.?? [Yes]
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes]
(c) Did you report error bars (e.g.. with respect the random seed after running experi- ments multiple times)? [Yes]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [Yes]
4. If you using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [Yes]]
(b) Did you mention the license of the assets? [N/A] We only use open-sourced datasets and codes.
(c) Did you include any new assets either in the supplemental material or URL? [No]
(d) Did you discuss whether and how consent obtained from people whose data you'n using/curating? [N/A] We only use open-sourced datasets and codes.
(c) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsoureing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid participants and the total amount spent on participant compensation? [N/A]
13


Reviews:
[{"review_id": "vwuK5VKM1ma", "reviewer": "Reviewer_HNeW", "summary": "This paper considers the combinatorial semi-bandits problem under two different settings: (1) probabilistically triggered arms setting where the set of played arms can trigger reward on other arms, (2) the non-triggering setting with independent arms. For both these settings the authors improve batch-size dependence in regret as compared to previous work by considering a new variance-based condition on the underlying reward distributions. The authors show that this condition is satisfied in many applications such as cascading bandits, influence maximization on DAGs etc, and leads to significant improvements in the regret achievable for these applications. ", "questions": "1. In Section 4, is the notion of regret still (\\alpha, \\beta)-approximate regret? If yes, then I do not understand the reason behind using this notion of regret. In the independent arms setting you are not using the oracle to return a (\\alpha, \\beta)-approximate set of arms, instead you are computing the argmax using brute force. In that case you should be able to compete with the best set. \n\n2. It would be great if the authors can provide experimental results for some applications which support the theoretical improvements.", "limitations": "I do not foresee any negative societal impact. ", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths: The paper provides a good contribution to the literature on combinatorial semi-bandits as it improves the dependence on batch size from linear to logarithmic in many practical applications. The paper is very well-written and provides clear intuition behind various ideas/assumptions. The comparison with prior work is also adequate.", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "guea8oQS_V5", "reviewer": "Reviewer_uueH", "summary": "This paper proposes new smoothness conditions for the well-known combinatorial semi-bandit problem with probabilistically triggered arms. It is shown that well-known combinatorial learning problems of interest, including combinatorial cascading, influence maximization, and probabilistic maximum coverage bandits, satisfy these conditions. With the so-called triggering probability and variance modulated smoothness condition, the authors significantly improved the O(K) factor that appears in the previous regret bounds, where K represents the batch size. The authors also propose a non-triggering version of the smoothness condition and show that dependency on K can be completely removed for the non-triggering combinatorial semi-bandit. In order to achieve the improved regret bounds for the triggering version of the problem, the paper relies on empirical Bernstein inequality to construct upper confidence bounds of base arms. For the non-triggering version, batch size independence is achieved by constructing sub-exponential concentrated confidence intervals. ", "questions": "I wonder if any computationally efficient algorithm can achieve batch size independence. ", "limitations": "Limitations are adequately discussed. This work is theoretical in nature and does not have a societal impact. ", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths: \n\nFinding general enough smoothness conditions under which the effect of batch size on the regret can be significantly improved is an important problem. This paper intuitively develops new smoothness conditions and algorithms that use tailored confidence intervals to address this problem. \n\nComputationally efficient algorithms are proposed for triggering and non-triggering cases. \n\nWriting is clear. Theorems are well organized. \n\nWeakness:\n\nTrue batch size independence comes with an algorithm that requires enumeration of all possible actions. I wonder if any computationally efficient algorithm can achieve batch size independence. ", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "JQioC-fcJPp", "reviewer": "Reviewer_kHgZ", "summary": "Remark: Throughout my review, [n] refers to the n-th reference in the full paper (with appendix) from the supplementary material. (I mention this because the reference numbers differ in the 9-page submission.)\n\nThis paper studies Combinatorial Multi-Armed Bandit (CMAB) problems with probabilistically-Triggered arms (CMAB-T). In essence, CMAB is a variant of the standard bandit setting where the learner chooses a subset of arms (a.k.a. a “super arm” or “action”) and the mean reward is a function of the chosen subset and of its component arms’ mean rewards, and for CMAB-T the learner only observes feedback on a random subset of the chosen arms. This formulation generalizes problems including cascading bandits for ranking search results, online influence maximization, etc.\n\nPrior work [27] introduced a smoothness condition (with respect to the function that maps the component arms’ mean rewards to the subset’s mean reward) that improved existing regret bounds [7] by a factor of $1/p^*$ (see Line 36 for details). This work provides a refined smoothness condition that involves the variance of the arms’ reward distribution, i.e., the condition is less restrictive when the variances are smaller (simply because the mean rewards are easier to learn in such cases). Provided this condition holds, the authors develop a variance-aware UCB-style algorithm based on the empirical Bernstein inequality [1] and show its regret improves existing work with respect to the “batch size” K, which is the maximum of arms that can be triggered at each round (e.g., the number of search results that a cascading bandit algorithm chooses).\n\nIn addition, the authors study non-triggered arms (Section 4) and specialize their results to various application settings (Section 5).", "questions": "~~In the first row of Table 3, the authors claim that their regret bound for disjunctive cascading bandits improves the existing one from [16] by a factor of $K / log K$. The existing bound is not explicitly shown, but the authors’ bound has the form $log(K) log(T) \\sum_i \\Delta_i^{-1}$, so I assume the existing bound refers to the bound $K \\log(T) \\sum_i \\Delta_i^{-1}$ from [16]. However, as best I can tell, this bound from [16] is specialized to cascading bandits from a more general setting; if one restricts to the special case like in the original cascading bandit paper [15], the bound $\\log(T) \\sum_i \\Delta_i^{-1}$ from Theorems 2 and 3 in [15] actually seems better than the bound from the current paper ... or at least, much better than the bound in [16], since [15] has no explicit multiplicative dependence on $K$? (Note: [15] does not refer to its model as \"disjunctive\", but I believe it's the same formulation.)~~\n\nUpdate post-rebuttal: This question has been satisfactorily addressed and I remain in support of acceptance.", "limitations": "Overall, I feel the limitations were acknowledged -- for example, the assumptions are clearly stated in each of the theorems, Remark 3 acknowledges that additional assumptions are needed to ensure the proposed Condition 3 implies the existing Condition 2, etc. In terms of negative societal impact, the authors simply state (in the checklist) that there is no foreseeable impact. Personally, I feel this view is somewhat narrow -- while the paper is theoretical, the algorithms could obviously have real-world impact if deployed -- but I understand the authors' point and view this more as a difference of opinion than an objective weakness.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "STRENGTHS:\n\nIn my opinion, the strengths of the paper are (1) a novel and fairly natural smoothness condition that incorporates variance information, (2) algorithms that exploit low variance problem instances via empirical Bernstein confidence sets (instead of “variance-unaware” Hoeffding-based confidence sets), and (3) analysis that shows exploiting variance in this manner can dramatically reduce regret in terms of $K$ (e.g., from $K$ to $log K$ in some settings).\n\nAt a higher level, I feel the main strength of this paper is to show that variance-aware algorithms lead to polynomial improvement in terms of K, and to do so in a fairly general setting (CMAB-T). More specifically, paper A (see below) recently proved something similar for cascading bandits (a special case of CMAB-T), although it focuses on gap-free bounds so is complementary to the current work (which focuses on gap-dependent bounds). More broadly, a number of recent papers have demonstrated similar (in spirit) polynomial improvements resulting from variance-aware algorithms in various bandit and RL settings (e.g., paper C below achieves a polynomial improvement in terms of the horizon for finite-horizon RL; see also the references therein and in paper B below). Thus, the current paper seems rather timely given the similar flavor to these works.\n\n(To be clear, I’m not demanding these papers be cited — reference A is a very recent preprint and the others are on different topics — but rather, emphasizing the timeliness of the current work).\n\n(A) Vial, Sanghavi, Shakkottai, Srikant, “Minimax Regret for Cascading Bandits”, arXiv preprint\n\n(B) Zhang, Yang, Ji, Du, “Improved Variance-Aware Confidence Sets for Linear Bandits and Linear Mixture MDP”, arXiv preprint\n\n(C) Zhou, Gu, Szepesvari, “Nearly Minimax Optimal Reinforcement Learning for Linear Mixture Markov Decision Processes”, COLT 2021\n\nWEAKNESSES:\n\n(1) While mostly well-written, the paper is very dense, particularly the first few technical sections (i.e., starting from Section 2). I imagine this is mostly a side effect of packing many technical definitions and results into a short page limit, but it was hard to follow at times. For example, Section 2 would have been easier to understand if the authors had used a simple special case of the CMAB-T model (e.g., cascading bandits) as a running example to help illustrate the technical definitions (of which there are many in Section 2).\n\n(2) Along these lines, I did not find the proof sketches very illuminating, and it was difficult to glean much intuition from the full proofs in the appendix given their length and density. In other words, I would have preferred an intermediate explanation -- high-level like the proof sketches, but more detailed like the actual proofs -- to illustrate the key ideas of the analysis (again, perhaps in a simpler special case of CMAB-T).\n\n~~(3) Unless I'm mistaken (in which case I'll gladly update during the discussion period), the improvement over prior work in the disjunctive cascading bandit setting is oversold. (See \"Questions\" section for details.)~~\n\nUpdate post-rebuttal: Weakness (3) has been satisfactorily addressed and I remain in support of acceptance.", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept