The Hardness Analysis of Thompson Sampling for Combinatorial Semi-bandits with Greedy Oracle
Authors: Fang Kong
Yueran Yang
Wei Chen
Shuai Li
Venue: NeurIPS 2021 Poster (2021)
Keywords: combinatorial multi-armed bandit (CMAB)
Thompson sampling (TS)
approximation oracle
Greedy oracle

Abstract: Thompson sampling (TS) has attracted a lot of interest in the bandit area. It was introduced in the 1930s but has not been theoretically proven until recent years. All of its analysis in the combinatorial multi-armed bandit (CMAB) setting requires an exact oracle to provide optimal solutions with any input. However, such an oracle is usually not feasible since many combinatorial optimization problems are NP-hard and only approximation oracles are available. An example \cite{WangC18} has shown the failure of TS to learn with an approximation oracle. However, this oracle is uncommon and is designed only for a specific problem instance. It is still an open question whether the convergence analysis of TS can be extended beyond the exact oracle in CMAB. In this paper, we study this question under the greedy oracle, which is a common (approximation) oracle with theoretical guarantees to solve many (offline) combinatorial optimization problems. We provide a problem-dependent regret lower bound of order $\Omega(\log T/\Delta^2)$ to quantify the hardness of TS to solve CMAB problems with greedy oracle, where $T$ is the time horizon and $\Delta$ is some reward gap. We also provide an almost matching regret upper bound. These are the first theoretical results for TS to solve CMAB with a common approximation oracle and break the misconception that TS cannot work with approximation oracles.

The Hardness Analysis of Thompson Sampling for Combinatorial Semi-bandits with Greedy Oracle
Fang Kong"
Yueran Yang' 'Shanghai Jiao Tong University
Wei Chen
Shuai Li
*Microsoft Research
(fangkong, yanngyrrn,yangy99 shuaili8)@ajtur jat.iii.,,.jjjeuuuu..u. edu. on weicmmicrosoft.com com
Abstract
Thompson sampling (TS) has attracted lot of interest in the bandit area. It was introduced the 1930s but has not been theoretically proven until recent years. All of its analysis in the combinatorial multi-armed bandit (CMAB) setting requires an exact oracle to provide optimal solutions with any input. However, such an oracle is usually not feasible since many combinatorial optimization problems are NP-hard and only approximation oracles are available. An example [30] has shown the failure of TS learn with an approximation oracle. However, this oracle is uncommon and is designed only for specific problem instance. It is still an open question whether the convergence analysis of TS can be extended beyond the exact oracle in CMAB. In this paper, we study this question under the greedy oracle, which a common (approximation) oracle with theoretical guarantees solve many (offline) combinatorial optimization problems. We provide a problem- dependent regret lower bound order Q[log T/A²) to quantify the hardness TS to solve CMAB problems with greedy oracle, where T is the time horizon and A is some reward gap. We also provide an almost matching regret upper bound. These are the first theoretical results for TS to solve CMAB with common approximation oracle and break the misconception that TS cannot work with approximation oracles.
Introduction
Stochastic multi-armed bandit (MAB) problem [20, 5, 3] is classical online learning framework. has been extensively studied in the literature and has a wide range of applications [13, 12, 20]. The problem is modeled by a T-round game between the learning agent and the environment. The environment contains an arm set and each arm associated with a reward distribution. At each round the agent first selects an arm, while the environment generates a random reward for each arm from its reward distribution. The agent then obtains the reward of the selected arm. The objective of the agent is to accumulate many expected rewards over T rounds, or equivalent to minimizing the cumulative expected regret, which defined as the cumulative difference between the expected reward of the optimal arm and the selected arms over T' rounds. To achieve this long-horizon goal, the learning agent has to face the dilemma of exploration and exploitation in each round. The former aims to try arms that have not been observed enough times to get a potentially higher reward, the latter focuses on the arm with the best observed performance so far to maintain a high profit. How to balance the tradeoff between exploration and exploitation is the main focus of the MAB algorithms.
One of the most popular bandit algorithms is the upper confidence bound (UCB) algorithm [5]. The algorithm aims to construct confidence sets for unknown expected rewards and selects arms according to their highest upper confidence bounds. The UCB-type algorithms have been widely studied and provided theoretical guarantees with regret upper bound of order Ollog T/A), where A is the
Conresponding author
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

minimum gap between the expected reward of the optimal arm and any suboptimal arms. Thompson sampling (TS) [3. 26] is another popular method to solve MAB problems. is a randomized algorithm based on the Bayesian idea, which maintains an iteratively updated posterior distribution for each arm and chooses arms according to their probabilities of being the best one. The TS algorithm was introduced in the 1930s [28]. but its theoretical analysis is open until recent years [15, 2]. It was proven that the regret upper bound of the TS algorithm is of the same order of (log T/)) in MAB problems [3]. Benefited from the advantages of easier implementation and better empirical performance compared to UCB, the TS-type algorithms attract more attentions in recent years.
Despite its importance, the MAB framework may fail to model many real applications since the agent's action is usually not single arm but a combination of several arms. This motivates the study on the combinatorial MAB (CMAB) problem [11, 9, 17, 31, 7, 29, 30, 24]. In the CMAB framework, the agent selects a combination of base arms as an action to play in each round. All outcomes of these selected arms are then revealed to the agent, which is called semi-handit feedback and is widely studied in the literature [7, 29, 32, 30, 14, 24). Such CMAB framework can cover many real application scenarios including probabilistic maximum coverage (PMC) [6], online influence maximization (OIM) [29], multiple-play MAB (MP-MAB) [17] and minimum spanning tree (MST).
TS-type algorithms have recently attracted a lot of interest in CMAB problems [17, 30, 14, 24J. All of these works need an exact oracle to provide the optimal solution with sampled parameters as input in each round. However, such oracles are usually not feasible since many offline combinatorial optimization problems, such as the offline problem of PMC and OIM [16], are NP-hard and only approximation oracles are available. With an example [30] illustrating the non-convergent regret of TS with an artificial approximation oracle designed for specifie problem instance, whether TS can work well in CMAB problems with common approximation oracles is still an open problem.
One of the most common oracles for offline combinatorial optimization problems with theoretical guarantee is the greedy algorithm. It sequentially finds the current optimal arm, or the optimal collection of multiple arms according to the structural correlations, maximize the current total expected reward. When the termination condition is met, it will return the set of all arms found in previous steps as the solution. The termination condition is usually formulated by a constraint on the number of steps. For example. in the PMC, OIM. and MP-MAB problems, such a process is limited to continue K steps. The greedy algorithm can provide approximate solutions for onf problems of PMC [8] and OIM [16], and exact optimal solutions for offline problems of MP-MAB [17] and MST [18]. general, as long as the expected reward in problem satisfies the monotonicity and submodularity on the action set, the greedy algorithm serves as an offline oracle to provide an approximate solution [23].
In this paper, we first formulate the CMAB problems with greedy oracle, which is general enough and covers PMC, MP-MAB, and many other problems. In this framework, the objective of the learning agent is to minimize the cumulative greedy regret, defined as the cumulative difference between the expected reward of the selected action and that of the greedy's 's solution in the real environment. Focusing on a specific PMC problem instance, we derive the hardness analysis of the TS algorithm with the greedy oracle to solve CMAB problems. Due to the mismatch between the estimation gaps that need to be eliminated by exploration and the actual regret the algorithm needs to pay for each such exploration, the TS algorithm with greedy oracle in this CMAB problem cannot achieve as good theoretical performance previous MAB algorithms. A problem-dependent regret lower bound of order 2(log 22) is provided to illustrate such hardness, where T is the time horizon and A is some reward gap. By carefully exploiting the property of the greedy oracle, we also provide an almost matching problem-dependee
regret upper bound, which is tight on that PMC problem instance and also recovers the main order of TS when solving MAB problems [3]. These results are the first theoretical results TS with approximation oracle to solve CMAB problems, which show that the linear regret example in [30] does not hold for every approximation oracle.
2 Related Work
CMAB problems have been widely studied in the literature [11, 6, 7, 29, 30, 24, 32, 21, 14]. Here we mainly focus on the most relevant works. Gai el al. [11] first study the CMAB problem with linear reward, where the reward of an action is linear in the reward of base arms included in it. They introduce UCB-type algorithm to solve such problems and allow approximation algorithms to
2

---

serve as offline oracles. Later, Chen et al. [6. 7, 29] generalize this framework by considering a larger class of rewards and the case with probabilistically triggered arms (CMAB-T). This framework only assumes the expected reward satisfies the monotonicity and Lipschitz condition on the mean vector of base arms. The combinatorial UCB (CUCB) algorithm is proposed to solve such general CMAB problems, which works with any offline oracle with approximation guarantees. When only approximation oracles are available, the goal of the algorithm is relaxed to minimize the cumulative approximation regret, which is defined as the difference between the expected reward of the selected action and that of the scaled optimal solution. The CUCB algorithm achieves the regret upper bound of order (loog T/ mman) [29], where Amin is the minimum reward gap from the scaled optimal solution over all suboptimal actions.
Compared with UCB-type algorithms which need to compute upper confidence bounds for unknown means of base arms [6. 7, 29), TS-type algorithms do not require the reward function to satisfy the monotonicity on the mean vector of base arms. Benefited from this and other advantages of easier implementation and better practical performances, TS-type algorithms have recently attracted lot of interest in CMAB problems. Komiyama et al. [17] consider using the TS algorithm to solve the MP-MAB problem, where the agent needs to select K from m arms to maximize the sum of rewards over these selected K arms. They provide an optimal regret upper bound of order O T T/Ax, K.K+)) for the TS algorithm to solve this problem, where A K,K+1 is the reward gap between the KC-th and (K + 1) optimal arm. Later, Wang and Chen [30] consider using TS to solve more general CMAB problems where only the Lipschitz condition is assumed to be satisfied. Their regret upper bound of order (log T/ Amin) matches the main order of the CUCB [29] in the same setting. The coefficient of this upper bound was recently improved by Perrault et al. [24], who study the same CMAB setting. Huyuk al. [14] extend the analysis of [30] and consider using the TS algorithm to solve the problem of CMAB-T. However, the current regret upper bound is O(1/p") worse than CUCB [29], where p" the minimum triggering probability.
All of the above bS-ba works need an exact oracle to provide the optimal solution with sampled parameters in each round. However, the exact oracles are usually not feasible as many combinatorial optimization problems, such as the offline problem of OIM and PMC, are NP-hard [16]. Wang and Chen [30] have constructed a problem instance and designed an approximation offline oracle for this problem instance. The analysis has shown that the TS algorithm suffers the linear regret of order O(T) when working with such an approximation oracle. However, this oracle is uncommon and artificial, thus cannot represent the performance of TS when working with common approximation oracles. It is still significant open problem that whether TS can perform well with approximation oracles.
The greedy algorithm is one of the most important methods with approximation guarantees to solve combinatorial optimization problems. When the mean vector is known beforehand, we call the problem of finding the action with the best expected reward offline problem. Using the greedy algorithm to solve offline combinatorial problems has been studied for decades, including the problem of shortest spanning subtree [18], shortest connection networks [25], set coverage [8], influence maximization [16], and general submodular lar optimization [23]. There is also line of studies considering using greedy to solve online problems [4, 19, 10, 27, 22], some of them require the exact reward function forms as prior knowledge. Among these works the most related to ours is [22], both aiming solve a general class of online problems. Lin et al. [22] consider using the online greedy strategy to make decisions based on UCB-type estimators. The algorithm sequentially selects a unit to maximize the current expected reward until no feasible unit can be selected in each round. In their setting, a unit conditioned on a set of previously selected units is regarded as an arm and the marginal reward of selecting this unit is the expected reward of this arm. Since the number of combinations of units is usually exponentially large, there is an exponential number of arms to explore, making the algorithm pay exponential memory cost in practical applications. Based on this framework, the algorithm needs to observe the marginal reward after the decision of each step to update the estimate on the arm. However, such observation may be not available as many combinatorial problems treat the action composed of several units as whole and select them together. Compared to this work, our framework only needs polynomial memory cost and does not require the observation of the marginal reward.
In this paper, we study the problem of CMAB with the common (approximation) greedy oracle and hope to answer the question of whether the TS algorithm can work well in this setting.
3

---

3 Setting
The combinatorial between the learning agent and the environment. The environment contains m base arms and the arm set is denoted by [m]] = {1.2.... m). Each arm i [m/] is associated with distribution D, on [0, 1]. We consider a combinatorial setting where the agent can select several base arms at a time. In many applications, different arms usually have structural correlations in the selection decision of the agent. For example, in the PMC problem, base arms (edges) starting from the same node must be selected together. Thus the base arm set [m]] can be further divided into n units, with each unit containing several base arms and unit of arms will be selected together. Let be the collection of all units and |s| be the number of base arms contained in unit for any 8 U.
bandit (CMAB) problem is formulated by T-round learning game
In each round t = 1, ..... the learning agent selects an action S. E S = { K} to play. Here S is the set of all candidate actions containing K units. For any action S, denote us {i E for some 8 E S} as the set of base arms that belong to units contained in S. The environment then draws a random output of all base arms X (Xx,1, Xt......, X1, X,,m) from the distribution D = D1 x D2 x... x Dm For any f, X is independent and identically distributed on D, with expectation 14, for any base i. Let μ (14))E(m) be the mean vector. We study the semi- bandit feedback [30, 7, 29] where the agent can observe feedback Q: {(i, Xt.)) i E US}). namely the output of all base arms in units contained in S, Denote H4 = ((S.. : 1 1 T < it as the history of observations at time The agent finally obtains a corresponding reward R₃ R(S,, X,) in this round, which is a function of action S, and output X,. We assume the expected reward satisfies the following two assumptions, which are standard in CMAB works [7, 30, 14, 24, 29].
The expected reward of an action S only depends on S and the mean vector p. That is to say, there exists function such that E [R,] Ix,,> [R(S) (St, X.)] r(S,, u).
Assumption 1.
Assumption 2. (Lipschitz continuity) There exists a constant such that for any action S and mean vectors u, pl, the reward of S under and pl satisfies
Ir(S, - r(S,
Σ 14- M4 YEUS
(1)
When the mean vector Ja is known beforehand, finding the optimal action containing K units is called the offfine problem. However, the offline problems usually NP-hard and enumerating all actions to find the best one is not feasible as the number of actions is exponentially large. The Greedy algorithm (presented in Algorithm 1) is a common method solve such offline problems, which is simple to implement and can provide approximate solutions for OIM [16] and PMC [8], and exact solutions for MP-MAB[17]. More specifically, long the reward function satisfies monotonicity and submodularity on the action set, the Greedy algorithm can provide solutions with approximate guarantees [23]. Moreover, the Greedy algorithm is also popular serve heuristic method in real applications and has good practical performance even without a theoretical guarantee.
Algorithm 1 Greedy algorithm
1: Input: base set [m] and mean vector μ = (Em)) unit set Ut action size K
2: Initialize: S,- = 0
3: for = 1, 2, ... K do
4: SІ argmax,euns, r(S, U (z)
5: Sg Sg U {su)
6: end for
7: Output: S,
We mainly study the CMAB problem with the Greedy oracle. With input μu (H:)iEmm) it sequen- tially selects K units to maximize the current expected reward. To simplify, we assume the Greedy's s solution S, (u), abbreviated as Sy, unique, or equivalently the optimal unit each step (Line in Algorithm 1) is unique. The general case with multiple solutions can also be solved and would be discussed later. The objective of the learning agent to maximize the cumulative expected reward over T' rounds, or cquivalently to minimizing the cumulative expected regret with respect to the

---

Greedy's solution Sg. which we call cumulative greedy regret [22] defined by
T
(T) = E
max {r(Sg. (4) (
where the expectation taken from the randomness in observations and the online algorithm.
We call Greedy an a-approximate oracle if (p") 2 a--r we-r(55 ((S" (u'),())) for any input μ², where S (n') is the optimal action under y'. Note when Greedy is a-approximate, the upper bound for greedy regret also implies the upper bound for the a-approximate regret defined by the cumulative distance between scaled optimal reward a eer(S"" (u)) ju) and r(,t, μ1) over I rounds. The approximate regret is adopted in previous CMAB works based on UCB-type algorithms [7, 29, 32, 21]. It is much weaker than greedy regret as relaxes the requirements for online algorithms and only needs them to return solutions satisfying the relaxed approximation ratio. We discuss more on challenges in analyzing the a-approximate regret with TS-type algorithms in Section 6.1.
An example of CMAB: probabilistic maximum coverage (PMC) The input for the PMC prob- R, E), where each edge (u, v) E is associated with weight ((,,,). Denote μ = (H(),)) (K,,,))(,,,,)EFFFF EF as the edge weight vector. The goal is to find a node set S C L with |S| K to maximize the number of influenced nodes in R, where each node v E R can be influenced by S with independent probability P(a,v). The advertisement placement problem can be modeled by PMC, where L is the web page set, R is the user set and ((w.,) represents the probability that user v clicks the advertisement on web page u. this application, the user click probabilities are unknown and need to be learned during iterative interactions. The PMC problem fits our CMAB framework with each edge being base arm and edges starting from the same node forming a unit. The expected reward of an action S is the expected number of nodes finally influenced by it, which defined as
lem is a weighted bipartite graph G = R,
r (S,
Σ VER
II
(1-M(u,))
(,,
is proved that the reward function satisfies Assumption [7] and the Greedy oracle can provide an approximate solution with approximation ratio (1 1-4] {)) for any input [23].
4 Algorithm
In this section, we introduce the combinatorial Thompson sampling (CTS) algorithm with Beta priors and Greedy oracle (presented in Algorithm 2) for CMAB problems.
Algorithm 2 CTS algorithm with Beta priors and Greedy oracle
1: Input: base arm set [m], unit set U, action size K
2: Initialize: Vi E [m]] a; = b; =
3: for = 1, 2, ... do
4: Vi E [m] Sample or,, Betala;; b:). Denote 02 = (ft.1, Oz.2,'.. Ot.m)
5: Select action S, Greedy ([m), U, K) and receive the observation Q:
6: //Update
7:
for Xi,) Q2 do
8:
With probability Xe. Yr, = 1; with probability 1 - Xe,in Ye, = 0
9: Update a; a; Ye,, bj b, Y2,)
10: end for
end for
The algorithm maintains Beta distribution with parameters a; and b, for each base arm i [m]] In the beginning. it initializes = b, = 1, Vi E [m] (Line 2). In each round the algorithm first samples a parameter candidate 0,, from Beta(a;, b.) representing the current estimate for μ4; (Line 4). Then the Greedy oracle outputs the solution S, according to the input vector 0, = (00,1, 0z.2..... Or.m) (Line 5). Based on the observation feedback, the algorithm then updates the corresponding Beta distributions for observed base arms (Line 7-10).
5

---

Lower Bound
We investigate the hardness of the CTS algorithm to solve CMAB problems with Greedy oracle by proving a problem-dependent regret lower bound.
First, we introduce some notations that will be used in the regret analysis. Recall Sg is the solution returned by the Greedy oracle when the input is μ.. We denote it as S. {8 -....-... 8g. K h where k..k is the k-th selected unit by Greedy. Further, define Sg { 2g.2. ......... 8g. } as the
sequence containing the first k units for any E [K]. Similarly, let S = [s.11,
St.K } and Si.k = { $t,..... St.k Note Sg00 St,0 = Ø. The corresponding gaps are defined measure the hardness of the task and the performance of the algorithm.
Definition 1. (Gaps) For any unit E U and index k E [K] such that & & Sg.k define the marginal reward gap
A = -1(5
as the reward difference between Sg.k and 1 we have Do, > for any ko such that s & Sggt- And for any action S, define As max (r(S,) r(S, 0} the reward difference from the Greedy's 's solution Sq. Let
U According to the Greedy algorithm,
min
min SES:eES
As,
A Amax
mAx
As
SES:sES
be the minimum and maximum reward gap of actions containing wnit respectively. Denote Amax maxses Ag as the maximum reward gap over all suboptimal actions.
We take the following PMC problem (shown in Figure 1) the instance to carry out the hardness analysis. Each edge in the graph a base arm and the set of all outgoing edges from a single node forms unit. The action size is set to K 2. The weight M(,,,) of each edge (u, v) is listed on the edges, where we assume 0 < A I 0.04. The expected reward (S, (4) of an action S under is defined as Eq (3). For example, when и and U2 are selected, the probability of 0j being influenced is 0.592 and the probability that V2 is influenced is M(w2.wz) 0.3. The expected reward of S = {u1, U2 is r(S, 14) = 0.592 + 0.3 0.892. For simplicity, we also assume the output of each base arm in each round is exactly mean. This assumption still satisfies the above properties and is also adopted in previous lower bound proofs [3] to simplify the analysis.
1 1- (1 (()).))) (1 (((2,
U1
0.49
t/1
0.2
0.3
0.3
A
U3
0.48
14
Figure 1: The underlying graph of the PMC instance used to derive the hardness analysis.
For convenience, we first list the expected reward each action in this problem Table 1. We can find that the greedy solution is S,, {u2, un} with sg.1 U2. $g.2 Uı, and r(S,, ,,, /4) 0.892, while the optimal action is { (u ). The corresponding marginal reward gaps of each unit can be then computed follows.
A 0.01;
Aug.1 A,
A 0.012 + 0.7A;
A Aus11 0.02,
A 0.056.

---

Action
Expected Reward
Action
Expected Reward
{
0.49
{ui, u2
0.892
{
0.5
{u1, U3)
0.843 A
{ua}
0.5
A
{u), ua)
0.97
{
0.48
{12, us}
0.88
0.7A
(ug, u43
0.884
0.52A
U22 u4)
0.836
Table 1: The expected rewards of actions in the problem instance shown in Figure 1.
In the following, mainly focus unit Wg and take it example to derive the hardness analysis. According to Table 1, all actions containing 0g are suboptimal actions compared to S, and An (us.ur) 0.52 0.008. Thus to avoid regret generation, the algorithm should avoid incorporating Ug in the action S,. Intuitively, M3 should be explored at least f (log T/42., ug.1) Ω (log T/ T/22) times to be distinguished from 8g.1 Greedy. However, in each round of exploration for Ug. the algorithm needs to pay a constant regret of at least 0.52A 0.008. Thus the estimation gap A needs to be eliminated by exploration on the denominator S2 (logT/AX T/A²) cannot canceled by the actual regret paid in each exploration round. Such mismatch would cause the greedy regret at least of order (log 7/
and thus can avoid being selected as the first unit by
We give the formal lower bound for both the expected number of selections of each unit and the cumulative greedy regret in the following Theorem 1.
Theorem 1. (Lower bound) Using the CTS algorithm with Gaussian priors and Greedy oracle to solve the CMAB problem shown in Figure 1, when T is sufficiently large, we have
log 5,1
[N++1ss] = 12
(4)
Σ 11 (8 E St) is the number of rounds when is for any Sy,1 u2, where NT+L, contained in the selected action set S.-
Further, the cumulative greedy regret satisfies
log
log T Ω
Rg = Ω
(5)
A
2
The proof of Theorem 1 follows directly the intuition of the above hardness analysis. Due the space limit, we include the detailed proof in Appendix B. The reason why we consider using Gaussian priors to derive the lower bound analysis is that hope use its concentration and anti-concentrattin incqualities. The analysis can directly apply to other types of prior distributions if similar inequalities can be provided. The main operations of CTS with Gaussian priors are very similar to that of Algorithm 2, while the only difference is on the prior distribution for unknown parameters and the corresponding updating mechanism. To be self-contained, we also present the detailed CTS algorithm with Gaussian priors in Appendix B.
Lin er al. [22] also show lower bound for greedy regret of order 2ilog T/A?) with A (0, 1/4). However, the problem instance used to derive this lower bound not CMAB problem and thus their result is not comparable with Theorem 1.
6 Upper Bound
By investigating the properties of the CTS algorithm and the Greedy oracle, we also provide problem-dependent regret upper bound for Algorithm 2 to solve general CMAB problems.
Theorem 2. (Upper bound) The cumulative greedy regret of Algorithm 2 can be upper bounded by
GB2 |s| max log
(T( S Σ
max ki
+
Σ kE[K]
A Amax
(A, 2B {)
7

---

[US
8 E²
+
2
+ 4m
Amax
(6)
Ba |s Amaa log
=0
Σ
max
k:s@ S
575211
for any e such that V's + $g.1 and l satisfying é Sgh. As. > 2B |JSg] where B is the coefficient of the Lipschitz continuity condition, |US is the number of base arms that belong to the units contained in Sg. C and C' are two universal constants.
Due to the space limit, we provide the proof sketch of Theorem Section 6.2 and defer the formal proof to Appendix C. In order to better compare the upper and lower bounds, also analyze the greedy regret of the CTS algorithm with Gaussian priors in Appendix D, which achieves the same order of the upper bound with Theorem 2 only up to some constant factors.
6.1 Discussions
Challenges in analyzing the a-approximate regret with CTS The a-approximate regret first brought up in analyzing UCB-type algorithms [6, 7, 29]. Under UCB, benefiting from the mono- tonicity between the true parameter μ and the UCB parameter jı, the a-approximate regret can be deducted as
a (.-r(S - r( S a
aa. r(S" , - r(S.. S rrSS, ((.,, S
l mil, Σ SEUS,
where 5* E arrgaassss r(S, (4) is an exact optimal action under real parameter μ.. Thus it only needs bound the number of selections of bad action S, get upper bound for the a-approximate regret. However, under CTS, since there is no monotonicity between the true parameter μ and the surrogate parameter 0, the approximate regret can only be deducted
a rr(" p1) r(... u) S a a.-r(S r(S" .1) - -r." + a-..rt rrrrr(S0000 -r(Se,
S a. r(S 1) a ve.r(5 0) r(S,, r(.,,
a Σ 00 mal + Σ 10,-ul.
SELS*
iEUS,
To get upper bound for the RHS, it requires sufficient number of selections of the exact optimal action 5*, which may not be the case with approximate oracles like the example shown in Theorem 1. Thus the a-approximate regret may not well fit TS-type algorithms.
Tightness of the upper bound We now discuss the tightness of the regret upper bound in Theorem 2 based on the problem instance shown in Figure 1. Specific to this problem, we have |s| < 2 for all 8 since each node has no more than 2 outgoing edges. And based on [21, Theorem 4], the coefficient of the Lipschitz condition in this problem is B 1. When 0 < A 0.04, we have A minge S.,a A for any s * $g.1 = ug and Amax = A (mz 0.056 is constant. Thus our regret upper bound in this problem instance is of order
Σ #
B²1 |s|
max log T
Σ
log T = O
log A
max kisg
A
=0
2
a,k
NE(uT,Na,uL)
8,1
where the last equality holds since A 1 0.01, Au,, 4.01,A...
0.02 are constants and A us,1 A.
We can see our regret upper bound matches the lower bound of (5) in Theorem only up to some constant factors in this specific problem instance.
Comparison with MAB When each unit contains only one base arm and the action size is K our CMAB framework recovers the MAB problem and the Greedy oracle can provide the exact optimal solution. Thus we can also compare our regret upper bound with the theoretical results the TS algorithm in MAB problems. In the MAB problem, the expected reward of each action is exactly the mean of the base arm contained in this action. Thus the Lipschitz coefficient is just B 1 and Isl 1 for any unit The optimal action is S, Sg,1 with JUS, 1. And for any unit * sg,1,
8

---

we have A = 1.,1. Thus, according to (6) of Theorem 2, the regret upper bound of Algorithm 2
in MAB problems is of order O E Eosteg A,,3
1og
which recovers the main order of the regret upper
bound of TS for MAB problems [3].
Comparison with [22] Though Lin el al. [22] also study greedy regret, the results are not directly comparable in general since the setting studied in [22] is not CMAB setting. We find that the PMC problem under a bar graph in these two settings can be equivalent, where a bar graph is a special bipartite graph with each left node's ' outdegree being (indegree being 0) and each right node's 's indegree being (outdegree being 0). In this case, our greedy regret upper bound is of order Omm log ² and theirs is O(mK log T/ So ours O(K) better than theirs. Even in this case, their algorithm needs to estimate (mm 2n) parameters, while Algorithm 2 is more efficient and only needs to estimate ((m) parameters.
The definition of the marginal reward gap Recall that the Greedy oracle provides approximate solutions for problems whose expected reward satisfies monotonicity and submodularity on the action set. Formally, the submodularity means for any action S C ''' and unit & T, there is r(S {s} 1²) r(8. n) 2 r(T' {s} r(T, ,)), which characterizes the phenomenon of diminishing returns. One may concern that in these problems, due to the submodularity, the marginal reward gap A for larger & may become much smaller and the main order of the upper bound thus blows up. We clarify that the submodularity cannot imply the relationships among marginal reward gaps A. for different k [K]. The problem instance in Figure satisfying submodularity [16] indicates that the marginal reward gap As,k does not necessarily decrease with the increase of k.
6.2 Proof Sketch
In this section, we briefly introduce the proof idea of Theorem 2. At any step k E [K], for any unit 8 & Sg.x, the selection of in action S. may force the Greedy oracle to choose a worse action in subsequential steps and make CTS suffer constant regret. A sufficient condition for generating zero greedy regret in round / is that each unit 8r,* selected in step k is actually 8g.8 for any k E [K]. Thus to bound the cumulative greedy regret, we sequentially analyze whether 8g.k is appropriately selected at each step k.
Recall that under the framework of the CTS algorithm, the Greedy oracle sequentially selects st,k for & E [K] based on 0, sampled from posterior distributions in round t. Focusing on step k = 1, to ensure 8t,1 1g.1, 1, the algorithm needs to guarantee the accurate estimations 0t,s for any unit s E l such that r([s},8) first assume sy,1 is already estimated well. Then based on this assumption, when all of the other units * 8g,1 have been explored O(log T/ times and thus estimated accurately, 8g,1 would be selected at the first step with high probability. But if after any other unit s * 8g.1 has already been estimated well, 89.1 is still not selected appropriately, for 8,,1 are not accurate enough. In this case, the Beta posterior for 8,,1 tends to be uniformly distributed. When CTS sample Or 0r.5..1 from its Beta posterior, with constant probability there would be r(S,,1, 0z) > r([s} 14) R r([s} 0,) for any unit + 8g.1. Thus after some rounds, $9,1 would be selected for enough times and also estimated accurately. In the following rounds, $g.1 would be selected appropriately at the first step with high probability. Above all, the expected number of missclections at the first step can be bounded.
< <r 1, Oe), Vs a $g,1. where fg., is the projection of 0g on unit s. We
conclude that the estimations
The above analysis can apply to other cases when k = 3.......A K. Based on the correct selections in the first k steps, the misselection of st,x also comes from the bad estimations for both sg.k and other units s & Sg.k. To distinguish r(Sy,k-1 U {s} 02) from r(S g.k: 0z), those units need to be explored at least Ollog T times.
According to the above analysis, for each unit & + 8g.1, we define the exploration price as
log T A
L(s) = 0
max k:
(8)
To avoid being incorrectly selected at some step h; each unit & Sy.k needs to be explored for at least (s(s) times. The sum of T.(s) over all units + 8y,1 leads to the main order of the regret upper bound in Theorem 2.

---

6.3 Extension to Multiple-solution Case
We can also extend the analysis of the regret upper bound the case where multiple solutions may be returned by Greedy with imput or equivalently the optimal unit in each step k (Line 4 in Algorithm 1) may not be unique. Let
ок (111 .2..... sK} $1 argmaxr((s) , ....................... SK E
argmax r((51,...,, =((......K-11
be the set of all actions that are possibly returned by the Greedy oracle when the input is μ. Here we do not care how Greedy breaks the tie at each step and regard this process as a black box. In order to take into account the worst compared to other possible solutions, we define Sg E argminşeax r(S, jJ) as one of Greedy's s possible solutions with the minimum expected reward and consider the cumulative greedy regret defined in Eq (2).
where Greedy always returns solution with minimum reward
The regret analysis of Algorithm 2 in this case is similar to the proof of Theorem 2. A sufficient condition for generating zero regret in round t is that the selected action S, falls into the set σи Thus to bound the cumulative greedy regret, we sequentially analyze whether the unit &1 selected in each step is an optimal unit conditioned on the previously selected units S-,-- For completeness, we include the regret upper bound as well as the detailed proof for this case in Appendix E.
7 Conclusion
In this paper, we aim to answer the question of whether the convergence analysis of TS can be extended beyond exact oracles in the CMAB area. Taking the common offline (approximation) Greedy oracle as an example, we derive the hardness analysis of CTS for CMAB problems based on constructed CMAB problem instance. When using CTS with Greedy oracle solve this problem. we find that the algorithm needs to explore at least (loo T/ rounds to distinguish suboptimal units from the optimal unit at some step. However, least constant regret needs be paid for each exploration round. The mismatch between the gap to be distinguished and the actually paid regret forces the algorithm to pay the cumulative greedy regret of order 2Yoog T/ We also provide an almost matching problem-dependent regret upper bound for the CTS algorithm with Creedy oracle to solve CMAB problems. The upper bound is tight on the constructed problem instance only up to some constant factors and also recovers the main order of TS when solving MAB problems.
An interesting future direction extend the current CMAB framework to the case with proba- bilistically triggered arms (CMAB-T). The CMAB-T framework can model the OIM problem on general social networks. As shown [21], using UCB-type algorithms to solve such a problem may face great challenges on the computation efficiency. This problem is expected to be avoided by TS-type algorithms since TS would sample candidate parameters to escape the computation of complicated optimization problems. However, the current proof idea based on each selection step of the Greedy oracle (proof of Lemma 1) cannot directly apply this setting as different units may probabilistically trigger some common base arms. New proof techniques are required to derive the theoretical guarantee of the TS algorithm with the Greedy oracle this framework.
10

---

Acknowledgement
The corresponding author Shuai Li is supported by National Natural Science Foundation of China (62006151, 62076161). This work is sponsored by Shanghai Sailing Program.
References
[1] Milton Abramowitz and Irene A Stegun. Handbook of mathematical functions with formulas, graphs, and mathematical tables. 1964.
[2] Shipra Agrawal and Navin Goyal. Analysis of thompson sampling for the multi-armed bandit problem. In Proceedings of the 25th Annual Conference on Learning Theory, pages 1-26, 2012.
[3] Shipra Agrawal and Navin Goyal. Further optimal regret bounds for thompson sampling. In Proceedings of the 16th International Conference on Artificial Intelligence and Statistics, pages 99-107, 2013.
[4] lean-Yves Audibert, Sébastien Bubeck, and Gábor Lugosi. Minimax policies for combinatorial prediction games. In Proceedings of the 24th Annual Conference on Learning Theory, pages 107-132, 2011.
[5] Peter Auer, Nicolo Cesa-Bianchi, and Paul Fischer. Finite-time analysis of the multiarmed bandit problem. Machine learning, 47(2):235-256, 2002.
[6] Wei Chen, Yajun Wang, and Yang Yuan. Combinatorial and applications. In Proceedings of the 30th International Conference on Machine Learning. pages 151 151-159, 2013.
bandit: General framework
[7] 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, pages 1746-1778, 2016.
[8] Vasek Chvatal. A greedy heuristic for the set-covering problem. Mathematics of operations research, 4(3))233-23))) 1979.
[9] Richard Combes, Sadegh Talebi, Alexandre Proutière, and Mare Lelarge. Combinatorial bandits revisited. In Advances in Neural Information Processing Systems, pages 2116-2124, 2015.
[10] Victor Gabillon, Branislav Kveton, Zheng Wen, Brian Eriksson, and S Muthukrishnan, Adaptive submodular maximization in bandit setting. In Advances in Neural Information Processing Systems, pages 2697-2705, 2013.
[11] Yi Gai, Bhaskar Krishnamachari, and Rahul Jain. Combinatorial network optimization with unknown variables: Multi-armed bandits with linear rewards and individual observations. IEEE/ACM Transactions on Networking, 2065):1466-144 1478, 2012.
[12] Dorota Glowacka. Bandit algorithms in information retrieval. Now Publishers, 2019.
[13] Dorota Glowacka. Bandit algorithms in recommender systems. In Proceedings of the 13th ACM Conference on Recommender Systems, pages 574-575, 2019.
[14] Alihan Huyuk and Cem Tekin. Analysis of thompson sampling for combinatorial multi- armed bandit with probabilistically triggered arms. In Proceedings of the 22nd International Conference on Artificial Intelligence and Statistics, pages 1322-13300 2019.
[15] Emilie Kaufmann, Nathaniel Korda, and Rémi Munos. Thompson sampling: asymptotically optimal finite-time analysis. In Proceedings of the 23rd international conference on Algorithmic Learning Theory, pages 199-213, 2012.
[16] David Kempe, Jon Kleinberg, and Éva Tardos. Maximizing the spread of influence through a social network. Proceedings of the 9th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pages 137-146, 2003.
11

---

[17] Junpei Komiyama, Junya Honda, and Hiroshi Nakagawa. Optimal regret analysis of thompson sampling in stochastic multi-armed bandit problem with multiple plays. In Proceedings of the 32nd International Conference on International Conference on Machine Learning, pages 1152-1161, 2015.
[18] Joseph B Kruskal. On the shortest spanning subtree of a graph and the traveling salesman problem. Proceedings of the American Mathematical society, 7(1):48-500 1956.
[19] Branislav Kveton, Zheng Wen, Azin Ashkan, Hoda Eydgahi, and Brian Eriksson. Matroid bandits: fast combinatorial optimization with learning. In Proceedings of the 30th Conference on Uncertainty in Artificial Intelligence, pages 420-429, 2014.
[20] Tor Lattimore and Csaba Szepesvári. Bandit algorithms. Cambridge University Press, 2020.
[21] Shuai Li, Fang Kong, Kejie Tang, Qizhi Li, and Wei Chen. Online influence maximization under linear threshold model. In Advances in Neural Information Processing Systems, 2020.
[22] Tian Lin, Jian Li, and Wei Chen. Stochastic online greedy learning with semi-bandit feedbacks. In Advances in Neural Information Processing Systems, pages 352-360, 2015.
[23] George L Nemhauser, Laurence A Wolsey, and Marshall Fisher. An analysis of approximations for maximizing submodular set functions-i. Mathematical programming, 14(1):265-29) 1978.
[24] Pierre Perrault, Etienne Boursier, Vianney Perchet, and Michal Valko. Statistical efficiency of thompson sampling for combinatorial semi-bandits. In Advances in Neural Information Processing Systems, 2020.
[25] R. C. Prim. Shortest connection networks and some generalizations. The Bell System Technical Journal, 36(6):1389-14))) 1401, 1957.
[26] Daniel J Russo, Benjamin Van Roy, Abbas Kazerouni, Ian Osband, and Zheng Wen. A tutorial on thompson sampling. Foundations and Trends in Machine Learning, 11(1):1-96, 2018.
[27] Matthew Streeter and Daniel Golovin. An online algorithm for maximizing submodular functions. In Advances Neural Information Processing Systems, pages 1577-1584, 2008
[28] William R Thompson. On the likelihood that one unknown probability exceeds another in view of the evidence of two samples. Biometrika, 25(3/4):285-29,, 1933.
[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 Proceedings of the 35th International Conference on International Conference on Machine Learning, pages 5114 5122, 2018. https:/aarxiv.or//bb/// 803.04623.
[31] Zheng Wen, Branislav Kveton, and Azin Ashkan. Efficient learning in large-scale combinatorial semi-bandits. In Proceedings the 32nd International Conference on International Conference on Machine Learning, pages 1 1113-1122, 2015.
[32] Zheng Wen, Branislav Kveton, Michal Valko, and Sharan Vaswani. Online influence maxi- mization under independent cascade model with semi-bandit feedback. In Advances Neural Information Processing Systems, pages 1-24, 2017.
Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes] Please see Abstract and Section 1.
12

---

(b) Did you describe the limitations of your work? [Yes] Please see the future work part in Section 7.
(c) Did you discuss any potential negative societal impacts your work? [N/A] This work mainly focuses the online learning theory, which does not have any potential negative societal impacts.
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes] Please see Section 3.
(b) Did you include complete proofs of all theoretical results? [Yes] Please see all sections in Appendix.
3. If you experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or URL)? [N/A]
(b) Did you specify all the training details (e.g., data splits, byperparameters, how they were chosen)? [N/A]
(c) Did you report error bars (e.g., with respect the random seed after running experi- ments multiple times)? [N/A]
(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)? [N/A]
4. If you using existing assets (e.g., code, data, models) curating/releasing assets...
(a) If your work uses existing assets, did you cite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material or as a URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you're using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing 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": "yZ0VmDwLZWN", "reviewer": "Reviewer_kJUS", "summary": "The paper studies the combinatorial semi-bandit problem. It provides the first analysis of Thompson sampling (TS) with the greedy oracle. It shows instances that the TS with Gaussian priors suffers $\\Omega(\\log T / \\Delta^2)$ regret from. It proposes a modified TS with Beta priors and shows that the proposed algorithm achieves $O(\\log T / \\Delta^2)$ regret for the instances. The proposed algorithm enjoys near-optimal regret for the multi-armed bandit problem.", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "### Originality: Are the tasks or methods new? Is the work a novel combination of well-known techniques? (This can be valuable!) Is it clear how this work differs from previous contributions? Is related work adequately cited?\n\nThe paper provides the first analysis of TS with the greedy oracle. It compares the problem with a wide range of existing studies and confirms the novelty of the problem. The proposed algorithm is a simple and novel modification of TS.\n\n### Quality: Is the submission technically sound? Are claims well supported (e.g., by theoretical analysis or experimental results)? Are the methods used appropriate? Is this a complete piece of work or work in progress? Are the authors careful and honest about evaluating both the strengths and weaknesses of their work?\n\nThe theoretical analysis looks correct. The paper shows regret lower bound of TS with Gaussian priors, but it shows upper bound of TS with Beta priors. It is open that the upper and lower bounds of TS with Gaussian and Beta priors, respectively.\n\n### Clarity: Is the submission clearly written? Is it well organized? (If not, please make constructive suggestions for improving its clarity.) Does it adequately inform the reader? (Note that a superbly written paper provides enough information for an expert reader to reproduce its results.)\n\nThe paper is well written and easy to follow.\n\n### Significance: Are the results important? Are others (researchers or practitioners) likely to use the ideas or build on them? Does the submission address a difficult task in a better way than previous work? Does it advance the state of the art in a demonstrable way? Does it provide unique data, unique conclusions about existing data, or a unique theoretical or experimental approach?\n\nAnalyzing algorithms with the approximation oracle is very important in practice. The paper motivates researchers to progress the theoretical analysis of TS with other approximation oracles.\n\n================\n\nAfter the discussion with other reviewers, I changed my score from 6 to 5.\nI agree with the opinion that the regret lower bound is limited to a special instance and does not capture the essential difficulty of the problem.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The paper clarifies the assumptions of the theoretical analysis.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3 hours"}, "extra_text": {}}, {"review_id": "uvmLHfVrf2", "reviewer": "Reviewer_x5US", "summary": "The paper presents a TS algorithm that uses Greedy oracle to minimise the cumulative regret on combinatorial multi-armed bandit (CMAB) setting. beside presenting an upper bound, they have also established a lower bound (on the cumulative regret) for their approach. The paper discuss the intuition of behind the proof of their proposed analysis for upper bound assuming the \"Greedy\" step (Line 4 in  Algorithm 1) returns a unique solution, and then in section 6.2 it relaxes that assumption.\n\nCMAB is a well-known framework in the MAB literature, that generalises probabilistic maximum coverage (PMC), online influence\nmaximization (OIM), multiple-play MAB (MP-MAB), minimum spanning tree (MST) and many others. TS based regret-minimisation algorithms are very efficient for the family of single parameter reward distribution; there are recent studies that apply TS under the CMAB setup. Again, finding the optimal solution (in offline learning) for many problems (like PMC, OIM etc.) is NP-hard. On the other hand, Greedy oracle is a popular choice in various optimisation methods (including submodular maximisation).  \nHence, the idea to attack the CMAB setup with TS using a Greedy oracle is very natural. ", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "The paper is very well-written. The assumptions, problem statement, related work, and contributions are presented with great clarity. The upper and the lower bound (on the cumulative regret) presented in the paper are useful, and the authors have put a fair amount of discussion on the intuitions behind their approach. \n\nThe authors are being strongly recommended for presenting experimental results to compare with the existing approaches and validate the efficiency of their algorithm. \n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes, the authors have discussed the limitation with clarity.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "10"}, "extra_text": {}}, {"review_id": "8LAuhB8kUdQ", "reviewer": "Reviewer_1vtP", "summary": "This paper studies TS for a certain set of Combinatorial semi-bandit problems with a greedy approximation algorithm.\nIt derives a logarithmic upper bound for this algorithm and also provides a single problem instance with $1/\\Delta^2$ regret, where the upper bound is provably tight.", "questions": "", "limitations": "", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "The problem setting seems relevant, though the authors do not do a very good job in describing the actual motivating problems. It would be good to formally define in a concise manner the OIM, PMC and MP-MAB problems at the beginning of the setting section.\nIt seems reasonable to define the regret against a baseline obtained by the offline oracle when finding the optimal solution is NP-hard.\nHowever I see issues with the regret definition. To cite the authors: \"The objective of the learning agent is to maximize the cumulative expected reward over $T$ rounds\", which is not what the regret is actually capturing. \nBy defining the clipped per-step regret, we do not capture the cumulative expected reward over $T$ rounds anymore.\n\nI did not check the details of the upper bound proof in the appendix, but the result sounds reasonable. It is at first surprising that the regret scales with $1/\\Delta^2$ instead of the typical $1/\\Delta$. The authors show in the lower bound that this squared dependency is unavoidable for this algorithm and is due to the fine workings of the greedy oracle. The regret definition with the clipped per-step regret serves as a short-cut to the lower bound proof. The proof should also go through with an unclipped regret but requires more technical work.\n\nOverall I am not convinced how meaningful regret bounds in this setting are. The actual performance is dominated by the effect of the greedy oracle. Swapping the means of $u_1$ and $u_4$ in the example changes the regret of the algorithm from $1/\\Delta^2$ to a finite value, even though the actual performance compared to the optimal action is almost identical.\nThe presented bounds are apparently worst-case bounds and the gap definitions do not capture the inherent hardness of the problem very well. \n\nMinor: Removing the redundant use of the word \"could\" would improve the reading flow.\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}, {"review_id": "1WpsWDOyfTn", "reviewer": "Reviewer_Lbtx", "summary": "The paper studies Thompson Sampling for combinatorial multi-armed bandit problems for based on a greedy oracle. An upper and lower bound on regret is provided. \n\n", "questions": "", "limitations": "", "rating": 4, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "Critique of the setting:\n\nThe paper only considers problems where the natural greedy algorithm (based on r(S,\\mu)) is a good optimization algorithm. For some problems like the MNL-bandit (assortment optimization under the MNL) choice model [Agrawal et al 2018], the optimization algorithm is quite simple but not the natural greedy. \n\nIt's a bit odd that we are able to observe X_t,i for every base arm i. For example, in the lower bound instance, it is natural to be able to observe which nodes get influenced, as a result of the action set S, but unnatural to be able to observe which edge they got influenced through. \n\nRegarding regret bound results:\n\nThe lower bound is only for the CTS algorithm and not for any bandit algorithm based on greedy algorithms. The intuition provided for the difficulty seems to hold for more general algorithm. Could the authors foresee a definition of more general algorithms that take incremental decisions like greedy and still face this lower bound?\n\nTheorem 1 needs to be stated in terms of the general problem - not in terms of the instance parameters. How does the \\Delta defined in this problem relate to Delta_min and Delta_max quantities? Is Delta = \\Omega(Delta_min)? Is there a family of instances that can be defined to show that the regret lower bound changes with Delta and T in this way?\n\nThe lower bound vs upper bound comparison is quite unsatisfactory - it is a very specific case in which the two bounds are matching - it says nothing about the the dependence on K, unit sizes, B etc.  I think the authors should present the Theorem 1 instance as an example, rather than a lower bound. In any case I would suggest removing the claim of “almost matching upper and lower bound”.\n\nHow does the upper bound result translate to specific CMAB problems, and how does it compare to existing regret bounds for the problems studied previously in the literature? \n\nRegarding proof techniques:\n\nThe proof is based on repeatedly applying the bound on number of exploration steps needed to select the right action at every step of the greedy algorithm. Since the upper bound the authors are aiming to prove is crudely log T/Delta^2 - with max over k,s a high probability bound on exploration steps suffices and detailed understanding of how much regret is lost is not required.\n\nFurther comments:\n\nIn the discussion below assumption 2, it will be useful to discuss what the value of B is for the different combinatorial bandit problems mentioned there.\n\nLine 256: not sure what this means: “exploration on the denominator of..”. do you mean “on the order of”?\n\nSummary:\n\nOverall, the paper studies an interesting problem, but the upper bound seems to stop short of providing an interesting insight in the problem - both in terms of the actual form of the bound and proof techniques. The lower bound is not very detailed. It only shows a weak dependence on problem parameters for that specific instance.\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Theoretical paper. No direct societal impacts.", "review_text": "", "extra_scores": {"ethical_concerns": "No direct ethical concerns.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}]

Author rebuttal:

Meta-review: While the review team recognizes the importance of the problem and like the direction that the paper took, they also felt that the paper is not yet ready for publication. The main concerns are:

* model is not well motivated. In some problems (like OIM) the feedback assumed here is inconsistent with what is observed in practice (nodes vs edges).
* the regret bounds don't directly reflect the performance of the algorithm
* lower bound is too stylized and may not say much about the actual hardness of the problem

While the reviewers appreciate the author responses on those issues, they were not sufficient to significantly change the sentiment.
Decision: Accept (Poster)