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,,>D [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 (s)
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(5 ((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,,,))(,,,e)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.,,'.. 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, 2..2..... Or.m) (Line 5). Based on the observation feedback, 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 = -
as the reward difference between Sg.k and 1 U According to the Greedy algorithm, 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
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 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 r(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
kis@ 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(5 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 x.-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,...,, =((......K111
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-233)) 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": "yqvQ-mBvmf-", "reviewer": "Reviewer_RTgq", "summary": "The paper studies the combinatorial multi-armed bandit (CMAB) problem in a setting where exactly solving the corresponding offline optimization problem is not feasible (due to its computational hardness) and the learning agent only has access to a greedy oracle which approximately solves the offline optimization problem. In this framework, the paper analyzes the behavior of a natural variant of the Thompson sampling algorithm called Combinatorial Thompson sampling (CTS). The paper first gives an algorithm-dependent and problem-dependent lower bound showing that CTS faces a fundamental limit, then provides an almost matching upper bound.", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "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 well-written. The research question is well-motivated and practically relevant (as greedy algorithms are common choices for approximately solving hard combinatorial optimization problems). While a similar research question has already been studied in Lin et al. [22], the framework considered in that paper is different from the framework studied in this paper , and the two papers focus on different types of algorithms (UCB vs. Thompson sampling). The results of this paper seem to be technically correct.\n\nI have the following questions/concerns:\n1. The lower bound is algorithm-dependent, which means that it only holds for the CTS algorithm. While this result does provide interesting insights on the behavior of CTS, a natural question is whether such a fundamental limit also exists for other algorithms. In other words, I feel that an information-theoretic lower bound could greatly improve the quality of the paper and provide more insights on the proposed framework.\n2. Currently, the algorithm uses a Beta prior (to obtain the upper bound), but the lower bound is shown for the Gaussian prior. This seems like a limitation. Can the authors provide matching upper and lower bounds for the same prior, or provide some explanations on deriving upper and lower bounds using different priors is not an issue?\n2. A main insight of this paper is that using TS-type algorithms to solve CMAB with a greedy oracle may necessarily lead to a larger regret bound (with worse dependence on the reward gap) compared with the regret bounds obtained by using exact oracles. I note that the paper considers the worst-case regret. Can the authors provide some insights on whether such phenomena still exist when the Bayesian regret is considered? I note that the current lower bound does not directly imply a Bayesian regret lower bound (as the constructed instance is not \"Gaussian\").", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "I discussed some questions/concerns in my review.", "review_text": "", "extra_scores": {"ethical_concerns": "I do not see any ethical concern.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "hE5Q4gVx_kJ", "reviewer": "Reviewer_wYkT", "summary": "This paper studies a setting where Thompson Sampling with greedy approximation oracles is applied to combinatorial semi-bandit. The main contribution is to theoretically reveal how the suboptimality of greedy oracles can affect Thompson sampling in the worst case. Specifically, the greedy regret is shown to be lower bounded by $\\Omega(\\log T / \\Delta^2)$. The authors also prove an almost matching upper bound. \n\n--- After rebuttal ---\n\nI appreciate the authors' kind response. Having read all the responses and review comments, I've found that the result is more significant than I thought. Therefore, I increased my score to 6.  ", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "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": "This paper addresses an interesting theoretical question and presents nice results: a regret lower bound together with an almost matching upper bound. The results are interesting, and the paper is well written. However, I have two concerns, as detailed below. \n\n1. I'm not fully convinced that it is de facto standard to use greedy approximation oracles in each round of combinatorial semi-bandit. For example, most online submodular maximization algorithms do not simply use offline greedy oracles; they are tailored to the online setting. Therefore, I cannot see how significant the hardness result is, which focuses only on the case with greedy oracles (In my opinion, the hardness result would be stronger if lower bounds are obtained for general cases where offline oracles with certain approximation guarantees are available). \n\n2. The original definition of the greedy regret in [22] does not have $\\max(\\ast, 0)$. It seems that making the instantaneous regret in each $t$-th round non-negative makes it easier to prove the hardness result. Is it possible to obtain the lower bound for the original greedy regret without $\\max(\\ast, 0)$?", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The limitations are described. The paper seems to have no negative societal impacts. ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "TgIKjd6Ncv2", "reviewer": "Reviewer_ah1S", "summary": "The paper studies the performance of Thompson-Sampling (TS) when applied to combinatorial multi-armed bandit (CMAB) problems with semi-bandit feedback. It is well known that the combinatorial TS (CTS) algorithm might suffer from linear regret when the combinatorial maximization is solved using an approximation oracle [30]. In this work, the authors apply CTS with a specific family of combinatorial maximization oracles – greedy oracles. They analyze the greedy regret of CTS (which compares the played actions to the greedy solution of the combinatorial problem) and derive regret upper bounds of $O(\\log T/\\Delta^2)$, where $\\Delta$ is a suboptimality gap. They also provide a matching lower bound for CTS on a specific small-scale problem.", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "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": "In my opinion, the paper has two notable contributions: first, CMAB papers usually analyze the approximation regret, which compares the played actions to $(1-1/e)OPT$ (in the case of greedy oracles). In contrast, the derived bounds compare the played action to the best greedy action, which is always better than $(1-1/e)OPT$. Therefore, the provided guarantees are stronger than the standard CMAB guarantees. To the best of my knowledge, the only paper that derives such guarantees is [22], where the algorithm is intractable. Therefore, a notable contribution of this paper is in analyzing a tractable algorithm (CTS) for this performance criterion. This kind of guarantee adds an ‘oracle-problem dependent’ flavor, i.e., compares to the performance of the oracle on the specific problem and not its worst-case guarantees.\n\nThe second contribution of this work is that the authors prove these guarantees to CTS. In particular, it shows that the linear regret lower bounds of [30] do not hold for any approximation oracle and breaks the misconception that CTS cannot be used with approximation oracles.\n\nOn the other hand, there are a few issues with this work. First, I believe that the lower bound doesn’t hold specifically to TS and that similar arguments should allow deriving lower bound to any (reasonable) algorithm (and I would love to read some discussion about the implications of the lower bound in [22] – if it holds in your setting, what is the contribution in Theorem 1?). In particular, I think that the lower bound stems from the comparison to the best greedy solution (and the fact that its value is nonsmooth - arbitrarily small changes might lead to constant difference), and not to the approximate-optimal value $(1-1/e)OPT$. Notably, the ‘problematic’ action $(u_3,u_4)$ is better than the $(1-1/e)OPT)$ (and is actually even better than the approximation ratio of $0.75\\cdot OPT$ for $K=2$). Thus, the inverse-dependence in the squared gaps might be the result of the criterion, rather than the algorithm. This is not discussed in the paper and creates the (possibly wrong) impression that TS-based algorithms are inherently worse than UCB-based algorithms for CMABs. In some sense, I am not convinced that the ‘story’ of the paper is the hardness of TS in the standard CMAB setting (with approximation regret), but rather a positive result on the greedy regret. I think this might be an interesting alternative story, but it requires drastic changes in the paper.\n\nAs a side effect, I think that the lower bound is weaker than it should be (namely, hold for any consistent algorithm). In addition, the lower bound is proven on a small-scale problem. Therefore, it does not allow understanding the right dependence in problem-constants. \n\nAnother issue is the specific combination of TS with a greedy oracle. As I see it, the main advantage of TS in CMAB problems is that it allows working with non monotone reward functions. As far as I know, greedy oracles have provable guarantees mainly (only?) for monotone (and submodular) combinatorial functions. Therefore, even though this is probably the most common family of oracles, the results do not allow using one of the greatest advantages of TS in this setting.\n\nFinally, the requirement that $\\epsilon\\lesssim \\Delta$, combined with a term of $\\epsilon^{-6}$ (or even a higher power) might lead to a terrible problem-independent bound – can you comment on that?\n\nClarity/writing: in general, the paper is well written and I didn’t see any critical issues.\n\nComparison to previous works: I find it hard to compare the resulting bounds to previous works, as the gaps are differently defined. One interesting thing that got my attention is that the bound does not directly depend on K, in contrast to the ‘classical’ bounds of [7]. Such a dependence is unavoidable in the approximation regret for linear reward functions [Kveton et. Al, 2015], but in general, varies between reward functions and does not exist in the PMC problem [Merlis and Mannor, 2019]. Do you think that it stems from the different regret definition, gap definition, the maximization over $k$, or maybe from the dominating effect of $1/\\Delta^2$ (instead of $1/\\Delta$)? \nIn general, I would love to see a more thorough comparison of the bounds to previous work (including the lower bounds of [22] that I already mentioned and their upper bounds).\n\nOther comments:\n- The set of all possible actions seems a bit nonstandard – can you say something about its relation to standard sets (e.g., it contains the uniform matroid, but what about other matroids/standard sets?)\n- In multiple places, there are references to the OIM and PMC problems. First, I think that many readers would require some additional explanation on the problems (and maybe writing explicit reward functions). Moreover, even though OIM is mentioned numerous times, the authors only actually work with the PMC problem. Also, to the best of my knowledge, OIM usually requires probabilistically triggered arms. Thus, for clarity’s sake, I think it would be beneficial to either only write on PMC problems or give a more concrete example of a different instance of OIM.\n\nMinor comments:\n- Line 26: either ‘which is equivalent to’ or ‘or equivalently,’.\n- Line 194: maximize -> minimize.\n- Line 198-199 consider rephrasing – maybe ‘When greedy...’ -> ‘We say that greedy...’?\n- Line 267: ‘we hope to use its...’ -> ‘use their....’\n\nReferences:\n- Kveton, Branislav, et al. \"Tight regret bounds for stochastic combinatorial semi-bandits.\" Artificial Intelligence and Statistics. PMLR, 2015.\n- Merlis, Nadav, and Shie Mannor. \"Batch-size independent regret bounds for the combinatorial multi-armed bandit problem.\" Conference on Learning Theory. PMLR, 2019.\n\n############\n\nI thank the authors for the response, clarifications and corrections. In light of the response, I am inclined towards accepting the paper.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Some limitations were described in the paper. However, I already mentioned a few possible missing ones - the fact that the results are limited to greedy oracles (and therefore, monotone reward functions) and the possible bad behavior of problem-independent bounds.", "review_text": "", "extra_scores": {"ethical_concerns": "None.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "10"}, "extra_text": {}}, {"review_id": "NrMTCEoDiXp", "reviewer": "Reviewer_nW4R", "summary": "This paper analyzes the performance of Thompson sampling for combinatorial multi-armed bandit problems where using an exact oracle is not feasible. While it is known that, in general, Thompson sampling cannot achieve sublinear regret with an arbitrary $\\alpha$-approximation oracle, the paper instead focuses on *greedy oracles* and shows that achieving $O(\\log T/\\Delta^2)$ is possible with a greedy oracle.", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "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": "Although most applications of CMAB require using greedy oracles, almost all analyses of TS under the CMAB setting consider exact oracles. This paper is first to show theoretically that TS is still a viable algorithm for such CMAB applications, which is a highly valuable contribution.\n\nIn Theorem 2, authors show an upper bound of $O(\\log T/\\Delta^2)$ for TS with a greedy oracle. While upper bounds of the form $O(\\log T/\\Delta)$ are more common in the bandit literature, Theorem 1 shows that this bound is actually tight with respect to $\\Delta$. However, Theorem 1 does not actually reveal anything regarding the hardness of optimizing greedy regret while the paper is phrased like it does. It is still not clear whether $O(\\log T/\\Delta^2)$ is the best possible greedy regret achievable by *any* algorithm, or a UCB-based algorithm can still achieve $O(\\log T/\\Delta)$ greedy regret. As authors have already pointed out in their paper, when a greedy oracle also happens to be an $\\alpha$-approximation oracle, the greedy regret would be larger than the $\\alpha$-approximation regret, meaning existing upper bounds on  the $\\alpha$-approximation regret of UCB-based algorithms do not answer this question. Conversely, knowing TS with a greedy oracle can achieve $O(\\log T/\\Delta^2)$ greedy regret does not imply it can also achieve $O(\\log T/\\Delta)$ $\\alpha$-approximation regret, when the greedy oracle also happens to be an $\\alpha$-approximation oracle.\n\nHaving said that, I still believe a tight upper bound on the greedy regret of TS for CMAB is still a significant enough contribution on its own. Until this paper, whether TS with a greedy oracle is even effective in solving CMAB problems was unknown theoretically. Now, the new question is whether TS with a greedy oracle is as effective as UCB-based algorithms, which is probably outside the scope of this paper.\n\nMy only concern is about Section 6.2, extending the analysis in Theorem 2 to the multiple-solution case. It is true that $S_g$ always being the solution with the minimum reward would be the worst case *if* we were to evaluate performance in terms of actual regret measured with respect to the actual optimal solution. When considering the greedy regret instead, if we assume $S_g$ is always the minimum reward solution, then we would also be measuring performance with respect to $\\arg\\min_{S\\in\\sigma_K} r(S,\\mu)$. This is not necessarily the case when the regret is the largest (for instance when $S_g$ is such that $S_g=\\arg\\max_{S\\in\\sigma_K} r(S,\\mu)$ and $S_g=\\arg\\min_{S\\in\\sigma_K} r(S,\\theta)$ for all $\\theta\\neq\\mu$, the greedy regret would be larger). However, I think the same analysis in Section 6.2 should also be possible for any deterministic function $f$ such that $S_g=f(\\sigma_K)$.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "One limitation that might be mentioned could be the fact that it is still an open question whether $O(\\log T/\\Delta^2)$ is the best greedy regret achievable by *any* algorithm (including UCB-based algorithms not just TS with a greedy oracle).", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The reviewers generally appreciate the upper bound results in this paper.  Although the lower bound appears to be a bit weak, it is nevertheless a useful complement to the upper bounds. 
Decision: Accept (Poster)